1*01826a49SYabin Cui /*
2*01826a49SYabin Cui * Copyright (c) Yann Collet, Meta Platforms, Inc. and affiliates.
3*01826a49SYabin Cui * All rights reserved.
4*01826a49SYabin Cui *
5*01826a49SYabin Cui * This source code is licensed under both the BSD-style license (found in the
6*01826a49SYabin Cui * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7*01826a49SYabin Cui * in the COPYING file in the root directory of this source tree).
8*01826a49SYabin Cui * You may select, at your option, one of the above-listed licenses.
9*01826a49SYabin Cui */
10*01826a49SYabin Cui
11*01826a49SYabin Cui
12*01826a49SYabin Cui #include <stddef.h> /* size_t, ptrdiff_t */
13*01826a49SYabin Cui #include "zstd_v03.h"
14*01826a49SYabin Cui #include "../common/compiler.h"
15*01826a49SYabin Cui #include "../common/error_private.h"
16*01826a49SYabin Cui
17*01826a49SYabin Cui
18*01826a49SYabin Cui /******************************************
19*01826a49SYabin Cui * Compiler-specific
20*01826a49SYabin Cui ******************************************/
21*01826a49SYabin Cui #if defined(_MSC_VER) /* Visual Studio */
22*01826a49SYabin Cui # include <stdlib.h> /* _byteswap_ulong */
23*01826a49SYabin Cui # include <intrin.h> /* _byteswap_* */
24*01826a49SYabin Cui #endif
25*01826a49SYabin Cui
26*01826a49SYabin Cui
27*01826a49SYabin Cui
28*01826a49SYabin Cui /* ******************************************************************
29*01826a49SYabin Cui mem.h
30*01826a49SYabin Cui low-level memory access routines
31*01826a49SYabin Cui Copyright (C) 2013-2015, Yann Collet.
32*01826a49SYabin Cui
33*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
34*01826a49SYabin Cui
35*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
36*01826a49SYabin Cui modification, are permitted provided that the following conditions are
37*01826a49SYabin Cui met:
38*01826a49SYabin Cui
39*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
40*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
41*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
42*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
43*01826a49SYabin Cui in the documentation and/or other materials provided with the
44*01826a49SYabin Cui distribution.
45*01826a49SYabin Cui
46*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
47*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
48*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
49*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
50*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
51*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
52*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
53*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
54*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
55*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
56*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
57*01826a49SYabin Cui
58*01826a49SYabin Cui You can contact the author at :
59*01826a49SYabin Cui - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
60*01826a49SYabin Cui - Public forum : https://groups.google.com/forum/#!forum/lz4c
61*01826a49SYabin Cui ****************************************************************** */
62*01826a49SYabin Cui #ifndef MEM_H_MODULE
63*01826a49SYabin Cui #define MEM_H_MODULE
64*01826a49SYabin Cui
65*01826a49SYabin Cui #if defined (__cplusplus)
66*01826a49SYabin Cui extern "C" {
67*01826a49SYabin Cui #endif
68*01826a49SYabin Cui
69*01826a49SYabin Cui /******************************************
70*01826a49SYabin Cui * Includes
71*01826a49SYabin Cui ******************************************/
72*01826a49SYabin Cui #include <stddef.h> /* size_t, ptrdiff_t */
73*01826a49SYabin Cui #include <string.h> /* memcpy */
74*01826a49SYabin Cui
75*01826a49SYabin Cui
76*01826a49SYabin Cui /****************************************************************
77*01826a49SYabin Cui * Basic Types
78*01826a49SYabin Cui *****************************************************************/
79*01826a49SYabin Cui #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
80*01826a49SYabin Cui # if defined(_AIX)
81*01826a49SYabin Cui # include <inttypes.h>
82*01826a49SYabin Cui # else
83*01826a49SYabin Cui # include <stdint.h> /* intptr_t */
84*01826a49SYabin Cui # endif
85*01826a49SYabin Cui typedef uint8_t BYTE;
86*01826a49SYabin Cui typedef uint16_t U16;
87*01826a49SYabin Cui typedef int16_t S16;
88*01826a49SYabin Cui typedef uint32_t U32;
89*01826a49SYabin Cui typedef int32_t S32;
90*01826a49SYabin Cui typedef uint64_t U64;
91*01826a49SYabin Cui typedef int64_t S64;
92*01826a49SYabin Cui #else
93*01826a49SYabin Cui typedef unsigned char BYTE;
94*01826a49SYabin Cui typedef unsigned short U16;
95*01826a49SYabin Cui typedef signed short S16;
96*01826a49SYabin Cui typedef unsigned int U32;
97*01826a49SYabin Cui typedef signed int S32;
98*01826a49SYabin Cui typedef unsigned long long U64;
99*01826a49SYabin Cui typedef signed long long S64;
100*01826a49SYabin Cui #endif
101*01826a49SYabin Cui
102*01826a49SYabin Cui
103*01826a49SYabin Cui /****************************************************************
104*01826a49SYabin Cui * Memory I/O
105*01826a49SYabin Cui *****************************************************************/
106*01826a49SYabin Cui
MEM_32bits(void)107*01826a49SYabin Cui MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
MEM_64bits(void)108*01826a49SYabin Cui MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
109*01826a49SYabin Cui
MEM_isLittleEndian(void)110*01826a49SYabin Cui MEM_STATIC unsigned MEM_isLittleEndian(void)
111*01826a49SYabin Cui {
112*01826a49SYabin Cui const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
113*01826a49SYabin Cui return one.c[0];
114*01826a49SYabin Cui }
115*01826a49SYabin Cui
MEM_read16(const void * memPtr)116*01826a49SYabin Cui MEM_STATIC U16 MEM_read16(const void* memPtr)
117*01826a49SYabin Cui {
118*01826a49SYabin Cui U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
119*01826a49SYabin Cui }
120*01826a49SYabin Cui
MEM_read32(const void * memPtr)121*01826a49SYabin Cui MEM_STATIC U32 MEM_read32(const void* memPtr)
122*01826a49SYabin Cui {
123*01826a49SYabin Cui U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
124*01826a49SYabin Cui }
125*01826a49SYabin Cui
MEM_read64(const void * memPtr)126*01826a49SYabin Cui MEM_STATIC U64 MEM_read64(const void* memPtr)
127*01826a49SYabin Cui {
128*01826a49SYabin Cui U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
129*01826a49SYabin Cui }
130*01826a49SYabin Cui
MEM_write16(void * memPtr,U16 value)131*01826a49SYabin Cui MEM_STATIC void MEM_write16(void* memPtr, U16 value)
132*01826a49SYabin Cui {
133*01826a49SYabin Cui memcpy(memPtr, &value, sizeof(value));
134*01826a49SYabin Cui }
135*01826a49SYabin Cui
MEM_readLE16(const void * memPtr)136*01826a49SYabin Cui MEM_STATIC U16 MEM_readLE16(const void* memPtr)
137*01826a49SYabin Cui {
138*01826a49SYabin Cui if (MEM_isLittleEndian())
139*01826a49SYabin Cui return MEM_read16(memPtr);
140*01826a49SYabin Cui else
141*01826a49SYabin Cui {
142*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
143*01826a49SYabin Cui return (U16)(p[0] + (p[1]<<8));
144*01826a49SYabin Cui }
145*01826a49SYabin Cui }
146*01826a49SYabin Cui
MEM_writeLE16(void * memPtr,U16 val)147*01826a49SYabin Cui MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
148*01826a49SYabin Cui {
149*01826a49SYabin Cui if (MEM_isLittleEndian())
150*01826a49SYabin Cui {
151*01826a49SYabin Cui MEM_write16(memPtr, val);
152*01826a49SYabin Cui }
153*01826a49SYabin Cui else
154*01826a49SYabin Cui {
155*01826a49SYabin Cui BYTE* p = (BYTE*)memPtr;
156*01826a49SYabin Cui p[0] = (BYTE)val;
157*01826a49SYabin Cui p[1] = (BYTE)(val>>8);
158*01826a49SYabin Cui }
159*01826a49SYabin Cui }
160*01826a49SYabin Cui
MEM_readLE24(const void * memPtr)161*01826a49SYabin Cui MEM_STATIC U32 MEM_readLE24(const void* memPtr)
162*01826a49SYabin Cui {
163*01826a49SYabin Cui return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
164*01826a49SYabin Cui }
165*01826a49SYabin Cui
MEM_readLE32(const void * memPtr)166*01826a49SYabin Cui MEM_STATIC U32 MEM_readLE32(const void* memPtr)
167*01826a49SYabin Cui {
168*01826a49SYabin Cui if (MEM_isLittleEndian())
169*01826a49SYabin Cui return MEM_read32(memPtr);
170*01826a49SYabin Cui else
171*01826a49SYabin Cui {
172*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
173*01826a49SYabin Cui return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
174*01826a49SYabin Cui }
175*01826a49SYabin Cui }
176*01826a49SYabin Cui
MEM_readLE64(const void * memPtr)177*01826a49SYabin Cui MEM_STATIC U64 MEM_readLE64(const void* memPtr)
178*01826a49SYabin Cui {
179*01826a49SYabin Cui if (MEM_isLittleEndian())
180*01826a49SYabin Cui return MEM_read64(memPtr);
181*01826a49SYabin Cui else
182*01826a49SYabin Cui {
183*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
184*01826a49SYabin Cui return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
185*01826a49SYabin Cui + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
186*01826a49SYabin Cui }
187*01826a49SYabin Cui }
188*01826a49SYabin Cui
189*01826a49SYabin Cui
MEM_readLEST(const void * memPtr)190*01826a49SYabin Cui MEM_STATIC size_t MEM_readLEST(const void* memPtr)
191*01826a49SYabin Cui {
192*01826a49SYabin Cui if (MEM_32bits())
193*01826a49SYabin Cui return (size_t)MEM_readLE32(memPtr);
194*01826a49SYabin Cui else
195*01826a49SYabin Cui return (size_t)MEM_readLE64(memPtr);
196*01826a49SYabin Cui }
197*01826a49SYabin Cui
198*01826a49SYabin Cui
199*01826a49SYabin Cui #if defined (__cplusplus)
200*01826a49SYabin Cui }
201*01826a49SYabin Cui #endif
202*01826a49SYabin Cui
203*01826a49SYabin Cui #endif /* MEM_H_MODULE */
204*01826a49SYabin Cui
205*01826a49SYabin Cui
206*01826a49SYabin Cui /* ******************************************************************
207*01826a49SYabin Cui bitstream
208*01826a49SYabin Cui Part of NewGen Entropy library
209*01826a49SYabin Cui header file (to include)
210*01826a49SYabin Cui Copyright (C) 2013-2015, Yann Collet.
211*01826a49SYabin Cui
212*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
213*01826a49SYabin Cui
214*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
215*01826a49SYabin Cui modification, are permitted provided that the following conditions are
216*01826a49SYabin Cui met:
217*01826a49SYabin Cui
218*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
219*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
220*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
221*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
222*01826a49SYabin Cui in the documentation and/or other materials provided with the
223*01826a49SYabin Cui distribution.
224*01826a49SYabin Cui
225*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
226*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
227*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
228*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
229*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
230*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
231*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
232*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
233*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
234*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
235*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
236*01826a49SYabin Cui
237*01826a49SYabin Cui You can contact the author at :
238*01826a49SYabin Cui - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
239*01826a49SYabin Cui - Public forum : https://groups.google.com/forum/#!forum/lz4c
240*01826a49SYabin Cui ****************************************************************** */
241*01826a49SYabin Cui #ifndef BITSTREAM_H_MODULE
242*01826a49SYabin Cui #define BITSTREAM_H_MODULE
243*01826a49SYabin Cui
244*01826a49SYabin Cui #if defined (__cplusplus)
245*01826a49SYabin Cui extern "C" {
246*01826a49SYabin Cui #endif
247*01826a49SYabin Cui
248*01826a49SYabin Cui
249*01826a49SYabin Cui /*
250*01826a49SYabin Cui * This API consists of small unitary functions, which highly benefit from being inlined.
251*01826a49SYabin Cui * Since link-time-optimization is not available for all compilers,
252*01826a49SYabin Cui * these functions are defined into a .h to be included.
253*01826a49SYabin Cui */
254*01826a49SYabin Cui
255*01826a49SYabin Cui
256*01826a49SYabin Cui /**********************************************
257*01826a49SYabin Cui * bitStream decompression API (read backward)
258*01826a49SYabin Cui **********************************************/
259*01826a49SYabin Cui typedef struct
260*01826a49SYabin Cui {
261*01826a49SYabin Cui size_t bitContainer;
262*01826a49SYabin Cui unsigned bitsConsumed;
263*01826a49SYabin Cui const char* ptr;
264*01826a49SYabin Cui const char* start;
265*01826a49SYabin Cui } BIT_DStream_t;
266*01826a49SYabin Cui
267*01826a49SYabin Cui typedef enum { BIT_DStream_unfinished = 0,
268*01826a49SYabin Cui BIT_DStream_endOfBuffer = 1,
269*01826a49SYabin Cui BIT_DStream_completed = 2,
270*01826a49SYabin Cui BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
271*01826a49SYabin Cui /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
272*01826a49SYabin Cui
273*01826a49SYabin Cui MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
274*01826a49SYabin Cui MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
275*01826a49SYabin Cui MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
276*01826a49SYabin Cui MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
277*01826a49SYabin Cui
278*01826a49SYabin Cui
279*01826a49SYabin Cui
280*01826a49SYabin Cui /******************************************
281*01826a49SYabin Cui * unsafe API
282*01826a49SYabin Cui ******************************************/
283*01826a49SYabin Cui MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
284*01826a49SYabin Cui /* faster, but works only if nbBits >= 1 */
285*01826a49SYabin Cui
286*01826a49SYabin Cui
287*01826a49SYabin Cui
288*01826a49SYabin Cui /****************************************************************
289*01826a49SYabin Cui * Helper functions
290*01826a49SYabin Cui ****************************************************************/
BIT_highbit32(U32 val)291*01826a49SYabin Cui MEM_STATIC unsigned BIT_highbit32 (U32 val)
292*01826a49SYabin Cui {
293*01826a49SYabin Cui # if defined(_MSC_VER) /* Visual */
294*01826a49SYabin Cui unsigned long r;
295*01826a49SYabin Cui return _BitScanReverse(&r, val) ? (unsigned)r : 0;
296*01826a49SYabin Cui # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
297*01826a49SYabin Cui return __builtin_clz (val) ^ 31;
298*01826a49SYabin Cui # else /* Software version */
299*01826a49SYabin Cui static const unsigned DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
300*01826a49SYabin Cui U32 v = val;
301*01826a49SYabin Cui unsigned r;
302*01826a49SYabin Cui v |= v >> 1;
303*01826a49SYabin Cui v |= v >> 2;
304*01826a49SYabin Cui v |= v >> 4;
305*01826a49SYabin Cui v |= v >> 8;
306*01826a49SYabin Cui v |= v >> 16;
307*01826a49SYabin Cui r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
308*01826a49SYabin Cui return r;
309*01826a49SYabin Cui # endif
310*01826a49SYabin Cui }
311*01826a49SYabin Cui
312*01826a49SYabin Cui
313*01826a49SYabin Cui
314*01826a49SYabin Cui /**********************************************************
315*01826a49SYabin Cui * bitStream decoding
316*01826a49SYabin Cui **********************************************************/
317*01826a49SYabin Cui
318*01826a49SYabin Cui /*!BIT_initDStream
319*01826a49SYabin Cui * Initialize a BIT_DStream_t.
320*01826a49SYabin Cui * @bitD : a pointer to an already allocated BIT_DStream_t structure
321*01826a49SYabin Cui * @srcBuffer must point at the beginning of a bitStream
322*01826a49SYabin Cui * @srcSize must be the exact size of the bitStream
323*01826a49SYabin Cui * @result : size of stream (== srcSize) or an errorCode if a problem is detected
324*01826a49SYabin Cui */
BIT_initDStream(BIT_DStream_t * bitD,const void * srcBuffer,size_t srcSize)325*01826a49SYabin Cui MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
326*01826a49SYabin Cui {
327*01826a49SYabin Cui if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
328*01826a49SYabin Cui
329*01826a49SYabin Cui if (srcSize >= sizeof(size_t)) /* normal case */
330*01826a49SYabin Cui {
331*01826a49SYabin Cui U32 contain32;
332*01826a49SYabin Cui bitD->start = (const char*)srcBuffer;
333*01826a49SYabin Cui bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
334*01826a49SYabin Cui bitD->bitContainer = MEM_readLEST(bitD->ptr);
335*01826a49SYabin Cui contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
336*01826a49SYabin Cui if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
337*01826a49SYabin Cui bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
338*01826a49SYabin Cui }
339*01826a49SYabin Cui else
340*01826a49SYabin Cui {
341*01826a49SYabin Cui U32 contain32;
342*01826a49SYabin Cui bitD->start = (const char*)srcBuffer;
343*01826a49SYabin Cui bitD->ptr = bitD->start;
344*01826a49SYabin Cui bitD->bitContainer = *(const BYTE*)(bitD->start);
345*01826a49SYabin Cui switch(srcSize)
346*01826a49SYabin Cui {
347*01826a49SYabin Cui case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
348*01826a49SYabin Cui /* fallthrough */
349*01826a49SYabin Cui case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
350*01826a49SYabin Cui /* fallthrough */
351*01826a49SYabin Cui case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
352*01826a49SYabin Cui /* fallthrough */
353*01826a49SYabin Cui case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
354*01826a49SYabin Cui /* fallthrough */
355*01826a49SYabin Cui case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
356*01826a49SYabin Cui /* fallthrough */
357*01826a49SYabin Cui case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
358*01826a49SYabin Cui /* fallthrough */
359*01826a49SYabin Cui default:;
360*01826a49SYabin Cui }
361*01826a49SYabin Cui contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
362*01826a49SYabin Cui if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
363*01826a49SYabin Cui bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
364*01826a49SYabin Cui bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
365*01826a49SYabin Cui }
366*01826a49SYabin Cui
367*01826a49SYabin Cui return srcSize;
368*01826a49SYabin Cui }
BIT_lookBits(BIT_DStream_t * bitD,U32 nbBits)369*01826a49SYabin Cui MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
370*01826a49SYabin Cui {
371*01826a49SYabin Cui const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
372*01826a49SYabin Cui return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
373*01826a49SYabin Cui }
374*01826a49SYabin Cui
375*01826a49SYabin Cui /*! BIT_lookBitsFast :
376*01826a49SYabin Cui * unsafe version; only works if nbBits >= 1 */
BIT_lookBitsFast(BIT_DStream_t * bitD,U32 nbBits)377*01826a49SYabin Cui MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
378*01826a49SYabin Cui {
379*01826a49SYabin Cui const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
380*01826a49SYabin Cui return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
381*01826a49SYabin Cui }
382*01826a49SYabin Cui
BIT_skipBits(BIT_DStream_t * bitD,U32 nbBits)383*01826a49SYabin Cui MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
384*01826a49SYabin Cui {
385*01826a49SYabin Cui bitD->bitsConsumed += nbBits;
386*01826a49SYabin Cui }
387*01826a49SYabin Cui
BIT_readBits(BIT_DStream_t * bitD,U32 nbBits)388*01826a49SYabin Cui MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
389*01826a49SYabin Cui {
390*01826a49SYabin Cui size_t value = BIT_lookBits(bitD, nbBits);
391*01826a49SYabin Cui BIT_skipBits(bitD, nbBits);
392*01826a49SYabin Cui return value;
393*01826a49SYabin Cui }
394*01826a49SYabin Cui
395*01826a49SYabin Cui /*!BIT_readBitsFast :
396*01826a49SYabin Cui * unsafe version; only works if nbBits >= 1 */
BIT_readBitsFast(BIT_DStream_t * bitD,U32 nbBits)397*01826a49SYabin Cui MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
398*01826a49SYabin Cui {
399*01826a49SYabin Cui size_t value = BIT_lookBitsFast(bitD, nbBits);
400*01826a49SYabin Cui BIT_skipBits(bitD, nbBits);
401*01826a49SYabin Cui return value;
402*01826a49SYabin Cui }
403*01826a49SYabin Cui
BIT_reloadDStream(BIT_DStream_t * bitD)404*01826a49SYabin Cui MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
405*01826a49SYabin Cui {
406*01826a49SYabin Cui if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
407*01826a49SYabin Cui return BIT_DStream_overflow;
408*01826a49SYabin Cui
409*01826a49SYabin Cui if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
410*01826a49SYabin Cui {
411*01826a49SYabin Cui bitD->ptr -= bitD->bitsConsumed >> 3;
412*01826a49SYabin Cui bitD->bitsConsumed &= 7;
413*01826a49SYabin Cui bitD->bitContainer = MEM_readLEST(bitD->ptr);
414*01826a49SYabin Cui return BIT_DStream_unfinished;
415*01826a49SYabin Cui }
416*01826a49SYabin Cui if (bitD->ptr == bitD->start)
417*01826a49SYabin Cui {
418*01826a49SYabin Cui if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
419*01826a49SYabin Cui return BIT_DStream_completed;
420*01826a49SYabin Cui }
421*01826a49SYabin Cui {
422*01826a49SYabin Cui U32 nbBytes = bitD->bitsConsumed >> 3;
423*01826a49SYabin Cui BIT_DStream_status result = BIT_DStream_unfinished;
424*01826a49SYabin Cui if (bitD->ptr - nbBytes < bitD->start)
425*01826a49SYabin Cui {
426*01826a49SYabin Cui nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
427*01826a49SYabin Cui result = BIT_DStream_endOfBuffer;
428*01826a49SYabin Cui }
429*01826a49SYabin Cui bitD->ptr -= nbBytes;
430*01826a49SYabin Cui bitD->bitsConsumed -= nbBytes*8;
431*01826a49SYabin Cui bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
432*01826a49SYabin Cui return result;
433*01826a49SYabin Cui }
434*01826a49SYabin Cui }
435*01826a49SYabin Cui
436*01826a49SYabin Cui /*! BIT_endOfDStream
437*01826a49SYabin Cui * @return Tells if DStream has reached its exact end
438*01826a49SYabin Cui */
BIT_endOfDStream(const BIT_DStream_t * DStream)439*01826a49SYabin Cui MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
440*01826a49SYabin Cui {
441*01826a49SYabin Cui return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
442*01826a49SYabin Cui }
443*01826a49SYabin Cui
444*01826a49SYabin Cui #if defined (__cplusplus)
445*01826a49SYabin Cui }
446*01826a49SYabin Cui #endif
447*01826a49SYabin Cui
448*01826a49SYabin Cui #endif /* BITSTREAM_H_MODULE */
449*01826a49SYabin Cui /* ******************************************************************
450*01826a49SYabin Cui Error codes and messages
451*01826a49SYabin Cui Copyright (C) 2013-2015, Yann Collet
452*01826a49SYabin Cui
453*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
454*01826a49SYabin Cui
455*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
456*01826a49SYabin Cui modification, are permitted provided that the following conditions are
457*01826a49SYabin Cui met:
458*01826a49SYabin Cui
459*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
460*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
461*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
462*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
463*01826a49SYabin Cui in the documentation and/or other materials provided with the
464*01826a49SYabin Cui distribution.
465*01826a49SYabin Cui
466*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
467*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
468*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
469*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
470*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
471*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
472*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
473*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
474*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
475*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
476*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
477*01826a49SYabin Cui
478*01826a49SYabin Cui You can contact the author at :
479*01826a49SYabin Cui - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
480*01826a49SYabin Cui - Public forum : https://groups.google.com/forum/#!forum/lz4c
481*01826a49SYabin Cui ****************************************************************** */
482*01826a49SYabin Cui #ifndef ERROR_H_MODULE
483*01826a49SYabin Cui #define ERROR_H_MODULE
484*01826a49SYabin Cui
485*01826a49SYabin Cui #if defined (__cplusplus)
486*01826a49SYabin Cui extern "C" {
487*01826a49SYabin Cui #endif
488*01826a49SYabin Cui
489*01826a49SYabin Cui
490*01826a49SYabin Cui /******************************************
491*01826a49SYabin Cui * Compiler-specific
492*01826a49SYabin Cui ******************************************/
493*01826a49SYabin Cui #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
494*01826a49SYabin Cui # define ERR_STATIC static inline
495*01826a49SYabin Cui #elif defined(_MSC_VER)
496*01826a49SYabin Cui # define ERR_STATIC static __inline
497*01826a49SYabin Cui #elif defined(__GNUC__)
498*01826a49SYabin Cui # define ERR_STATIC static __attribute__((unused))
499*01826a49SYabin Cui #else
500*01826a49SYabin Cui # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
501*01826a49SYabin Cui #endif
502*01826a49SYabin Cui
503*01826a49SYabin Cui
504*01826a49SYabin Cui /******************************************
505*01826a49SYabin Cui * Error Management
506*01826a49SYabin Cui ******************************************/
507*01826a49SYabin Cui #define PREFIX(name) ZSTD_error_##name
508*01826a49SYabin Cui
509*01826a49SYabin Cui #define ERROR(name) (size_t)-PREFIX(name)
510*01826a49SYabin Cui
511*01826a49SYabin Cui #define ERROR_LIST(ITEM) \
512*01826a49SYabin Cui ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
513*01826a49SYabin Cui ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
514*01826a49SYabin Cui ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
515*01826a49SYabin Cui ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
516*01826a49SYabin Cui ITEM(PREFIX(maxCode))
517*01826a49SYabin Cui
518*01826a49SYabin Cui #define ERROR_GENERATE_ENUM(ENUM) ENUM,
519*01826a49SYabin Cui typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
520*01826a49SYabin Cui
521*01826a49SYabin Cui #define ERROR_CONVERTTOSTRING(STRING) #STRING,
522*01826a49SYabin Cui #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
523*01826a49SYabin Cui static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
524*01826a49SYabin Cui
ERR_isError(size_t code)525*01826a49SYabin Cui ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
526*01826a49SYabin Cui
ERR_getErrorName(size_t code)527*01826a49SYabin Cui ERR_STATIC const char* ERR_getErrorName(size_t code)
528*01826a49SYabin Cui {
529*01826a49SYabin Cui static const char* codeError = "Unspecified error code";
530*01826a49SYabin Cui if (ERR_isError(code)) return ERR_strings[-(int)(code)];
531*01826a49SYabin Cui return codeError;
532*01826a49SYabin Cui }
533*01826a49SYabin Cui
534*01826a49SYabin Cui
535*01826a49SYabin Cui #if defined (__cplusplus)
536*01826a49SYabin Cui }
537*01826a49SYabin Cui #endif
538*01826a49SYabin Cui
539*01826a49SYabin Cui #endif /* ERROR_H_MODULE */
540*01826a49SYabin Cui /*
541*01826a49SYabin Cui Constructor and Destructor of type FSE_CTable
542*01826a49SYabin Cui Note that its size depends on 'tableLog' and 'maxSymbolValue' */
543*01826a49SYabin Cui typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
544*01826a49SYabin Cui typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
545*01826a49SYabin Cui
546*01826a49SYabin Cui
547*01826a49SYabin Cui /* ******************************************************************
548*01826a49SYabin Cui FSE : Finite State Entropy coder
549*01826a49SYabin Cui header file for static linking (only)
550*01826a49SYabin Cui Copyright (C) 2013-2015, Yann Collet
551*01826a49SYabin Cui
552*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
553*01826a49SYabin Cui
554*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
555*01826a49SYabin Cui modification, are permitted provided that the following conditions are
556*01826a49SYabin Cui met:
557*01826a49SYabin Cui
558*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
559*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
560*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
561*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
562*01826a49SYabin Cui in the documentation and/or other materials provided with the
563*01826a49SYabin Cui distribution.
564*01826a49SYabin Cui
565*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
566*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
567*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
568*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
569*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
570*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
571*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
572*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
573*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
574*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
575*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
576*01826a49SYabin Cui
577*01826a49SYabin Cui You can contact the author at :
578*01826a49SYabin Cui - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
579*01826a49SYabin Cui - Public forum : https://groups.google.com/forum/#!forum/lz4c
580*01826a49SYabin Cui ****************************************************************** */
581*01826a49SYabin Cui #if defined (__cplusplus)
582*01826a49SYabin Cui extern "C" {
583*01826a49SYabin Cui #endif
584*01826a49SYabin Cui
585*01826a49SYabin Cui
586*01826a49SYabin Cui /******************************************
587*01826a49SYabin Cui * Static allocation
588*01826a49SYabin Cui ******************************************/
589*01826a49SYabin Cui /* FSE buffer bounds */
590*01826a49SYabin Cui #define FSE_NCOUNTBOUND 512
591*01826a49SYabin Cui #define FSE_BLOCKBOUND(size) (size + (size>>7))
592*01826a49SYabin Cui #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
593*01826a49SYabin Cui
594*01826a49SYabin Cui /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
595*01826a49SYabin Cui #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
596*01826a49SYabin Cui #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
597*01826a49SYabin Cui
598*01826a49SYabin Cui
599*01826a49SYabin Cui /******************************************
600*01826a49SYabin Cui * FSE advanced API
601*01826a49SYabin Cui ******************************************/
602*01826a49SYabin Cui static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
603*01826a49SYabin Cui /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
604*01826a49SYabin Cui
605*01826a49SYabin Cui static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
606*01826a49SYabin Cui /* build a fake FSE_DTable, designed to always generate the same symbolValue */
607*01826a49SYabin Cui
608*01826a49SYabin Cui
609*01826a49SYabin Cui /******************************************
610*01826a49SYabin Cui * FSE symbol decompression API
611*01826a49SYabin Cui ******************************************/
612*01826a49SYabin Cui typedef struct
613*01826a49SYabin Cui {
614*01826a49SYabin Cui size_t state;
615*01826a49SYabin Cui const void* table; /* precise table may vary, depending on U16 */
616*01826a49SYabin Cui } FSE_DState_t;
617*01826a49SYabin Cui
618*01826a49SYabin Cui
619*01826a49SYabin Cui static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
620*01826a49SYabin Cui
621*01826a49SYabin Cui static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
622*01826a49SYabin Cui
623*01826a49SYabin Cui static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
624*01826a49SYabin Cui
625*01826a49SYabin Cui
626*01826a49SYabin Cui /******************************************
627*01826a49SYabin Cui * FSE unsafe API
628*01826a49SYabin Cui ******************************************/
629*01826a49SYabin Cui static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
630*01826a49SYabin Cui /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
631*01826a49SYabin Cui
632*01826a49SYabin Cui
633*01826a49SYabin Cui /******************************************
634*01826a49SYabin Cui * Implementation of inline functions
635*01826a49SYabin Cui ******************************************/
636*01826a49SYabin Cui
637*01826a49SYabin Cui /* decompression */
638*01826a49SYabin Cui
639*01826a49SYabin Cui typedef struct {
640*01826a49SYabin Cui U16 tableLog;
641*01826a49SYabin Cui U16 fastMode;
642*01826a49SYabin Cui } FSE_DTableHeader; /* sizeof U32 */
643*01826a49SYabin Cui
644*01826a49SYabin Cui typedef struct
645*01826a49SYabin Cui {
646*01826a49SYabin Cui unsigned short newState;
647*01826a49SYabin Cui unsigned char symbol;
648*01826a49SYabin Cui unsigned char nbBits;
649*01826a49SYabin Cui } FSE_decode_t; /* size == U32 */
650*01826a49SYabin Cui
FSE_initDState(FSE_DState_t * DStatePtr,BIT_DStream_t * bitD,const FSE_DTable * dt)651*01826a49SYabin Cui MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
652*01826a49SYabin Cui {
653*01826a49SYabin Cui FSE_DTableHeader DTableH;
654*01826a49SYabin Cui memcpy(&DTableH, dt, sizeof(DTableH));
655*01826a49SYabin Cui DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
656*01826a49SYabin Cui BIT_reloadDStream(bitD);
657*01826a49SYabin Cui DStatePtr->table = dt + 1;
658*01826a49SYabin Cui }
659*01826a49SYabin Cui
FSE_decodeSymbol(FSE_DState_t * DStatePtr,BIT_DStream_t * bitD)660*01826a49SYabin Cui MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
661*01826a49SYabin Cui {
662*01826a49SYabin Cui const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
663*01826a49SYabin Cui const U32 nbBits = DInfo.nbBits;
664*01826a49SYabin Cui BYTE symbol = DInfo.symbol;
665*01826a49SYabin Cui size_t lowBits = BIT_readBits(bitD, nbBits);
666*01826a49SYabin Cui
667*01826a49SYabin Cui DStatePtr->state = DInfo.newState + lowBits;
668*01826a49SYabin Cui return symbol;
669*01826a49SYabin Cui }
670*01826a49SYabin Cui
FSE_decodeSymbolFast(FSE_DState_t * DStatePtr,BIT_DStream_t * bitD)671*01826a49SYabin Cui MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
672*01826a49SYabin Cui {
673*01826a49SYabin Cui const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
674*01826a49SYabin Cui const U32 nbBits = DInfo.nbBits;
675*01826a49SYabin Cui BYTE symbol = DInfo.symbol;
676*01826a49SYabin Cui size_t lowBits = BIT_readBitsFast(bitD, nbBits);
677*01826a49SYabin Cui
678*01826a49SYabin Cui DStatePtr->state = DInfo.newState + lowBits;
679*01826a49SYabin Cui return symbol;
680*01826a49SYabin Cui }
681*01826a49SYabin Cui
FSE_endOfDState(const FSE_DState_t * DStatePtr)682*01826a49SYabin Cui MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
683*01826a49SYabin Cui {
684*01826a49SYabin Cui return DStatePtr->state == 0;
685*01826a49SYabin Cui }
686*01826a49SYabin Cui
687*01826a49SYabin Cui
688*01826a49SYabin Cui #if defined (__cplusplus)
689*01826a49SYabin Cui }
690*01826a49SYabin Cui #endif
691*01826a49SYabin Cui /* ******************************************************************
692*01826a49SYabin Cui Huff0 : Huffman coder, part of New Generation Entropy library
693*01826a49SYabin Cui header file for static linking (only)
694*01826a49SYabin Cui Copyright (C) 2013-2015, Yann Collet
695*01826a49SYabin Cui
696*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
697*01826a49SYabin Cui
698*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
699*01826a49SYabin Cui modification, are permitted provided that the following conditions are
700*01826a49SYabin Cui met:
701*01826a49SYabin Cui
702*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
703*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
704*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
705*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
706*01826a49SYabin Cui in the documentation and/or other materials provided with the
707*01826a49SYabin Cui distribution.
708*01826a49SYabin Cui
709*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
710*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
711*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
712*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
713*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
714*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
715*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
716*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
717*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
718*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
719*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
720*01826a49SYabin Cui
721*01826a49SYabin Cui You can contact the author at :
722*01826a49SYabin Cui - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
723*01826a49SYabin Cui - Public forum : https://groups.google.com/forum/#!forum/lz4c
724*01826a49SYabin Cui ****************************************************************** */
725*01826a49SYabin Cui
726*01826a49SYabin Cui #if defined (__cplusplus)
727*01826a49SYabin Cui extern "C" {
728*01826a49SYabin Cui #endif
729*01826a49SYabin Cui
730*01826a49SYabin Cui /******************************************
731*01826a49SYabin Cui * Static allocation macros
732*01826a49SYabin Cui ******************************************/
733*01826a49SYabin Cui /* Huff0 buffer bounds */
734*01826a49SYabin Cui #define HUF_CTABLEBOUND 129
735*01826a49SYabin Cui #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
736*01826a49SYabin Cui #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
737*01826a49SYabin Cui
738*01826a49SYabin Cui /* static allocation of Huff0's DTable */
739*01826a49SYabin Cui #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
740*01826a49SYabin Cui #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
741*01826a49SYabin Cui unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
742*01826a49SYabin Cui #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
743*01826a49SYabin Cui unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
744*01826a49SYabin Cui #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
745*01826a49SYabin Cui unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
746*01826a49SYabin Cui
747*01826a49SYabin Cui
748*01826a49SYabin Cui /******************************************
749*01826a49SYabin Cui * Advanced functions
750*01826a49SYabin Cui ******************************************/
751*01826a49SYabin Cui static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
752*01826a49SYabin Cui static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
753*01826a49SYabin Cui
754*01826a49SYabin Cui
755*01826a49SYabin Cui #if defined (__cplusplus)
756*01826a49SYabin Cui }
757*01826a49SYabin Cui #endif
758*01826a49SYabin Cui
759*01826a49SYabin Cui /*
760*01826a49SYabin Cui zstd - standard compression library
761*01826a49SYabin Cui Header File
762*01826a49SYabin Cui Copyright (C) 2014-2015, Yann Collet.
763*01826a49SYabin Cui
764*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
765*01826a49SYabin Cui
766*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
767*01826a49SYabin Cui modification, are permitted provided that the following conditions are
768*01826a49SYabin Cui met:
769*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
770*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
771*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
772*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
773*01826a49SYabin Cui in the documentation and/or other materials provided with the
774*01826a49SYabin Cui distribution.
775*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
776*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
777*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
778*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
779*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
780*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
781*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
782*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
783*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
784*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
785*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
786*01826a49SYabin Cui
787*01826a49SYabin Cui You can contact the author at :
788*01826a49SYabin Cui - zstd source repository : https://github.com/Cyan4973/zstd
789*01826a49SYabin Cui - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
790*01826a49SYabin Cui */
791*01826a49SYabin Cui
792*01826a49SYabin Cui #if defined (__cplusplus)
793*01826a49SYabin Cui extern "C" {
794*01826a49SYabin Cui #endif
795*01826a49SYabin Cui
796*01826a49SYabin Cui /* *************************************
797*01826a49SYabin Cui * Includes
798*01826a49SYabin Cui ***************************************/
799*01826a49SYabin Cui #include <stddef.h> /* size_t */
800*01826a49SYabin Cui
801*01826a49SYabin Cui
802*01826a49SYabin Cui /* *************************************
803*01826a49SYabin Cui * Version
804*01826a49SYabin Cui ***************************************/
805*01826a49SYabin Cui #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
806*01826a49SYabin Cui #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
807*01826a49SYabin Cui #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
808*01826a49SYabin Cui #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
809*01826a49SYabin Cui
810*01826a49SYabin Cui
811*01826a49SYabin Cui /* *************************************
812*01826a49SYabin Cui * Advanced functions
813*01826a49SYabin Cui ***************************************/
814*01826a49SYabin Cui typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */
815*01826a49SYabin Cui
816*01826a49SYabin Cui #if defined (__cplusplus)
817*01826a49SYabin Cui }
818*01826a49SYabin Cui #endif
819*01826a49SYabin Cui /*
820*01826a49SYabin Cui zstd - standard compression library
821*01826a49SYabin Cui Header File for static linking only
822*01826a49SYabin Cui Copyright (C) 2014-2015, Yann Collet.
823*01826a49SYabin Cui
824*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
825*01826a49SYabin Cui
826*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
827*01826a49SYabin Cui modification, are permitted provided that the following conditions are
828*01826a49SYabin Cui met:
829*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
830*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
831*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
832*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
833*01826a49SYabin Cui in the documentation and/or other materials provided with the
834*01826a49SYabin Cui distribution.
835*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
836*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
837*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
838*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
839*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
840*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
841*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
842*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
843*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
844*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
845*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
846*01826a49SYabin Cui
847*01826a49SYabin Cui You can contact the author at :
848*01826a49SYabin Cui - zstd source repository : https://github.com/Cyan4973/zstd
849*01826a49SYabin Cui - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
850*01826a49SYabin Cui */
851*01826a49SYabin Cui
852*01826a49SYabin Cui /* The objects defined into this file should be considered experimental.
853*01826a49SYabin Cui * They are not labelled stable, as their prototype may change in the future.
854*01826a49SYabin Cui * You can use them for tests, provide feedback, or if you can endure risk of future changes.
855*01826a49SYabin Cui */
856*01826a49SYabin Cui
857*01826a49SYabin Cui #if defined (__cplusplus)
858*01826a49SYabin Cui extern "C" {
859*01826a49SYabin Cui #endif
860*01826a49SYabin Cui
861*01826a49SYabin Cui /* *************************************
862*01826a49SYabin Cui * Streaming functions
863*01826a49SYabin Cui ***************************************/
864*01826a49SYabin Cui
865*01826a49SYabin Cui typedef struct ZSTDv03_Dctx_s ZSTD_DCtx;
866*01826a49SYabin Cui
867*01826a49SYabin Cui /*
868*01826a49SYabin Cui Use above functions alternatively.
869*01826a49SYabin Cui ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
870*01826a49SYabin Cui ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
871*01826a49SYabin Cui Result is the number of bytes regenerated within 'dst'.
872*01826a49SYabin Cui It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
873*01826a49SYabin Cui */
874*01826a49SYabin Cui
875*01826a49SYabin Cui /* *************************************
876*01826a49SYabin Cui * Prefix - version detection
877*01826a49SYabin Cui ***************************************/
878*01826a49SYabin Cui #define ZSTD_magicNumber 0xFD2FB523 /* v0.3 */
879*01826a49SYabin Cui
880*01826a49SYabin Cui
881*01826a49SYabin Cui #if defined (__cplusplus)
882*01826a49SYabin Cui }
883*01826a49SYabin Cui #endif
884*01826a49SYabin Cui /* ******************************************************************
885*01826a49SYabin Cui FSE : Finite State Entropy coder
886*01826a49SYabin Cui Copyright (C) 2013-2015, Yann Collet.
887*01826a49SYabin Cui
888*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
889*01826a49SYabin Cui
890*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
891*01826a49SYabin Cui modification, are permitted provided that the following conditions are
892*01826a49SYabin Cui met:
893*01826a49SYabin Cui
894*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
895*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
896*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
897*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
898*01826a49SYabin Cui in the documentation and/or other materials provided with the
899*01826a49SYabin Cui distribution.
900*01826a49SYabin Cui
901*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
902*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
903*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
904*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
905*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
906*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
907*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
908*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
909*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
910*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
911*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
912*01826a49SYabin Cui
913*01826a49SYabin Cui You can contact the author at :
914*01826a49SYabin Cui - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
915*01826a49SYabin Cui - Public forum : https://groups.google.com/forum/#!forum/lz4c
916*01826a49SYabin Cui ****************************************************************** */
917*01826a49SYabin Cui
918*01826a49SYabin Cui #ifndef FSE_COMMONDEFS_ONLY
919*01826a49SYabin Cui
920*01826a49SYabin Cui /****************************************************************
921*01826a49SYabin Cui * Tuning parameters
922*01826a49SYabin Cui ****************************************************************/
923*01826a49SYabin Cui /* MEMORY_USAGE :
924*01826a49SYabin Cui * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
925*01826a49SYabin Cui * Increasing memory usage improves compression ratio
926*01826a49SYabin Cui * Reduced memory usage can improve speed, due to cache effect
927*01826a49SYabin Cui * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
928*01826a49SYabin Cui #define FSE_MAX_MEMORY_USAGE 14
929*01826a49SYabin Cui #define FSE_DEFAULT_MEMORY_USAGE 13
930*01826a49SYabin Cui
931*01826a49SYabin Cui /* FSE_MAX_SYMBOL_VALUE :
932*01826a49SYabin Cui * Maximum symbol value authorized.
933*01826a49SYabin Cui * Required for proper stack allocation */
934*01826a49SYabin Cui #define FSE_MAX_SYMBOL_VALUE 255
935*01826a49SYabin Cui
936*01826a49SYabin Cui
937*01826a49SYabin Cui /****************************************************************
938*01826a49SYabin Cui * template functions type & suffix
939*01826a49SYabin Cui ****************************************************************/
940*01826a49SYabin Cui #define FSE_FUNCTION_TYPE BYTE
941*01826a49SYabin Cui #define FSE_FUNCTION_EXTENSION
942*01826a49SYabin Cui
943*01826a49SYabin Cui
944*01826a49SYabin Cui /****************************************************************
945*01826a49SYabin Cui * Byte symbol type
946*01826a49SYabin Cui ****************************************************************/
947*01826a49SYabin Cui #endif /* !FSE_COMMONDEFS_ONLY */
948*01826a49SYabin Cui
949*01826a49SYabin Cui
950*01826a49SYabin Cui /****************************************************************
951*01826a49SYabin Cui * Compiler specifics
952*01826a49SYabin Cui ****************************************************************/
953*01826a49SYabin Cui #ifdef _MSC_VER /* Visual Studio */
954*01826a49SYabin Cui # define FORCE_INLINE static __forceinline
955*01826a49SYabin Cui # include <intrin.h> /* For Visual 2005 */
956*01826a49SYabin Cui # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
957*01826a49SYabin Cui # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
958*01826a49SYabin Cui #else
959*01826a49SYabin Cui # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
960*01826a49SYabin Cui # ifdef __GNUC__
961*01826a49SYabin Cui # define FORCE_INLINE static inline __attribute__((always_inline))
962*01826a49SYabin Cui # else
963*01826a49SYabin Cui # define FORCE_INLINE static inline
964*01826a49SYabin Cui # endif
965*01826a49SYabin Cui # else
966*01826a49SYabin Cui # define FORCE_INLINE static
967*01826a49SYabin Cui # endif /* __STDC_VERSION__ */
968*01826a49SYabin Cui #endif
969*01826a49SYabin Cui
970*01826a49SYabin Cui
971*01826a49SYabin Cui /****************************************************************
972*01826a49SYabin Cui * Includes
973*01826a49SYabin Cui ****************************************************************/
974*01826a49SYabin Cui #include <stdlib.h> /* malloc, free, qsort */
975*01826a49SYabin Cui #include <string.h> /* memcpy, memset */
976*01826a49SYabin Cui #include <stdio.h> /* printf (debug) */
977*01826a49SYabin Cui
978*01826a49SYabin Cui /****************************************************************
979*01826a49SYabin Cui * Constants
980*01826a49SYabin Cui *****************************************************************/
981*01826a49SYabin Cui #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
982*01826a49SYabin Cui #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
983*01826a49SYabin Cui #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
984*01826a49SYabin Cui #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
985*01826a49SYabin Cui #define FSE_MIN_TABLELOG 5
986*01826a49SYabin Cui
987*01826a49SYabin Cui #define FSE_TABLELOG_ABSOLUTE_MAX 15
988*01826a49SYabin Cui #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
989*01826a49SYabin Cui #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
990*01826a49SYabin Cui #endif
991*01826a49SYabin Cui
992*01826a49SYabin Cui
993*01826a49SYabin Cui /****************************************************************
994*01826a49SYabin Cui * Error Management
995*01826a49SYabin Cui ****************************************************************/
996*01826a49SYabin Cui #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
997*01826a49SYabin Cui
998*01826a49SYabin Cui
999*01826a49SYabin Cui /****************************************************************
1000*01826a49SYabin Cui * Complex types
1001*01826a49SYabin Cui ****************************************************************/
1002*01826a49SYabin Cui typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1003*01826a49SYabin Cui
1004*01826a49SYabin Cui
1005*01826a49SYabin Cui /****************************************************************
1006*01826a49SYabin Cui * Templates
1007*01826a49SYabin Cui ****************************************************************/
1008*01826a49SYabin Cui /*
1009*01826a49SYabin Cui designed to be included
1010*01826a49SYabin Cui for type-specific functions (template emulation in C)
1011*01826a49SYabin Cui Objective is to write these functions only once, for improved maintenance
1012*01826a49SYabin Cui */
1013*01826a49SYabin Cui
1014*01826a49SYabin Cui /* safety checks */
1015*01826a49SYabin Cui #ifndef FSE_FUNCTION_EXTENSION
1016*01826a49SYabin Cui # error "FSE_FUNCTION_EXTENSION must be defined"
1017*01826a49SYabin Cui #endif
1018*01826a49SYabin Cui #ifndef FSE_FUNCTION_TYPE
1019*01826a49SYabin Cui # error "FSE_FUNCTION_TYPE must be defined"
1020*01826a49SYabin Cui #endif
1021*01826a49SYabin Cui
1022*01826a49SYabin Cui /* Function names */
1023*01826a49SYabin Cui #define FSE_CAT(X,Y) X##Y
1024*01826a49SYabin Cui #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1025*01826a49SYabin Cui #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1026*01826a49SYabin Cui
1027*01826a49SYabin Cui
1028*01826a49SYabin Cui /* Function templates */
1029*01826a49SYabin Cui
1030*01826a49SYabin Cui #define FSE_DECODE_TYPE FSE_decode_t
1031*01826a49SYabin Cui
FSE_tableStep(U32 tableSize)1032*01826a49SYabin Cui static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1033*01826a49SYabin Cui
FSE_buildDTable(FSE_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog)1034*01826a49SYabin Cui static size_t FSE_buildDTable
1035*01826a49SYabin Cui (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1036*01826a49SYabin Cui {
1037*01826a49SYabin Cui void* ptr = dt+1;
1038*01826a49SYabin Cui FSE_DTableHeader DTableH;
1039*01826a49SYabin Cui FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1040*01826a49SYabin Cui const U32 tableSize = 1 << tableLog;
1041*01826a49SYabin Cui const U32 tableMask = tableSize-1;
1042*01826a49SYabin Cui const U32 step = FSE_tableStep(tableSize);
1043*01826a49SYabin Cui U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1044*01826a49SYabin Cui U32 position = 0;
1045*01826a49SYabin Cui U32 highThreshold = tableSize-1;
1046*01826a49SYabin Cui const S16 largeLimit= (S16)(1 << (tableLog-1));
1047*01826a49SYabin Cui U32 noLarge = 1;
1048*01826a49SYabin Cui U32 s;
1049*01826a49SYabin Cui
1050*01826a49SYabin Cui /* Sanity Checks */
1051*01826a49SYabin Cui if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1052*01826a49SYabin Cui if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1053*01826a49SYabin Cui
1054*01826a49SYabin Cui /* Init, lay down lowprob symbols */
1055*01826a49SYabin Cui DTableH.tableLog = (U16)tableLog;
1056*01826a49SYabin Cui for (s=0; s<=maxSymbolValue; s++)
1057*01826a49SYabin Cui {
1058*01826a49SYabin Cui if (normalizedCounter[s]==-1)
1059*01826a49SYabin Cui {
1060*01826a49SYabin Cui tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1061*01826a49SYabin Cui symbolNext[s] = 1;
1062*01826a49SYabin Cui }
1063*01826a49SYabin Cui else
1064*01826a49SYabin Cui {
1065*01826a49SYabin Cui if (normalizedCounter[s] >= largeLimit) noLarge=0;
1066*01826a49SYabin Cui symbolNext[s] = normalizedCounter[s];
1067*01826a49SYabin Cui }
1068*01826a49SYabin Cui }
1069*01826a49SYabin Cui
1070*01826a49SYabin Cui /* Spread symbols */
1071*01826a49SYabin Cui for (s=0; s<=maxSymbolValue; s++)
1072*01826a49SYabin Cui {
1073*01826a49SYabin Cui int i;
1074*01826a49SYabin Cui for (i=0; i<normalizedCounter[s]; i++)
1075*01826a49SYabin Cui {
1076*01826a49SYabin Cui tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1077*01826a49SYabin Cui position = (position + step) & tableMask;
1078*01826a49SYabin Cui while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1079*01826a49SYabin Cui }
1080*01826a49SYabin Cui }
1081*01826a49SYabin Cui
1082*01826a49SYabin Cui if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1083*01826a49SYabin Cui
1084*01826a49SYabin Cui /* Build Decoding table */
1085*01826a49SYabin Cui {
1086*01826a49SYabin Cui U32 i;
1087*01826a49SYabin Cui for (i=0; i<tableSize; i++)
1088*01826a49SYabin Cui {
1089*01826a49SYabin Cui FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1090*01826a49SYabin Cui U16 nextState = symbolNext[symbol]++;
1091*01826a49SYabin Cui tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1092*01826a49SYabin Cui tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1093*01826a49SYabin Cui }
1094*01826a49SYabin Cui }
1095*01826a49SYabin Cui
1096*01826a49SYabin Cui DTableH.fastMode = (U16)noLarge;
1097*01826a49SYabin Cui memcpy(dt, &DTableH, sizeof(DTableH));
1098*01826a49SYabin Cui return 0;
1099*01826a49SYabin Cui }
1100*01826a49SYabin Cui
1101*01826a49SYabin Cui
1102*01826a49SYabin Cui #ifndef FSE_COMMONDEFS_ONLY
1103*01826a49SYabin Cui /******************************************
1104*01826a49SYabin Cui * FSE helper functions
1105*01826a49SYabin Cui ******************************************/
FSE_isError(size_t code)1106*01826a49SYabin Cui static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1107*01826a49SYabin Cui
1108*01826a49SYabin Cui
1109*01826a49SYabin Cui /****************************************************************
1110*01826a49SYabin Cui * FSE NCount encoding-decoding
1111*01826a49SYabin Cui ****************************************************************/
FSE_abs(short a)1112*01826a49SYabin Cui static short FSE_abs(short a)
1113*01826a49SYabin Cui {
1114*01826a49SYabin Cui return a<0 ? -a : a;
1115*01826a49SYabin Cui }
1116*01826a49SYabin Cui
FSE_readNCount(short * normalizedCounter,unsigned * maxSVPtr,unsigned * tableLogPtr,const void * headerBuffer,size_t hbSize)1117*01826a49SYabin Cui static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1118*01826a49SYabin Cui const void* headerBuffer, size_t hbSize)
1119*01826a49SYabin Cui {
1120*01826a49SYabin Cui const BYTE* const istart = (const BYTE*) headerBuffer;
1121*01826a49SYabin Cui const BYTE* const iend = istart + hbSize;
1122*01826a49SYabin Cui const BYTE* ip = istart;
1123*01826a49SYabin Cui int nbBits;
1124*01826a49SYabin Cui int remaining;
1125*01826a49SYabin Cui int threshold;
1126*01826a49SYabin Cui U32 bitStream;
1127*01826a49SYabin Cui int bitCount;
1128*01826a49SYabin Cui unsigned charnum = 0;
1129*01826a49SYabin Cui int previous0 = 0;
1130*01826a49SYabin Cui
1131*01826a49SYabin Cui if (hbSize < 4) return ERROR(srcSize_wrong);
1132*01826a49SYabin Cui bitStream = MEM_readLE32(ip);
1133*01826a49SYabin Cui nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1134*01826a49SYabin Cui if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1135*01826a49SYabin Cui bitStream >>= 4;
1136*01826a49SYabin Cui bitCount = 4;
1137*01826a49SYabin Cui *tableLogPtr = nbBits;
1138*01826a49SYabin Cui remaining = (1<<nbBits)+1;
1139*01826a49SYabin Cui threshold = 1<<nbBits;
1140*01826a49SYabin Cui nbBits++;
1141*01826a49SYabin Cui
1142*01826a49SYabin Cui while ((remaining>1) && (charnum<=*maxSVPtr))
1143*01826a49SYabin Cui {
1144*01826a49SYabin Cui if (previous0)
1145*01826a49SYabin Cui {
1146*01826a49SYabin Cui unsigned n0 = charnum;
1147*01826a49SYabin Cui while ((bitStream & 0xFFFF) == 0xFFFF)
1148*01826a49SYabin Cui {
1149*01826a49SYabin Cui n0+=24;
1150*01826a49SYabin Cui if (ip < iend-5)
1151*01826a49SYabin Cui {
1152*01826a49SYabin Cui ip+=2;
1153*01826a49SYabin Cui bitStream = MEM_readLE32(ip) >> bitCount;
1154*01826a49SYabin Cui }
1155*01826a49SYabin Cui else
1156*01826a49SYabin Cui {
1157*01826a49SYabin Cui bitStream >>= 16;
1158*01826a49SYabin Cui bitCount+=16;
1159*01826a49SYabin Cui }
1160*01826a49SYabin Cui }
1161*01826a49SYabin Cui while ((bitStream & 3) == 3)
1162*01826a49SYabin Cui {
1163*01826a49SYabin Cui n0+=3;
1164*01826a49SYabin Cui bitStream>>=2;
1165*01826a49SYabin Cui bitCount+=2;
1166*01826a49SYabin Cui }
1167*01826a49SYabin Cui n0 += bitStream & 3;
1168*01826a49SYabin Cui bitCount += 2;
1169*01826a49SYabin Cui if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1170*01826a49SYabin Cui while (charnum < n0) normalizedCounter[charnum++] = 0;
1171*01826a49SYabin Cui if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1172*01826a49SYabin Cui {
1173*01826a49SYabin Cui ip += bitCount>>3;
1174*01826a49SYabin Cui bitCount &= 7;
1175*01826a49SYabin Cui bitStream = MEM_readLE32(ip) >> bitCount;
1176*01826a49SYabin Cui }
1177*01826a49SYabin Cui else
1178*01826a49SYabin Cui bitStream >>= 2;
1179*01826a49SYabin Cui }
1180*01826a49SYabin Cui {
1181*01826a49SYabin Cui const short max = (short)((2*threshold-1)-remaining);
1182*01826a49SYabin Cui short count;
1183*01826a49SYabin Cui
1184*01826a49SYabin Cui if ((bitStream & (threshold-1)) < (U32)max)
1185*01826a49SYabin Cui {
1186*01826a49SYabin Cui count = (short)(bitStream & (threshold-1));
1187*01826a49SYabin Cui bitCount += nbBits-1;
1188*01826a49SYabin Cui }
1189*01826a49SYabin Cui else
1190*01826a49SYabin Cui {
1191*01826a49SYabin Cui count = (short)(bitStream & (2*threshold-1));
1192*01826a49SYabin Cui if (count >= threshold) count -= max;
1193*01826a49SYabin Cui bitCount += nbBits;
1194*01826a49SYabin Cui }
1195*01826a49SYabin Cui
1196*01826a49SYabin Cui count--; /* extra accuracy */
1197*01826a49SYabin Cui remaining -= FSE_abs(count);
1198*01826a49SYabin Cui normalizedCounter[charnum++] = count;
1199*01826a49SYabin Cui previous0 = !count;
1200*01826a49SYabin Cui while (remaining < threshold)
1201*01826a49SYabin Cui {
1202*01826a49SYabin Cui nbBits--;
1203*01826a49SYabin Cui threshold >>= 1;
1204*01826a49SYabin Cui }
1205*01826a49SYabin Cui
1206*01826a49SYabin Cui {
1207*01826a49SYabin Cui if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1208*01826a49SYabin Cui {
1209*01826a49SYabin Cui ip += bitCount>>3;
1210*01826a49SYabin Cui bitCount &= 7;
1211*01826a49SYabin Cui }
1212*01826a49SYabin Cui else
1213*01826a49SYabin Cui {
1214*01826a49SYabin Cui bitCount -= (int)(8 * (iend - 4 - ip));
1215*01826a49SYabin Cui ip = iend - 4;
1216*01826a49SYabin Cui }
1217*01826a49SYabin Cui bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1218*01826a49SYabin Cui }
1219*01826a49SYabin Cui }
1220*01826a49SYabin Cui }
1221*01826a49SYabin Cui if (remaining != 1) return ERROR(GENERIC);
1222*01826a49SYabin Cui *maxSVPtr = charnum-1;
1223*01826a49SYabin Cui
1224*01826a49SYabin Cui ip += (bitCount+7)>>3;
1225*01826a49SYabin Cui if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1226*01826a49SYabin Cui return ip-istart;
1227*01826a49SYabin Cui }
1228*01826a49SYabin Cui
1229*01826a49SYabin Cui
1230*01826a49SYabin Cui /*********************************************************
1231*01826a49SYabin Cui * Decompression (Byte symbols)
1232*01826a49SYabin Cui *********************************************************/
FSE_buildDTable_rle(FSE_DTable * dt,BYTE symbolValue)1233*01826a49SYabin Cui static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1234*01826a49SYabin Cui {
1235*01826a49SYabin Cui void* ptr = dt;
1236*01826a49SYabin Cui FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1237*01826a49SYabin Cui FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1;
1238*01826a49SYabin Cui
1239*01826a49SYabin Cui DTableH->tableLog = 0;
1240*01826a49SYabin Cui DTableH->fastMode = 0;
1241*01826a49SYabin Cui
1242*01826a49SYabin Cui cell->newState = 0;
1243*01826a49SYabin Cui cell->symbol = symbolValue;
1244*01826a49SYabin Cui cell->nbBits = 0;
1245*01826a49SYabin Cui
1246*01826a49SYabin Cui return 0;
1247*01826a49SYabin Cui }
1248*01826a49SYabin Cui
1249*01826a49SYabin Cui
FSE_buildDTable_raw(FSE_DTable * dt,unsigned nbBits)1250*01826a49SYabin Cui static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1251*01826a49SYabin Cui {
1252*01826a49SYabin Cui void* ptr = dt;
1253*01826a49SYabin Cui FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1254*01826a49SYabin Cui FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1;
1255*01826a49SYabin Cui const unsigned tableSize = 1 << nbBits;
1256*01826a49SYabin Cui const unsigned tableMask = tableSize - 1;
1257*01826a49SYabin Cui const unsigned maxSymbolValue = tableMask;
1258*01826a49SYabin Cui unsigned s;
1259*01826a49SYabin Cui
1260*01826a49SYabin Cui /* Sanity checks */
1261*01826a49SYabin Cui if (nbBits < 1) return ERROR(GENERIC); /* min size */
1262*01826a49SYabin Cui
1263*01826a49SYabin Cui /* Build Decoding Table */
1264*01826a49SYabin Cui DTableH->tableLog = (U16)nbBits;
1265*01826a49SYabin Cui DTableH->fastMode = 1;
1266*01826a49SYabin Cui for (s=0; s<=maxSymbolValue; s++)
1267*01826a49SYabin Cui {
1268*01826a49SYabin Cui dinfo[s].newState = 0;
1269*01826a49SYabin Cui dinfo[s].symbol = (BYTE)s;
1270*01826a49SYabin Cui dinfo[s].nbBits = (BYTE)nbBits;
1271*01826a49SYabin Cui }
1272*01826a49SYabin Cui
1273*01826a49SYabin Cui return 0;
1274*01826a49SYabin Cui }
1275*01826a49SYabin Cui
FSE_decompress_usingDTable_generic(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt,const unsigned fast)1276*01826a49SYabin Cui FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1277*01826a49SYabin Cui void* dst, size_t maxDstSize,
1278*01826a49SYabin Cui const void* cSrc, size_t cSrcSize,
1279*01826a49SYabin Cui const FSE_DTable* dt, const unsigned fast)
1280*01826a49SYabin Cui {
1281*01826a49SYabin Cui BYTE* const ostart = (BYTE*) dst;
1282*01826a49SYabin Cui BYTE* op = ostart;
1283*01826a49SYabin Cui BYTE* const omax = op + maxDstSize;
1284*01826a49SYabin Cui BYTE* const olimit = omax-3;
1285*01826a49SYabin Cui
1286*01826a49SYabin Cui BIT_DStream_t bitD;
1287*01826a49SYabin Cui FSE_DState_t state1;
1288*01826a49SYabin Cui FSE_DState_t state2;
1289*01826a49SYabin Cui size_t errorCode;
1290*01826a49SYabin Cui
1291*01826a49SYabin Cui /* Init */
1292*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1293*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1294*01826a49SYabin Cui
1295*01826a49SYabin Cui FSE_initDState(&state1, &bitD, dt);
1296*01826a49SYabin Cui FSE_initDState(&state2, &bitD, dt);
1297*01826a49SYabin Cui
1298*01826a49SYabin Cui #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1299*01826a49SYabin Cui
1300*01826a49SYabin Cui /* 4 symbols per loop */
1301*01826a49SYabin Cui for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1302*01826a49SYabin Cui {
1303*01826a49SYabin Cui op[0] = FSE_GETSYMBOL(&state1);
1304*01826a49SYabin Cui
1305*01826a49SYabin Cui if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1306*01826a49SYabin Cui BIT_reloadDStream(&bitD);
1307*01826a49SYabin Cui
1308*01826a49SYabin Cui op[1] = FSE_GETSYMBOL(&state2);
1309*01826a49SYabin Cui
1310*01826a49SYabin Cui if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1311*01826a49SYabin Cui { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1312*01826a49SYabin Cui
1313*01826a49SYabin Cui op[2] = FSE_GETSYMBOL(&state1);
1314*01826a49SYabin Cui
1315*01826a49SYabin Cui if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1316*01826a49SYabin Cui BIT_reloadDStream(&bitD);
1317*01826a49SYabin Cui
1318*01826a49SYabin Cui op[3] = FSE_GETSYMBOL(&state2);
1319*01826a49SYabin Cui }
1320*01826a49SYabin Cui
1321*01826a49SYabin Cui /* tail */
1322*01826a49SYabin Cui /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1323*01826a49SYabin Cui while (1)
1324*01826a49SYabin Cui {
1325*01826a49SYabin Cui if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1326*01826a49SYabin Cui break;
1327*01826a49SYabin Cui
1328*01826a49SYabin Cui *op++ = FSE_GETSYMBOL(&state1);
1329*01826a49SYabin Cui
1330*01826a49SYabin Cui if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1331*01826a49SYabin Cui break;
1332*01826a49SYabin Cui
1333*01826a49SYabin Cui *op++ = FSE_GETSYMBOL(&state2);
1334*01826a49SYabin Cui }
1335*01826a49SYabin Cui
1336*01826a49SYabin Cui /* end ? */
1337*01826a49SYabin Cui if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1338*01826a49SYabin Cui return op-ostart;
1339*01826a49SYabin Cui
1340*01826a49SYabin Cui if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1341*01826a49SYabin Cui
1342*01826a49SYabin Cui return ERROR(corruption_detected);
1343*01826a49SYabin Cui }
1344*01826a49SYabin Cui
1345*01826a49SYabin Cui
FSE_decompress_usingDTable(void * dst,size_t originalSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt)1346*01826a49SYabin Cui static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1347*01826a49SYabin Cui const void* cSrc, size_t cSrcSize,
1348*01826a49SYabin Cui const FSE_DTable* dt)
1349*01826a49SYabin Cui {
1350*01826a49SYabin Cui FSE_DTableHeader DTableH;
1351*01826a49SYabin Cui memcpy(&DTableH, dt, sizeof(DTableH));
1352*01826a49SYabin Cui
1353*01826a49SYabin Cui /* select fast mode (static) */
1354*01826a49SYabin Cui if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1355*01826a49SYabin Cui return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1356*01826a49SYabin Cui }
1357*01826a49SYabin Cui
1358*01826a49SYabin Cui
FSE_decompress(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize)1359*01826a49SYabin Cui static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1360*01826a49SYabin Cui {
1361*01826a49SYabin Cui const BYTE* const istart = (const BYTE*)cSrc;
1362*01826a49SYabin Cui const BYTE* ip = istart;
1363*01826a49SYabin Cui short counting[FSE_MAX_SYMBOL_VALUE+1];
1364*01826a49SYabin Cui DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1365*01826a49SYabin Cui unsigned tableLog;
1366*01826a49SYabin Cui unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1367*01826a49SYabin Cui size_t errorCode;
1368*01826a49SYabin Cui
1369*01826a49SYabin Cui if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1370*01826a49SYabin Cui
1371*01826a49SYabin Cui /* normal FSE decoding mode */
1372*01826a49SYabin Cui errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1373*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1374*01826a49SYabin Cui if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1375*01826a49SYabin Cui ip += errorCode;
1376*01826a49SYabin Cui cSrcSize -= errorCode;
1377*01826a49SYabin Cui
1378*01826a49SYabin Cui errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1379*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1380*01826a49SYabin Cui
1381*01826a49SYabin Cui /* always return, even if it is an error code */
1382*01826a49SYabin Cui return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1383*01826a49SYabin Cui }
1384*01826a49SYabin Cui
1385*01826a49SYabin Cui
1386*01826a49SYabin Cui
1387*01826a49SYabin Cui #endif /* FSE_COMMONDEFS_ONLY */
1388*01826a49SYabin Cui /* ******************************************************************
1389*01826a49SYabin Cui Huff0 : Huffman coder, part of New Generation Entropy library
1390*01826a49SYabin Cui Copyright (C) 2013-2015, Yann Collet.
1391*01826a49SYabin Cui
1392*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1393*01826a49SYabin Cui
1394*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
1395*01826a49SYabin Cui modification, are permitted provided that the following conditions are
1396*01826a49SYabin Cui met:
1397*01826a49SYabin Cui
1398*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
1399*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
1400*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
1401*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
1402*01826a49SYabin Cui in the documentation and/or other materials provided with the
1403*01826a49SYabin Cui distribution.
1404*01826a49SYabin Cui
1405*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1406*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1407*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1408*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1409*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1410*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1411*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1412*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1413*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1414*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1415*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1416*01826a49SYabin Cui
1417*01826a49SYabin Cui You can contact the author at :
1418*01826a49SYabin Cui - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1419*01826a49SYabin Cui - Public forum : https://groups.google.com/forum/#!forum/lz4c
1420*01826a49SYabin Cui ****************************************************************** */
1421*01826a49SYabin Cui
1422*01826a49SYabin Cui /****************************************************************
1423*01826a49SYabin Cui * Compiler specifics
1424*01826a49SYabin Cui ****************************************************************/
1425*01826a49SYabin Cui #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1426*01826a49SYabin Cui /* inline is defined */
1427*01826a49SYabin Cui #elif defined(_MSC_VER)
1428*01826a49SYabin Cui # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1429*01826a49SYabin Cui # define inline __inline
1430*01826a49SYabin Cui #else
1431*01826a49SYabin Cui # define inline /* disable inline */
1432*01826a49SYabin Cui #endif
1433*01826a49SYabin Cui
1434*01826a49SYabin Cui
1435*01826a49SYabin Cui /****************************************************************
1436*01826a49SYabin Cui * Includes
1437*01826a49SYabin Cui ****************************************************************/
1438*01826a49SYabin Cui #include <stdlib.h> /* malloc, free, qsort */
1439*01826a49SYabin Cui #include <string.h> /* memcpy, memset */
1440*01826a49SYabin Cui #include <stdio.h> /* printf (debug) */
1441*01826a49SYabin Cui
1442*01826a49SYabin Cui /****************************************************************
1443*01826a49SYabin Cui * Error Management
1444*01826a49SYabin Cui ****************************************************************/
1445*01826a49SYabin Cui #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1446*01826a49SYabin Cui
1447*01826a49SYabin Cui
1448*01826a49SYabin Cui /******************************************
1449*01826a49SYabin Cui * Helper functions
1450*01826a49SYabin Cui ******************************************/
HUF_isError(size_t code)1451*01826a49SYabin Cui static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1452*01826a49SYabin Cui
1453*01826a49SYabin Cui #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1454*01826a49SYabin Cui #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1455*01826a49SYabin Cui #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1456*01826a49SYabin Cui #define HUF_MAX_SYMBOL_VALUE 255
1457*01826a49SYabin Cui #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1458*01826a49SYabin Cui # error "HUF_MAX_TABLELOG is too large !"
1459*01826a49SYabin Cui #endif
1460*01826a49SYabin Cui
1461*01826a49SYabin Cui
1462*01826a49SYabin Cui
1463*01826a49SYabin Cui /*********************************************************
1464*01826a49SYabin Cui * Huff0 : Huffman block decompression
1465*01826a49SYabin Cui *********************************************************/
1466*01826a49SYabin Cui typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1467*01826a49SYabin Cui
1468*01826a49SYabin Cui typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1469*01826a49SYabin Cui
1470*01826a49SYabin Cui typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1471*01826a49SYabin Cui
1472*01826a49SYabin Cui /*! HUF_readStats
1473*01826a49SYabin Cui Read compact Huffman tree, saved by HUF_writeCTable
1474*01826a49SYabin Cui @huffWeight : destination buffer
1475*01826a49SYabin Cui @return : size read from `src`
1476*01826a49SYabin Cui */
HUF_readStats(BYTE * huffWeight,size_t hwSize,U32 * rankStats,U32 * nbSymbolsPtr,U32 * tableLogPtr,const void * src,size_t srcSize)1477*01826a49SYabin Cui static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1478*01826a49SYabin Cui U32* nbSymbolsPtr, U32* tableLogPtr,
1479*01826a49SYabin Cui const void* src, size_t srcSize)
1480*01826a49SYabin Cui {
1481*01826a49SYabin Cui U32 weightTotal;
1482*01826a49SYabin Cui U32 tableLog;
1483*01826a49SYabin Cui const BYTE* ip = (const BYTE*) src;
1484*01826a49SYabin Cui size_t iSize;
1485*01826a49SYabin Cui size_t oSize;
1486*01826a49SYabin Cui U32 n;
1487*01826a49SYabin Cui
1488*01826a49SYabin Cui if (!srcSize) return ERROR(srcSize_wrong);
1489*01826a49SYabin Cui iSize = ip[0];
1490*01826a49SYabin Cui //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1491*01826a49SYabin Cui
1492*01826a49SYabin Cui if (iSize >= 128) /* special header */
1493*01826a49SYabin Cui {
1494*01826a49SYabin Cui if (iSize >= (242)) /* RLE */
1495*01826a49SYabin Cui {
1496*01826a49SYabin Cui static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1497*01826a49SYabin Cui oSize = l[iSize-242];
1498*01826a49SYabin Cui memset(huffWeight, 1, hwSize);
1499*01826a49SYabin Cui iSize = 0;
1500*01826a49SYabin Cui }
1501*01826a49SYabin Cui else /* Incompressible */
1502*01826a49SYabin Cui {
1503*01826a49SYabin Cui oSize = iSize - 127;
1504*01826a49SYabin Cui iSize = ((oSize+1)/2);
1505*01826a49SYabin Cui if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1506*01826a49SYabin Cui if (oSize >= hwSize) return ERROR(corruption_detected);
1507*01826a49SYabin Cui ip += 1;
1508*01826a49SYabin Cui for (n=0; n<oSize; n+=2)
1509*01826a49SYabin Cui {
1510*01826a49SYabin Cui huffWeight[n] = ip[n/2] >> 4;
1511*01826a49SYabin Cui huffWeight[n+1] = ip[n/2] & 15;
1512*01826a49SYabin Cui }
1513*01826a49SYabin Cui }
1514*01826a49SYabin Cui }
1515*01826a49SYabin Cui else /* header compressed with FSE (normal case) */
1516*01826a49SYabin Cui {
1517*01826a49SYabin Cui if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1518*01826a49SYabin Cui oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1519*01826a49SYabin Cui if (FSE_isError(oSize)) return oSize;
1520*01826a49SYabin Cui }
1521*01826a49SYabin Cui
1522*01826a49SYabin Cui /* collect weight stats */
1523*01826a49SYabin Cui memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1524*01826a49SYabin Cui weightTotal = 0;
1525*01826a49SYabin Cui for (n=0; n<oSize; n++)
1526*01826a49SYabin Cui {
1527*01826a49SYabin Cui if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1528*01826a49SYabin Cui rankStats[huffWeight[n]]++;
1529*01826a49SYabin Cui weightTotal += (1 << huffWeight[n]) >> 1;
1530*01826a49SYabin Cui }
1531*01826a49SYabin Cui if (weightTotal == 0) return ERROR(corruption_detected);
1532*01826a49SYabin Cui
1533*01826a49SYabin Cui /* get last non-null symbol weight (implied, total must be 2^n) */
1534*01826a49SYabin Cui tableLog = BIT_highbit32(weightTotal) + 1;
1535*01826a49SYabin Cui if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1536*01826a49SYabin Cui {
1537*01826a49SYabin Cui U32 total = 1 << tableLog;
1538*01826a49SYabin Cui U32 rest = total - weightTotal;
1539*01826a49SYabin Cui U32 verif = 1 << BIT_highbit32(rest);
1540*01826a49SYabin Cui U32 lastWeight = BIT_highbit32(rest) + 1;
1541*01826a49SYabin Cui if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1542*01826a49SYabin Cui huffWeight[oSize] = (BYTE)lastWeight;
1543*01826a49SYabin Cui rankStats[lastWeight]++;
1544*01826a49SYabin Cui }
1545*01826a49SYabin Cui
1546*01826a49SYabin Cui /* check tree construction validity */
1547*01826a49SYabin Cui if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1548*01826a49SYabin Cui
1549*01826a49SYabin Cui /* results */
1550*01826a49SYabin Cui *nbSymbolsPtr = (U32)(oSize+1);
1551*01826a49SYabin Cui *tableLogPtr = tableLog;
1552*01826a49SYabin Cui return iSize+1;
1553*01826a49SYabin Cui }
1554*01826a49SYabin Cui
1555*01826a49SYabin Cui
1556*01826a49SYabin Cui /**************************/
1557*01826a49SYabin Cui /* single-symbol decoding */
1558*01826a49SYabin Cui /**************************/
1559*01826a49SYabin Cui
HUF_readDTableX2(U16 * DTable,const void * src,size_t srcSize)1560*01826a49SYabin Cui static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1561*01826a49SYabin Cui {
1562*01826a49SYabin Cui BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1563*01826a49SYabin Cui U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1564*01826a49SYabin Cui U32 tableLog = 0;
1565*01826a49SYabin Cui const BYTE* ip = (const BYTE*) src;
1566*01826a49SYabin Cui size_t iSize = ip[0];
1567*01826a49SYabin Cui U32 nbSymbols = 0;
1568*01826a49SYabin Cui U32 n;
1569*01826a49SYabin Cui U32 nextRankStart;
1570*01826a49SYabin Cui void* ptr = DTable+1;
1571*01826a49SYabin Cui HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr);
1572*01826a49SYabin Cui
1573*01826a49SYabin Cui HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1574*01826a49SYabin Cui //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1575*01826a49SYabin Cui
1576*01826a49SYabin Cui iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1577*01826a49SYabin Cui if (HUF_isError(iSize)) return iSize;
1578*01826a49SYabin Cui
1579*01826a49SYabin Cui /* check result */
1580*01826a49SYabin Cui if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1581*01826a49SYabin Cui DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1582*01826a49SYabin Cui
1583*01826a49SYabin Cui /* Prepare ranks */
1584*01826a49SYabin Cui nextRankStart = 0;
1585*01826a49SYabin Cui for (n=1; n<=tableLog; n++)
1586*01826a49SYabin Cui {
1587*01826a49SYabin Cui U32 current = nextRankStart;
1588*01826a49SYabin Cui nextRankStart += (rankVal[n] << (n-1));
1589*01826a49SYabin Cui rankVal[n] = current;
1590*01826a49SYabin Cui }
1591*01826a49SYabin Cui
1592*01826a49SYabin Cui /* fill DTable */
1593*01826a49SYabin Cui for (n=0; n<nbSymbols; n++)
1594*01826a49SYabin Cui {
1595*01826a49SYabin Cui const U32 w = huffWeight[n];
1596*01826a49SYabin Cui const U32 length = (1 << w) >> 1;
1597*01826a49SYabin Cui U32 i;
1598*01826a49SYabin Cui HUF_DEltX2 D;
1599*01826a49SYabin Cui D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1600*01826a49SYabin Cui for (i = rankVal[w]; i < rankVal[w] + length; i++)
1601*01826a49SYabin Cui dt[i] = D;
1602*01826a49SYabin Cui rankVal[w] += length;
1603*01826a49SYabin Cui }
1604*01826a49SYabin Cui
1605*01826a49SYabin Cui return iSize;
1606*01826a49SYabin Cui }
1607*01826a49SYabin Cui
HUF_decodeSymbolX2(BIT_DStream_t * Dstream,const HUF_DEltX2 * dt,const U32 dtLog)1608*01826a49SYabin Cui static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1609*01826a49SYabin Cui {
1610*01826a49SYabin Cui const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1611*01826a49SYabin Cui const BYTE c = dt[val].byte;
1612*01826a49SYabin Cui BIT_skipBits(Dstream, dt[val].nbBits);
1613*01826a49SYabin Cui return c;
1614*01826a49SYabin Cui }
1615*01826a49SYabin Cui
1616*01826a49SYabin Cui #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1617*01826a49SYabin Cui *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1618*01826a49SYabin Cui
1619*01826a49SYabin Cui #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1620*01826a49SYabin Cui if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1621*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1622*01826a49SYabin Cui
1623*01826a49SYabin Cui #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1624*01826a49SYabin Cui if (MEM_64bits()) \
1625*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1626*01826a49SYabin Cui
HUF_decodeStreamX2(BYTE * p,BIT_DStream_t * const bitDPtr,BYTE * const pEnd,const HUF_DEltX2 * const dt,const U32 dtLog)1627*01826a49SYabin Cui static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1628*01826a49SYabin Cui {
1629*01826a49SYabin Cui BYTE* const pStart = p;
1630*01826a49SYabin Cui
1631*01826a49SYabin Cui /* up to 4 symbols at a time */
1632*01826a49SYabin Cui while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1633*01826a49SYabin Cui {
1634*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1635*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1636*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1637*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1638*01826a49SYabin Cui }
1639*01826a49SYabin Cui
1640*01826a49SYabin Cui /* closer to the end */
1641*01826a49SYabin Cui while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1642*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1643*01826a49SYabin Cui
1644*01826a49SYabin Cui /* no more data to retrieve from bitstream, hence no need to reload */
1645*01826a49SYabin Cui while (p < pEnd)
1646*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1647*01826a49SYabin Cui
1648*01826a49SYabin Cui return pEnd-pStart;
1649*01826a49SYabin Cui }
1650*01826a49SYabin Cui
1651*01826a49SYabin Cui
HUF_decompress4X2_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const U16 * DTable)1652*01826a49SYabin Cui static size_t HUF_decompress4X2_usingDTable(
1653*01826a49SYabin Cui void* dst, size_t dstSize,
1654*01826a49SYabin Cui const void* cSrc, size_t cSrcSize,
1655*01826a49SYabin Cui const U16* DTable)
1656*01826a49SYabin Cui {
1657*01826a49SYabin Cui if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1658*01826a49SYabin Cui
1659*01826a49SYabin Cui {
1660*01826a49SYabin Cui const BYTE* const istart = (const BYTE*) cSrc;
1661*01826a49SYabin Cui BYTE* const ostart = (BYTE*) dst;
1662*01826a49SYabin Cui BYTE* const oend = ostart + dstSize;
1663*01826a49SYabin Cui
1664*01826a49SYabin Cui const void* ptr = DTable;
1665*01826a49SYabin Cui const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1666*01826a49SYabin Cui const U32 dtLog = DTable[0];
1667*01826a49SYabin Cui size_t errorCode;
1668*01826a49SYabin Cui
1669*01826a49SYabin Cui /* Init */
1670*01826a49SYabin Cui BIT_DStream_t bitD1;
1671*01826a49SYabin Cui BIT_DStream_t bitD2;
1672*01826a49SYabin Cui BIT_DStream_t bitD3;
1673*01826a49SYabin Cui BIT_DStream_t bitD4;
1674*01826a49SYabin Cui const size_t length1 = MEM_readLE16(istart);
1675*01826a49SYabin Cui const size_t length2 = MEM_readLE16(istart+2);
1676*01826a49SYabin Cui const size_t length3 = MEM_readLE16(istart+4);
1677*01826a49SYabin Cui size_t length4;
1678*01826a49SYabin Cui const BYTE* const istart1 = istart + 6; /* jumpTable */
1679*01826a49SYabin Cui const BYTE* const istart2 = istart1 + length1;
1680*01826a49SYabin Cui const BYTE* const istart3 = istart2 + length2;
1681*01826a49SYabin Cui const BYTE* const istart4 = istart3 + length3;
1682*01826a49SYabin Cui const size_t segmentSize = (dstSize+3) / 4;
1683*01826a49SYabin Cui BYTE* const opStart2 = ostart + segmentSize;
1684*01826a49SYabin Cui BYTE* const opStart3 = opStart2 + segmentSize;
1685*01826a49SYabin Cui BYTE* const opStart4 = opStart3 + segmentSize;
1686*01826a49SYabin Cui BYTE* op1 = ostart;
1687*01826a49SYabin Cui BYTE* op2 = opStart2;
1688*01826a49SYabin Cui BYTE* op3 = opStart3;
1689*01826a49SYabin Cui BYTE* op4 = opStart4;
1690*01826a49SYabin Cui U32 endSignal;
1691*01826a49SYabin Cui
1692*01826a49SYabin Cui length4 = cSrcSize - (length1 + length2 + length3 + 6);
1693*01826a49SYabin Cui if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1694*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD1, istart1, length1);
1695*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
1696*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD2, istart2, length2);
1697*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
1698*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD3, istart3, length3);
1699*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
1700*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD4, istart4, length4);
1701*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
1702*01826a49SYabin Cui
1703*01826a49SYabin Cui /* 16-32 symbols per loop (4-8 symbols per stream) */
1704*01826a49SYabin Cui endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1705*01826a49SYabin Cui for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1706*01826a49SYabin Cui {
1707*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1708*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1709*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1710*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1711*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1712*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1713*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1714*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1715*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1716*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1717*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1718*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1719*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1720*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1721*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1722*01826a49SYabin Cui HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1723*01826a49SYabin Cui
1724*01826a49SYabin Cui endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1725*01826a49SYabin Cui }
1726*01826a49SYabin Cui
1727*01826a49SYabin Cui /* check corruption */
1728*01826a49SYabin Cui if (op1 > opStart2) return ERROR(corruption_detected);
1729*01826a49SYabin Cui if (op2 > opStart3) return ERROR(corruption_detected);
1730*01826a49SYabin Cui if (op3 > opStart4) return ERROR(corruption_detected);
1731*01826a49SYabin Cui /* note : op4 supposed already verified within main loop */
1732*01826a49SYabin Cui
1733*01826a49SYabin Cui /* finish bitStreams one by one */
1734*01826a49SYabin Cui HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1735*01826a49SYabin Cui HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1736*01826a49SYabin Cui HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1737*01826a49SYabin Cui HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1738*01826a49SYabin Cui
1739*01826a49SYabin Cui /* check */
1740*01826a49SYabin Cui endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1741*01826a49SYabin Cui if (!endSignal) return ERROR(corruption_detected);
1742*01826a49SYabin Cui
1743*01826a49SYabin Cui /* decoded size */
1744*01826a49SYabin Cui return dstSize;
1745*01826a49SYabin Cui }
1746*01826a49SYabin Cui }
1747*01826a49SYabin Cui
1748*01826a49SYabin Cui
HUF_decompress4X2(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)1749*01826a49SYabin Cui static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1750*01826a49SYabin Cui {
1751*01826a49SYabin Cui HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1752*01826a49SYabin Cui const BYTE* ip = (const BYTE*) cSrc;
1753*01826a49SYabin Cui size_t errorCode;
1754*01826a49SYabin Cui
1755*01826a49SYabin Cui errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1756*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
1757*01826a49SYabin Cui if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1758*01826a49SYabin Cui ip += errorCode;
1759*01826a49SYabin Cui cSrcSize -= errorCode;
1760*01826a49SYabin Cui
1761*01826a49SYabin Cui return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1762*01826a49SYabin Cui }
1763*01826a49SYabin Cui
1764*01826a49SYabin Cui
1765*01826a49SYabin Cui /***************************/
1766*01826a49SYabin Cui /* double-symbols decoding */
1767*01826a49SYabin Cui /***************************/
1768*01826a49SYabin Cui
HUF_fillDTableX4Level2(HUF_DEltX4 * DTable,U32 sizeLog,const U32 consumed,const U32 * rankValOrigin,const int minWeight,const sortedSymbol_t * sortedSymbols,const U32 sortedListSize,U32 nbBitsBaseline,U16 baseSeq)1769*01826a49SYabin Cui static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1770*01826a49SYabin Cui const U32* rankValOrigin, const int minWeight,
1771*01826a49SYabin Cui const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1772*01826a49SYabin Cui U32 nbBitsBaseline, U16 baseSeq)
1773*01826a49SYabin Cui {
1774*01826a49SYabin Cui HUF_DEltX4 DElt;
1775*01826a49SYabin Cui U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1776*01826a49SYabin Cui U32 s;
1777*01826a49SYabin Cui
1778*01826a49SYabin Cui /* get pre-calculated rankVal */
1779*01826a49SYabin Cui memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1780*01826a49SYabin Cui
1781*01826a49SYabin Cui /* fill skipped values */
1782*01826a49SYabin Cui if (minWeight>1)
1783*01826a49SYabin Cui {
1784*01826a49SYabin Cui U32 i, skipSize = rankVal[minWeight];
1785*01826a49SYabin Cui MEM_writeLE16(&(DElt.sequence), baseSeq);
1786*01826a49SYabin Cui DElt.nbBits = (BYTE)(consumed);
1787*01826a49SYabin Cui DElt.length = 1;
1788*01826a49SYabin Cui for (i = 0; i < skipSize; i++)
1789*01826a49SYabin Cui DTable[i] = DElt;
1790*01826a49SYabin Cui }
1791*01826a49SYabin Cui
1792*01826a49SYabin Cui /* fill DTable */
1793*01826a49SYabin Cui for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1794*01826a49SYabin Cui {
1795*01826a49SYabin Cui const U32 symbol = sortedSymbols[s].symbol;
1796*01826a49SYabin Cui const U32 weight = sortedSymbols[s].weight;
1797*01826a49SYabin Cui const U32 nbBits = nbBitsBaseline - weight;
1798*01826a49SYabin Cui const U32 length = 1 << (sizeLog-nbBits);
1799*01826a49SYabin Cui const U32 start = rankVal[weight];
1800*01826a49SYabin Cui U32 i = start;
1801*01826a49SYabin Cui const U32 end = start + length;
1802*01826a49SYabin Cui
1803*01826a49SYabin Cui MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1804*01826a49SYabin Cui DElt.nbBits = (BYTE)(nbBits + consumed);
1805*01826a49SYabin Cui DElt.length = 2;
1806*01826a49SYabin Cui do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1807*01826a49SYabin Cui
1808*01826a49SYabin Cui rankVal[weight] += length;
1809*01826a49SYabin Cui }
1810*01826a49SYabin Cui }
1811*01826a49SYabin Cui
1812*01826a49SYabin Cui typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1813*01826a49SYabin Cui
HUF_fillDTableX4(HUF_DEltX4 * DTable,const U32 targetLog,const sortedSymbol_t * sortedList,const U32 sortedListSize,const U32 * rankStart,rankVal_t rankValOrigin,const U32 maxWeight,const U32 nbBitsBaseline)1814*01826a49SYabin Cui static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1815*01826a49SYabin Cui const sortedSymbol_t* sortedList, const U32 sortedListSize,
1816*01826a49SYabin Cui const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1817*01826a49SYabin Cui const U32 nbBitsBaseline)
1818*01826a49SYabin Cui {
1819*01826a49SYabin Cui U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1820*01826a49SYabin Cui const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1821*01826a49SYabin Cui const U32 minBits = nbBitsBaseline - maxWeight;
1822*01826a49SYabin Cui U32 s;
1823*01826a49SYabin Cui
1824*01826a49SYabin Cui memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1825*01826a49SYabin Cui
1826*01826a49SYabin Cui /* fill DTable */
1827*01826a49SYabin Cui for (s=0; s<sortedListSize; s++)
1828*01826a49SYabin Cui {
1829*01826a49SYabin Cui const U16 symbol = sortedList[s].symbol;
1830*01826a49SYabin Cui const U32 weight = sortedList[s].weight;
1831*01826a49SYabin Cui const U32 nbBits = nbBitsBaseline - weight;
1832*01826a49SYabin Cui const U32 start = rankVal[weight];
1833*01826a49SYabin Cui const U32 length = 1 << (targetLog-nbBits);
1834*01826a49SYabin Cui
1835*01826a49SYabin Cui if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1836*01826a49SYabin Cui {
1837*01826a49SYabin Cui U32 sortedRank;
1838*01826a49SYabin Cui int minWeight = nbBits + scaleLog;
1839*01826a49SYabin Cui if (minWeight < 1) minWeight = 1;
1840*01826a49SYabin Cui sortedRank = rankStart[minWeight];
1841*01826a49SYabin Cui HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1842*01826a49SYabin Cui rankValOrigin[nbBits], minWeight,
1843*01826a49SYabin Cui sortedList+sortedRank, sortedListSize-sortedRank,
1844*01826a49SYabin Cui nbBitsBaseline, symbol);
1845*01826a49SYabin Cui }
1846*01826a49SYabin Cui else
1847*01826a49SYabin Cui {
1848*01826a49SYabin Cui U32 i;
1849*01826a49SYabin Cui const U32 end = start + length;
1850*01826a49SYabin Cui HUF_DEltX4 DElt;
1851*01826a49SYabin Cui
1852*01826a49SYabin Cui MEM_writeLE16(&(DElt.sequence), symbol);
1853*01826a49SYabin Cui DElt.nbBits = (BYTE)(nbBits);
1854*01826a49SYabin Cui DElt.length = 1;
1855*01826a49SYabin Cui for (i = start; i < end; i++)
1856*01826a49SYabin Cui DTable[i] = DElt;
1857*01826a49SYabin Cui }
1858*01826a49SYabin Cui rankVal[weight] += length;
1859*01826a49SYabin Cui }
1860*01826a49SYabin Cui }
1861*01826a49SYabin Cui
HUF_readDTableX4(U32 * DTable,const void * src,size_t srcSize)1862*01826a49SYabin Cui static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1863*01826a49SYabin Cui {
1864*01826a49SYabin Cui BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1865*01826a49SYabin Cui sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1866*01826a49SYabin Cui U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1867*01826a49SYabin Cui U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1868*01826a49SYabin Cui U32* const rankStart = rankStart0+1;
1869*01826a49SYabin Cui rankVal_t rankVal;
1870*01826a49SYabin Cui U32 tableLog, maxW, sizeOfSort, nbSymbols;
1871*01826a49SYabin Cui const U32 memLog = DTable[0];
1872*01826a49SYabin Cui const BYTE* ip = (const BYTE*) src;
1873*01826a49SYabin Cui size_t iSize = ip[0];
1874*01826a49SYabin Cui void* ptr = DTable;
1875*01826a49SYabin Cui HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1876*01826a49SYabin Cui
1877*01826a49SYabin Cui HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
1878*01826a49SYabin Cui if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1879*01826a49SYabin Cui //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1880*01826a49SYabin Cui
1881*01826a49SYabin Cui iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1882*01826a49SYabin Cui if (HUF_isError(iSize)) return iSize;
1883*01826a49SYabin Cui
1884*01826a49SYabin Cui /* check result */
1885*01826a49SYabin Cui if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
1886*01826a49SYabin Cui
1887*01826a49SYabin Cui /* find maxWeight */
1888*01826a49SYabin Cui for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1889*01826a49SYabin Cui { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
1890*01826a49SYabin Cui
1891*01826a49SYabin Cui /* Get start index of each weight */
1892*01826a49SYabin Cui {
1893*01826a49SYabin Cui U32 w, nextRankStart = 0;
1894*01826a49SYabin Cui for (w=1; w<=maxW; w++)
1895*01826a49SYabin Cui {
1896*01826a49SYabin Cui U32 current = nextRankStart;
1897*01826a49SYabin Cui nextRankStart += rankStats[w];
1898*01826a49SYabin Cui rankStart[w] = current;
1899*01826a49SYabin Cui }
1900*01826a49SYabin Cui rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
1901*01826a49SYabin Cui sizeOfSort = nextRankStart;
1902*01826a49SYabin Cui }
1903*01826a49SYabin Cui
1904*01826a49SYabin Cui /* sort symbols by weight */
1905*01826a49SYabin Cui {
1906*01826a49SYabin Cui U32 s;
1907*01826a49SYabin Cui for (s=0; s<nbSymbols; s++)
1908*01826a49SYabin Cui {
1909*01826a49SYabin Cui U32 w = weightList[s];
1910*01826a49SYabin Cui U32 r = rankStart[w]++;
1911*01826a49SYabin Cui sortedSymbol[r].symbol = (BYTE)s;
1912*01826a49SYabin Cui sortedSymbol[r].weight = (BYTE)w;
1913*01826a49SYabin Cui }
1914*01826a49SYabin Cui rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1915*01826a49SYabin Cui }
1916*01826a49SYabin Cui
1917*01826a49SYabin Cui /* Build rankVal */
1918*01826a49SYabin Cui {
1919*01826a49SYabin Cui const U32 minBits = tableLog+1 - maxW;
1920*01826a49SYabin Cui U32 nextRankVal = 0;
1921*01826a49SYabin Cui U32 w, consumed;
1922*01826a49SYabin Cui const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
1923*01826a49SYabin Cui U32* rankVal0 = rankVal[0];
1924*01826a49SYabin Cui for (w=1; w<=maxW; w++)
1925*01826a49SYabin Cui {
1926*01826a49SYabin Cui U32 current = nextRankVal;
1927*01826a49SYabin Cui nextRankVal += rankStats[w] << (w+rescale);
1928*01826a49SYabin Cui rankVal0[w] = current;
1929*01826a49SYabin Cui }
1930*01826a49SYabin Cui for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1931*01826a49SYabin Cui {
1932*01826a49SYabin Cui U32* rankValPtr = rankVal[consumed];
1933*01826a49SYabin Cui for (w = 1; w <= maxW; w++)
1934*01826a49SYabin Cui {
1935*01826a49SYabin Cui rankValPtr[w] = rankVal0[w] >> consumed;
1936*01826a49SYabin Cui }
1937*01826a49SYabin Cui }
1938*01826a49SYabin Cui }
1939*01826a49SYabin Cui
1940*01826a49SYabin Cui HUF_fillDTableX4(dt, memLog,
1941*01826a49SYabin Cui sortedSymbol, sizeOfSort,
1942*01826a49SYabin Cui rankStart0, rankVal, maxW,
1943*01826a49SYabin Cui tableLog+1);
1944*01826a49SYabin Cui
1945*01826a49SYabin Cui return iSize;
1946*01826a49SYabin Cui }
1947*01826a49SYabin Cui
1948*01826a49SYabin Cui
HUF_decodeSymbolX4(void * op,BIT_DStream_t * DStream,const HUF_DEltX4 * dt,const U32 dtLog)1949*01826a49SYabin Cui static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1950*01826a49SYabin Cui {
1951*01826a49SYabin Cui const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1952*01826a49SYabin Cui memcpy(op, dt+val, 2);
1953*01826a49SYabin Cui BIT_skipBits(DStream, dt[val].nbBits);
1954*01826a49SYabin Cui return dt[val].length;
1955*01826a49SYabin Cui }
1956*01826a49SYabin Cui
HUF_decodeLastSymbolX4(void * op,BIT_DStream_t * DStream,const HUF_DEltX4 * dt,const U32 dtLog)1957*01826a49SYabin Cui static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1958*01826a49SYabin Cui {
1959*01826a49SYabin Cui const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1960*01826a49SYabin Cui memcpy(op, dt+val, 1);
1961*01826a49SYabin Cui if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
1962*01826a49SYabin Cui else
1963*01826a49SYabin Cui {
1964*01826a49SYabin Cui if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
1965*01826a49SYabin Cui {
1966*01826a49SYabin Cui BIT_skipBits(DStream, dt[val].nbBits);
1967*01826a49SYabin Cui if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
1968*01826a49SYabin Cui DStream->bitsConsumed = (sizeof(DStream->bitContainer)*8); /* ugly hack; works only because it's the last symbol. Note : can't easily extract nbBits from just this symbol */
1969*01826a49SYabin Cui }
1970*01826a49SYabin Cui }
1971*01826a49SYabin Cui return 1;
1972*01826a49SYabin Cui }
1973*01826a49SYabin Cui
1974*01826a49SYabin Cui
1975*01826a49SYabin Cui #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
1976*01826a49SYabin Cui ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1977*01826a49SYabin Cui
1978*01826a49SYabin Cui #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
1979*01826a49SYabin Cui if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1980*01826a49SYabin Cui ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1981*01826a49SYabin Cui
1982*01826a49SYabin Cui #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
1983*01826a49SYabin Cui if (MEM_64bits()) \
1984*01826a49SYabin Cui ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1985*01826a49SYabin Cui
HUF_decodeStreamX4(BYTE * p,BIT_DStream_t * bitDPtr,BYTE * const pEnd,const HUF_DEltX4 * const dt,const U32 dtLog)1986*01826a49SYabin Cui static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
1987*01826a49SYabin Cui {
1988*01826a49SYabin Cui BYTE* const pStart = p;
1989*01826a49SYabin Cui
1990*01826a49SYabin Cui /* up to 8 symbols at a time */
1991*01826a49SYabin Cui while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
1992*01826a49SYabin Cui {
1993*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
1994*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
1995*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
1996*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
1997*01826a49SYabin Cui }
1998*01826a49SYabin Cui
1999*01826a49SYabin Cui /* closer to the end */
2000*01826a49SYabin Cui while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2001*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2002*01826a49SYabin Cui
2003*01826a49SYabin Cui while (p <= pEnd-2)
2004*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2005*01826a49SYabin Cui
2006*01826a49SYabin Cui if (p < pEnd)
2007*01826a49SYabin Cui p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2008*01826a49SYabin Cui
2009*01826a49SYabin Cui return p-pStart;
2010*01826a49SYabin Cui }
2011*01826a49SYabin Cui
2012*01826a49SYabin Cui
2013*01826a49SYabin Cui
HUF_decompress4X4_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const U32 * DTable)2014*01826a49SYabin Cui static size_t HUF_decompress4X4_usingDTable(
2015*01826a49SYabin Cui void* dst, size_t dstSize,
2016*01826a49SYabin Cui const void* cSrc, size_t cSrcSize,
2017*01826a49SYabin Cui const U32* DTable)
2018*01826a49SYabin Cui {
2019*01826a49SYabin Cui if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2020*01826a49SYabin Cui
2021*01826a49SYabin Cui {
2022*01826a49SYabin Cui const BYTE* const istart = (const BYTE*) cSrc;
2023*01826a49SYabin Cui BYTE* const ostart = (BYTE*) dst;
2024*01826a49SYabin Cui BYTE* const oend = ostart + dstSize;
2025*01826a49SYabin Cui
2026*01826a49SYabin Cui const void* ptr = DTable;
2027*01826a49SYabin Cui const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2028*01826a49SYabin Cui const U32 dtLog = DTable[0];
2029*01826a49SYabin Cui size_t errorCode;
2030*01826a49SYabin Cui
2031*01826a49SYabin Cui /* Init */
2032*01826a49SYabin Cui BIT_DStream_t bitD1;
2033*01826a49SYabin Cui BIT_DStream_t bitD2;
2034*01826a49SYabin Cui BIT_DStream_t bitD3;
2035*01826a49SYabin Cui BIT_DStream_t bitD4;
2036*01826a49SYabin Cui const size_t length1 = MEM_readLE16(istart);
2037*01826a49SYabin Cui const size_t length2 = MEM_readLE16(istart+2);
2038*01826a49SYabin Cui const size_t length3 = MEM_readLE16(istart+4);
2039*01826a49SYabin Cui size_t length4;
2040*01826a49SYabin Cui const BYTE* const istart1 = istart + 6; /* jumpTable */
2041*01826a49SYabin Cui const BYTE* const istart2 = istart1 + length1;
2042*01826a49SYabin Cui const BYTE* const istart3 = istart2 + length2;
2043*01826a49SYabin Cui const BYTE* const istart4 = istart3 + length3;
2044*01826a49SYabin Cui const size_t segmentSize = (dstSize+3) / 4;
2045*01826a49SYabin Cui BYTE* const opStart2 = ostart + segmentSize;
2046*01826a49SYabin Cui BYTE* const opStart3 = opStart2 + segmentSize;
2047*01826a49SYabin Cui BYTE* const opStart4 = opStart3 + segmentSize;
2048*01826a49SYabin Cui BYTE* op1 = ostart;
2049*01826a49SYabin Cui BYTE* op2 = opStart2;
2050*01826a49SYabin Cui BYTE* op3 = opStart3;
2051*01826a49SYabin Cui BYTE* op4 = opStart4;
2052*01826a49SYabin Cui U32 endSignal;
2053*01826a49SYabin Cui
2054*01826a49SYabin Cui length4 = cSrcSize - (length1 + length2 + length3 + 6);
2055*01826a49SYabin Cui if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2056*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD1, istart1, length1);
2057*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
2058*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD2, istart2, length2);
2059*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
2060*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD3, istart3, length3);
2061*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
2062*01826a49SYabin Cui errorCode = BIT_initDStream(&bitD4, istart4, length4);
2063*01826a49SYabin Cui if (HUF_isError(errorCode)) return errorCode;
2064*01826a49SYabin Cui
2065*01826a49SYabin Cui /* 16-32 symbols per loop (4-8 symbols per stream) */
2066*01826a49SYabin Cui endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2067*01826a49SYabin Cui for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2068*01826a49SYabin Cui {
2069*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2070*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2071*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2072*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2073*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2074*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2075*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2076*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2077*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2078*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2079*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2080*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2081*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2082*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2083*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2084*01826a49SYabin Cui HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2085*01826a49SYabin Cui
2086*01826a49SYabin Cui endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2087*01826a49SYabin Cui }
2088*01826a49SYabin Cui
2089*01826a49SYabin Cui /* check corruption */
2090*01826a49SYabin Cui if (op1 > opStart2) return ERROR(corruption_detected);
2091*01826a49SYabin Cui if (op2 > opStart3) return ERROR(corruption_detected);
2092*01826a49SYabin Cui if (op3 > opStart4) return ERROR(corruption_detected);
2093*01826a49SYabin Cui /* note : op4 supposed already verified within main loop */
2094*01826a49SYabin Cui
2095*01826a49SYabin Cui /* finish bitStreams one by one */
2096*01826a49SYabin Cui HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2097*01826a49SYabin Cui HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2098*01826a49SYabin Cui HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2099*01826a49SYabin Cui HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2100*01826a49SYabin Cui
2101*01826a49SYabin Cui /* check */
2102*01826a49SYabin Cui endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2103*01826a49SYabin Cui if (!endSignal) return ERROR(corruption_detected);
2104*01826a49SYabin Cui
2105*01826a49SYabin Cui /* decoded size */
2106*01826a49SYabin Cui return dstSize;
2107*01826a49SYabin Cui }
2108*01826a49SYabin Cui }
2109*01826a49SYabin Cui
2110*01826a49SYabin Cui
HUF_decompress4X4(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2111*01826a49SYabin Cui static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2112*01826a49SYabin Cui {
2113*01826a49SYabin Cui HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2114*01826a49SYabin Cui const BYTE* ip = (const BYTE*) cSrc;
2115*01826a49SYabin Cui
2116*01826a49SYabin Cui size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2117*01826a49SYabin Cui if (HUF_isError(hSize)) return hSize;
2118*01826a49SYabin Cui if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2119*01826a49SYabin Cui ip += hSize;
2120*01826a49SYabin Cui cSrcSize -= hSize;
2121*01826a49SYabin Cui
2122*01826a49SYabin Cui return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2123*01826a49SYabin Cui }
2124*01826a49SYabin Cui
2125*01826a49SYabin Cui
2126*01826a49SYabin Cui /**********************************/
2127*01826a49SYabin Cui /* Generic decompression selector */
2128*01826a49SYabin Cui /**********************************/
2129*01826a49SYabin Cui
2130*01826a49SYabin Cui typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2131*01826a49SYabin Cui static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2132*01826a49SYabin Cui {
2133*01826a49SYabin Cui /* single, double, quad */
2134*01826a49SYabin Cui {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2135*01826a49SYabin Cui {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2136*01826a49SYabin Cui {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2137*01826a49SYabin Cui {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2138*01826a49SYabin Cui {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2139*01826a49SYabin Cui {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2140*01826a49SYabin Cui {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2141*01826a49SYabin Cui {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2142*01826a49SYabin Cui {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2143*01826a49SYabin Cui {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2144*01826a49SYabin Cui {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2145*01826a49SYabin Cui {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2146*01826a49SYabin Cui {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2147*01826a49SYabin Cui {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2148*01826a49SYabin Cui {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2149*01826a49SYabin Cui {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2150*01826a49SYabin Cui };
2151*01826a49SYabin Cui
2152*01826a49SYabin Cui typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2153*01826a49SYabin Cui
HUF_decompress(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2154*01826a49SYabin Cui static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2155*01826a49SYabin Cui {
2156*01826a49SYabin Cui static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2157*01826a49SYabin Cui /* estimate decompression time */
2158*01826a49SYabin Cui U32 Q;
2159*01826a49SYabin Cui const U32 D256 = (U32)(dstSize >> 8);
2160*01826a49SYabin Cui U32 Dtime[3];
2161*01826a49SYabin Cui U32 algoNb = 0;
2162*01826a49SYabin Cui int n;
2163*01826a49SYabin Cui
2164*01826a49SYabin Cui /* validation checks */
2165*01826a49SYabin Cui if (dstSize == 0) return ERROR(dstSize_tooSmall);
2166*01826a49SYabin Cui if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2167*01826a49SYabin Cui if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2168*01826a49SYabin Cui if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2169*01826a49SYabin Cui
2170*01826a49SYabin Cui /* decoder timing evaluation */
2171*01826a49SYabin Cui Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2172*01826a49SYabin Cui for (n=0; n<3; n++)
2173*01826a49SYabin Cui Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2174*01826a49SYabin Cui
2175*01826a49SYabin Cui Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2176*01826a49SYabin Cui
2177*01826a49SYabin Cui if (Dtime[1] < Dtime[0]) algoNb = 1;
2178*01826a49SYabin Cui
2179*01826a49SYabin Cui return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2180*01826a49SYabin Cui
2181*01826a49SYabin Cui //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2182*01826a49SYabin Cui //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2183*01826a49SYabin Cui //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2184*01826a49SYabin Cui }
2185*01826a49SYabin Cui /*
2186*01826a49SYabin Cui zstd - standard compression library
2187*01826a49SYabin Cui Copyright (C) 2014-2015, Yann Collet.
2188*01826a49SYabin Cui
2189*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2190*01826a49SYabin Cui
2191*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
2192*01826a49SYabin Cui modification, are permitted provided that the following conditions are
2193*01826a49SYabin Cui met:
2194*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
2195*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
2196*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
2197*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
2198*01826a49SYabin Cui in the documentation and/or other materials provided with the
2199*01826a49SYabin Cui distribution.
2200*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2201*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2202*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2203*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2204*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2205*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2206*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2207*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2208*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2209*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2210*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2211*01826a49SYabin Cui
2212*01826a49SYabin Cui You can contact the author at :
2213*01826a49SYabin Cui - zstd source repository : https://github.com/Cyan4973/zstd
2214*01826a49SYabin Cui - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2215*01826a49SYabin Cui */
2216*01826a49SYabin Cui
2217*01826a49SYabin Cui /* ***************************************************************
2218*01826a49SYabin Cui * Tuning parameters
2219*01826a49SYabin Cui *****************************************************************/
2220*01826a49SYabin Cui /*!
2221*01826a49SYabin Cui * MEMORY_USAGE :
2222*01826a49SYabin Cui * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2223*01826a49SYabin Cui * Increasing memory usage improves compression ratio
2224*01826a49SYabin Cui * Reduced memory usage can improve speed, due to cache effect
2225*01826a49SYabin Cui */
2226*01826a49SYabin Cui #define ZSTD_MEMORY_USAGE 17
2227*01826a49SYabin Cui
2228*01826a49SYabin Cui /*!
2229*01826a49SYabin Cui * HEAPMODE :
2230*01826a49SYabin Cui * Select how default compression functions will allocate memory for their hash table,
2231*01826a49SYabin Cui * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2232*01826a49SYabin Cui * Note that compression context is fairly large, as a consequence heap memory is recommended.
2233*01826a49SYabin Cui */
2234*01826a49SYabin Cui #ifndef ZSTD_HEAPMODE
2235*01826a49SYabin Cui # define ZSTD_HEAPMODE 1
2236*01826a49SYabin Cui #endif /* ZSTD_HEAPMODE */
2237*01826a49SYabin Cui
2238*01826a49SYabin Cui /*!
2239*01826a49SYabin Cui * LEGACY_SUPPORT :
2240*01826a49SYabin Cui * decompressor can decode older formats (starting from Zstd 0.1+)
2241*01826a49SYabin Cui */
2242*01826a49SYabin Cui #ifndef ZSTD_LEGACY_SUPPORT
2243*01826a49SYabin Cui # define ZSTD_LEGACY_SUPPORT 1
2244*01826a49SYabin Cui #endif
2245*01826a49SYabin Cui
2246*01826a49SYabin Cui
2247*01826a49SYabin Cui /* *******************************************************
2248*01826a49SYabin Cui * Includes
2249*01826a49SYabin Cui *********************************************************/
2250*01826a49SYabin Cui #include <stdlib.h> /* calloc */
2251*01826a49SYabin Cui #include <string.h> /* memcpy, memmove */
2252*01826a49SYabin Cui #include <stdio.h> /* debug : printf */
2253*01826a49SYabin Cui
2254*01826a49SYabin Cui
2255*01826a49SYabin Cui /* *******************************************************
2256*01826a49SYabin Cui * Compiler specifics
2257*01826a49SYabin Cui *********************************************************/
2258*01826a49SYabin Cui #ifdef __AVX2__
2259*01826a49SYabin Cui # include <immintrin.h> /* AVX2 intrinsics */
2260*01826a49SYabin Cui #endif
2261*01826a49SYabin Cui
2262*01826a49SYabin Cui #ifdef _MSC_VER /* Visual Studio */
2263*01826a49SYabin Cui # include <intrin.h> /* For Visual 2005 */
2264*01826a49SYabin Cui # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2265*01826a49SYabin Cui # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2266*01826a49SYabin Cui #else
2267*01826a49SYabin Cui # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
2268*01826a49SYabin Cui #endif
2269*01826a49SYabin Cui
2270*01826a49SYabin Cui
2271*01826a49SYabin Cui /* *******************************************************
2272*01826a49SYabin Cui * Constants
2273*01826a49SYabin Cui *********************************************************/
2274*01826a49SYabin Cui #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2275*01826a49SYabin Cui #define HASH_TABLESIZE (1 << HASH_LOG)
2276*01826a49SYabin Cui #define HASH_MASK (HASH_TABLESIZE - 1)
2277*01826a49SYabin Cui
2278*01826a49SYabin Cui #define KNUTH 2654435761
2279*01826a49SYabin Cui
2280*01826a49SYabin Cui #define BIT7 128
2281*01826a49SYabin Cui #define BIT6 64
2282*01826a49SYabin Cui #define BIT5 32
2283*01826a49SYabin Cui #define BIT4 16
2284*01826a49SYabin Cui #define BIT1 2
2285*01826a49SYabin Cui #define BIT0 1
2286*01826a49SYabin Cui
2287*01826a49SYabin Cui #define KB *(1 <<10)
2288*01826a49SYabin Cui #define MB *(1 <<20)
2289*01826a49SYabin Cui #define GB *(1U<<30)
2290*01826a49SYabin Cui
2291*01826a49SYabin Cui #define BLOCKSIZE (128 KB) /* define, for static allocation */
2292*01826a49SYabin Cui #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2293*01826a49SYabin Cui #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2294*01826a49SYabin Cui #define IS_RAW BIT0
2295*01826a49SYabin Cui #define IS_RLE BIT1
2296*01826a49SYabin Cui
2297*01826a49SYabin Cui #define WORKPLACESIZE (BLOCKSIZE*3)
2298*01826a49SYabin Cui #define MINMATCH 4
2299*01826a49SYabin Cui #define MLbits 7
2300*01826a49SYabin Cui #define LLbits 6
2301*01826a49SYabin Cui #define Offbits 5
2302*01826a49SYabin Cui #define MaxML ((1<<MLbits )-1)
2303*01826a49SYabin Cui #define MaxLL ((1<<LLbits )-1)
2304*01826a49SYabin Cui #define MaxOff 31
2305*01826a49SYabin Cui #define LitFSELog 11
2306*01826a49SYabin Cui #define MLFSELog 10
2307*01826a49SYabin Cui #define LLFSELog 10
2308*01826a49SYabin Cui #define OffFSELog 9
2309*01826a49SYabin Cui #define MAX(a,b) ((a)<(b)?(b):(a))
2310*01826a49SYabin Cui #define MaxSeq MAX(MaxLL, MaxML)
2311*01826a49SYabin Cui
2312*01826a49SYabin Cui #define LITERAL_NOENTROPY 63
2313*01826a49SYabin Cui #define COMMAND_NOENTROPY 7 /* to remove */
2314*01826a49SYabin Cui
2315*01826a49SYabin Cui #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2316*01826a49SYabin Cui
2317*01826a49SYabin Cui static const size_t ZSTD_blockHeaderSize = 3;
2318*01826a49SYabin Cui static const size_t ZSTD_frameHeaderSize = 4;
2319*01826a49SYabin Cui
2320*01826a49SYabin Cui
2321*01826a49SYabin Cui /* *******************************************************
2322*01826a49SYabin Cui * Memory operations
2323*01826a49SYabin Cui **********************************************************/
ZSTD_copy4(void * dst,const void * src)2324*01826a49SYabin Cui static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2325*01826a49SYabin Cui
ZSTD_copy8(void * dst,const void * src)2326*01826a49SYabin Cui static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2327*01826a49SYabin Cui
2328*01826a49SYabin Cui #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2329*01826a49SYabin Cui
2330*01826a49SYabin Cui /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
ZSTD_wildcopy(void * dst,const void * src,ptrdiff_t length)2331*01826a49SYabin Cui static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2332*01826a49SYabin Cui {
2333*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
2334*01826a49SYabin Cui BYTE* op = (BYTE*)dst;
2335*01826a49SYabin Cui BYTE* const oend = op + length;
2336*01826a49SYabin Cui do COPY8(op, ip) while (op < oend);
2337*01826a49SYabin Cui }
2338*01826a49SYabin Cui
2339*01826a49SYabin Cui
2340*01826a49SYabin Cui /* **************************************
2341*01826a49SYabin Cui * Local structures
2342*01826a49SYabin Cui ****************************************/
2343*01826a49SYabin Cui typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2344*01826a49SYabin Cui
2345*01826a49SYabin Cui typedef struct
2346*01826a49SYabin Cui {
2347*01826a49SYabin Cui blockType_t blockType;
2348*01826a49SYabin Cui U32 origSize;
2349*01826a49SYabin Cui } blockProperties_t;
2350*01826a49SYabin Cui
2351*01826a49SYabin Cui typedef struct {
2352*01826a49SYabin Cui void* buffer;
2353*01826a49SYabin Cui U32* offsetStart;
2354*01826a49SYabin Cui U32* offset;
2355*01826a49SYabin Cui BYTE* offCodeStart;
2356*01826a49SYabin Cui BYTE* offCode;
2357*01826a49SYabin Cui BYTE* litStart;
2358*01826a49SYabin Cui BYTE* lit;
2359*01826a49SYabin Cui BYTE* litLengthStart;
2360*01826a49SYabin Cui BYTE* litLength;
2361*01826a49SYabin Cui BYTE* matchLengthStart;
2362*01826a49SYabin Cui BYTE* matchLength;
2363*01826a49SYabin Cui BYTE* dumpsStart;
2364*01826a49SYabin Cui BYTE* dumps;
2365*01826a49SYabin Cui } seqStore_t;
2366*01826a49SYabin Cui
2367*01826a49SYabin Cui
2368*01826a49SYabin Cui /* *************************************
2369*01826a49SYabin Cui * Error Management
2370*01826a49SYabin Cui ***************************************/
2371*01826a49SYabin Cui /*! ZSTD_isError
2372*01826a49SYabin Cui * tells if a return value is an error code */
ZSTD_isError(size_t code)2373*01826a49SYabin Cui static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2374*01826a49SYabin Cui
2375*01826a49SYabin Cui
2376*01826a49SYabin Cui
2377*01826a49SYabin Cui /* *************************************************************
2378*01826a49SYabin Cui * Decompression section
2379*01826a49SYabin Cui ***************************************************************/
2380*01826a49SYabin Cui struct ZSTDv03_Dctx_s
2381*01826a49SYabin Cui {
2382*01826a49SYabin Cui U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2383*01826a49SYabin Cui U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2384*01826a49SYabin Cui U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2385*01826a49SYabin Cui void* previousDstEnd;
2386*01826a49SYabin Cui void* base;
2387*01826a49SYabin Cui size_t expected;
2388*01826a49SYabin Cui blockType_t bType;
2389*01826a49SYabin Cui U32 phase;
2390*01826a49SYabin Cui const BYTE* litPtr;
2391*01826a49SYabin Cui size_t litSize;
2392*01826a49SYabin Cui BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2393*01826a49SYabin Cui }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2394*01826a49SYabin Cui
2395*01826a49SYabin Cui
ZSTD_getcBlockSize(const void * src,size_t srcSize,blockProperties_t * bpPtr)2396*01826a49SYabin Cui static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2397*01826a49SYabin Cui {
2398*01826a49SYabin Cui const BYTE* const in = (const BYTE* const)src;
2399*01826a49SYabin Cui BYTE headerFlags;
2400*01826a49SYabin Cui U32 cSize;
2401*01826a49SYabin Cui
2402*01826a49SYabin Cui if (srcSize < 3) return ERROR(srcSize_wrong);
2403*01826a49SYabin Cui
2404*01826a49SYabin Cui headerFlags = *in;
2405*01826a49SYabin Cui cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2406*01826a49SYabin Cui
2407*01826a49SYabin Cui bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2408*01826a49SYabin Cui bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2409*01826a49SYabin Cui
2410*01826a49SYabin Cui if (bpPtr->blockType == bt_end) return 0;
2411*01826a49SYabin Cui if (bpPtr->blockType == bt_rle) return 1;
2412*01826a49SYabin Cui return cSize;
2413*01826a49SYabin Cui }
2414*01826a49SYabin Cui
ZSTD_copyUncompressedBlock(void * dst,size_t maxDstSize,const void * src,size_t srcSize)2415*01826a49SYabin Cui static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2416*01826a49SYabin Cui {
2417*01826a49SYabin Cui if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2418*01826a49SYabin Cui if (srcSize > 0) {
2419*01826a49SYabin Cui memcpy(dst, src, srcSize);
2420*01826a49SYabin Cui }
2421*01826a49SYabin Cui return srcSize;
2422*01826a49SYabin Cui }
2423*01826a49SYabin Cui
2424*01826a49SYabin Cui
2425*01826a49SYabin Cui /** ZSTD_decompressLiterals
2426*01826a49SYabin Cui @return : nb of bytes read from src, or an error code*/
ZSTD_decompressLiterals(void * dst,size_t * maxDstSizePtr,const void * src,size_t srcSize)2427*01826a49SYabin Cui static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2428*01826a49SYabin Cui const void* src, size_t srcSize)
2429*01826a49SYabin Cui {
2430*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
2431*01826a49SYabin Cui
2432*01826a49SYabin Cui const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2433*01826a49SYabin Cui const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2434*01826a49SYabin Cui
2435*01826a49SYabin Cui if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2436*01826a49SYabin Cui if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2437*01826a49SYabin Cui
2438*01826a49SYabin Cui if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2439*01826a49SYabin Cui
2440*01826a49SYabin Cui *maxDstSizePtr = litSize;
2441*01826a49SYabin Cui return litCSize + 5;
2442*01826a49SYabin Cui }
2443*01826a49SYabin Cui
2444*01826a49SYabin Cui
2445*01826a49SYabin Cui /** ZSTD_decodeLiteralsBlock
2446*01826a49SYabin Cui @return : nb of bytes read from src (< srcSize )*/
ZSTD_decodeLiteralsBlock(void * ctx,const void * src,size_t srcSize)2447*01826a49SYabin Cui static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2448*01826a49SYabin Cui const void* src, size_t srcSize)
2449*01826a49SYabin Cui {
2450*01826a49SYabin Cui ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2451*01826a49SYabin Cui const BYTE* const istart = (const BYTE* const)src;
2452*01826a49SYabin Cui
2453*01826a49SYabin Cui /* any compressed block with literals segment must be at least this size */
2454*01826a49SYabin Cui if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2455*01826a49SYabin Cui
2456*01826a49SYabin Cui switch(*istart & 3)
2457*01826a49SYabin Cui {
2458*01826a49SYabin Cui default:
2459*01826a49SYabin Cui case 0:
2460*01826a49SYabin Cui {
2461*01826a49SYabin Cui size_t litSize = BLOCKSIZE;
2462*01826a49SYabin Cui const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2463*01826a49SYabin Cui dctx->litPtr = dctx->litBuffer;
2464*01826a49SYabin Cui dctx->litSize = litSize;
2465*01826a49SYabin Cui memset(dctx->litBuffer + dctx->litSize, 0, 8);
2466*01826a49SYabin Cui return readSize; /* works if it's an error too */
2467*01826a49SYabin Cui }
2468*01826a49SYabin Cui case IS_RAW:
2469*01826a49SYabin Cui {
2470*01826a49SYabin Cui const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2471*01826a49SYabin Cui if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2472*01826a49SYabin Cui {
2473*01826a49SYabin Cui if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2474*01826a49SYabin Cui if (litSize > srcSize-3) return ERROR(corruption_detected);
2475*01826a49SYabin Cui memcpy(dctx->litBuffer, istart, litSize);
2476*01826a49SYabin Cui dctx->litPtr = dctx->litBuffer;
2477*01826a49SYabin Cui dctx->litSize = litSize;
2478*01826a49SYabin Cui memset(dctx->litBuffer + dctx->litSize, 0, 8);
2479*01826a49SYabin Cui return litSize+3;
2480*01826a49SYabin Cui }
2481*01826a49SYabin Cui /* direct reference into compressed stream */
2482*01826a49SYabin Cui dctx->litPtr = istart+3;
2483*01826a49SYabin Cui dctx->litSize = litSize;
2484*01826a49SYabin Cui return litSize+3;
2485*01826a49SYabin Cui }
2486*01826a49SYabin Cui case IS_RLE:
2487*01826a49SYabin Cui {
2488*01826a49SYabin Cui const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2489*01826a49SYabin Cui if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2490*01826a49SYabin Cui memset(dctx->litBuffer, istart[3], litSize + 8);
2491*01826a49SYabin Cui dctx->litPtr = dctx->litBuffer;
2492*01826a49SYabin Cui dctx->litSize = litSize;
2493*01826a49SYabin Cui return 4;
2494*01826a49SYabin Cui }
2495*01826a49SYabin Cui }
2496*01826a49SYabin Cui }
2497*01826a49SYabin Cui
2498*01826a49SYabin Cui
ZSTD_decodeSeqHeaders(int * nbSeq,const BYTE ** dumpsPtr,size_t * dumpsLengthPtr,FSE_DTable * DTableLL,FSE_DTable * DTableML,FSE_DTable * DTableOffb,const void * src,size_t srcSize)2499*01826a49SYabin Cui static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2500*01826a49SYabin Cui FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2501*01826a49SYabin Cui const void* src, size_t srcSize)
2502*01826a49SYabin Cui {
2503*01826a49SYabin Cui const BYTE* const istart = (const BYTE* const)src;
2504*01826a49SYabin Cui const BYTE* ip = istart;
2505*01826a49SYabin Cui const BYTE* const iend = istart + srcSize;
2506*01826a49SYabin Cui U32 LLtype, Offtype, MLtype;
2507*01826a49SYabin Cui U32 LLlog, Offlog, MLlog;
2508*01826a49SYabin Cui size_t dumpsLength;
2509*01826a49SYabin Cui
2510*01826a49SYabin Cui /* check */
2511*01826a49SYabin Cui if (srcSize < 5) return ERROR(srcSize_wrong);
2512*01826a49SYabin Cui
2513*01826a49SYabin Cui /* SeqHead */
2514*01826a49SYabin Cui *nbSeq = MEM_readLE16(ip); ip+=2;
2515*01826a49SYabin Cui LLtype = *ip >> 6;
2516*01826a49SYabin Cui Offtype = (*ip >> 4) & 3;
2517*01826a49SYabin Cui MLtype = (*ip >> 2) & 3;
2518*01826a49SYabin Cui if (*ip & 2)
2519*01826a49SYabin Cui {
2520*01826a49SYabin Cui dumpsLength = ip[2];
2521*01826a49SYabin Cui dumpsLength += ip[1] << 8;
2522*01826a49SYabin Cui ip += 3;
2523*01826a49SYabin Cui }
2524*01826a49SYabin Cui else
2525*01826a49SYabin Cui {
2526*01826a49SYabin Cui dumpsLength = ip[1];
2527*01826a49SYabin Cui dumpsLength += (ip[0] & 1) << 8;
2528*01826a49SYabin Cui ip += 2;
2529*01826a49SYabin Cui }
2530*01826a49SYabin Cui *dumpsPtr = ip;
2531*01826a49SYabin Cui ip += dumpsLength;
2532*01826a49SYabin Cui *dumpsLengthPtr = dumpsLength;
2533*01826a49SYabin Cui
2534*01826a49SYabin Cui /* check */
2535*01826a49SYabin Cui if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2536*01826a49SYabin Cui
2537*01826a49SYabin Cui /* sequences */
2538*01826a49SYabin Cui {
2539*01826a49SYabin Cui S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2540*01826a49SYabin Cui size_t headerSize;
2541*01826a49SYabin Cui
2542*01826a49SYabin Cui /* Build DTables */
2543*01826a49SYabin Cui switch(LLtype)
2544*01826a49SYabin Cui {
2545*01826a49SYabin Cui case bt_rle :
2546*01826a49SYabin Cui LLlog = 0;
2547*01826a49SYabin Cui FSE_buildDTable_rle(DTableLL, *ip++); break;
2548*01826a49SYabin Cui case bt_raw :
2549*01826a49SYabin Cui LLlog = LLbits;
2550*01826a49SYabin Cui FSE_buildDTable_raw(DTableLL, LLbits); break;
2551*01826a49SYabin Cui default :
2552*01826a49SYabin Cui { U32 max = MaxLL;
2553*01826a49SYabin Cui headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2554*01826a49SYabin Cui if (FSE_isError(headerSize)) return ERROR(GENERIC);
2555*01826a49SYabin Cui if (LLlog > LLFSELog) return ERROR(corruption_detected);
2556*01826a49SYabin Cui ip += headerSize;
2557*01826a49SYabin Cui FSE_buildDTable(DTableLL, norm, max, LLlog);
2558*01826a49SYabin Cui } }
2559*01826a49SYabin Cui
2560*01826a49SYabin Cui switch(Offtype)
2561*01826a49SYabin Cui {
2562*01826a49SYabin Cui case bt_rle :
2563*01826a49SYabin Cui Offlog = 0;
2564*01826a49SYabin Cui if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2565*01826a49SYabin Cui FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2566*01826a49SYabin Cui break;
2567*01826a49SYabin Cui case bt_raw :
2568*01826a49SYabin Cui Offlog = Offbits;
2569*01826a49SYabin Cui FSE_buildDTable_raw(DTableOffb, Offbits); break;
2570*01826a49SYabin Cui default :
2571*01826a49SYabin Cui { U32 max = MaxOff;
2572*01826a49SYabin Cui headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2573*01826a49SYabin Cui if (FSE_isError(headerSize)) return ERROR(GENERIC);
2574*01826a49SYabin Cui if (Offlog > OffFSELog) return ERROR(corruption_detected);
2575*01826a49SYabin Cui ip += headerSize;
2576*01826a49SYabin Cui FSE_buildDTable(DTableOffb, norm, max, Offlog);
2577*01826a49SYabin Cui } }
2578*01826a49SYabin Cui
2579*01826a49SYabin Cui switch(MLtype)
2580*01826a49SYabin Cui {
2581*01826a49SYabin Cui case bt_rle :
2582*01826a49SYabin Cui MLlog = 0;
2583*01826a49SYabin Cui if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2584*01826a49SYabin Cui FSE_buildDTable_rle(DTableML, *ip++); break;
2585*01826a49SYabin Cui case bt_raw :
2586*01826a49SYabin Cui MLlog = MLbits;
2587*01826a49SYabin Cui FSE_buildDTable_raw(DTableML, MLbits); break;
2588*01826a49SYabin Cui default :
2589*01826a49SYabin Cui { U32 max = MaxML;
2590*01826a49SYabin Cui headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2591*01826a49SYabin Cui if (FSE_isError(headerSize)) return ERROR(GENERIC);
2592*01826a49SYabin Cui if (MLlog > MLFSELog) return ERROR(corruption_detected);
2593*01826a49SYabin Cui ip += headerSize;
2594*01826a49SYabin Cui FSE_buildDTable(DTableML, norm, max, MLlog);
2595*01826a49SYabin Cui } } }
2596*01826a49SYabin Cui
2597*01826a49SYabin Cui return ip-istart;
2598*01826a49SYabin Cui }
2599*01826a49SYabin Cui
2600*01826a49SYabin Cui
2601*01826a49SYabin Cui typedef struct {
2602*01826a49SYabin Cui size_t litLength;
2603*01826a49SYabin Cui size_t offset;
2604*01826a49SYabin Cui size_t matchLength;
2605*01826a49SYabin Cui } seq_t;
2606*01826a49SYabin Cui
2607*01826a49SYabin Cui typedef struct {
2608*01826a49SYabin Cui BIT_DStream_t DStream;
2609*01826a49SYabin Cui FSE_DState_t stateLL;
2610*01826a49SYabin Cui FSE_DState_t stateOffb;
2611*01826a49SYabin Cui FSE_DState_t stateML;
2612*01826a49SYabin Cui size_t prevOffset;
2613*01826a49SYabin Cui const BYTE* dumps;
2614*01826a49SYabin Cui const BYTE* dumpsEnd;
2615*01826a49SYabin Cui } seqState_t;
2616*01826a49SYabin Cui
2617*01826a49SYabin Cui
ZSTD_decodeSequence(seq_t * seq,seqState_t * seqState)2618*01826a49SYabin Cui static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2619*01826a49SYabin Cui {
2620*01826a49SYabin Cui size_t litLength;
2621*01826a49SYabin Cui size_t prevOffset;
2622*01826a49SYabin Cui size_t offset;
2623*01826a49SYabin Cui size_t matchLength;
2624*01826a49SYabin Cui const BYTE* dumps = seqState->dumps;
2625*01826a49SYabin Cui const BYTE* const de = seqState->dumpsEnd;
2626*01826a49SYabin Cui
2627*01826a49SYabin Cui /* Literal length */
2628*01826a49SYabin Cui litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2629*01826a49SYabin Cui prevOffset = litLength ? seq->offset : seqState->prevOffset;
2630*01826a49SYabin Cui seqState->prevOffset = seq->offset;
2631*01826a49SYabin Cui if (litLength == MaxLL)
2632*01826a49SYabin Cui {
2633*01826a49SYabin Cui const U32 add = dumps<de ? *dumps++ : 0;
2634*01826a49SYabin Cui if (add < 255) litLength += add;
2635*01826a49SYabin Cui else if (dumps + 3 <= de)
2636*01826a49SYabin Cui {
2637*01826a49SYabin Cui litLength = MEM_readLE24(dumps);
2638*01826a49SYabin Cui dumps += 3;
2639*01826a49SYabin Cui }
2640*01826a49SYabin Cui if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2641*01826a49SYabin Cui }
2642*01826a49SYabin Cui
2643*01826a49SYabin Cui /* Offset */
2644*01826a49SYabin Cui {
2645*01826a49SYabin Cui static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
2646*01826a49SYabin Cui 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2647*01826a49SYabin Cui 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2648*01826a49SYabin Cui 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2649*01826a49SYabin Cui U32 offsetCode, nbBits;
2650*01826a49SYabin Cui offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
2651*01826a49SYabin Cui if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2652*01826a49SYabin Cui nbBits = offsetCode - 1;
2653*01826a49SYabin Cui if (offsetCode==0) nbBits = 0; /* cmove */
2654*01826a49SYabin Cui offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2655*01826a49SYabin Cui if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2656*01826a49SYabin Cui if (offsetCode==0) offset = prevOffset; /* cmove */
2657*01826a49SYabin Cui }
2658*01826a49SYabin Cui
2659*01826a49SYabin Cui /* MatchLength */
2660*01826a49SYabin Cui matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2661*01826a49SYabin Cui if (matchLength == MaxML)
2662*01826a49SYabin Cui {
2663*01826a49SYabin Cui const U32 add = dumps<de ? *dumps++ : 0;
2664*01826a49SYabin Cui if (add < 255) matchLength += add;
2665*01826a49SYabin Cui else if (dumps + 3 <= de)
2666*01826a49SYabin Cui {
2667*01826a49SYabin Cui matchLength = MEM_readLE24(dumps);
2668*01826a49SYabin Cui dumps += 3;
2669*01826a49SYabin Cui }
2670*01826a49SYabin Cui if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2671*01826a49SYabin Cui }
2672*01826a49SYabin Cui matchLength += MINMATCH;
2673*01826a49SYabin Cui
2674*01826a49SYabin Cui /* save result */
2675*01826a49SYabin Cui seq->litLength = litLength;
2676*01826a49SYabin Cui seq->offset = offset;
2677*01826a49SYabin Cui seq->matchLength = matchLength;
2678*01826a49SYabin Cui seqState->dumps = dumps;
2679*01826a49SYabin Cui }
2680*01826a49SYabin Cui
2681*01826a49SYabin Cui
ZSTD_execSequence(BYTE * op,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,BYTE * const base,BYTE * const oend)2682*01826a49SYabin Cui static size_t ZSTD_execSequence(BYTE* op,
2683*01826a49SYabin Cui seq_t sequence,
2684*01826a49SYabin Cui const BYTE** litPtr, const BYTE* const litLimit,
2685*01826a49SYabin Cui BYTE* const base, BYTE* const oend)
2686*01826a49SYabin Cui {
2687*01826a49SYabin Cui static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
2688*01826a49SYabin Cui static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */
2689*01826a49SYabin Cui const BYTE* const ostart = op;
2690*01826a49SYabin Cui BYTE* const oLitEnd = op + sequence.litLength;
2691*01826a49SYabin Cui BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
2692*01826a49SYabin Cui BYTE* const oend_8 = oend-8;
2693*01826a49SYabin Cui const BYTE* const litEnd = *litPtr + sequence.litLength;
2694*01826a49SYabin Cui
2695*01826a49SYabin Cui /* checks */
2696*01826a49SYabin Cui size_t const seqLength = sequence.litLength + sequence.matchLength;
2697*01826a49SYabin Cui
2698*01826a49SYabin Cui if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
2699*01826a49SYabin Cui if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
2700*01826a49SYabin Cui /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
2701*01826a49SYabin Cui if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
2702*01826a49SYabin Cui if (sequence.offset > (U32)(oLitEnd - base)) return ERROR(corruption_detected);
2703*01826a49SYabin Cui
2704*01826a49SYabin Cui if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
2705*01826a49SYabin Cui if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
2706*01826a49SYabin Cui
2707*01826a49SYabin Cui /* copy Literals */
2708*01826a49SYabin Cui ZSTD_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2709*01826a49SYabin Cui op = oLitEnd;
2710*01826a49SYabin Cui *litPtr = litEnd; /* update for next sequence */
2711*01826a49SYabin Cui
2712*01826a49SYabin Cui /* copy Match */
2713*01826a49SYabin Cui { const BYTE* match = op - sequence.offset;
2714*01826a49SYabin Cui
2715*01826a49SYabin Cui /* check */
2716*01826a49SYabin Cui if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
2717*01826a49SYabin Cui //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
2718*01826a49SYabin Cui if (match < base) return ERROR(corruption_detected);
2719*01826a49SYabin Cui
2720*01826a49SYabin Cui /* close range match, overlap */
2721*01826a49SYabin Cui if (sequence.offset < 8)
2722*01826a49SYabin Cui {
2723*01826a49SYabin Cui const int dec64 = dec64table[sequence.offset];
2724*01826a49SYabin Cui op[0] = match[0];
2725*01826a49SYabin Cui op[1] = match[1];
2726*01826a49SYabin Cui op[2] = match[2];
2727*01826a49SYabin Cui op[3] = match[3];
2728*01826a49SYabin Cui match += dec32table[sequence.offset];
2729*01826a49SYabin Cui ZSTD_copy4(op+4, match);
2730*01826a49SYabin Cui match -= dec64;
2731*01826a49SYabin Cui }
2732*01826a49SYabin Cui else
2733*01826a49SYabin Cui {
2734*01826a49SYabin Cui ZSTD_copy8(op, match);
2735*01826a49SYabin Cui }
2736*01826a49SYabin Cui op += 8; match += 8;
2737*01826a49SYabin Cui
2738*01826a49SYabin Cui if (oMatchEnd > oend-(16-MINMATCH))
2739*01826a49SYabin Cui {
2740*01826a49SYabin Cui if (op < oend_8)
2741*01826a49SYabin Cui {
2742*01826a49SYabin Cui ZSTD_wildcopy(op, match, oend_8 - op);
2743*01826a49SYabin Cui match += oend_8 - op;
2744*01826a49SYabin Cui op = oend_8;
2745*01826a49SYabin Cui }
2746*01826a49SYabin Cui while (op < oMatchEnd) *op++ = *match++;
2747*01826a49SYabin Cui }
2748*01826a49SYabin Cui else
2749*01826a49SYabin Cui {
2750*01826a49SYabin Cui ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
2751*01826a49SYabin Cui }
2752*01826a49SYabin Cui }
2753*01826a49SYabin Cui
2754*01826a49SYabin Cui return oMatchEnd - ostart;
2755*01826a49SYabin Cui }
2756*01826a49SYabin Cui
ZSTD_decompressSequences(void * ctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize)2757*01826a49SYabin Cui static size_t ZSTD_decompressSequences(
2758*01826a49SYabin Cui void* ctx,
2759*01826a49SYabin Cui void* dst, size_t maxDstSize,
2760*01826a49SYabin Cui const void* seqStart, size_t seqSize)
2761*01826a49SYabin Cui {
2762*01826a49SYabin Cui ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2763*01826a49SYabin Cui const BYTE* ip = (const BYTE*)seqStart;
2764*01826a49SYabin Cui const BYTE* const iend = ip + seqSize;
2765*01826a49SYabin Cui BYTE* const ostart = (BYTE* const)dst;
2766*01826a49SYabin Cui BYTE* op = ostart;
2767*01826a49SYabin Cui BYTE* const oend = ostart + maxDstSize;
2768*01826a49SYabin Cui size_t errorCode, dumpsLength;
2769*01826a49SYabin Cui const BYTE* litPtr = dctx->litPtr;
2770*01826a49SYabin Cui const BYTE* const litEnd = litPtr + dctx->litSize;
2771*01826a49SYabin Cui int nbSeq;
2772*01826a49SYabin Cui const BYTE* dumps;
2773*01826a49SYabin Cui U32* DTableLL = dctx->LLTable;
2774*01826a49SYabin Cui U32* DTableML = dctx->MLTable;
2775*01826a49SYabin Cui U32* DTableOffb = dctx->OffTable;
2776*01826a49SYabin Cui BYTE* const base = (BYTE*) (dctx->base);
2777*01826a49SYabin Cui
2778*01826a49SYabin Cui /* Build Decoding Tables */
2779*01826a49SYabin Cui errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2780*01826a49SYabin Cui DTableLL, DTableML, DTableOffb,
2781*01826a49SYabin Cui ip, iend-ip);
2782*01826a49SYabin Cui if (ZSTD_isError(errorCode)) return errorCode;
2783*01826a49SYabin Cui ip += errorCode;
2784*01826a49SYabin Cui
2785*01826a49SYabin Cui /* Regen sequences */
2786*01826a49SYabin Cui {
2787*01826a49SYabin Cui seq_t sequence;
2788*01826a49SYabin Cui seqState_t seqState;
2789*01826a49SYabin Cui
2790*01826a49SYabin Cui memset(&sequence, 0, sizeof(sequence));
2791*01826a49SYabin Cui seqState.dumps = dumps;
2792*01826a49SYabin Cui seqState.dumpsEnd = dumps + dumpsLength;
2793*01826a49SYabin Cui seqState.prevOffset = sequence.offset = 4;
2794*01826a49SYabin Cui errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2795*01826a49SYabin Cui if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2796*01826a49SYabin Cui FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2797*01826a49SYabin Cui FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2798*01826a49SYabin Cui FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2799*01826a49SYabin Cui
2800*01826a49SYabin Cui for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
2801*01826a49SYabin Cui {
2802*01826a49SYabin Cui size_t oneSeqSize;
2803*01826a49SYabin Cui nbSeq--;
2804*01826a49SYabin Cui ZSTD_decodeSequence(&sequence, &seqState);
2805*01826a49SYabin Cui oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
2806*01826a49SYabin Cui if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2807*01826a49SYabin Cui op += oneSeqSize;
2808*01826a49SYabin Cui }
2809*01826a49SYabin Cui
2810*01826a49SYabin Cui /* check if reached exact end */
2811*01826a49SYabin Cui if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
2812*01826a49SYabin Cui if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
2813*01826a49SYabin Cui
2814*01826a49SYabin Cui /* last literal segment */
2815*01826a49SYabin Cui {
2816*01826a49SYabin Cui size_t lastLLSize = litEnd - litPtr;
2817*01826a49SYabin Cui if (litPtr > litEnd) return ERROR(corruption_detected);
2818*01826a49SYabin Cui if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2819*01826a49SYabin Cui if (lastLLSize > 0) {
2820*01826a49SYabin Cui if (op != litPtr) memmove(op, litPtr, lastLLSize);
2821*01826a49SYabin Cui op += lastLLSize;
2822*01826a49SYabin Cui }
2823*01826a49SYabin Cui }
2824*01826a49SYabin Cui }
2825*01826a49SYabin Cui
2826*01826a49SYabin Cui return op-ostart;
2827*01826a49SYabin Cui }
2828*01826a49SYabin Cui
2829*01826a49SYabin Cui
ZSTD_decompressBlock(void * ctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)2830*01826a49SYabin Cui static size_t ZSTD_decompressBlock(
2831*01826a49SYabin Cui void* ctx,
2832*01826a49SYabin Cui void* dst, size_t maxDstSize,
2833*01826a49SYabin Cui const void* src, size_t srcSize)
2834*01826a49SYabin Cui {
2835*01826a49SYabin Cui /* blockType == blockCompressed */
2836*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
2837*01826a49SYabin Cui
2838*01826a49SYabin Cui /* Decode literals sub-block */
2839*01826a49SYabin Cui size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
2840*01826a49SYabin Cui if (ZSTD_isError(litCSize)) return litCSize;
2841*01826a49SYabin Cui ip += litCSize;
2842*01826a49SYabin Cui srcSize -= litCSize;
2843*01826a49SYabin Cui
2844*01826a49SYabin Cui return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
2845*01826a49SYabin Cui }
2846*01826a49SYabin Cui
2847*01826a49SYabin Cui
ZSTD_decompressDCtx(void * ctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)2848*01826a49SYabin Cui static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2849*01826a49SYabin Cui {
2850*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
2851*01826a49SYabin Cui const BYTE* iend = ip + srcSize;
2852*01826a49SYabin Cui BYTE* const ostart = (BYTE* const)dst;
2853*01826a49SYabin Cui BYTE* op = ostart;
2854*01826a49SYabin Cui BYTE* const oend = ostart + maxDstSize;
2855*01826a49SYabin Cui size_t remainingSize = srcSize;
2856*01826a49SYabin Cui U32 magicNumber;
2857*01826a49SYabin Cui blockProperties_t blockProperties;
2858*01826a49SYabin Cui
2859*01826a49SYabin Cui /* Frame Header */
2860*01826a49SYabin Cui if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2861*01826a49SYabin Cui magicNumber = MEM_readLE32(src);
2862*01826a49SYabin Cui if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2863*01826a49SYabin Cui ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2864*01826a49SYabin Cui
2865*01826a49SYabin Cui /* Loop on each block */
2866*01826a49SYabin Cui while (1)
2867*01826a49SYabin Cui {
2868*01826a49SYabin Cui size_t decodedSize=0;
2869*01826a49SYabin Cui size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
2870*01826a49SYabin Cui if (ZSTD_isError(cBlockSize)) return cBlockSize;
2871*01826a49SYabin Cui
2872*01826a49SYabin Cui ip += ZSTD_blockHeaderSize;
2873*01826a49SYabin Cui remainingSize -= ZSTD_blockHeaderSize;
2874*01826a49SYabin Cui if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2875*01826a49SYabin Cui
2876*01826a49SYabin Cui switch(blockProperties.blockType)
2877*01826a49SYabin Cui {
2878*01826a49SYabin Cui case bt_compressed:
2879*01826a49SYabin Cui decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
2880*01826a49SYabin Cui break;
2881*01826a49SYabin Cui case bt_raw :
2882*01826a49SYabin Cui decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
2883*01826a49SYabin Cui break;
2884*01826a49SYabin Cui case bt_rle :
2885*01826a49SYabin Cui return ERROR(GENERIC); /* not yet supported */
2886*01826a49SYabin Cui break;
2887*01826a49SYabin Cui case bt_end :
2888*01826a49SYabin Cui /* end of frame */
2889*01826a49SYabin Cui if (remainingSize) return ERROR(srcSize_wrong);
2890*01826a49SYabin Cui break;
2891*01826a49SYabin Cui default:
2892*01826a49SYabin Cui return ERROR(GENERIC); /* impossible */
2893*01826a49SYabin Cui }
2894*01826a49SYabin Cui if (cBlockSize == 0) break; /* bt_end */
2895*01826a49SYabin Cui
2896*01826a49SYabin Cui if (ZSTD_isError(decodedSize)) return decodedSize;
2897*01826a49SYabin Cui op += decodedSize;
2898*01826a49SYabin Cui ip += cBlockSize;
2899*01826a49SYabin Cui remainingSize -= cBlockSize;
2900*01826a49SYabin Cui }
2901*01826a49SYabin Cui
2902*01826a49SYabin Cui return op-ostart;
2903*01826a49SYabin Cui }
2904*01826a49SYabin Cui
ZSTD_decompress(void * dst,size_t maxDstSize,const void * src,size_t srcSize)2905*01826a49SYabin Cui static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2906*01826a49SYabin Cui {
2907*01826a49SYabin Cui ZSTD_DCtx ctx;
2908*01826a49SYabin Cui ctx.base = dst;
2909*01826a49SYabin Cui return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
2910*01826a49SYabin Cui }
2911*01826a49SYabin Cui
2912*01826a49SYabin Cui /* ZSTD_errorFrameSizeInfoLegacy() :
2913*01826a49SYabin Cui assumes `cSize` and `dBound` are _not_ NULL */
ZSTD_errorFrameSizeInfoLegacy(size_t * cSize,unsigned long long * dBound,size_t ret)2914*01826a49SYabin Cui MEM_STATIC void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
2915*01826a49SYabin Cui {
2916*01826a49SYabin Cui *cSize = ret;
2917*01826a49SYabin Cui *dBound = ZSTD_CONTENTSIZE_ERROR;
2918*01826a49SYabin Cui }
2919*01826a49SYabin Cui
ZSTDv03_findFrameSizeInfoLegacy(const void * src,size_t srcSize,size_t * cSize,unsigned long long * dBound)2920*01826a49SYabin Cui void ZSTDv03_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
2921*01826a49SYabin Cui {
2922*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
2923*01826a49SYabin Cui size_t remainingSize = srcSize;
2924*01826a49SYabin Cui size_t nbBlocks = 0;
2925*01826a49SYabin Cui U32 magicNumber;
2926*01826a49SYabin Cui blockProperties_t blockProperties;
2927*01826a49SYabin Cui
2928*01826a49SYabin Cui /* Frame Header */
2929*01826a49SYabin Cui if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
2930*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2931*01826a49SYabin Cui return;
2932*01826a49SYabin Cui }
2933*01826a49SYabin Cui magicNumber = MEM_readLE32(src);
2934*01826a49SYabin Cui if (magicNumber != ZSTD_magicNumber) {
2935*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
2936*01826a49SYabin Cui return;
2937*01826a49SYabin Cui }
2938*01826a49SYabin Cui ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2939*01826a49SYabin Cui
2940*01826a49SYabin Cui /* Loop on each block */
2941*01826a49SYabin Cui while (1)
2942*01826a49SYabin Cui {
2943*01826a49SYabin Cui size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
2944*01826a49SYabin Cui if (ZSTD_isError(cBlockSize)) {
2945*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
2946*01826a49SYabin Cui return;
2947*01826a49SYabin Cui }
2948*01826a49SYabin Cui
2949*01826a49SYabin Cui ip += ZSTD_blockHeaderSize;
2950*01826a49SYabin Cui remainingSize -= ZSTD_blockHeaderSize;
2951*01826a49SYabin Cui if (cBlockSize > remainingSize) {
2952*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2953*01826a49SYabin Cui return;
2954*01826a49SYabin Cui }
2955*01826a49SYabin Cui
2956*01826a49SYabin Cui if (cBlockSize == 0) break; /* bt_end */
2957*01826a49SYabin Cui
2958*01826a49SYabin Cui ip += cBlockSize;
2959*01826a49SYabin Cui remainingSize -= cBlockSize;
2960*01826a49SYabin Cui nbBlocks++;
2961*01826a49SYabin Cui }
2962*01826a49SYabin Cui
2963*01826a49SYabin Cui *cSize = ip - (const BYTE*)src;
2964*01826a49SYabin Cui *dBound = nbBlocks * BLOCKSIZE;
2965*01826a49SYabin Cui }
2966*01826a49SYabin Cui
2967*01826a49SYabin Cui
2968*01826a49SYabin Cui /*******************************
2969*01826a49SYabin Cui * Streaming Decompression API
2970*01826a49SYabin Cui *******************************/
2971*01826a49SYabin Cui
ZSTD_resetDCtx(ZSTD_DCtx * dctx)2972*01826a49SYabin Cui static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2973*01826a49SYabin Cui {
2974*01826a49SYabin Cui dctx->expected = ZSTD_frameHeaderSize;
2975*01826a49SYabin Cui dctx->phase = 0;
2976*01826a49SYabin Cui dctx->previousDstEnd = NULL;
2977*01826a49SYabin Cui dctx->base = NULL;
2978*01826a49SYabin Cui return 0;
2979*01826a49SYabin Cui }
2980*01826a49SYabin Cui
ZSTD_createDCtx(void)2981*01826a49SYabin Cui static ZSTD_DCtx* ZSTD_createDCtx(void)
2982*01826a49SYabin Cui {
2983*01826a49SYabin Cui ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2984*01826a49SYabin Cui if (dctx==NULL) return NULL;
2985*01826a49SYabin Cui ZSTD_resetDCtx(dctx);
2986*01826a49SYabin Cui return dctx;
2987*01826a49SYabin Cui }
2988*01826a49SYabin Cui
ZSTD_freeDCtx(ZSTD_DCtx * dctx)2989*01826a49SYabin Cui static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
2990*01826a49SYabin Cui {
2991*01826a49SYabin Cui free(dctx);
2992*01826a49SYabin Cui return 0;
2993*01826a49SYabin Cui }
2994*01826a49SYabin Cui
ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx * dctx)2995*01826a49SYabin Cui static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
2996*01826a49SYabin Cui {
2997*01826a49SYabin Cui return dctx->expected;
2998*01826a49SYabin Cui }
2999*01826a49SYabin Cui
ZSTD_decompressContinue(ZSTD_DCtx * ctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)3000*01826a49SYabin Cui static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3001*01826a49SYabin Cui {
3002*01826a49SYabin Cui /* Sanity check */
3003*01826a49SYabin Cui if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3004*01826a49SYabin Cui if (dst != ctx->previousDstEnd) /* not contiguous */
3005*01826a49SYabin Cui ctx->base = dst;
3006*01826a49SYabin Cui
3007*01826a49SYabin Cui /* Decompress : frame header */
3008*01826a49SYabin Cui if (ctx->phase == 0)
3009*01826a49SYabin Cui {
3010*01826a49SYabin Cui /* Check frame magic header */
3011*01826a49SYabin Cui U32 magicNumber = MEM_readLE32(src);
3012*01826a49SYabin Cui if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3013*01826a49SYabin Cui ctx->phase = 1;
3014*01826a49SYabin Cui ctx->expected = ZSTD_blockHeaderSize;
3015*01826a49SYabin Cui return 0;
3016*01826a49SYabin Cui }
3017*01826a49SYabin Cui
3018*01826a49SYabin Cui /* Decompress : block header */
3019*01826a49SYabin Cui if (ctx->phase == 1)
3020*01826a49SYabin Cui {
3021*01826a49SYabin Cui blockProperties_t bp;
3022*01826a49SYabin Cui size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3023*01826a49SYabin Cui if (ZSTD_isError(blockSize)) return blockSize;
3024*01826a49SYabin Cui if (bp.blockType == bt_end)
3025*01826a49SYabin Cui {
3026*01826a49SYabin Cui ctx->expected = 0;
3027*01826a49SYabin Cui ctx->phase = 0;
3028*01826a49SYabin Cui }
3029*01826a49SYabin Cui else
3030*01826a49SYabin Cui {
3031*01826a49SYabin Cui ctx->expected = blockSize;
3032*01826a49SYabin Cui ctx->bType = bp.blockType;
3033*01826a49SYabin Cui ctx->phase = 2;
3034*01826a49SYabin Cui }
3035*01826a49SYabin Cui
3036*01826a49SYabin Cui return 0;
3037*01826a49SYabin Cui }
3038*01826a49SYabin Cui
3039*01826a49SYabin Cui /* Decompress : block content */
3040*01826a49SYabin Cui {
3041*01826a49SYabin Cui size_t rSize;
3042*01826a49SYabin Cui switch(ctx->bType)
3043*01826a49SYabin Cui {
3044*01826a49SYabin Cui case bt_compressed:
3045*01826a49SYabin Cui rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3046*01826a49SYabin Cui break;
3047*01826a49SYabin Cui case bt_raw :
3048*01826a49SYabin Cui rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3049*01826a49SYabin Cui break;
3050*01826a49SYabin Cui case bt_rle :
3051*01826a49SYabin Cui return ERROR(GENERIC); /* not yet handled */
3052*01826a49SYabin Cui break;
3053*01826a49SYabin Cui case bt_end : /* should never happen (filtered at phase 1) */
3054*01826a49SYabin Cui rSize = 0;
3055*01826a49SYabin Cui break;
3056*01826a49SYabin Cui default:
3057*01826a49SYabin Cui return ERROR(GENERIC);
3058*01826a49SYabin Cui }
3059*01826a49SYabin Cui ctx->phase = 1;
3060*01826a49SYabin Cui ctx->expected = ZSTD_blockHeaderSize;
3061*01826a49SYabin Cui if (ZSTD_isError(rSize)) return rSize;
3062*01826a49SYabin Cui ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3063*01826a49SYabin Cui return rSize;
3064*01826a49SYabin Cui }
3065*01826a49SYabin Cui
3066*01826a49SYabin Cui }
3067*01826a49SYabin Cui
3068*01826a49SYabin Cui
3069*01826a49SYabin Cui /* wrapper layer */
3070*01826a49SYabin Cui
ZSTDv03_isError(size_t code)3071*01826a49SYabin Cui unsigned ZSTDv03_isError(size_t code)
3072*01826a49SYabin Cui {
3073*01826a49SYabin Cui return ZSTD_isError(code);
3074*01826a49SYabin Cui }
3075*01826a49SYabin Cui
ZSTDv03_decompress(void * dst,size_t maxOriginalSize,const void * src,size_t compressedSize)3076*01826a49SYabin Cui size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3077*01826a49SYabin Cui const void* src, size_t compressedSize)
3078*01826a49SYabin Cui {
3079*01826a49SYabin Cui return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3080*01826a49SYabin Cui }
3081*01826a49SYabin Cui
ZSTDv03_createDCtx(void)3082*01826a49SYabin Cui ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3083*01826a49SYabin Cui {
3084*01826a49SYabin Cui return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3085*01826a49SYabin Cui }
3086*01826a49SYabin Cui
ZSTDv03_freeDCtx(ZSTDv03_Dctx * dctx)3087*01826a49SYabin Cui size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3088*01826a49SYabin Cui {
3089*01826a49SYabin Cui return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3090*01826a49SYabin Cui }
3091*01826a49SYabin Cui
ZSTDv03_resetDCtx(ZSTDv03_Dctx * dctx)3092*01826a49SYabin Cui size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3093*01826a49SYabin Cui {
3094*01826a49SYabin Cui return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3095*01826a49SYabin Cui }
3096*01826a49SYabin Cui
ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx * dctx)3097*01826a49SYabin Cui size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3098*01826a49SYabin Cui {
3099*01826a49SYabin Cui return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3100*01826a49SYabin Cui }
3101*01826a49SYabin Cui
ZSTDv03_decompressContinue(ZSTDv03_Dctx * dctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)3102*01826a49SYabin Cui size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3103*01826a49SYabin Cui {
3104*01826a49SYabin Cui return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);
3105*01826a49SYabin Cui }
3106