]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - lib/zstd/fse_decompress.c
2 * FSE : Finite State Entropy decoder
3 * Copyright (C) 2013-2015, Yann Collet.
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * This program is free software; you can redistribute it and/or modify it under
31 * the terms of the GNU General Public License version 2 as published by the
32 * Free Software Foundation. This program is dual-licensed; you may select
33 * either version 2 of the GNU General Public License ("GPL") or BSD license
36 * You can contact the author at :
37 * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
40 /* **************************************************************
42 ****************************************************************/
43 #define FORCE_INLINE static __always_inline
45 /* **************************************************************
47 ****************************************************************/
48 #include "bitstream.h"
50 #include <linux/compiler.h>
51 #include <linux/kernel.h>
52 #include <linux/string.h> /* memcpy, memset */
54 /* **************************************************************
56 ****************************************************************/
57 #define FSE_isError ERR_isError
58 #define FSE_STATIC_ASSERT(c) \
60 enum { FSE_static_assert = 1 / (int)(!!(c)) }; \
61 } /* use only *after* variable declarations */
63 /* check and forward error code */
71 /* **************************************************************
73 ****************************************************************/
75 designed to be included
76 for type-specific functions (template emulation in C)
77 Objective is to write these functions only once, for improved maintenance
81 #ifndef FSE_FUNCTION_EXTENSION
82 #error "FSE_FUNCTION_EXTENSION must be defined"
84 #ifndef FSE_FUNCTION_TYPE
85 #error "FSE_FUNCTION_TYPE must be defined"
89 #define FSE_CAT(X, Y) X##Y
90 #define FSE_FUNCTION_NAME(X, Y) FSE_CAT(X, Y)
91 #define FSE_TYPE_NAME(X, Y) FSE_CAT(X, Y)
93 /* Function templates */
95 size_t FSE_buildDTable_wksp ( FSE_DTable
* dt
, const short * normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
, void * workspace
, size_t workspaceSize
)
97 void * const tdPtr
= dt
+ 1 ; /* because *dt is unsigned, 32-bits aligned on 32-bits */
98 FSE_DECODE_TYPE
* const tableDecode
= ( FSE_DECODE_TYPE
*)( tdPtr
);
99 U16
* symbolNext
= ( U16
*) workspace
;
101 U32
const maxSV1
= maxSymbolValue
+ 1 ;
102 U32
const tableSize
= 1 << tableLog
;
103 U32 highThreshold
= tableSize
- 1 ;
106 if ( workspaceSize
< sizeof ( U16
) * ( FSE_MAX_SYMBOL_VALUE
+ 1 ))
107 return ERROR ( tableLog_tooLarge
);
108 if ( maxSymbolValue
> FSE_MAX_SYMBOL_VALUE
)
109 return ERROR ( maxSymbolValue_tooLarge
);
110 if ( tableLog
> FSE_MAX_TABLELOG
)
111 return ERROR ( tableLog_tooLarge
);
113 /* Init, lay down lowprob symbols */
115 FSE_DTableHeader DTableH
;
116 DTableH
. tableLog
= ( U16
) tableLog
;
117 DTableH
. fastMode
= 1 ;
119 S16
const largeLimit
= ( S16
)( 1 << ( tableLog
- 1 ));
121 for ( s
= 0 ; s
< maxSV1
; s
++) {
122 if ( normalizedCounter
[ s
] == - 1 ) {
123 tableDecode
[ highThreshold
--]. symbol
= ( FSE_FUNCTION_TYPE
) s
;
126 if ( normalizedCounter
[ s
] >= largeLimit
)
127 DTableH
. fastMode
= 0 ;
128 symbolNext
[ s
] = normalizedCounter
[ s
];
132 memcpy ( dt
, & DTableH
, sizeof ( DTableH
));
137 U32
const tableMask
= tableSize
- 1 ;
138 U32
const step
= FSE_TABLESTEP ( tableSize
);
140 for ( s
= 0 ; s
< maxSV1
; s
++) {
142 for ( i
= 0 ; i
< normalizedCounter
[ s
]; i
++) {
143 tableDecode
[ position
]. symbol
= ( FSE_FUNCTION_TYPE
) s
;
144 position
= ( position
+ step
) & tableMask
;
145 while ( position
> highThreshold
)
146 position
= ( position
+ step
) & tableMask
; /* lowprob area */
150 return ERROR ( GENERIC
); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
153 /* Build Decoding table */
156 for ( u
= 0 ; u
< tableSize
; u
++) {
157 FSE_FUNCTION_TYPE
const symbol
= ( FSE_FUNCTION_TYPE
)( tableDecode
[ u
]. symbol
);
158 U16 nextState
= symbolNext
[ symbol
]++;
159 tableDecode
[ u
]. nbBits
= ( BYTE
)( tableLog
- BIT_highbit32 (( U32
) nextState
));
160 tableDecode
[ u
]. newState
= ( U16
)(( nextState
<< tableDecode
[ u
]. nbBits
) - tableSize
);
167 /*-*******************************************************
168 * Decompression (Byte symbols)
169 *********************************************************/
170 size_t FSE_buildDTable_rle ( FSE_DTable
* dt
, BYTE symbolValue
)
173 FSE_DTableHeader
* const DTableH
= ( FSE_DTableHeader
*) ptr
;
175 FSE_decode_t
* const cell
= ( FSE_decode_t
*) dPtr
;
177 DTableH
-> tableLog
= 0 ;
178 DTableH
-> fastMode
= 0 ;
181 cell
-> symbol
= symbolValue
;
187 size_t FSE_buildDTable_raw ( FSE_DTable
* dt
, unsigned nbBits
)
190 FSE_DTableHeader
* const DTableH
= ( FSE_DTableHeader
*) ptr
;
192 FSE_decode_t
* const dinfo
= ( FSE_decode_t
*) dPtr
;
193 const unsigned tableSize
= 1 << nbBits
;
194 const unsigned tableMask
= tableSize
- 1 ;
195 const unsigned maxSV1
= tableMask
+ 1 ;
200 return ERROR ( GENERIC
); /* min size */
202 /* Build Decoding Table */
203 DTableH
-> tableLog
= ( U16
) nbBits
;
204 DTableH
-> fastMode
= 1 ;
205 for ( s
= 0 ; s
< maxSV1
; s
++) {
206 dinfo
[ s
]. newState
= 0 ;
207 dinfo
[ s
]. symbol
= ( BYTE
) s
;
208 dinfo
[ s
]. nbBits
= ( BYTE
) nbBits
;
214 FORCE_INLINE
size_t FSE_decompress_usingDTable_generic ( void * dst
, size_t maxDstSize
, const void * cSrc
, size_t cSrcSize
, const FSE_DTable
* dt
,
217 BYTE
* const ostart
= ( BYTE
*) dst
;
219 BYTE
* const omax
= op
+ maxDstSize
;
220 BYTE
* const olimit
= omax
- 3 ;
227 CHECK_F ( BIT_initDStream (& bitD
, cSrc
, cSrcSize
));
229 FSE_initDState (& state1
, & bitD
, dt
);
230 FSE_initDState (& state2
, & bitD
, dt
);
232 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
234 /* 4 symbols per loop */
235 for (; ( BIT_reloadDStream (& bitD
) == BIT_DStream_unfinished
) & ( op
< olimit
); op
+= 4 ) {
236 op
[ 0 ] = FSE_GETSYMBOL (& state1
);
238 if ( FSE_MAX_TABLELOG
* 2 + 7 > sizeof ( bitD
. bitContainer
) * 8 ) /* This test must be static */
239 BIT_reloadDStream (& bitD
);
241 op
[ 1 ] = FSE_GETSYMBOL (& state2
);
243 if ( FSE_MAX_TABLELOG
* 4 + 7 > sizeof ( bitD
. bitContainer
) * 8 ) /* This test must be static */
245 if ( BIT_reloadDStream (& bitD
) > BIT_DStream_unfinished
) {
251 op
[ 2 ] = FSE_GETSYMBOL (& state1
);
253 if ( FSE_MAX_TABLELOG
* 2 + 7 > sizeof ( bitD
. bitContainer
) * 8 ) /* This test must be static */
254 BIT_reloadDStream (& bitD
);
256 op
[ 3 ] = FSE_GETSYMBOL (& state2
);
260 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
263 return ERROR ( dstSize_tooSmall
);
264 * op
++ = FSE_GETSYMBOL (& state1
);
265 if ( BIT_reloadDStream (& bitD
) == BIT_DStream_overflow
) {
266 * op
++ = FSE_GETSYMBOL (& state2
);
271 return ERROR ( dstSize_tooSmall
);
272 * op
++ = FSE_GETSYMBOL (& state2
);
273 if ( BIT_reloadDStream (& bitD
) == BIT_DStream_overflow
) {
274 * op
++ = FSE_GETSYMBOL (& state1
);
282 size_t FSE_decompress_usingDTable ( void * dst
, size_t originalSize
, const void * cSrc
, size_t cSrcSize
, const FSE_DTable
* dt
)
284 const void * ptr
= dt
;
285 const FSE_DTableHeader
* DTableH
= ( const FSE_DTableHeader
*) ptr
;
286 const U32 fastMode
= DTableH
-> fastMode
;
288 /* select fast mode (static) */
290 return FSE_decompress_usingDTable_generic ( dst
, originalSize
, cSrc
, cSrcSize
, dt
, 1 );
291 return FSE_decompress_usingDTable_generic ( dst
, originalSize
, cSrc
, cSrcSize
, dt
, 0 );
294 size_t FSE_decompress_wksp ( void * dst
, size_t dstCapacity
, const void * cSrc
, size_t cSrcSize
, unsigned maxLog
, void * workspace
, size_t workspaceSize
)
296 const BYTE
* const istart
= ( const BYTE
*) cSrc
;
297 const BYTE
* ip
= istart
;
299 unsigned maxSymbolValue
= FSE_MAX_SYMBOL_VALUE
;
304 size_t spaceUsed32
= 0 ;
306 FSE_STATIC_ASSERT ( sizeof ( FSE_DTable
) == sizeof ( U32
));
308 dt
= ( FSE_DTable
*)(( U32
*) workspace
+ spaceUsed32
);
309 spaceUsed32
+= FSE_DTABLE_SIZE_U32 ( maxLog
);
310 counting
= ( short *)(( U32
*) workspace
+ spaceUsed32
);
311 spaceUsed32
+= ALIGN ( sizeof ( short ) * ( FSE_MAX_SYMBOL_VALUE
+ 1 ), sizeof ( U32
)) >> 2 ;
313 if (( spaceUsed32
<< 2 ) > workspaceSize
)
314 return ERROR ( tableLog_tooLarge
);
315 workspace
= ( U32
*) workspace
+ spaceUsed32
;
316 workspaceSize
-= ( spaceUsed32
<< 2 );
318 /* normal FSE decoding mode */
319 NCountLength
= FSE_readNCount ( counting
, & maxSymbolValue
, & tableLog
, istart
, cSrcSize
);
320 if ( FSE_isError ( NCountLength
))
322 // if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size; supposed to be already checked in NCountLength, only remaining
323 // case : NCountLength==cSrcSize */
324 if ( tableLog
> maxLog
)
325 return ERROR ( tableLog_tooLarge
);
327 cSrcSize
-= NCountLength
;
329 CHECK_F ( FSE_buildDTable_wksp ( dt
, counting
, maxSymbolValue
, tableLog
, workspace
, workspaceSize
));
331 return FSE_decompress_usingDTable ( dst
, dstCapacity
, ip
, cSrcSize
, dt
); /* always return, even if it is an error code */