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 /******************************************
13*01826a49SYabin Cui * Includes
14*01826a49SYabin Cui ******************************************/
15*01826a49SYabin Cui #include <stddef.h> /* size_t, ptrdiff_t */
16*01826a49SYabin Cui #include "zstd_v01.h"
17*01826a49SYabin Cui #include "../common/compiler.h"
18*01826a49SYabin Cui #include "../common/error_private.h"
19*01826a49SYabin Cui
20*01826a49SYabin Cui
21*01826a49SYabin Cui /******************************************
22*01826a49SYabin Cui * Static allocation
23*01826a49SYabin Cui ******************************************/
24*01826a49SYabin Cui /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
25*01826a49SYabin Cui #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
26*01826a49SYabin Cui
27*01826a49SYabin Cui /* You can statically allocate Huff0 DTable as a table of unsigned short using below macro */
28*01826a49SYabin Cui #define HUF_DTABLE_SIZE_U16(maxTableLog) (1 + (1<<maxTableLog))
29*01826a49SYabin Cui #define HUF_CREATE_STATIC_DTABLE(DTable, maxTableLog) \
30*01826a49SYabin Cui unsigned short DTable[HUF_DTABLE_SIZE_U16(maxTableLog)] = { maxTableLog }
31*01826a49SYabin Cui
32*01826a49SYabin Cui
33*01826a49SYabin Cui /******************************************
34*01826a49SYabin Cui * Error Management
35*01826a49SYabin Cui ******************************************/
36*01826a49SYabin Cui #define FSE_LIST_ERRORS(ITEM) \
37*01826a49SYabin Cui ITEM(FSE_OK_NoError) ITEM(FSE_ERROR_GENERIC) \
38*01826a49SYabin Cui ITEM(FSE_ERROR_tableLog_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooSmall) \
39*01826a49SYabin Cui ITEM(FSE_ERROR_dstSize_tooSmall) ITEM(FSE_ERROR_srcSize_wrong)\
40*01826a49SYabin Cui ITEM(FSE_ERROR_corruptionDetected) \
41*01826a49SYabin Cui ITEM(FSE_ERROR_maxCode)
42*01826a49SYabin Cui
43*01826a49SYabin Cui #define FSE_GENERATE_ENUM(ENUM) ENUM,
44*01826a49SYabin Cui typedef enum { FSE_LIST_ERRORS(FSE_GENERATE_ENUM) } FSE_errorCodes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
45*01826a49SYabin Cui
46*01826a49SYabin Cui
47*01826a49SYabin Cui /******************************************
48*01826a49SYabin Cui * FSE symbol compression API
49*01826a49SYabin Cui ******************************************/
50*01826a49SYabin Cui /*
51*01826a49SYabin Cui This API consists of small unitary functions, which highly benefit from being inlined.
52*01826a49SYabin Cui You will want to enable link-time-optimization to ensure these functions are properly inlined in your binary.
53*01826a49SYabin Cui Visual seems to do it automatically.
54*01826a49SYabin Cui For gcc or clang, you'll need to add -flto flag at compilation and linking stages.
55*01826a49SYabin Cui If none of these solutions is applicable, include "fse.c" directly.
56*01826a49SYabin Cui */
57*01826a49SYabin Cui
58*01826a49SYabin Cui typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
59*01826a49SYabin Cui typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
60*01826a49SYabin Cui
61*01826a49SYabin Cui typedef struct
62*01826a49SYabin Cui {
63*01826a49SYabin Cui size_t bitContainer;
64*01826a49SYabin Cui int bitPos;
65*01826a49SYabin Cui char* startPtr;
66*01826a49SYabin Cui char* ptr;
67*01826a49SYabin Cui char* endPtr;
68*01826a49SYabin Cui } FSE_CStream_t;
69*01826a49SYabin Cui
70*01826a49SYabin Cui typedef struct
71*01826a49SYabin Cui {
72*01826a49SYabin Cui ptrdiff_t value;
73*01826a49SYabin Cui const void* stateTable;
74*01826a49SYabin Cui const void* symbolTT;
75*01826a49SYabin Cui unsigned stateLog;
76*01826a49SYabin Cui } FSE_CState_t;
77*01826a49SYabin Cui
78*01826a49SYabin Cui typedef struct
79*01826a49SYabin Cui {
80*01826a49SYabin Cui size_t bitContainer;
81*01826a49SYabin Cui unsigned bitsConsumed;
82*01826a49SYabin Cui const char* ptr;
83*01826a49SYabin Cui const char* start;
84*01826a49SYabin Cui } FSE_DStream_t;
85*01826a49SYabin Cui
86*01826a49SYabin Cui typedef struct
87*01826a49SYabin Cui {
88*01826a49SYabin Cui size_t state;
89*01826a49SYabin Cui const void* table; /* precise table may vary, depending on U16 */
90*01826a49SYabin Cui } FSE_DState_t;
91*01826a49SYabin Cui
92*01826a49SYabin Cui typedef enum { FSE_DStream_unfinished = 0,
93*01826a49SYabin Cui FSE_DStream_endOfBuffer = 1,
94*01826a49SYabin Cui FSE_DStream_completed = 2,
95*01826a49SYabin Cui FSE_DStream_tooFar = 3 } FSE_DStream_status; /* result of FSE_reloadDStream() */
96*01826a49SYabin Cui /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... ?! */
97*01826a49SYabin Cui
98*01826a49SYabin Cui
99*01826a49SYabin Cui /****************************************************************
100*01826a49SYabin Cui * Tuning parameters
101*01826a49SYabin Cui ****************************************************************/
102*01826a49SYabin Cui /* MEMORY_USAGE :
103*01826a49SYabin Cui * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
104*01826a49SYabin Cui * Increasing memory usage improves compression ratio
105*01826a49SYabin Cui * Reduced memory usage can improve speed, due to cache effect
106*01826a49SYabin Cui * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
107*01826a49SYabin Cui #define FSE_MAX_MEMORY_USAGE 14
108*01826a49SYabin Cui #define FSE_DEFAULT_MEMORY_USAGE 13
109*01826a49SYabin Cui
110*01826a49SYabin Cui /* FSE_MAX_SYMBOL_VALUE :
111*01826a49SYabin Cui * Maximum symbol value authorized.
112*01826a49SYabin Cui * Required for proper stack allocation */
113*01826a49SYabin Cui #define FSE_MAX_SYMBOL_VALUE 255
114*01826a49SYabin Cui
115*01826a49SYabin Cui
116*01826a49SYabin Cui /****************************************************************
117*01826a49SYabin Cui * template functions type & suffix
118*01826a49SYabin Cui ****************************************************************/
119*01826a49SYabin Cui #define FSE_FUNCTION_TYPE BYTE
120*01826a49SYabin Cui #define FSE_FUNCTION_EXTENSION
121*01826a49SYabin Cui
122*01826a49SYabin Cui
123*01826a49SYabin Cui /****************************************************************
124*01826a49SYabin Cui * Byte symbol type
125*01826a49SYabin Cui ****************************************************************/
126*01826a49SYabin Cui typedef struct
127*01826a49SYabin Cui {
128*01826a49SYabin Cui unsigned short newState;
129*01826a49SYabin Cui unsigned char symbol;
130*01826a49SYabin Cui unsigned char nbBits;
131*01826a49SYabin Cui } FSE_decode_t; /* size == U32 */
132*01826a49SYabin Cui
133*01826a49SYabin Cui
134*01826a49SYabin Cui
135*01826a49SYabin Cui /****************************************************************
136*01826a49SYabin Cui * Compiler specifics
137*01826a49SYabin Cui ****************************************************************/
138*01826a49SYabin Cui #ifdef _MSC_VER /* Visual Studio */
139*01826a49SYabin Cui # define FORCE_INLINE static __forceinline
140*01826a49SYabin Cui # include <intrin.h> /* For Visual 2005 */
141*01826a49SYabin Cui # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
142*01826a49SYabin Cui # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
143*01826a49SYabin Cui #else
144*01826a49SYabin Cui # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
145*01826a49SYabin Cui # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
146*01826a49SYabin Cui # ifdef __GNUC__
147*01826a49SYabin Cui # define FORCE_INLINE static inline __attribute__((always_inline))
148*01826a49SYabin Cui # else
149*01826a49SYabin Cui # define FORCE_INLINE static inline
150*01826a49SYabin Cui # endif
151*01826a49SYabin Cui # else
152*01826a49SYabin Cui # define FORCE_INLINE static
153*01826a49SYabin Cui # endif /* __STDC_VERSION__ */
154*01826a49SYabin Cui #endif
155*01826a49SYabin Cui
156*01826a49SYabin Cui
157*01826a49SYabin Cui /****************************************************************
158*01826a49SYabin Cui * Includes
159*01826a49SYabin Cui ****************************************************************/
160*01826a49SYabin Cui #include <stdlib.h> /* malloc, free, qsort */
161*01826a49SYabin Cui #include <string.h> /* memcpy, memset */
162*01826a49SYabin Cui #include <stdio.h> /* printf (debug) */
163*01826a49SYabin Cui
164*01826a49SYabin Cui
165*01826a49SYabin Cui #ifndef MEM_ACCESS_MODULE
166*01826a49SYabin Cui #define MEM_ACCESS_MODULE
167*01826a49SYabin Cui /****************************************************************
168*01826a49SYabin Cui * Basic Types
169*01826a49SYabin Cui *****************************************************************/
170*01826a49SYabin Cui #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
171*01826a49SYabin Cui # include <stdint.h>
172*01826a49SYabin Cui typedef uint8_t BYTE;
173*01826a49SYabin Cui typedef uint16_t U16;
174*01826a49SYabin Cui typedef int16_t S16;
175*01826a49SYabin Cui typedef uint32_t U32;
176*01826a49SYabin Cui typedef int32_t S32;
177*01826a49SYabin Cui typedef uint64_t U64;
178*01826a49SYabin Cui typedef int64_t S64;
179*01826a49SYabin Cui #else
180*01826a49SYabin Cui typedef unsigned char BYTE;
181*01826a49SYabin Cui typedef unsigned short U16;
182*01826a49SYabin Cui typedef signed short S16;
183*01826a49SYabin Cui typedef unsigned int U32;
184*01826a49SYabin Cui typedef signed int S32;
185*01826a49SYabin Cui typedef unsigned long long U64;
186*01826a49SYabin Cui typedef signed long long S64;
187*01826a49SYabin Cui #endif
188*01826a49SYabin Cui
189*01826a49SYabin Cui #endif /* MEM_ACCESS_MODULE */
190*01826a49SYabin Cui
191*01826a49SYabin Cui /****************************************************************
192*01826a49SYabin Cui * Memory I/O
193*01826a49SYabin Cui *****************************************************************/
194*01826a49SYabin Cui
FSE_32bits(void)195*01826a49SYabin Cui static unsigned FSE_32bits(void)
196*01826a49SYabin Cui {
197*01826a49SYabin Cui return sizeof(void*)==4;
198*01826a49SYabin Cui }
199*01826a49SYabin Cui
FSE_isLittleEndian(void)200*01826a49SYabin Cui static unsigned FSE_isLittleEndian(void)
201*01826a49SYabin Cui {
202*01826a49SYabin Cui const union { U32 i; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
203*01826a49SYabin Cui return one.c[0];
204*01826a49SYabin Cui }
205*01826a49SYabin Cui
FSE_read16(const void * memPtr)206*01826a49SYabin Cui static U16 FSE_read16(const void* memPtr)
207*01826a49SYabin Cui {
208*01826a49SYabin Cui U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
209*01826a49SYabin Cui }
210*01826a49SYabin Cui
FSE_read32(const void * memPtr)211*01826a49SYabin Cui static U32 FSE_read32(const void* memPtr)
212*01826a49SYabin Cui {
213*01826a49SYabin Cui U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
214*01826a49SYabin Cui }
215*01826a49SYabin Cui
FSE_read64(const void * memPtr)216*01826a49SYabin Cui static U64 FSE_read64(const void* memPtr)
217*01826a49SYabin Cui {
218*01826a49SYabin Cui U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
219*01826a49SYabin Cui }
220*01826a49SYabin Cui
FSE_readLE16(const void * memPtr)221*01826a49SYabin Cui static U16 FSE_readLE16(const void* memPtr)
222*01826a49SYabin Cui {
223*01826a49SYabin Cui if (FSE_isLittleEndian())
224*01826a49SYabin Cui return FSE_read16(memPtr);
225*01826a49SYabin Cui else
226*01826a49SYabin Cui {
227*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
228*01826a49SYabin Cui return (U16)(p[0] + (p[1]<<8));
229*01826a49SYabin Cui }
230*01826a49SYabin Cui }
231*01826a49SYabin Cui
FSE_readLE32(const void * memPtr)232*01826a49SYabin Cui static U32 FSE_readLE32(const void* memPtr)
233*01826a49SYabin Cui {
234*01826a49SYabin Cui if (FSE_isLittleEndian())
235*01826a49SYabin Cui return FSE_read32(memPtr);
236*01826a49SYabin Cui else
237*01826a49SYabin Cui {
238*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
239*01826a49SYabin Cui return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
240*01826a49SYabin Cui }
241*01826a49SYabin Cui }
242*01826a49SYabin Cui
243*01826a49SYabin Cui
FSE_readLE64(const void * memPtr)244*01826a49SYabin Cui static U64 FSE_readLE64(const void* memPtr)
245*01826a49SYabin Cui {
246*01826a49SYabin Cui if (FSE_isLittleEndian())
247*01826a49SYabin Cui return FSE_read64(memPtr);
248*01826a49SYabin Cui else
249*01826a49SYabin Cui {
250*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
251*01826a49SYabin Cui return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
252*01826a49SYabin Cui + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
253*01826a49SYabin Cui }
254*01826a49SYabin Cui }
255*01826a49SYabin Cui
FSE_readLEST(const void * memPtr)256*01826a49SYabin Cui static size_t FSE_readLEST(const void* memPtr)
257*01826a49SYabin Cui {
258*01826a49SYabin Cui if (FSE_32bits())
259*01826a49SYabin Cui return (size_t)FSE_readLE32(memPtr);
260*01826a49SYabin Cui else
261*01826a49SYabin Cui return (size_t)FSE_readLE64(memPtr);
262*01826a49SYabin Cui }
263*01826a49SYabin Cui
264*01826a49SYabin Cui
265*01826a49SYabin Cui
266*01826a49SYabin Cui /****************************************************************
267*01826a49SYabin Cui * Constants
268*01826a49SYabin Cui *****************************************************************/
269*01826a49SYabin Cui #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
270*01826a49SYabin Cui #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
271*01826a49SYabin Cui #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
272*01826a49SYabin Cui #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
273*01826a49SYabin Cui #define FSE_MIN_TABLELOG 5
274*01826a49SYabin Cui
275*01826a49SYabin Cui #define FSE_TABLELOG_ABSOLUTE_MAX 15
276*01826a49SYabin Cui #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
277*01826a49SYabin Cui #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
278*01826a49SYabin Cui #endif
279*01826a49SYabin Cui
280*01826a49SYabin Cui
281*01826a49SYabin Cui /****************************************************************
282*01826a49SYabin Cui * Error Management
283*01826a49SYabin Cui ****************************************************************/
284*01826a49SYabin Cui #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
285*01826a49SYabin Cui
286*01826a49SYabin Cui
287*01826a49SYabin Cui /****************************************************************
288*01826a49SYabin Cui * Complex types
289*01826a49SYabin Cui ****************************************************************/
290*01826a49SYabin Cui typedef struct
291*01826a49SYabin Cui {
292*01826a49SYabin Cui int deltaFindState;
293*01826a49SYabin Cui U32 deltaNbBits;
294*01826a49SYabin Cui } FSE_symbolCompressionTransform; /* total 8 bytes */
295*01826a49SYabin Cui
296*01826a49SYabin Cui typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
297*01826a49SYabin Cui
298*01826a49SYabin Cui /****************************************************************
299*01826a49SYabin Cui * Internal functions
300*01826a49SYabin Cui ****************************************************************/
FSE_highbit32(U32 val)301*01826a49SYabin Cui FORCE_INLINE unsigned FSE_highbit32 (U32 val)
302*01826a49SYabin Cui {
303*01826a49SYabin Cui # if defined(_MSC_VER) /* Visual */
304*01826a49SYabin Cui unsigned long r;
305*01826a49SYabin Cui return _BitScanReverse(&r, val) ? (unsigned)r : 0;
306*01826a49SYabin Cui # elif defined(__GNUC__) && (GCC_VERSION >= 304) /* GCC Intrinsic */
307*01826a49SYabin Cui return __builtin_clz (val) ^ 31;
308*01826a49SYabin Cui # else /* Software version */
309*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 };
310*01826a49SYabin Cui U32 v = val;
311*01826a49SYabin Cui unsigned r;
312*01826a49SYabin Cui v |= v >> 1;
313*01826a49SYabin Cui v |= v >> 2;
314*01826a49SYabin Cui v |= v >> 4;
315*01826a49SYabin Cui v |= v >> 8;
316*01826a49SYabin Cui v |= v >> 16;
317*01826a49SYabin Cui r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
318*01826a49SYabin Cui return r;
319*01826a49SYabin Cui # endif
320*01826a49SYabin Cui }
321*01826a49SYabin Cui
322*01826a49SYabin Cui
323*01826a49SYabin Cui /****************************************************************
324*01826a49SYabin Cui * Templates
325*01826a49SYabin Cui ****************************************************************/
326*01826a49SYabin Cui /*
327*01826a49SYabin Cui designed to be included
328*01826a49SYabin Cui for type-specific functions (template emulation in C)
329*01826a49SYabin Cui Objective is to write these functions only once, for improved maintenance
330*01826a49SYabin Cui */
331*01826a49SYabin Cui
332*01826a49SYabin Cui /* safety checks */
333*01826a49SYabin Cui #ifndef FSE_FUNCTION_EXTENSION
334*01826a49SYabin Cui # error "FSE_FUNCTION_EXTENSION must be defined"
335*01826a49SYabin Cui #endif
336*01826a49SYabin Cui #ifndef FSE_FUNCTION_TYPE
337*01826a49SYabin Cui # error "FSE_FUNCTION_TYPE must be defined"
338*01826a49SYabin Cui #endif
339*01826a49SYabin Cui
340*01826a49SYabin Cui /* Function names */
341*01826a49SYabin Cui #define FSE_CAT(X,Y) X##Y
342*01826a49SYabin Cui #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
343*01826a49SYabin Cui #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
344*01826a49SYabin Cui
345*01826a49SYabin Cui
346*01826a49SYabin Cui
FSE_tableStep(U32 tableSize)347*01826a49SYabin Cui static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
348*01826a49SYabin Cui
349*01826a49SYabin Cui #define FSE_DECODE_TYPE FSE_decode_t
350*01826a49SYabin Cui
351*01826a49SYabin Cui
352*01826a49SYabin Cui typedef struct {
353*01826a49SYabin Cui U16 tableLog;
354*01826a49SYabin Cui U16 fastMode;
355*01826a49SYabin Cui } FSE_DTableHeader; /* sizeof U32 */
356*01826a49SYabin Cui
FSE_buildDTable(FSE_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog)357*01826a49SYabin Cui static size_t FSE_buildDTable
358*01826a49SYabin Cui (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
359*01826a49SYabin Cui {
360*01826a49SYabin Cui void* ptr = dt;
361*01826a49SYabin Cui FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
362*01826a49SYabin Cui FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)(ptr) + 1; /* because dt is unsigned, 32-bits aligned on 32-bits */
363*01826a49SYabin Cui const U32 tableSize = 1 << tableLog;
364*01826a49SYabin Cui const U32 tableMask = tableSize-1;
365*01826a49SYabin Cui const U32 step = FSE_tableStep(tableSize);
366*01826a49SYabin Cui U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
367*01826a49SYabin Cui U32 position = 0;
368*01826a49SYabin Cui U32 highThreshold = tableSize-1;
369*01826a49SYabin Cui const S16 largeLimit= (S16)(1 << (tableLog-1));
370*01826a49SYabin Cui U32 noLarge = 1;
371*01826a49SYabin Cui U32 s;
372*01826a49SYabin Cui
373*01826a49SYabin Cui /* Sanity Checks */
374*01826a49SYabin Cui if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return (size_t)-FSE_ERROR_maxSymbolValue_tooLarge;
375*01826a49SYabin Cui if (tableLog > FSE_MAX_TABLELOG) return (size_t)-FSE_ERROR_tableLog_tooLarge;
376*01826a49SYabin Cui
377*01826a49SYabin Cui /* Init, lay down lowprob symbols */
378*01826a49SYabin Cui DTableH[0].tableLog = (U16)tableLog;
379*01826a49SYabin Cui for (s=0; s<=maxSymbolValue; s++)
380*01826a49SYabin Cui {
381*01826a49SYabin Cui if (normalizedCounter[s]==-1)
382*01826a49SYabin Cui {
383*01826a49SYabin Cui tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
384*01826a49SYabin Cui symbolNext[s] = 1;
385*01826a49SYabin Cui }
386*01826a49SYabin Cui else
387*01826a49SYabin Cui {
388*01826a49SYabin Cui if (normalizedCounter[s] >= largeLimit) noLarge=0;
389*01826a49SYabin Cui symbolNext[s] = normalizedCounter[s];
390*01826a49SYabin Cui }
391*01826a49SYabin Cui }
392*01826a49SYabin Cui
393*01826a49SYabin Cui /* Spread symbols */
394*01826a49SYabin Cui for (s=0; s<=maxSymbolValue; s++)
395*01826a49SYabin Cui {
396*01826a49SYabin Cui int i;
397*01826a49SYabin Cui for (i=0; i<normalizedCounter[s]; i++)
398*01826a49SYabin Cui {
399*01826a49SYabin Cui tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
400*01826a49SYabin Cui position = (position + step) & tableMask;
401*01826a49SYabin Cui while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
402*01826a49SYabin Cui }
403*01826a49SYabin Cui }
404*01826a49SYabin Cui
405*01826a49SYabin Cui if (position!=0) return (size_t)-FSE_ERROR_GENERIC; /* position must reach all cells once, otherwise normalizedCounter is incorrect */
406*01826a49SYabin Cui
407*01826a49SYabin Cui /* Build Decoding table */
408*01826a49SYabin Cui {
409*01826a49SYabin Cui U32 i;
410*01826a49SYabin Cui for (i=0; i<tableSize; i++)
411*01826a49SYabin Cui {
412*01826a49SYabin Cui FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
413*01826a49SYabin Cui U16 nextState = symbolNext[symbol]++;
414*01826a49SYabin Cui tableDecode[i].nbBits = (BYTE) (tableLog - FSE_highbit32 ((U32)nextState) );
415*01826a49SYabin Cui tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
416*01826a49SYabin Cui }
417*01826a49SYabin Cui }
418*01826a49SYabin Cui
419*01826a49SYabin Cui DTableH->fastMode = (U16)noLarge;
420*01826a49SYabin Cui return 0;
421*01826a49SYabin Cui }
422*01826a49SYabin Cui
423*01826a49SYabin Cui
424*01826a49SYabin Cui /******************************************
425*01826a49SYabin Cui * FSE byte symbol
426*01826a49SYabin Cui ******************************************/
427*01826a49SYabin Cui #ifndef FSE_COMMONDEFS_ONLY
428*01826a49SYabin Cui
FSE_isError(size_t code)429*01826a49SYabin Cui static unsigned FSE_isError(size_t code) { return (code > (size_t)(-FSE_ERROR_maxCode)); }
430*01826a49SYabin Cui
FSE_abs(short a)431*01826a49SYabin Cui static short FSE_abs(short a)
432*01826a49SYabin Cui {
433*01826a49SYabin Cui return a<0? -a : a;
434*01826a49SYabin Cui }
435*01826a49SYabin Cui
436*01826a49SYabin Cui
437*01826a49SYabin Cui /****************************************************************
438*01826a49SYabin Cui * Header bitstream management
439*01826a49SYabin Cui ****************************************************************/
FSE_readNCount(short * normalizedCounter,unsigned * maxSVPtr,unsigned * tableLogPtr,const void * headerBuffer,size_t hbSize)440*01826a49SYabin Cui static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
441*01826a49SYabin Cui const void* headerBuffer, size_t hbSize)
442*01826a49SYabin Cui {
443*01826a49SYabin Cui const BYTE* const istart = (const BYTE*) headerBuffer;
444*01826a49SYabin Cui const BYTE* const iend = istart + hbSize;
445*01826a49SYabin Cui const BYTE* ip = istart;
446*01826a49SYabin Cui int nbBits;
447*01826a49SYabin Cui int remaining;
448*01826a49SYabin Cui int threshold;
449*01826a49SYabin Cui U32 bitStream;
450*01826a49SYabin Cui int bitCount;
451*01826a49SYabin Cui unsigned charnum = 0;
452*01826a49SYabin Cui int previous0 = 0;
453*01826a49SYabin Cui
454*01826a49SYabin Cui if (hbSize < 4) return (size_t)-FSE_ERROR_srcSize_wrong;
455*01826a49SYabin Cui bitStream = FSE_readLE32(ip);
456*01826a49SYabin Cui nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
457*01826a49SYabin Cui if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return (size_t)-FSE_ERROR_tableLog_tooLarge;
458*01826a49SYabin Cui bitStream >>= 4;
459*01826a49SYabin Cui bitCount = 4;
460*01826a49SYabin Cui *tableLogPtr = nbBits;
461*01826a49SYabin Cui remaining = (1<<nbBits)+1;
462*01826a49SYabin Cui threshold = 1<<nbBits;
463*01826a49SYabin Cui nbBits++;
464*01826a49SYabin Cui
465*01826a49SYabin Cui while ((remaining>1) && (charnum<=*maxSVPtr))
466*01826a49SYabin Cui {
467*01826a49SYabin Cui if (previous0)
468*01826a49SYabin Cui {
469*01826a49SYabin Cui unsigned n0 = charnum;
470*01826a49SYabin Cui while ((bitStream & 0xFFFF) == 0xFFFF)
471*01826a49SYabin Cui {
472*01826a49SYabin Cui n0+=24;
473*01826a49SYabin Cui if (ip < iend-5)
474*01826a49SYabin Cui {
475*01826a49SYabin Cui ip+=2;
476*01826a49SYabin Cui bitStream = FSE_readLE32(ip) >> bitCount;
477*01826a49SYabin Cui }
478*01826a49SYabin Cui else
479*01826a49SYabin Cui {
480*01826a49SYabin Cui bitStream >>= 16;
481*01826a49SYabin Cui bitCount+=16;
482*01826a49SYabin Cui }
483*01826a49SYabin Cui }
484*01826a49SYabin Cui while ((bitStream & 3) == 3)
485*01826a49SYabin Cui {
486*01826a49SYabin Cui n0+=3;
487*01826a49SYabin Cui bitStream>>=2;
488*01826a49SYabin Cui bitCount+=2;
489*01826a49SYabin Cui }
490*01826a49SYabin Cui n0 += bitStream & 3;
491*01826a49SYabin Cui bitCount += 2;
492*01826a49SYabin Cui if (n0 > *maxSVPtr) return (size_t)-FSE_ERROR_maxSymbolValue_tooSmall;
493*01826a49SYabin Cui while (charnum < n0) normalizedCounter[charnum++] = 0;
494*01826a49SYabin Cui if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
495*01826a49SYabin Cui {
496*01826a49SYabin Cui ip += bitCount>>3;
497*01826a49SYabin Cui bitCount &= 7;
498*01826a49SYabin Cui bitStream = FSE_readLE32(ip) >> bitCount;
499*01826a49SYabin Cui }
500*01826a49SYabin Cui else
501*01826a49SYabin Cui bitStream >>= 2;
502*01826a49SYabin Cui }
503*01826a49SYabin Cui {
504*01826a49SYabin Cui const short max = (short)((2*threshold-1)-remaining);
505*01826a49SYabin Cui short count;
506*01826a49SYabin Cui
507*01826a49SYabin Cui if ((bitStream & (threshold-1)) < (U32)max)
508*01826a49SYabin Cui {
509*01826a49SYabin Cui count = (short)(bitStream & (threshold-1));
510*01826a49SYabin Cui bitCount += nbBits-1;
511*01826a49SYabin Cui }
512*01826a49SYabin Cui else
513*01826a49SYabin Cui {
514*01826a49SYabin Cui count = (short)(bitStream & (2*threshold-1));
515*01826a49SYabin Cui if (count >= threshold) count -= max;
516*01826a49SYabin Cui bitCount += nbBits;
517*01826a49SYabin Cui }
518*01826a49SYabin Cui
519*01826a49SYabin Cui count--; /* extra accuracy */
520*01826a49SYabin Cui remaining -= FSE_abs(count);
521*01826a49SYabin Cui normalizedCounter[charnum++] = count;
522*01826a49SYabin Cui previous0 = !count;
523*01826a49SYabin Cui while (remaining < threshold)
524*01826a49SYabin Cui {
525*01826a49SYabin Cui nbBits--;
526*01826a49SYabin Cui threshold >>= 1;
527*01826a49SYabin Cui }
528*01826a49SYabin Cui
529*01826a49SYabin Cui {
530*01826a49SYabin Cui if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
531*01826a49SYabin Cui {
532*01826a49SYabin Cui ip += bitCount>>3;
533*01826a49SYabin Cui bitCount &= 7;
534*01826a49SYabin Cui }
535*01826a49SYabin Cui else
536*01826a49SYabin Cui {
537*01826a49SYabin Cui bitCount -= (int)(8 * (iend - 4 - ip));
538*01826a49SYabin Cui ip = iend - 4;
539*01826a49SYabin Cui }
540*01826a49SYabin Cui bitStream = FSE_readLE32(ip) >> (bitCount & 31);
541*01826a49SYabin Cui }
542*01826a49SYabin Cui }
543*01826a49SYabin Cui }
544*01826a49SYabin Cui if (remaining != 1) return (size_t)-FSE_ERROR_GENERIC;
545*01826a49SYabin Cui *maxSVPtr = charnum-1;
546*01826a49SYabin Cui
547*01826a49SYabin Cui ip += (bitCount+7)>>3;
548*01826a49SYabin Cui if ((size_t)(ip-istart) > hbSize) return (size_t)-FSE_ERROR_srcSize_wrong;
549*01826a49SYabin Cui return ip-istart;
550*01826a49SYabin Cui }
551*01826a49SYabin Cui
552*01826a49SYabin Cui
553*01826a49SYabin Cui /*********************************************************
554*01826a49SYabin Cui * Decompression (Byte symbols)
555*01826a49SYabin Cui *********************************************************/
FSE_buildDTable_rle(FSE_DTable * dt,BYTE symbolValue)556*01826a49SYabin Cui static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
557*01826a49SYabin Cui {
558*01826a49SYabin Cui void* ptr = dt;
559*01826a49SYabin Cui FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
560*01826a49SYabin Cui FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */
561*01826a49SYabin Cui
562*01826a49SYabin Cui DTableH->tableLog = 0;
563*01826a49SYabin Cui DTableH->fastMode = 0;
564*01826a49SYabin Cui
565*01826a49SYabin Cui cell->newState = 0;
566*01826a49SYabin Cui cell->symbol = symbolValue;
567*01826a49SYabin Cui cell->nbBits = 0;
568*01826a49SYabin Cui
569*01826a49SYabin Cui return 0;
570*01826a49SYabin Cui }
571*01826a49SYabin Cui
572*01826a49SYabin Cui
FSE_buildDTable_raw(FSE_DTable * dt,unsigned nbBits)573*01826a49SYabin Cui static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
574*01826a49SYabin Cui {
575*01826a49SYabin Cui void* ptr = dt;
576*01826a49SYabin Cui FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
577*01826a49SYabin Cui FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */
578*01826a49SYabin Cui const unsigned tableSize = 1 << nbBits;
579*01826a49SYabin Cui const unsigned tableMask = tableSize - 1;
580*01826a49SYabin Cui const unsigned maxSymbolValue = tableMask;
581*01826a49SYabin Cui unsigned s;
582*01826a49SYabin Cui
583*01826a49SYabin Cui /* Sanity checks */
584*01826a49SYabin Cui if (nbBits < 1) return (size_t)-FSE_ERROR_GENERIC; /* min size */
585*01826a49SYabin Cui
586*01826a49SYabin Cui /* Build Decoding Table */
587*01826a49SYabin Cui DTableH->tableLog = (U16)nbBits;
588*01826a49SYabin Cui DTableH->fastMode = 1;
589*01826a49SYabin Cui for (s=0; s<=maxSymbolValue; s++)
590*01826a49SYabin Cui {
591*01826a49SYabin Cui dinfo[s].newState = 0;
592*01826a49SYabin Cui dinfo[s].symbol = (BYTE)s;
593*01826a49SYabin Cui dinfo[s].nbBits = (BYTE)nbBits;
594*01826a49SYabin Cui }
595*01826a49SYabin Cui
596*01826a49SYabin Cui return 0;
597*01826a49SYabin Cui }
598*01826a49SYabin Cui
599*01826a49SYabin Cui
600*01826a49SYabin Cui /* FSE_initDStream
601*01826a49SYabin Cui * Initialize a FSE_DStream_t.
602*01826a49SYabin Cui * srcBuffer must point at the beginning of an FSE block.
603*01826a49SYabin Cui * The function result is the size of the FSE_block (== srcSize).
604*01826a49SYabin Cui * If srcSize is too small, the function will return an errorCode;
605*01826a49SYabin Cui */
FSE_initDStream(FSE_DStream_t * bitD,const void * srcBuffer,size_t srcSize)606*01826a49SYabin Cui static size_t FSE_initDStream(FSE_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
607*01826a49SYabin Cui {
608*01826a49SYabin Cui if (srcSize < 1) return (size_t)-FSE_ERROR_srcSize_wrong;
609*01826a49SYabin Cui
610*01826a49SYabin Cui if (srcSize >= sizeof(size_t))
611*01826a49SYabin Cui {
612*01826a49SYabin Cui U32 contain32;
613*01826a49SYabin Cui bitD->start = (const char*)srcBuffer;
614*01826a49SYabin Cui bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
615*01826a49SYabin Cui bitD->bitContainer = FSE_readLEST(bitD->ptr);
616*01826a49SYabin Cui contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
617*01826a49SYabin Cui if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC; /* stop bit not present */
618*01826a49SYabin Cui bitD->bitsConsumed = 8 - FSE_highbit32(contain32);
619*01826a49SYabin Cui }
620*01826a49SYabin Cui else
621*01826a49SYabin Cui {
622*01826a49SYabin Cui U32 contain32;
623*01826a49SYabin Cui bitD->start = (const char*)srcBuffer;
624*01826a49SYabin Cui bitD->ptr = bitD->start;
625*01826a49SYabin Cui bitD->bitContainer = *(const BYTE*)(bitD->start);
626*01826a49SYabin Cui switch(srcSize)
627*01826a49SYabin Cui {
628*01826a49SYabin Cui case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
629*01826a49SYabin Cui /* fallthrough */
630*01826a49SYabin Cui case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
631*01826a49SYabin Cui /* fallthrough */
632*01826a49SYabin Cui case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
633*01826a49SYabin Cui /* fallthrough */
634*01826a49SYabin Cui case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
635*01826a49SYabin Cui /* fallthrough */
636*01826a49SYabin Cui case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
637*01826a49SYabin Cui /* fallthrough */
638*01826a49SYabin Cui case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
639*01826a49SYabin Cui /* fallthrough */
640*01826a49SYabin Cui default:;
641*01826a49SYabin Cui }
642*01826a49SYabin Cui contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
643*01826a49SYabin Cui if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC; /* stop bit not present */
644*01826a49SYabin Cui bitD->bitsConsumed = 8 - FSE_highbit32(contain32);
645*01826a49SYabin Cui bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
646*01826a49SYabin Cui }
647*01826a49SYabin Cui
648*01826a49SYabin Cui return srcSize;
649*01826a49SYabin Cui }
650*01826a49SYabin Cui
651*01826a49SYabin Cui
652*01826a49SYabin Cui /*!FSE_lookBits
653*01826a49SYabin Cui * Provides next n bits from the bitContainer.
654*01826a49SYabin Cui * bitContainer is not modified (bits are still present for next read/look)
655*01826a49SYabin Cui * On 32-bits, maxNbBits==25
656*01826a49SYabin Cui * On 64-bits, maxNbBits==57
657*01826a49SYabin Cui * return : value extracted.
658*01826a49SYabin Cui */
FSE_lookBits(FSE_DStream_t * bitD,U32 nbBits)659*01826a49SYabin Cui static size_t FSE_lookBits(FSE_DStream_t* bitD, U32 nbBits)
660*01826a49SYabin Cui {
661*01826a49SYabin Cui const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
662*01826a49SYabin Cui return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
663*01826a49SYabin Cui }
664*01826a49SYabin Cui
FSE_lookBitsFast(FSE_DStream_t * bitD,U32 nbBits)665*01826a49SYabin Cui static size_t FSE_lookBitsFast(FSE_DStream_t* bitD, U32 nbBits) /* only if nbBits >= 1 !! */
666*01826a49SYabin Cui {
667*01826a49SYabin Cui const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
668*01826a49SYabin Cui return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
669*01826a49SYabin Cui }
670*01826a49SYabin Cui
FSE_skipBits(FSE_DStream_t * bitD,U32 nbBits)671*01826a49SYabin Cui static void FSE_skipBits(FSE_DStream_t* bitD, U32 nbBits)
672*01826a49SYabin Cui {
673*01826a49SYabin Cui bitD->bitsConsumed += nbBits;
674*01826a49SYabin Cui }
675*01826a49SYabin Cui
676*01826a49SYabin Cui
677*01826a49SYabin Cui /*!FSE_readBits
678*01826a49SYabin Cui * Read next n bits from the bitContainer.
679*01826a49SYabin Cui * On 32-bits, don't read more than maxNbBits==25
680*01826a49SYabin Cui * On 64-bits, don't read more than maxNbBits==57
681*01826a49SYabin Cui * Use the fast variant *only* if n >= 1.
682*01826a49SYabin Cui * return : value extracted.
683*01826a49SYabin Cui */
FSE_readBits(FSE_DStream_t * bitD,U32 nbBits)684*01826a49SYabin Cui static size_t FSE_readBits(FSE_DStream_t* bitD, U32 nbBits)
685*01826a49SYabin Cui {
686*01826a49SYabin Cui size_t value = FSE_lookBits(bitD, nbBits);
687*01826a49SYabin Cui FSE_skipBits(bitD, nbBits);
688*01826a49SYabin Cui return value;
689*01826a49SYabin Cui }
690*01826a49SYabin Cui
FSE_readBitsFast(FSE_DStream_t * bitD,U32 nbBits)691*01826a49SYabin Cui static size_t FSE_readBitsFast(FSE_DStream_t* bitD, U32 nbBits) /* only if nbBits >= 1 !! */
692*01826a49SYabin Cui {
693*01826a49SYabin Cui size_t value = FSE_lookBitsFast(bitD, nbBits);
694*01826a49SYabin Cui FSE_skipBits(bitD, nbBits);
695*01826a49SYabin Cui return value;
696*01826a49SYabin Cui }
697*01826a49SYabin Cui
FSE_reloadDStream(FSE_DStream_t * bitD)698*01826a49SYabin Cui static unsigned FSE_reloadDStream(FSE_DStream_t* bitD)
699*01826a49SYabin Cui {
700*01826a49SYabin Cui if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
701*01826a49SYabin Cui return FSE_DStream_tooFar;
702*01826a49SYabin Cui
703*01826a49SYabin Cui if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
704*01826a49SYabin Cui {
705*01826a49SYabin Cui bitD->ptr -= bitD->bitsConsumed >> 3;
706*01826a49SYabin Cui bitD->bitsConsumed &= 7;
707*01826a49SYabin Cui bitD->bitContainer = FSE_readLEST(bitD->ptr);
708*01826a49SYabin Cui return FSE_DStream_unfinished;
709*01826a49SYabin Cui }
710*01826a49SYabin Cui if (bitD->ptr == bitD->start)
711*01826a49SYabin Cui {
712*01826a49SYabin Cui if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return FSE_DStream_endOfBuffer;
713*01826a49SYabin Cui return FSE_DStream_completed;
714*01826a49SYabin Cui }
715*01826a49SYabin Cui {
716*01826a49SYabin Cui U32 nbBytes = bitD->bitsConsumed >> 3;
717*01826a49SYabin Cui U32 result = FSE_DStream_unfinished;
718*01826a49SYabin Cui if (bitD->ptr - nbBytes < bitD->start)
719*01826a49SYabin Cui {
720*01826a49SYabin Cui nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
721*01826a49SYabin Cui result = FSE_DStream_endOfBuffer;
722*01826a49SYabin Cui }
723*01826a49SYabin Cui bitD->ptr -= nbBytes;
724*01826a49SYabin Cui bitD->bitsConsumed -= nbBytes*8;
725*01826a49SYabin Cui bitD->bitContainer = FSE_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
726*01826a49SYabin Cui return result;
727*01826a49SYabin Cui }
728*01826a49SYabin Cui }
729*01826a49SYabin Cui
730*01826a49SYabin Cui
FSE_initDState(FSE_DState_t * DStatePtr,FSE_DStream_t * bitD,const FSE_DTable * dt)731*01826a49SYabin Cui static void FSE_initDState(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD, const FSE_DTable* dt)
732*01826a49SYabin Cui {
733*01826a49SYabin Cui const void* ptr = dt;
734*01826a49SYabin Cui const FSE_DTableHeader* const DTableH = (const FSE_DTableHeader*)ptr;
735*01826a49SYabin Cui DStatePtr->state = FSE_readBits(bitD, DTableH->tableLog);
736*01826a49SYabin Cui FSE_reloadDStream(bitD);
737*01826a49SYabin Cui DStatePtr->table = dt + 1;
738*01826a49SYabin Cui }
739*01826a49SYabin Cui
FSE_decodeSymbol(FSE_DState_t * DStatePtr,FSE_DStream_t * bitD)740*01826a49SYabin Cui static BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD)
741*01826a49SYabin Cui {
742*01826a49SYabin Cui const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
743*01826a49SYabin Cui const U32 nbBits = DInfo.nbBits;
744*01826a49SYabin Cui BYTE symbol = DInfo.symbol;
745*01826a49SYabin Cui size_t lowBits = FSE_readBits(bitD, nbBits);
746*01826a49SYabin Cui
747*01826a49SYabin Cui DStatePtr->state = DInfo.newState + lowBits;
748*01826a49SYabin Cui return symbol;
749*01826a49SYabin Cui }
750*01826a49SYabin Cui
FSE_decodeSymbolFast(FSE_DState_t * DStatePtr,FSE_DStream_t * bitD)751*01826a49SYabin Cui static BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD)
752*01826a49SYabin Cui {
753*01826a49SYabin Cui const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
754*01826a49SYabin Cui const U32 nbBits = DInfo.nbBits;
755*01826a49SYabin Cui BYTE symbol = DInfo.symbol;
756*01826a49SYabin Cui size_t lowBits = FSE_readBitsFast(bitD, nbBits);
757*01826a49SYabin Cui
758*01826a49SYabin Cui DStatePtr->state = DInfo.newState + lowBits;
759*01826a49SYabin Cui return symbol;
760*01826a49SYabin Cui }
761*01826a49SYabin Cui
762*01826a49SYabin Cui /* FSE_endOfDStream
763*01826a49SYabin Cui Tells if bitD has reached end of bitStream or not */
764*01826a49SYabin Cui
FSE_endOfDStream(const FSE_DStream_t * bitD)765*01826a49SYabin Cui static unsigned FSE_endOfDStream(const FSE_DStream_t* bitD)
766*01826a49SYabin Cui {
767*01826a49SYabin Cui return ((bitD->ptr == bitD->start) && (bitD->bitsConsumed == sizeof(bitD->bitContainer)*8));
768*01826a49SYabin Cui }
769*01826a49SYabin Cui
FSE_endOfDState(const FSE_DState_t * DStatePtr)770*01826a49SYabin Cui static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
771*01826a49SYabin Cui {
772*01826a49SYabin Cui return DStatePtr->state == 0;
773*01826a49SYabin Cui }
774*01826a49SYabin Cui
775*01826a49SYabin Cui
FSE_decompress_usingDTable_generic(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt,const unsigned fast)776*01826a49SYabin Cui FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
777*01826a49SYabin Cui void* dst, size_t maxDstSize,
778*01826a49SYabin Cui const void* cSrc, size_t cSrcSize,
779*01826a49SYabin Cui const FSE_DTable* dt, const unsigned fast)
780*01826a49SYabin Cui {
781*01826a49SYabin Cui BYTE* const ostart = (BYTE*) dst;
782*01826a49SYabin Cui BYTE* op = ostart;
783*01826a49SYabin Cui BYTE* const omax = op + maxDstSize;
784*01826a49SYabin Cui BYTE* const olimit = omax-3;
785*01826a49SYabin Cui
786*01826a49SYabin Cui FSE_DStream_t bitD;
787*01826a49SYabin Cui FSE_DState_t state1;
788*01826a49SYabin Cui FSE_DState_t state2;
789*01826a49SYabin Cui size_t errorCode;
790*01826a49SYabin Cui
791*01826a49SYabin Cui /* Init */
792*01826a49SYabin Cui errorCode = FSE_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
793*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
794*01826a49SYabin Cui
795*01826a49SYabin Cui FSE_initDState(&state1, &bitD, dt);
796*01826a49SYabin Cui FSE_initDState(&state2, &bitD, dt);
797*01826a49SYabin Cui
798*01826a49SYabin Cui #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
799*01826a49SYabin Cui
800*01826a49SYabin Cui /* 4 symbols per loop */
801*01826a49SYabin Cui for ( ; (FSE_reloadDStream(&bitD)==FSE_DStream_unfinished) && (op<olimit) ; op+=4)
802*01826a49SYabin Cui {
803*01826a49SYabin Cui op[0] = FSE_GETSYMBOL(&state1);
804*01826a49SYabin Cui
805*01826a49SYabin Cui if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
806*01826a49SYabin Cui FSE_reloadDStream(&bitD);
807*01826a49SYabin Cui
808*01826a49SYabin Cui op[1] = FSE_GETSYMBOL(&state2);
809*01826a49SYabin Cui
810*01826a49SYabin Cui if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
811*01826a49SYabin Cui { if (FSE_reloadDStream(&bitD) > FSE_DStream_unfinished) { op+=2; break; } }
812*01826a49SYabin Cui
813*01826a49SYabin Cui op[2] = FSE_GETSYMBOL(&state1);
814*01826a49SYabin Cui
815*01826a49SYabin Cui if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
816*01826a49SYabin Cui FSE_reloadDStream(&bitD);
817*01826a49SYabin Cui
818*01826a49SYabin Cui op[3] = FSE_GETSYMBOL(&state2);
819*01826a49SYabin Cui }
820*01826a49SYabin Cui
821*01826a49SYabin Cui /* tail */
822*01826a49SYabin Cui /* note : FSE_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly FSE_DStream_completed */
823*01826a49SYabin Cui while (1)
824*01826a49SYabin Cui {
825*01826a49SYabin Cui if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
826*01826a49SYabin Cui break;
827*01826a49SYabin Cui
828*01826a49SYabin Cui *op++ = FSE_GETSYMBOL(&state1);
829*01826a49SYabin Cui
830*01826a49SYabin Cui if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
831*01826a49SYabin Cui break;
832*01826a49SYabin Cui
833*01826a49SYabin Cui *op++ = FSE_GETSYMBOL(&state2);
834*01826a49SYabin Cui }
835*01826a49SYabin Cui
836*01826a49SYabin Cui /* end ? */
837*01826a49SYabin Cui if (FSE_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
838*01826a49SYabin Cui return op-ostart;
839*01826a49SYabin Cui
840*01826a49SYabin Cui if (op==omax) return (size_t)-FSE_ERROR_dstSize_tooSmall; /* dst buffer is full, but cSrc unfinished */
841*01826a49SYabin Cui
842*01826a49SYabin Cui return (size_t)-FSE_ERROR_corruptionDetected;
843*01826a49SYabin Cui }
844*01826a49SYabin Cui
845*01826a49SYabin Cui
FSE_decompress_usingDTable(void * dst,size_t originalSize,const void * cSrc,size_t cSrcSize,const FSE_DTable * dt)846*01826a49SYabin Cui static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
847*01826a49SYabin Cui const void* cSrc, size_t cSrcSize,
848*01826a49SYabin Cui const FSE_DTable* dt)
849*01826a49SYabin Cui {
850*01826a49SYabin Cui FSE_DTableHeader DTableH;
851*01826a49SYabin Cui memcpy(&DTableH, dt, sizeof(DTableH)); /* memcpy() into local variable, to avoid strict aliasing warning */
852*01826a49SYabin Cui
853*01826a49SYabin Cui /* select fast mode (static) */
854*01826a49SYabin Cui if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
855*01826a49SYabin Cui return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
856*01826a49SYabin Cui }
857*01826a49SYabin Cui
858*01826a49SYabin Cui
FSE_decompress(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize)859*01826a49SYabin Cui static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
860*01826a49SYabin Cui {
861*01826a49SYabin Cui const BYTE* const istart = (const BYTE*)cSrc;
862*01826a49SYabin Cui const BYTE* ip = istart;
863*01826a49SYabin Cui short counting[FSE_MAX_SYMBOL_VALUE+1];
864*01826a49SYabin Cui DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
865*01826a49SYabin Cui unsigned tableLog;
866*01826a49SYabin Cui unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
867*01826a49SYabin Cui size_t errorCode;
868*01826a49SYabin Cui
869*01826a49SYabin Cui if (cSrcSize<2) return (size_t)-FSE_ERROR_srcSize_wrong; /* too small input size */
870*01826a49SYabin Cui
871*01826a49SYabin Cui /* normal FSE decoding mode */
872*01826a49SYabin Cui errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
873*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
874*01826a49SYabin Cui if (errorCode >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong; /* too small input size */
875*01826a49SYabin Cui ip += errorCode;
876*01826a49SYabin Cui cSrcSize -= errorCode;
877*01826a49SYabin Cui
878*01826a49SYabin Cui errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
879*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
880*01826a49SYabin Cui
881*01826a49SYabin Cui /* always return, even if it is an error code */
882*01826a49SYabin Cui return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
883*01826a49SYabin Cui }
884*01826a49SYabin Cui
885*01826a49SYabin Cui
886*01826a49SYabin Cui
887*01826a49SYabin Cui /* *******************************************************
888*01826a49SYabin Cui * Huff0 : Huffman block compression
889*01826a49SYabin Cui *********************************************************/
890*01826a49SYabin Cui #define HUF_MAX_SYMBOL_VALUE 255
891*01826a49SYabin Cui #define HUF_DEFAULT_TABLELOG 12 /* used by default, when not specified */
892*01826a49SYabin Cui #define HUF_MAX_TABLELOG 12 /* max possible tableLog; for allocation purpose; can be modified */
893*01826a49SYabin Cui #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
894*01826a49SYabin Cui #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
895*01826a49SYabin Cui # error "HUF_MAX_TABLELOG is too large !"
896*01826a49SYabin Cui #endif
897*01826a49SYabin Cui
898*01826a49SYabin Cui typedef struct HUF_CElt_s {
899*01826a49SYabin Cui U16 val;
900*01826a49SYabin Cui BYTE nbBits;
901*01826a49SYabin Cui } HUF_CElt ;
902*01826a49SYabin Cui
903*01826a49SYabin Cui typedef struct nodeElt_s {
904*01826a49SYabin Cui U32 count;
905*01826a49SYabin Cui U16 parent;
906*01826a49SYabin Cui BYTE byte;
907*01826a49SYabin Cui BYTE nbBits;
908*01826a49SYabin Cui } nodeElt;
909*01826a49SYabin Cui
910*01826a49SYabin Cui
911*01826a49SYabin Cui /* *******************************************************
912*01826a49SYabin Cui * Huff0 : Huffman block decompression
913*01826a49SYabin Cui *********************************************************/
914*01826a49SYabin Cui typedef struct {
915*01826a49SYabin Cui BYTE byte;
916*01826a49SYabin Cui BYTE nbBits;
917*01826a49SYabin Cui } HUF_DElt;
918*01826a49SYabin Cui
HUF_readDTable(U16 * DTable,const void * src,size_t srcSize)919*01826a49SYabin Cui static size_t HUF_readDTable (U16* DTable, const void* src, size_t srcSize)
920*01826a49SYabin Cui {
921*01826a49SYabin Cui BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
922*01826a49SYabin Cui U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
923*01826a49SYabin Cui U32 weightTotal;
924*01826a49SYabin Cui U32 maxBits;
925*01826a49SYabin Cui const BYTE* ip = (const BYTE*) src;
926*01826a49SYabin Cui size_t iSize;
927*01826a49SYabin Cui size_t oSize;
928*01826a49SYabin Cui U32 n;
929*01826a49SYabin Cui U32 nextRankStart;
930*01826a49SYabin Cui void* ptr = DTable+1;
931*01826a49SYabin Cui HUF_DElt* const dt = (HUF_DElt*)ptr;
932*01826a49SYabin Cui
933*01826a49SYabin Cui if (!srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
934*01826a49SYabin Cui iSize = ip[0];
935*01826a49SYabin Cui
936*01826a49SYabin Cui FSE_STATIC_ASSERT(sizeof(HUF_DElt) == sizeof(U16)); /* if compilation fails here, assertion is false */
937*01826a49SYabin Cui //memset(huffWeight, 0, sizeof(huffWeight)); /* should not be necessary, but some analyzer complain ... */
938*01826a49SYabin Cui if (iSize >= 128) /* special header */
939*01826a49SYabin Cui {
940*01826a49SYabin Cui if (iSize >= (242)) /* RLE */
941*01826a49SYabin Cui {
942*01826a49SYabin Cui static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
943*01826a49SYabin Cui oSize = l[iSize-242];
944*01826a49SYabin Cui memset(huffWeight, 1, sizeof(huffWeight));
945*01826a49SYabin Cui iSize = 0;
946*01826a49SYabin Cui }
947*01826a49SYabin Cui else /* Incompressible */
948*01826a49SYabin Cui {
949*01826a49SYabin Cui oSize = iSize - 127;
950*01826a49SYabin Cui iSize = ((oSize+1)/2);
951*01826a49SYabin Cui if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
952*01826a49SYabin Cui ip += 1;
953*01826a49SYabin Cui for (n=0; n<oSize; n+=2)
954*01826a49SYabin Cui {
955*01826a49SYabin Cui huffWeight[n] = ip[n/2] >> 4;
956*01826a49SYabin Cui huffWeight[n+1] = ip[n/2] & 15;
957*01826a49SYabin Cui }
958*01826a49SYabin Cui }
959*01826a49SYabin Cui }
960*01826a49SYabin Cui else /* header compressed with FSE (normal case) */
961*01826a49SYabin Cui {
962*01826a49SYabin Cui if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
963*01826a49SYabin Cui oSize = FSE_decompress(huffWeight, HUF_MAX_SYMBOL_VALUE, ip+1, iSize); /* max 255 values decoded, last one is implied */
964*01826a49SYabin Cui if (FSE_isError(oSize)) return oSize;
965*01826a49SYabin Cui }
966*01826a49SYabin Cui
967*01826a49SYabin Cui /* collect weight stats */
968*01826a49SYabin Cui memset(rankVal, 0, sizeof(rankVal));
969*01826a49SYabin Cui weightTotal = 0;
970*01826a49SYabin Cui for (n=0; n<oSize; n++)
971*01826a49SYabin Cui {
972*01826a49SYabin Cui if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return (size_t)-FSE_ERROR_corruptionDetected;
973*01826a49SYabin Cui rankVal[huffWeight[n]]++;
974*01826a49SYabin Cui weightTotal += (1 << huffWeight[n]) >> 1;
975*01826a49SYabin Cui }
976*01826a49SYabin Cui if (weightTotal == 0) return (size_t)-FSE_ERROR_corruptionDetected;
977*01826a49SYabin Cui
978*01826a49SYabin Cui /* get last non-null symbol weight (implied, total must be 2^n) */
979*01826a49SYabin Cui maxBits = FSE_highbit32(weightTotal) + 1;
980*01826a49SYabin Cui if (maxBits > DTable[0]) return (size_t)-FSE_ERROR_tableLog_tooLarge; /* DTable is too small */
981*01826a49SYabin Cui DTable[0] = (U16)maxBits;
982*01826a49SYabin Cui {
983*01826a49SYabin Cui U32 total = 1 << maxBits;
984*01826a49SYabin Cui U32 rest = total - weightTotal;
985*01826a49SYabin Cui U32 verif = 1 << FSE_highbit32(rest);
986*01826a49SYabin Cui U32 lastWeight = FSE_highbit32(rest) + 1;
987*01826a49SYabin Cui if (verif != rest) return (size_t)-FSE_ERROR_corruptionDetected; /* last value must be a clean power of 2 */
988*01826a49SYabin Cui huffWeight[oSize] = (BYTE)lastWeight;
989*01826a49SYabin Cui rankVal[lastWeight]++;
990*01826a49SYabin Cui }
991*01826a49SYabin Cui
992*01826a49SYabin Cui /* check tree construction validity */
993*01826a49SYabin Cui if ((rankVal[1] < 2) || (rankVal[1] & 1)) return (size_t)-FSE_ERROR_corruptionDetected; /* by construction : at least 2 elts of rank 1, must be even */
994*01826a49SYabin Cui
995*01826a49SYabin Cui /* Prepare ranks */
996*01826a49SYabin Cui nextRankStart = 0;
997*01826a49SYabin Cui for (n=1; n<=maxBits; n++)
998*01826a49SYabin Cui {
999*01826a49SYabin Cui U32 current = nextRankStart;
1000*01826a49SYabin Cui nextRankStart += (rankVal[n] << (n-1));
1001*01826a49SYabin Cui rankVal[n] = current;
1002*01826a49SYabin Cui }
1003*01826a49SYabin Cui
1004*01826a49SYabin Cui /* fill DTable */
1005*01826a49SYabin Cui for (n=0; n<=oSize; n++)
1006*01826a49SYabin Cui {
1007*01826a49SYabin Cui const U32 w = huffWeight[n];
1008*01826a49SYabin Cui const U32 length = (1 << w) >> 1;
1009*01826a49SYabin Cui U32 i;
1010*01826a49SYabin Cui HUF_DElt D;
1011*01826a49SYabin Cui D.byte = (BYTE)n; D.nbBits = (BYTE)(maxBits + 1 - w);
1012*01826a49SYabin Cui for (i = rankVal[w]; i < rankVal[w] + length; i++)
1013*01826a49SYabin Cui dt[i] = D;
1014*01826a49SYabin Cui rankVal[w] += length;
1015*01826a49SYabin Cui }
1016*01826a49SYabin Cui
1017*01826a49SYabin Cui return iSize+1;
1018*01826a49SYabin Cui }
1019*01826a49SYabin Cui
1020*01826a49SYabin Cui
HUF_decodeSymbol(FSE_DStream_t * Dstream,const HUF_DElt * dt,const U32 dtLog)1021*01826a49SYabin Cui static BYTE HUF_decodeSymbol(FSE_DStream_t* Dstream, const HUF_DElt* dt, const U32 dtLog)
1022*01826a49SYabin Cui {
1023*01826a49SYabin Cui const size_t val = FSE_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1024*01826a49SYabin Cui const BYTE c = dt[val].byte;
1025*01826a49SYabin Cui FSE_skipBits(Dstream, dt[val].nbBits);
1026*01826a49SYabin Cui return c;
1027*01826a49SYabin Cui }
1028*01826a49SYabin Cui
HUF_decompress_usingDTable(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const U16 * DTable)1029*01826a49SYabin Cui static size_t HUF_decompress_usingDTable( /* -3% slower when non static */
1030*01826a49SYabin Cui void* dst, size_t maxDstSize,
1031*01826a49SYabin Cui const void* cSrc, size_t cSrcSize,
1032*01826a49SYabin Cui const U16* DTable)
1033*01826a49SYabin Cui {
1034*01826a49SYabin Cui if (cSrcSize < 6) return (size_t)-FSE_ERROR_srcSize_wrong;
1035*01826a49SYabin Cui {
1036*01826a49SYabin Cui BYTE* const ostart = (BYTE*) dst;
1037*01826a49SYabin Cui BYTE* op = ostart;
1038*01826a49SYabin Cui BYTE* const omax = op + maxDstSize;
1039*01826a49SYabin Cui BYTE* const olimit = maxDstSize < 15 ? op : omax-15;
1040*01826a49SYabin Cui
1041*01826a49SYabin Cui const void* ptr = DTable;
1042*01826a49SYabin Cui const HUF_DElt* const dt = (const HUF_DElt*)(ptr)+1;
1043*01826a49SYabin Cui const U32 dtLog = DTable[0];
1044*01826a49SYabin Cui size_t errorCode;
1045*01826a49SYabin Cui U32 reloadStatus;
1046*01826a49SYabin Cui
1047*01826a49SYabin Cui /* Init */
1048*01826a49SYabin Cui
1049*01826a49SYabin Cui const U16* jumpTable = (const U16*)cSrc;
1050*01826a49SYabin Cui const size_t length1 = FSE_readLE16(jumpTable);
1051*01826a49SYabin Cui const size_t length2 = FSE_readLE16(jumpTable+1);
1052*01826a49SYabin Cui const size_t length3 = FSE_readLE16(jumpTable+2);
1053*01826a49SYabin Cui const size_t length4 = cSrcSize - 6 - length1 - length2 - length3; /* check coherency !! */
1054*01826a49SYabin Cui const char* const start1 = (const char*)(cSrc) + 6;
1055*01826a49SYabin Cui const char* const start2 = start1 + length1;
1056*01826a49SYabin Cui const char* const start3 = start2 + length2;
1057*01826a49SYabin Cui const char* const start4 = start3 + length3;
1058*01826a49SYabin Cui FSE_DStream_t bitD1, bitD2, bitD3, bitD4;
1059*01826a49SYabin Cui
1060*01826a49SYabin Cui if (length1+length2+length3+6 >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
1061*01826a49SYabin Cui
1062*01826a49SYabin Cui errorCode = FSE_initDStream(&bitD1, start1, length1);
1063*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1064*01826a49SYabin Cui errorCode = FSE_initDStream(&bitD2, start2, length2);
1065*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1066*01826a49SYabin Cui errorCode = FSE_initDStream(&bitD3, start3, length3);
1067*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1068*01826a49SYabin Cui errorCode = FSE_initDStream(&bitD4, start4, length4);
1069*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1070*01826a49SYabin Cui
1071*01826a49SYabin Cui reloadStatus=FSE_reloadDStream(&bitD2);
1072*01826a49SYabin Cui
1073*01826a49SYabin Cui /* 16 symbols per loop */
1074*01826a49SYabin Cui for ( ; (reloadStatus<FSE_DStream_completed) && (op<olimit); /* D2-3-4 are supposed to be synchronized and finish together */
1075*01826a49SYabin Cui op+=16, reloadStatus = FSE_reloadDStream(&bitD2) | FSE_reloadDStream(&bitD3) | FSE_reloadDStream(&bitD4), FSE_reloadDStream(&bitD1))
1076*01826a49SYabin Cui {
1077*01826a49SYabin Cui #define HUF_DECODE_SYMBOL_0(n, Dstream) \
1078*01826a49SYabin Cui op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog);
1079*01826a49SYabin Cui
1080*01826a49SYabin Cui #define HUF_DECODE_SYMBOL_1(n, Dstream) \
1081*01826a49SYabin Cui op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog); \
1082*01826a49SYabin Cui if (FSE_32bits() && (HUF_MAX_TABLELOG>12)) FSE_reloadDStream(&Dstream)
1083*01826a49SYabin Cui
1084*01826a49SYabin Cui #define HUF_DECODE_SYMBOL_2(n, Dstream) \
1085*01826a49SYabin Cui op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog); \
1086*01826a49SYabin Cui if (FSE_32bits()) FSE_reloadDStream(&Dstream)
1087*01826a49SYabin Cui
1088*01826a49SYabin Cui HUF_DECODE_SYMBOL_1( 0, bitD1);
1089*01826a49SYabin Cui HUF_DECODE_SYMBOL_1( 1, bitD2);
1090*01826a49SYabin Cui HUF_DECODE_SYMBOL_1( 2, bitD3);
1091*01826a49SYabin Cui HUF_DECODE_SYMBOL_1( 3, bitD4);
1092*01826a49SYabin Cui HUF_DECODE_SYMBOL_2( 4, bitD1);
1093*01826a49SYabin Cui HUF_DECODE_SYMBOL_2( 5, bitD2);
1094*01826a49SYabin Cui HUF_DECODE_SYMBOL_2( 6, bitD3);
1095*01826a49SYabin Cui HUF_DECODE_SYMBOL_2( 7, bitD4);
1096*01826a49SYabin Cui HUF_DECODE_SYMBOL_1( 8, bitD1);
1097*01826a49SYabin Cui HUF_DECODE_SYMBOL_1( 9, bitD2);
1098*01826a49SYabin Cui HUF_DECODE_SYMBOL_1(10, bitD3);
1099*01826a49SYabin Cui HUF_DECODE_SYMBOL_1(11, bitD4);
1100*01826a49SYabin Cui HUF_DECODE_SYMBOL_0(12, bitD1);
1101*01826a49SYabin Cui HUF_DECODE_SYMBOL_0(13, bitD2);
1102*01826a49SYabin Cui HUF_DECODE_SYMBOL_0(14, bitD3);
1103*01826a49SYabin Cui HUF_DECODE_SYMBOL_0(15, bitD4);
1104*01826a49SYabin Cui }
1105*01826a49SYabin Cui
1106*01826a49SYabin Cui if (reloadStatus!=FSE_DStream_completed) /* not complete : some bitStream might be FSE_DStream_unfinished */
1107*01826a49SYabin Cui return (size_t)-FSE_ERROR_corruptionDetected;
1108*01826a49SYabin Cui
1109*01826a49SYabin Cui /* tail */
1110*01826a49SYabin Cui {
1111*01826a49SYabin Cui /* bitTail = bitD1; */ /* *much* slower : -20% !??! */
1112*01826a49SYabin Cui FSE_DStream_t bitTail;
1113*01826a49SYabin Cui bitTail.ptr = bitD1.ptr;
1114*01826a49SYabin Cui bitTail.bitsConsumed = bitD1.bitsConsumed;
1115*01826a49SYabin Cui bitTail.bitContainer = bitD1.bitContainer; /* required in case of FSE_DStream_endOfBuffer */
1116*01826a49SYabin Cui bitTail.start = start1;
1117*01826a49SYabin Cui for ( ; (FSE_reloadDStream(&bitTail) < FSE_DStream_completed) && (op<omax) ; op++)
1118*01826a49SYabin Cui {
1119*01826a49SYabin Cui HUF_DECODE_SYMBOL_0(0, bitTail);
1120*01826a49SYabin Cui }
1121*01826a49SYabin Cui
1122*01826a49SYabin Cui if (FSE_endOfDStream(&bitTail))
1123*01826a49SYabin Cui return op-ostart;
1124*01826a49SYabin Cui }
1125*01826a49SYabin Cui
1126*01826a49SYabin Cui if (op==omax) return (size_t)-FSE_ERROR_dstSize_tooSmall; /* dst buffer is full, but cSrc unfinished */
1127*01826a49SYabin Cui
1128*01826a49SYabin Cui return (size_t)-FSE_ERROR_corruptionDetected;
1129*01826a49SYabin Cui }
1130*01826a49SYabin Cui }
1131*01826a49SYabin Cui
1132*01826a49SYabin Cui
HUF_decompress(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize)1133*01826a49SYabin Cui static size_t HUF_decompress (void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1134*01826a49SYabin Cui {
1135*01826a49SYabin Cui HUF_CREATE_STATIC_DTABLE(DTable, HUF_MAX_TABLELOG);
1136*01826a49SYabin Cui const BYTE* ip = (const BYTE*) cSrc;
1137*01826a49SYabin Cui size_t errorCode;
1138*01826a49SYabin Cui
1139*01826a49SYabin Cui errorCode = HUF_readDTable (DTable, cSrc, cSrcSize);
1140*01826a49SYabin Cui if (FSE_isError(errorCode)) return errorCode;
1141*01826a49SYabin Cui if (errorCode >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
1142*01826a49SYabin Cui ip += errorCode;
1143*01826a49SYabin Cui cSrcSize -= errorCode;
1144*01826a49SYabin Cui
1145*01826a49SYabin Cui return HUF_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, DTable);
1146*01826a49SYabin Cui }
1147*01826a49SYabin Cui
1148*01826a49SYabin Cui
1149*01826a49SYabin Cui #endif /* FSE_COMMONDEFS_ONLY */
1150*01826a49SYabin Cui
1151*01826a49SYabin Cui /*
1152*01826a49SYabin Cui zstd - standard compression library
1153*01826a49SYabin Cui Copyright (C) 2014-2015, Yann Collet.
1154*01826a49SYabin Cui
1155*01826a49SYabin Cui BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1156*01826a49SYabin Cui
1157*01826a49SYabin Cui Redistribution and use in source and binary forms, with or without
1158*01826a49SYabin Cui modification, are permitted provided that the following conditions are
1159*01826a49SYabin Cui met:
1160*01826a49SYabin Cui * Redistributions of source code must retain the above copyright
1161*01826a49SYabin Cui notice, this list of conditions and the following disclaimer.
1162*01826a49SYabin Cui * Redistributions in binary form must reproduce the above
1163*01826a49SYabin Cui copyright notice, this list of conditions and the following disclaimer
1164*01826a49SYabin Cui in the documentation and/or other materials provided with the
1165*01826a49SYabin Cui distribution.
1166*01826a49SYabin Cui THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1167*01826a49SYabin Cui "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1168*01826a49SYabin Cui LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1169*01826a49SYabin Cui A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1170*01826a49SYabin Cui OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1171*01826a49SYabin Cui SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1172*01826a49SYabin Cui LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1173*01826a49SYabin Cui DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1174*01826a49SYabin Cui THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1175*01826a49SYabin Cui (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1176*01826a49SYabin Cui OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1177*01826a49SYabin Cui
1178*01826a49SYabin Cui You can contact the author at :
1179*01826a49SYabin Cui - zstd source repository : https://github.com/Cyan4973/zstd
1180*01826a49SYabin Cui - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
1181*01826a49SYabin Cui */
1182*01826a49SYabin Cui
1183*01826a49SYabin Cui /****************************************************************
1184*01826a49SYabin Cui * Tuning parameters
1185*01826a49SYabin Cui *****************************************************************/
1186*01826a49SYabin Cui /* MEMORY_USAGE :
1187*01826a49SYabin Cui * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1188*01826a49SYabin Cui * Increasing memory usage improves compression ratio
1189*01826a49SYabin Cui * Reduced memory usage can improve speed, due to cache effect */
1190*01826a49SYabin Cui #define ZSTD_MEMORY_USAGE 17
1191*01826a49SYabin Cui
1192*01826a49SYabin Cui
1193*01826a49SYabin Cui /**************************************
1194*01826a49SYabin Cui CPU Feature Detection
1195*01826a49SYabin Cui **************************************/
1196*01826a49SYabin Cui /*
1197*01826a49SYabin Cui * Automated efficient unaligned memory access detection
1198*01826a49SYabin Cui * Based on known hardware architectures
1199*01826a49SYabin Cui * This list will be updated thanks to feedbacks
1200*01826a49SYabin Cui */
1201*01826a49SYabin Cui #if defined(CPU_HAS_EFFICIENT_UNALIGNED_MEMORY_ACCESS) \
1202*01826a49SYabin Cui || defined(__ARM_FEATURE_UNALIGNED) \
1203*01826a49SYabin Cui || defined(__i386__) || defined(__x86_64__) \
1204*01826a49SYabin Cui || defined(_M_IX86) || defined(_M_X64) \
1205*01826a49SYabin Cui || defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_8__) \
1206*01826a49SYabin Cui || (defined(_M_ARM) && (_M_ARM >= 7))
1207*01826a49SYabin Cui # define ZSTD_UNALIGNED_ACCESS 1
1208*01826a49SYabin Cui #else
1209*01826a49SYabin Cui # define ZSTD_UNALIGNED_ACCESS 0
1210*01826a49SYabin Cui #endif
1211*01826a49SYabin Cui
1212*01826a49SYabin Cui
1213*01826a49SYabin Cui /********************************************************
1214*01826a49SYabin Cui * Includes
1215*01826a49SYabin Cui *********************************************************/
1216*01826a49SYabin Cui #include <stdlib.h> /* calloc */
1217*01826a49SYabin Cui #include <string.h> /* memcpy, memmove */
1218*01826a49SYabin Cui #include <stdio.h> /* debug : printf */
1219*01826a49SYabin Cui
1220*01826a49SYabin Cui
1221*01826a49SYabin Cui /********************************************************
1222*01826a49SYabin Cui * Compiler specifics
1223*01826a49SYabin Cui *********************************************************/
1224*01826a49SYabin Cui #ifdef __AVX2__
1225*01826a49SYabin Cui # include <immintrin.h> /* AVX2 intrinsics */
1226*01826a49SYabin Cui #endif
1227*01826a49SYabin Cui
1228*01826a49SYabin Cui #ifdef _MSC_VER /* Visual Studio */
1229*01826a49SYabin Cui # include <intrin.h> /* For Visual 2005 */
1230*01826a49SYabin Cui # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1231*01826a49SYabin Cui # pragma warning(disable : 4324) /* disable: C4324: padded structure */
1232*01826a49SYabin Cui #endif
1233*01826a49SYabin Cui
1234*01826a49SYabin Cui
1235*01826a49SYabin Cui #ifndef MEM_ACCESS_MODULE
1236*01826a49SYabin Cui #define MEM_ACCESS_MODULE
1237*01826a49SYabin Cui /********************************************************
1238*01826a49SYabin Cui * Basic Types
1239*01826a49SYabin Cui *********************************************************/
1240*01826a49SYabin Cui #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1241*01826a49SYabin Cui # if defined(_AIX)
1242*01826a49SYabin Cui # include <inttypes.h>
1243*01826a49SYabin Cui # else
1244*01826a49SYabin Cui # include <stdint.h> /* intptr_t */
1245*01826a49SYabin Cui # endif
1246*01826a49SYabin Cui typedef uint8_t BYTE;
1247*01826a49SYabin Cui typedef uint16_t U16;
1248*01826a49SYabin Cui typedef int16_t S16;
1249*01826a49SYabin Cui typedef uint32_t U32;
1250*01826a49SYabin Cui typedef int32_t S32;
1251*01826a49SYabin Cui typedef uint64_t U64;
1252*01826a49SYabin Cui #else
1253*01826a49SYabin Cui typedef unsigned char BYTE;
1254*01826a49SYabin Cui typedef unsigned short U16;
1255*01826a49SYabin Cui typedef signed short S16;
1256*01826a49SYabin Cui typedef unsigned int U32;
1257*01826a49SYabin Cui typedef signed int S32;
1258*01826a49SYabin Cui typedef unsigned long long U64;
1259*01826a49SYabin Cui #endif
1260*01826a49SYabin Cui
1261*01826a49SYabin Cui #endif /* MEM_ACCESS_MODULE */
1262*01826a49SYabin Cui
1263*01826a49SYabin Cui
1264*01826a49SYabin Cui /********************************************************
1265*01826a49SYabin Cui * Constants
1266*01826a49SYabin Cui *********************************************************/
1267*01826a49SYabin Cui static const U32 ZSTD_magicNumber = 0xFD2FB51E; /* 3rd version : seqNb header */
1268*01826a49SYabin Cui
1269*01826a49SYabin Cui #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
1270*01826a49SYabin Cui #define HASH_TABLESIZE (1 << HASH_LOG)
1271*01826a49SYabin Cui #define HASH_MASK (HASH_TABLESIZE - 1)
1272*01826a49SYabin Cui
1273*01826a49SYabin Cui #define KNUTH 2654435761
1274*01826a49SYabin Cui
1275*01826a49SYabin Cui #define BIT7 128
1276*01826a49SYabin Cui #define BIT6 64
1277*01826a49SYabin Cui #define BIT5 32
1278*01826a49SYabin Cui #define BIT4 16
1279*01826a49SYabin Cui
1280*01826a49SYabin Cui #define KB *(1 <<10)
1281*01826a49SYabin Cui #define MB *(1 <<20)
1282*01826a49SYabin Cui #define GB *(1U<<30)
1283*01826a49SYabin Cui
1284*01826a49SYabin Cui #define BLOCKSIZE (128 KB) /* define, for static allocation */
1285*01826a49SYabin Cui
1286*01826a49SYabin Cui #define WORKPLACESIZE (BLOCKSIZE*3)
1287*01826a49SYabin Cui #define MINMATCH 4
1288*01826a49SYabin Cui #define MLbits 7
1289*01826a49SYabin Cui #define LLbits 6
1290*01826a49SYabin Cui #define Offbits 5
1291*01826a49SYabin Cui #define MaxML ((1<<MLbits )-1)
1292*01826a49SYabin Cui #define MaxLL ((1<<LLbits )-1)
1293*01826a49SYabin Cui #define MaxOff ((1<<Offbits)-1)
1294*01826a49SYabin Cui #define LitFSELog 11
1295*01826a49SYabin Cui #define MLFSELog 10
1296*01826a49SYabin Cui #define LLFSELog 10
1297*01826a49SYabin Cui #define OffFSELog 9
1298*01826a49SYabin Cui #define MAX(a,b) ((a)<(b)?(b):(a))
1299*01826a49SYabin Cui #define MaxSeq MAX(MaxLL, MaxML)
1300*01826a49SYabin Cui
1301*01826a49SYabin Cui #define LITERAL_NOENTROPY 63
1302*01826a49SYabin Cui #define COMMAND_NOENTROPY 7 /* to remove */
1303*01826a49SYabin Cui
1304*01826a49SYabin Cui #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
1305*01826a49SYabin Cui
1306*01826a49SYabin Cui static const size_t ZSTD_blockHeaderSize = 3;
1307*01826a49SYabin Cui static const size_t ZSTD_frameHeaderSize = 4;
1308*01826a49SYabin Cui
1309*01826a49SYabin Cui
1310*01826a49SYabin Cui /********************************************************
1311*01826a49SYabin Cui * Memory operations
1312*01826a49SYabin Cui *********************************************************/
ZSTD_32bits(void)1313*01826a49SYabin Cui static unsigned ZSTD_32bits(void) { return sizeof(void*)==4; }
1314*01826a49SYabin Cui
ZSTD_isLittleEndian(void)1315*01826a49SYabin Cui static unsigned ZSTD_isLittleEndian(void)
1316*01826a49SYabin Cui {
1317*01826a49SYabin Cui const union { U32 i; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
1318*01826a49SYabin Cui return one.c[0];
1319*01826a49SYabin Cui }
1320*01826a49SYabin Cui
ZSTD_read16(const void * p)1321*01826a49SYabin Cui static U16 ZSTD_read16(const void* p) { U16 r; memcpy(&r, p, sizeof(r)); return r; }
1322*01826a49SYabin Cui
ZSTD_copy4(void * dst,const void * src)1323*01826a49SYabin Cui static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
1324*01826a49SYabin Cui
ZSTD_copy8(void * dst,const void * src)1325*01826a49SYabin Cui static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
1326*01826a49SYabin Cui
1327*01826a49SYabin Cui #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
1328*01826a49SYabin Cui
ZSTD_wildcopy(void * dst,const void * src,ptrdiff_t length)1329*01826a49SYabin Cui static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
1330*01826a49SYabin Cui {
1331*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
1332*01826a49SYabin Cui BYTE* op = (BYTE*)dst;
1333*01826a49SYabin Cui BYTE* const oend = op + length;
1334*01826a49SYabin Cui while (op < oend) COPY8(op, ip);
1335*01826a49SYabin Cui }
1336*01826a49SYabin Cui
ZSTD_readLE16(const void * memPtr)1337*01826a49SYabin Cui static U16 ZSTD_readLE16(const void* memPtr)
1338*01826a49SYabin Cui {
1339*01826a49SYabin Cui if (ZSTD_isLittleEndian()) return ZSTD_read16(memPtr);
1340*01826a49SYabin Cui else
1341*01826a49SYabin Cui {
1342*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
1343*01826a49SYabin Cui return (U16)((U16)p[0] + ((U16)p[1]<<8));
1344*01826a49SYabin Cui }
1345*01826a49SYabin Cui }
1346*01826a49SYabin Cui
ZSTD_readLE24(const void * memPtr)1347*01826a49SYabin Cui static U32 ZSTD_readLE24(const void* memPtr)
1348*01826a49SYabin Cui {
1349*01826a49SYabin Cui return ZSTD_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
1350*01826a49SYabin Cui }
1351*01826a49SYabin Cui
ZSTD_readBE32(const void * memPtr)1352*01826a49SYabin Cui static U32 ZSTD_readBE32(const void* memPtr)
1353*01826a49SYabin Cui {
1354*01826a49SYabin Cui const BYTE* p = (const BYTE*)memPtr;
1355*01826a49SYabin Cui return (U32)(((U32)p[0]<<24) + ((U32)p[1]<<16) + ((U32)p[2]<<8) + ((U32)p[3]<<0));
1356*01826a49SYabin Cui }
1357*01826a49SYabin Cui
1358*01826a49SYabin Cui
1359*01826a49SYabin Cui /**************************************
1360*01826a49SYabin Cui * Local structures
1361*01826a49SYabin Cui ***************************************/
1362*01826a49SYabin Cui typedef struct ZSTD_Cctx_s ZSTD_Cctx;
1363*01826a49SYabin Cui
1364*01826a49SYabin Cui typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
1365*01826a49SYabin Cui
1366*01826a49SYabin Cui typedef struct
1367*01826a49SYabin Cui {
1368*01826a49SYabin Cui blockType_t blockType;
1369*01826a49SYabin Cui U32 origSize;
1370*01826a49SYabin Cui } blockProperties_t;
1371*01826a49SYabin Cui
1372*01826a49SYabin Cui typedef struct {
1373*01826a49SYabin Cui void* buffer;
1374*01826a49SYabin Cui U32* offsetStart;
1375*01826a49SYabin Cui U32* offset;
1376*01826a49SYabin Cui BYTE* offCodeStart;
1377*01826a49SYabin Cui BYTE* offCode;
1378*01826a49SYabin Cui BYTE* litStart;
1379*01826a49SYabin Cui BYTE* lit;
1380*01826a49SYabin Cui BYTE* litLengthStart;
1381*01826a49SYabin Cui BYTE* litLength;
1382*01826a49SYabin Cui BYTE* matchLengthStart;
1383*01826a49SYabin Cui BYTE* matchLength;
1384*01826a49SYabin Cui BYTE* dumpsStart;
1385*01826a49SYabin Cui BYTE* dumps;
1386*01826a49SYabin Cui } seqStore_t;
1387*01826a49SYabin Cui
1388*01826a49SYabin Cui
1389*01826a49SYabin Cui typedef struct ZSTD_Cctx_s
1390*01826a49SYabin Cui {
1391*01826a49SYabin Cui const BYTE* base;
1392*01826a49SYabin Cui U32 current;
1393*01826a49SYabin Cui U32 nextUpdate;
1394*01826a49SYabin Cui seqStore_t seqStore;
1395*01826a49SYabin Cui #ifdef __AVX2__
1396*01826a49SYabin Cui __m256i hashTable[HASH_TABLESIZE>>3];
1397*01826a49SYabin Cui #else
1398*01826a49SYabin Cui U32 hashTable[HASH_TABLESIZE];
1399*01826a49SYabin Cui #endif
1400*01826a49SYabin Cui BYTE buffer[WORKPLACESIZE];
1401*01826a49SYabin Cui } cctxi_t;
1402*01826a49SYabin Cui
1403*01826a49SYabin Cui
1404*01826a49SYabin Cui
1405*01826a49SYabin Cui
1406*01826a49SYabin Cui /**************************************
1407*01826a49SYabin Cui * Error Management
1408*01826a49SYabin Cui **************************************/
1409*01826a49SYabin Cui /* published entry point */
ZSTDv01_isError(size_t code)1410*01826a49SYabin Cui unsigned ZSTDv01_isError(size_t code) { return ERR_isError(code); }
1411*01826a49SYabin Cui
1412*01826a49SYabin Cui
1413*01826a49SYabin Cui /**************************************
1414*01826a49SYabin Cui * Tool functions
1415*01826a49SYabin Cui **************************************/
1416*01826a49SYabin Cui #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
1417*01826a49SYabin Cui #define ZSTD_VERSION_MINOR 1 /* for new (non-breaking) interface capabilities */
1418*01826a49SYabin Cui #define ZSTD_VERSION_RELEASE 3 /* for tweaks, bug-fixes, or development */
1419*01826a49SYabin Cui #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
1420*01826a49SYabin Cui
1421*01826a49SYabin Cui /**************************************************************
1422*01826a49SYabin Cui * Decompression code
1423*01826a49SYabin Cui **************************************************************/
1424*01826a49SYabin Cui
ZSTDv01_getcBlockSize(const void * src,size_t srcSize,blockProperties_t * bpPtr)1425*01826a49SYabin Cui static size_t ZSTDv01_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
1426*01826a49SYabin Cui {
1427*01826a49SYabin Cui const BYTE* const in = (const BYTE* const)src;
1428*01826a49SYabin Cui BYTE headerFlags;
1429*01826a49SYabin Cui U32 cSize;
1430*01826a49SYabin Cui
1431*01826a49SYabin Cui if (srcSize < 3) return ERROR(srcSize_wrong);
1432*01826a49SYabin Cui
1433*01826a49SYabin Cui headerFlags = *in;
1434*01826a49SYabin Cui cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
1435*01826a49SYabin Cui
1436*01826a49SYabin Cui bpPtr->blockType = (blockType_t)(headerFlags >> 6);
1437*01826a49SYabin Cui bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
1438*01826a49SYabin Cui
1439*01826a49SYabin Cui if (bpPtr->blockType == bt_end) return 0;
1440*01826a49SYabin Cui if (bpPtr->blockType == bt_rle) return 1;
1441*01826a49SYabin Cui return cSize;
1442*01826a49SYabin Cui }
1443*01826a49SYabin Cui
1444*01826a49SYabin Cui
ZSTD_copyUncompressedBlock(void * dst,size_t maxDstSize,const void * src,size_t srcSize)1445*01826a49SYabin Cui static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
1446*01826a49SYabin Cui {
1447*01826a49SYabin Cui if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
1448*01826a49SYabin Cui if (srcSize > 0) {
1449*01826a49SYabin Cui memcpy(dst, src, srcSize);
1450*01826a49SYabin Cui }
1451*01826a49SYabin Cui return srcSize;
1452*01826a49SYabin Cui }
1453*01826a49SYabin Cui
1454*01826a49SYabin Cui
ZSTD_decompressLiterals(void * ctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)1455*01826a49SYabin Cui static size_t ZSTD_decompressLiterals(void* ctx,
1456*01826a49SYabin Cui void* dst, size_t maxDstSize,
1457*01826a49SYabin Cui const void* src, size_t srcSize)
1458*01826a49SYabin Cui {
1459*01826a49SYabin Cui BYTE* op = (BYTE*)dst;
1460*01826a49SYabin Cui BYTE* const oend = op + maxDstSize;
1461*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
1462*01826a49SYabin Cui size_t errorCode;
1463*01826a49SYabin Cui size_t litSize;
1464*01826a49SYabin Cui
1465*01826a49SYabin Cui /* check : minimum 2, for litSize, +1, for content */
1466*01826a49SYabin Cui if (srcSize <= 3) return ERROR(corruption_detected);
1467*01826a49SYabin Cui
1468*01826a49SYabin Cui litSize = ip[1] + (ip[0]<<8);
1469*01826a49SYabin Cui litSize += ((ip[-3] >> 3) & 7) << 16; /* mmmmh.... */
1470*01826a49SYabin Cui op = oend - litSize;
1471*01826a49SYabin Cui
1472*01826a49SYabin Cui (void)ctx;
1473*01826a49SYabin Cui if (litSize > maxDstSize) return ERROR(dstSize_tooSmall);
1474*01826a49SYabin Cui errorCode = HUF_decompress(op, litSize, ip+2, srcSize-2);
1475*01826a49SYabin Cui if (FSE_isError(errorCode)) return ERROR(GENERIC);
1476*01826a49SYabin Cui return litSize;
1477*01826a49SYabin Cui }
1478*01826a49SYabin Cui
1479*01826a49SYabin Cui
ZSTDv01_decodeLiteralsBlock(void * ctx,void * dst,size_t maxDstSize,const BYTE ** litStart,size_t * litSize,const void * src,size_t srcSize)1480*01826a49SYabin Cui static size_t ZSTDv01_decodeLiteralsBlock(void* ctx,
1481*01826a49SYabin Cui void* dst, size_t maxDstSize,
1482*01826a49SYabin Cui const BYTE** litStart, size_t* litSize,
1483*01826a49SYabin Cui const void* src, size_t srcSize)
1484*01826a49SYabin Cui {
1485*01826a49SYabin Cui const BYTE* const istart = (const BYTE* const)src;
1486*01826a49SYabin Cui const BYTE* ip = istart;
1487*01826a49SYabin Cui BYTE* const ostart = (BYTE* const)dst;
1488*01826a49SYabin Cui BYTE* const oend = ostart + maxDstSize;
1489*01826a49SYabin Cui blockProperties_t litbp;
1490*01826a49SYabin Cui
1491*01826a49SYabin Cui size_t litcSize = ZSTDv01_getcBlockSize(src, srcSize, &litbp);
1492*01826a49SYabin Cui if (ZSTDv01_isError(litcSize)) return litcSize;
1493*01826a49SYabin Cui if (litcSize > srcSize - ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
1494*01826a49SYabin Cui ip += ZSTD_blockHeaderSize;
1495*01826a49SYabin Cui
1496*01826a49SYabin Cui switch(litbp.blockType)
1497*01826a49SYabin Cui {
1498*01826a49SYabin Cui case bt_raw:
1499*01826a49SYabin Cui *litStart = ip;
1500*01826a49SYabin Cui ip += litcSize;
1501*01826a49SYabin Cui *litSize = litcSize;
1502*01826a49SYabin Cui break;
1503*01826a49SYabin Cui case bt_rle:
1504*01826a49SYabin Cui {
1505*01826a49SYabin Cui size_t rleSize = litbp.origSize;
1506*01826a49SYabin Cui if (rleSize>maxDstSize) return ERROR(dstSize_tooSmall);
1507*01826a49SYabin Cui if (!srcSize) return ERROR(srcSize_wrong);
1508*01826a49SYabin Cui if (rleSize > 0) {
1509*01826a49SYabin Cui memset(oend - rleSize, *ip, rleSize);
1510*01826a49SYabin Cui }
1511*01826a49SYabin Cui *litStart = oend - rleSize;
1512*01826a49SYabin Cui *litSize = rleSize;
1513*01826a49SYabin Cui ip++;
1514*01826a49SYabin Cui break;
1515*01826a49SYabin Cui }
1516*01826a49SYabin Cui case bt_compressed:
1517*01826a49SYabin Cui {
1518*01826a49SYabin Cui size_t decodedLitSize = ZSTD_decompressLiterals(ctx, dst, maxDstSize, ip, litcSize);
1519*01826a49SYabin Cui if (ZSTDv01_isError(decodedLitSize)) return decodedLitSize;
1520*01826a49SYabin Cui *litStart = oend - decodedLitSize;
1521*01826a49SYabin Cui *litSize = decodedLitSize;
1522*01826a49SYabin Cui ip += litcSize;
1523*01826a49SYabin Cui break;
1524*01826a49SYabin Cui }
1525*01826a49SYabin Cui case bt_end:
1526*01826a49SYabin Cui default:
1527*01826a49SYabin Cui return ERROR(GENERIC);
1528*01826a49SYabin Cui }
1529*01826a49SYabin Cui
1530*01826a49SYabin Cui return ip-istart;
1531*01826a49SYabin Cui }
1532*01826a49SYabin Cui
1533*01826a49SYabin Cui
ZSTDv01_decodeSeqHeaders(int * nbSeq,const BYTE ** dumpsPtr,size_t * dumpsLengthPtr,FSE_DTable * DTableLL,FSE_DTable * DTableML,FSE_DTable * DTableOffb,const void * src,size_t srcSize)1534*01826a49SYabin Cui static size_t ZSTDv01_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
1535*01826a49SYabin Cui FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
1536*01826a49SYabin Cui const void* src, size_t srcSize)
1537*01826a49SYabin Cui {
1538*01826a49SYabin Cui const BYTE* const istart = (const BYTE* const)src;
1539*01826a49SYabin Cui const BYTE* ip = istart;
1540*01826a49SYabin Cui const BYTE* const iend = istart + srcSize;
1541*01826a49SYabin Cui U32 LLtype, Offtype, MLtype;
1542*01826a49SYabin Cui U32 LLlog, Offlog, MLlog;
1543*01826a49SYabin Cui size_t dumpsLength;
1544*01826a49SYabin Cui
1545*01826a49SYabin Cui /* check */
1546*01826a49SYabin Cui if (srcSize < 5) return ERROR(srcSize_wrong);
1547*01826a49SYabin Cui
1548*01826a49SYabin Cui /* SeqHead */
1549*01826a49SYabin Cui *nbSeq = ZSTD_readLE16(ip); ip+=2;
1550*01826a49SYabin Cui LLtype = *ip >> 6;
1551*01826a49SYabin Cui Offtype = (*ip >> 4) & 3;
1552*01826a49SYabin Cui MLtype = (*ip >> 2) & 3;
1553*01826a49SYabin Cui if (*ip & 2)
1554*01826a49SYabin Cui {
1555*01826a49SYabin Cui dumpsLength = ip[2];
1556*01826a49SYabin Cui dumpsLength += ip[1] << 8;
1557*01826a49SYabin Cui ip += 3;
1558*01826a49SYabin Cui }
1559*01826a49SYabin Cui else
1560*01826a49SYabin Cui {
1561*01826a49SYabin Cui dumpsLength = ip[1];
1562*01826a49SYabin Cui dumpsLength += (ip[0] & 1) << 8;
1563*01826a49SYabin Cui ip += 2;
1564*01826a49SYabin Cui }
1565*01826a49SYabin Cui *dumpsPtr = ip;
1566*01826a49SYabin Cui ip += dumpsLength;
1567*01826a49SYabin Cui *dumpsLengthPtr = dumpsLength;
1568*01826a49SYabin Cui
1569*01826a49SYabin Cui /* check */
1570*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 */
1571*01826a49SYabin Cui
1572*01826a49SYabin Cui /* sequences */
1573*01826a49SYabin Cui {
1574*01826a49SYabin Cui S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
1575*01826a49SYabin Cui size_t headerSize;
1576*01826a49SYabin Cui
1577*01826a49SYabin Cui /* Build DTables */
1578*01826a49SYabin Cui switch(LLtype)
1579*01826a49SYabin Cui {
1580*01826a49SYabin Cui case bt_rle :
1581*01826a49SYabin Cui LLlog = 0;
1582*01826a49SYabin Cui FSE_buildDTable_rle(DTableLL, *ip++); break;
1583*01826a49SYabin Cui case bt_raw :
1584*01826a49SYabin Cui LLlog = LLbits;
1585*01826a49SYabin Cui FSE_buildDTable_raw(DTableLL, LLbits); break;
1586*01826a49SYabin Cui default :
1587*01826a49SYabin Cui { U32 max = MaxLL;
1588*01826a49SYabin Cui headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
1589*01826a49SYabin Cui if (FSE_isError(headerSize)) return ERROR(GENERIC);
1590*01826a49SYabin Cui if (LLlog > LLFSELog) return ERROR(corruption_detected);
1591*01826a49SYabin Cui ip += headerSize;
1592*01826a49SYabin Cui FSE_buildDTable(DTableLL, norm, max, LLlog);
1593*01826a49SYabin Cui } }
1594*01826a49SYabin Cui
1595*01826a49SYabin Cui switch(Offtype)
1596*01826a49SYabin Cui {
1597*01826a49SYabin Cui case bt_rle :
1598*01826a49SYabin Cui Offlog = 0;
1599*01826a49SYabin Cui if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
1600*01826a49SYabin Cui FSE_buildDTable_rle(DTableOffb, *ip++); break;
1601*01826a49SYabin Cui case bt_raw :
1602*01826a49SYabin Cui Offlog = Offbits;
1603*01826a49SYabin Cui FSE_buildDTable_raw(DTableOffb, Offbits); break;
1604*01826a49SYabin Cui default :
1605*01826a49SYabin Cui { U32 max = MaxOff;
1606*01826a49SYabin Cui headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
1607*01826a49SYabin Cui if (FSE_isError(headerSize)) return ERROR(GENERIC);
1608*01826a49SYabin Cui if (Offlog > OffFSELog) return ERROR(corruption_detected);
1609*01826a49SYabin Cui ip += headerSize;
1610*01826a49SYabin Cui FSE_buildDTable(DTableOffb, norm, max, Offlog);
1611*01826a49SYabin Cui } }
1612*01826a49SYabin Cui
1613*01826a49SYabin Cui switch(MLtype)
1614*01826a49SYabin Cui {
1615*01826a49SYabin Cui case bt_rle :
1616*01826a49SYabin Cui MLlog = 0;
1617*01826a49SYabin Cui if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
1618*01826a49SYabin Cui FSE_buildDTable_rle(DTableML, *ip++); break;
1619*01826a49SYabin Cui case bt_raw :
1620*01826a49SYabin Cui MLlog = MLbits;
1621*01826a49SYabin Cui FSE_buildDTable_raw(DTableML, MLbits); break;
1622*01826a49SYabin Cui default :
1623*01826a49SYabin Cui { U32 max = MaxML;
1624*01826a49SYabin Cui headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
1625*01826a49SYabin Cui if (FSE_isError(headerSize)) return ERROR(GENERIC);
1626*01826a49SYabin Cui if (MLlog > MLFSELog) return ERROR(corruption_detected);
1627*01826a49SYabin Cui ip += headerSize;
1628*01826a49SYabin Cui FSE_buildDTable(DTableML, norm, max, MLlog);
1629*01826a49SYabin Cui } } }
1630*01826a49SYabin Cui
1631*01826a49SYabin Cui return ip-istart;
1632*01826a49SYabin Cui }
1633*01826a49SYabin Cui
1634*01826a49SYabin Cui
1635*01826a49SYabin Cui typedef struct {
1636*01826a49SYabin Cui size_t litLength;
1637*01826a49SYabin Cui size_t offset;
1638*01826a49SYabin Cui size_t matchLength;
1639*01826a49SYabin Cui } seq_t;
1640*01826a49SYabin Cui
1641*01826a49SYabin Cui typedef struct {
1642*01826a49SYabin Cui FSE_DStream_t DStream;
1643*01826a49SYabin Cui FSE_DState_t stateLL;
1644*01826a49SYabin Cui FSE_DState_t stateOffb;
1645*01826a49SYabin Cui FSE_DState_t stateML;
1646*01826a49SYabin Cui size_t prevOffset;
1647*01826a49SYabin Cui const BYTE* dumps;
1648*01826a49SYabin Cui const BYTE* dumpsEnd;
1649*01826a49SYabin Cui } seqState_t;
1650*01826a49SYabin Cui
1651*01826a49SYabin Cui
ZSTD_decodeSequence(seq_t * seq,seqState_t * seqState)1652*01826a49SYabin Cui static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
1653*01826a49SYabin Cui {
1654*01826a49SYabin Cui size_t litLength;
1655*01826a49SYabin Cui size_t prevOffset;
1656*01826a49SYabin Cui size_t offset;
1657*01826a49SYabin Cui size_t matchLength;
1658*01826a49SYabin Cui const BYTE* dumps = seqState->dumps;
1659*01826a49SYabin Cui const BYTE* const de = seqState->dumpsEnd;
1660*01826a49SYabin Cui
1661*01826a49SYabin Cui /* Literal length */
1662*01826a49SYabin Cui litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
1663*01826a49SYabin Cui prevOffset = litLength ? seq->offset : seqState->prevOffset;
1664*01826a49SYabin Cui seqState->prevOffset = seq->offset;
1665*01826a49SYabin Cui if (litLength == MaxLL)
1666*01826a49SYabin Cui {
1667*01826a49SYabin Cui const U32 add = dumps<de ? *dumps++ : 0;
1668*01826a49SYabin Cui if (add < 255) litLength += add;
1669*01826a49SYabin Cui else
1670*01826a49SYabin Cui {
1671*01826a49SYabin Cui if (dumps<=(de-3))
1672*01826a49SYabin Cui {
1673*01826a49SYabin Cui litLength = ZSTD_readLE24(dumps);
1674*01826a49SYabin Cui dumps += 3;
1675*01826a49SYabin Cui }
1676*01826a49SYabin Cui }
1677*01826a49SYabin Cui }
1678*01826a49SYabin Cui
1679*01826a49SYabin Cui /* Offset */
1680*01826a49SYabin Cui {
1681*01826a49SYabin Cui U32 offsetCode, nbBits;
1682*01826a49SYabin Cui offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream));
1683*01826a49SYabin Cui if (ZSTD_32bits()) FSE_reloadDStream(&(seqState->DStream));
1684*01826a49SYabin Cui nbBits = offsetCode - 1;
1685*01826a49SYabin Cui if (offsetCode==0) nbBits = 0; /* cmove */
1686*01826a49SYabin Cui offset = ((size_t)1 << (nbBits & ((sizeof(offset)*8)-1))) + FSE_readBits(&(seqState->DStream), nbBits);
1687*01826a49SYabin Cui if (ZSTD_32bits()) FSE_reloadDStream(&(seqState->DStream));
1688*01826a49SYabin Cui if (offsetCode==0) offset = prevOffset;
1689*01826a49SYabin Cui }
1690*01826a49SYabin Cui
1691*01826a49SYabin Cui /* MatchLength */
1692*01826a49SYabin Cui matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
1693*01826a49SYabin Cui if (matchLength == MaxML)
1694*01826a49SYabin Cui {
1695*01826a49SYabin Cui const U32 add = dumps<de ? *dumps++ : 0;
1696*01826a49SYabin Cui if (add < 255) matchLength += add;
1697*01826a49SYabin Cui else
1698*01826a49SYabin Cui {
1699*01826a49SYabin Cui if (dumps<=(de-3))
1700*01826a49SYabin Cui {
1701*01826a49SYabin Cui matchLength = ZSTD_readLE24(dumps);
1702*01826a49SYabin Cui dumps += 3;
1703*01826a49SYabin Cui }
1704*01826a49SYabin Cui }
1705*01826a49SYabin Cui }
1706*01826a49SYabin Cui matchLength += MINMATCH;
1707*01826a49SYabin Cui
1708*01826a49SYabin Cui /* save result */
1709*01826a49SYabin Cui seq->litLength = litLength;
1710*01826a49SYabin Cui seq->offset = offset;
1711*01826a49SYabin Cui seq->matchLength = matchLength;
1712*01826a49SYabin Cui seqState->dumps = dumps;
1713*01826a49SYabin Cui }
1714*01826a49SYabin Cui
1715*01826a49SYabin Cui
ZSTD_execSequence(BYTE * op,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,BYTE * const base,BYTE * const oend)1716*01826a49SYabin Cui static size_t ZSTD_execSequence(BYTE* op,
1717*01826a49SYabin Cui seq_t sequence,
1718*01826a49SYabin Cui const BYTE** litPtr, const BYTE* const litLimit,
1719*01826a49SYabin Cui BYTE* const base, BYTE* const oend)
1720*01826a49SYabin Cui {
1721*01826a49SYabin Cui static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
1722*01826a49SYabin Cui static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */
1723*01826a49SYabin Cui const BYTE* const ostart = op;
1724*01826a49SYabin Cui BYTE* const oLitEnd = op + sequence.litLength;
1725*01826a49SYabin Cui const size_t litLength = sequence.litLength;
1726*01826a49SYabin Cui BYTE* const endMatch = op + litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
1727*01826a49SYabin Cui const BYTE* const litEnd = *litPtr + litLength;
1728*01826a49SYabin Cui
1729*01826a49SYabin Cui /* checks */
1730*01826a49SYabin Cui size_t const seqLength = sequence.litLength + sequence.matchLength;
1731*01826a49SYabin Cui
1732*01826a49SYabin Cui if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
1733*01826a49SYabin Cui if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
1734*01826a49SYabin Cui /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
1735*01826a49SYabin Cui if (sequence.offset > (U32)(oLitEnd - base)) return ERROR(corruption_detected);
1736*01826a49SYabin Cui
1737*01826a49SYabin Cui if (endMatch > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
1738*01826a49SYabin Cui if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
1739*01826a49SYabin Cui if (sequence.matchLength > (size_t)(*litPtr-op)) return ERROR(dstSize_tooSmall); /* overwrite literal segment */
1740*01826a49SYabin Cui
1741*01826a49SYabin Cui /* copy Literals */
1742*01826a49SYabin Cui ZSTD_memmove(op, *litPtr, sequence.litLength); /* note : v0.1 seems to allow scenarios where output or input are close to end of buffer */
1743*01826a49SYabin Cui
1744*01826a49SYabin Cui op += litLength;
1745*01826a49SYabin Cui *litPtr = litEnd; /* update for next sequence */
1746*01826a49SYabin Cui
1747*01826a49SYabin Cui /* check : last match must be at a minimum distance of 8 from end of dest buffer */
1748*01826a49SYabin Cui if (oend-op < 8) return ERROR(dstSize_tooSmall);
1749*01826a49SYabin Cui
1750*01826a49SYabin Cui /* copy Match */
1751*01826a49SYabin Cui {
1752*01826a49SYabin Cui const U32 overlapRisk = (((size_t)(litEnd - endMatch)) < 12);
1753*01826a49SYabin Cui const BYTE* match = op - sequence.offset; /* possible underflow at op - offset ? */
1754*01826a49SYabin Cui size_t qutt = 12;
1755*01826a49SYabin Cui U64 saved[2];
1756*01826a49SYabin Cui
1757*01826a49SYabin Cui /* check */
1758*01826a49SYabin Cui if (match < base) return ERROR(corruption_detected);
1759*01826a49SYabin Cui if (sequence.offset > (size_t)base) return ERROR(corruption_detected);
1760*01826a49SYabin Cui
1761*01826a49SYabin Cui /* save beginning of literal sequence, in case of write overlap */
1762*01826a49SYabin Cui if (overlapRisk)
1763*01826a49SYabin Cui {
1764*01826a49SYabin Cui if ((endMatch + qutt) > oend) qutt = oend-endMatch;
1765*01826a49SYabin Cui memcpy(saved, endMatch, qutt);
1766*01826a49SYabin Cui }
1767*01826a49SYabin Cui
1768*01826a49SYabin Cui if (sequence.offset < 8)
1769*01826a49SYabin Cui {
1770*01826a49SYabin Cui const int dec64 = dec64table[sequence.offset];
1771*01826a49SYabin Cui op[0] = match[0];
1772*01826a49SYabin Cui op[1] = match[1];
1773*01826a49SYabin Cui op[2] = match[2];
1774*01826a49SYabin Cui op[3] = match[3];
1775*01826a49SYabin Cui match += dec32table[sequence.offset];
1776*01826a49SYabin Cui ZSTD_copy4(op+4, match);
1777*01826a49SYabin Cui match -= dec64;
1778*01826a49SYabin Cui } else { ZSTD_copy8(op, match); }
1779*01826a49SYabin Cui op += 8; match += 8;
1780*01826a49SYabin Cui
1781*01826a49SYabin Cui if (endMatch > oend-(16-MINMATCH))
1782*01826a49SYabin Cui {
1783*01826a49SYabin Cui if (op < oend-8)
1784*01826a49SYabin Cui {
1785*01826a49SYabin Cui ZSTD_wildcopy(op, match, (oend-8) - op);
1786*01826a49SYabin Cui match += (oend-8) - op;
1787*01826a49SYabin Cui op = oend-8;
1788*01826a49SYabin Cui }
1789*01826a49SYabin Cui while (op<endMatch) *op++ = *match++;
1790*01826a49SYabin Cui }
1791*01826a49SYabin Cui else
1792*01826a49SYabin Cui ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
1793*01826a49SYabin Cui
1794*01826a49SYabin Cui /* restore, in case of overlap */
1795*01826a49SYabin Cui if (overlapRisk) memcpy(endMatch, saved, qutt);
1796*01826a49SYabin Cui }
1797*01826a49SYabin Cui
1798*01826a49SYabin Cui return endMatch-ostart;
1799*01826a49SYabin Cui }
1800*01826a49SYabin Cui
1801*01826a49SYabin Cui typedef struct ZSTDv01_Dctx_s
1802*01826a49SYabin Cui {
1803*01826a49SYabin Cui U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
1804*01826a49SYabin Cui U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
1805*01826a49SYabin Cui U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
1806*01826a49SYabin Cui void* previousDstEnd;
1807*01826a49SYabin Cui void* base;
1808*01826a49SYabin Cui size_t expected;
1809*01826a49SYabin Cui blockType_t bType;
1810*01826a49SYabin Cui U32 phase;
1811*01826a49SYabin Cui } dctx_t;
1812*01826a49SYabin Cui
1813*01826a49SYabin Cui
ZSTD_decompressSequences(void * ctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,const BYTE * litStart,size_t litSize)1814*01826a49SYabin Cui static size_t ZSTD_decompressSequences(
1815*01826a49SYabin Cui void* ctx,
1816*01826a49SYabin Cui void* dst, size_t maxDstSize,
1817*01826a49SYabin Cui const void* seqStart, size_t seqSize,
1818*01826a49SYabin Cui const BYTE* litStart, size_t litSize)
1819*01826a49SYabin Cui {
1820*01826a49SYabin Cui dctx_t* dctx = (dctx_t*)ctx;
1821*01826a49SYabin Cui const BYTE* ip = (const BYTE*)seqStart;
1822*01826a49SYabin Cui const BYTE* const iend = ip + seqSize;
1823*01826a49SYabin Cui BYTE* const ostart = (BYTE* const)dst;
1824*01826a49SYabin Cui BYTE* op = ostart;
1825*01826a49SYabin Cui BYTE* const oend = ostart + maxDstSize;
1826*01826a49SYabin Cui size_t errorCode, dumpsLength;
1827*01826a49SYabin Cui const BYTE* litPtr = litStart;
1828*01826a49SYabin Cui const BYTE* const litEnd = litStart + litSize;
1829*01826a49SYabin Cui int nbSeq;
1830*01826a49SYabin Cui const BYTE* dumps;
1831*01826a49SYabin Cui U32* DTableLL = dctx->LLTable;
1832*01826a49SYabin Cui U32* DTableML = dctx->MLTable;
1833*01826a49SYabin Cui U32* DTableOffb = dctx->OffTable;
1834*01826a49SYabin Cui BYTE* const base = (BYTE*) (dctx->base);
1835*01826a49SYabin Cui
1836*01826a49SYabin Cui /* Build Decoding Tables */
1837*01826a49SYabin Cui errorCode = ZSTDv01_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
1838*01826a49SYabin Cui DTableLL, DTableML, DTableOffb,
1839*01826a49SYabin Cui ip, iend-ip);
1840*01826a49SYabin Cui if (ZSTDv01_isError(errorCode)) return errorCode;
1841*01826a49SYabin Cui ip += errorCode;
1842*01826a49SYabin Cui
1843*01826a49SYabin Cui /* Regen sequences */
1844*01826a49SYabin Cui {
1845*01826a49SYabin Cui seq_t sequence;
1846*01826a49SYabin Cui seqState_t seqState;
1847*01826a49SYabin Cui
1848*01826a49SYabin Cui memset(&sequence, 0, sizeof(sequence));
1849*01826a49SYabin Cui seqState.dumps = dumps;
1850*01826a49SYabin Cui seqState.dumpsEnd = dumps + dumpsLength;
1851*01826a49SYabin Cui seqState.prevOffset = 1;
1852*01826a49SYabin Cui errorCode = FSE_initDStream(&(seqState.DStream), ip, iend-ip);
1853*01826a49SYabin Cui if (FSE_isError(errorCode)) return ERROR(corruption_detected);
1854*01826a49SYabin Cui FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
1855*01826a49SYabin Cui FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
1856*01826a49SYabin Cui FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
1857*01826a49SYabin Cui
1858*01826a49SYabin Cui for ( ; (FSE_reloadDStream(&(seqState.DStream)) <= FSE_DStream_completed) && (nbSeq>0) ; )
1859*01826a49SYabin Cui {
1860*01826a49SYabin Cui size_t oneSeqSize;
1861*01826a49SYabin Cui nbSeq--;
1862*01826a49SYabin Cui ZSTD_decodeSequence(&sequence, &seqState);
1863*01826a49SYabin Cui oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
1864*01826a49SYabin Cui if (ZSTDv01_isError(oneSeqSize)) return oneSeqSize;
1865*01826a49SYabin Cui op += oneSeqSize;
1866*01826a49SYabin Cui }
1867*01826a49SYabin Cui
1868*01826a49SYabin Cui /* check if reached exact end */
1869*01826a49SYabin Cui if ( !FSE_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
1870*01826a49SYabin Cui if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
1871*01826a49SYabin Cui
1872*01826a49SYabin Cui /* last literal segment */
1873*01826a49SYabin Cui {
1874*01826a49SYabin Cui size_t lastLLSize = litEnd - litPtr;
1875*01826a49SYabin Cui if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
1876*01826a49SYabin Cui if (lastLLSize > 0) {
1877*01826a49SYabin Cui if (op != litPtr) memmove(op, litPtr, lastLLSize);
1878*01826a49SYabin Cui op += lastLLSize;
1879*01826a49SYabin Cui }
1880*01826a49SYabin Cui }
1881*01826a49SYabin Cui }
1882*01826a49SYabin Cui
1883*01826a49SYabin Cui return op-ostart;
1884*01826a49SYabin Cui }
1885*01826a49SYabin Cui
1886*01826a49SYabin Cui
ZSTD_decompressBlock(void * ctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)1887*01826a49SYabin Cui static size_t ZSTD_decompressBlock(
1888*01826a49SYabin Cui void* ctx,
1889*01826a49SYabin Cui void* dst, size_t maxDstSize,
1890*01826a49SYabin Cui const void* src, size_t srcSize)
1891*01826a49SYabin Cui {
1892*01826a49SYabin Cui /* blockType == blockCompressed, srcSize is trusted */
1893*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
1894*01826a49SYabin Cui const BYTE* litPtr = NULL;
1895*01826a49SYabin Cui size_t litSize = 0;
1896*01826a49SYabin Cui size_t errorCode;
1897*01826a49SYabin Cui
1898*01826a49SYabin Cui /* Decode literals sub-block */
1899*01826a49SYabin Cui errorCode = ZSTDv01_decodeLiteralsBlock(ctx, dst, maxDstSize, &litPtr, &litSize, src, srcSize);
1900*01826a49SYabin Cui if (ZSTDv01_isError(errorCode)) return errorCode;
1901*01826a49SYabin Cui ip += errorCode;
1902*01826a49SYabin Cui srcSize -= errorCode;
1903*01826a49SYabin Cui
1904*01826a49SYabin Cui return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize, litPtr, litSize);
1905*01826a49SYabin Cui }
1906*01826a49SYabin Cui
1907*01826a49SYabin Cui
ZSTDv01_decompressDCtx(void * ctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)1908*01826a49SYabin Cui size_t ZSTDv01_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
1909*01826a49SYabin Cui {
1910*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
1911*01826a49SYabin Cui const BYTE* iend = ip + srcSize;
1912*01826a49SYabin Cui BYTE* const ostart = (BYTE* const)dst;
1913*01826a49SYabin Cui BYTE* op = ostart;
1914*01826a49SYabin Cui BYTE* const oend = ostart + maxDstSize;
1915*01826a49SYabin Cui size_t remainingSize = srcSize;
1916*01826a49SYabin Cui U32 magicNumber;
1917*01826a49SYabin Cui size_t errorCode=0;
1918*01826a49SYabin Cui blockProperties_t blockProperties;
1919*01826a49SYabin Cui
1920*01826a49SYabin Cui /* Frame Header */
1921*01826a49SYabin Cui if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
1922*01826a49SYabin Cui magicNumber = ZSTD_readBE32(src);
1923*01826a49SYabin Cui if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
1924*01826a49SYabin Cui ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
1925*01826a49SYabin Cui
1926*01826a49SYabin Cui /* Loop on each block */
1927*01826a49SYabin Cui while (1)
1928*01826a49SYabin Cui {
1929*01826a49SYabin Cui size_t blockSize = ZSTDv01_getcBlockSize(ip, iend-ip, &blockProperties);
1930*01826a49SYabin Cui if (ZSTDv01_isError(blockSize)) return blockSize;
1931*01826a49SYabin Cui
1932*01826a49SYabin Cui ip += ZSTD_blockHeaderSize;
1933*01826a49SYabin Cui remainingSize -= ZSTD_blockHeaderSize;
1934*01826a49SYabin Cui if (blockSize > remainingSize) return ERROR(srcSize_wrong);
1935*01826a49SYabin Cui
1936*01826a49SYabin Cui switch(blockProperties.blockType)
1937*01826a49SYabin Cui {
1938*01826a49SYabin Cui case bt_compressed:
1939*01826a49SYabin Cui errorCode = ZSTD_decompressBlock(ctx, op, oend-op, ip, blockSize);
1940*01826a49SYabin Cui break;
1941*01826a49SYabin Cui case bt_raw :
1942*01826a49SYabin Cui errorCode = ZSTD_copyUncompressedBlock(op, oend-op, ip, blockSize);
1943*01826a49SYabin Cui break;
1944*01826a49SYabin Cui case bt_rle :
1945*01826a49SYabin Cui return ERROR(GENERIC); /* not yet supported */
1946*01826a49SYabin Cui break;
1947*01826a49SYabin Cui case bt_end :
1948*01826a49SYabin Cui /* end of frame */
1949*01826a49SYabin Cui if (remainingSize) return ERROR(srcSize_wrong);
1950*01826a49SYabin Cui break;
1951*01826a49SYabin Cui default:
1952*01826a49SYabin Cui return ERROR(GENERIC);
1953*01826a49SYabin Cui }
1954*01826a49SYabin Cui if (blockSize == 0) break; /* bt_end */
1955*01826a49SYabin Cui
1956*01826a49SYabin Cui if (ZSTDv01_isError(errorCode)) return errorCode;
1957*01826a49SYabin Cui op += errorCode;
1958*01826a49SYabin Cui ip += blockSize;
1959*01826a49SYabin Cui remainingSize -= blockSize;
1960*01826a49SYabin Cui }
1961*01826a49SYabin Cui
1962*01826a49SYabin Cui return op-ostart;
1963*01826a49SYabin Cui }
1964*01826a49SYabin Cui
ZSTDv01_decompress(void * dst,size_t maxDstSize,const void * src,size_t srcSize)1965*01826a49SYabin Cui size_t ZSTDv01_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
1966*01826a49SYabin Cui {
1967*01826a49SYabin Cui dctx_t ctx;
1968*01826a49SYabin Cui ctx.base = dst;
1969*01826a49SYabin Cui return ZSTDv01_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
1970*01826a49SYabin Cui }
1971*01826a49SYabin Cui
1972*01826a49SYabin Cui /* ZSTD_errorFrameSizeInfoLegacy() :
1973*01826a49SYabin Cui assumes `cSize` and `dBound` are _not_ NULL */
ZSTD_errorFrameSizeInfoLegacy(size_t * cSize,unsigned long long * dBound,size_t ret)1974*01826a49SYabin Cui static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
1975*01826a49SYabin Cui {
1976*01826a49SYabin Cui *cSize = ret;
1977*01826a49SYabin Cui *dBound = ZSTD_CONTENTSIZE_ERROR;
1978*01826a49SYabin Cui }
1979*01826a49SYabin Cui
ZSTDv01_findFrameSizeInfoLegacy(const void * src,size_t srcSize,size_t * cSize,unsigned long long * dBound)1980*01826a49SYabin Cui void ZSTDv01_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
1981*01826a49SYabin Cui {
1982*01826a49SYabin Cui const BYTE* ip = (const BYTE*)src;
1983*01826a49SYabin Cui size_t remainingSize = srcSize;
1984*01826a49SYabin Cui size_t nbBlocks = 0;
1985*01826a49SYabin Cui U32 magicNumber;
1986*01826a49SYabin Cui blockProperties_t blockProperties;
1987*01826a49SYabin Cui
1988*01826a49SYabin Cui /* Frame Header */
1989*01826a49SYabin Cui if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
1990*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
1991*01826a49SYabin Cui return;
1992*01826a49SYabin Cui }
1993*01826a49SYabin Cui magicNumber = ZSTD_readBE32(src);
1994*01826a49SYabin Cui if (magicNumber != ZSTD_magicNumber) {
1995*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
1996*01826a49SYabin Cui return;
1997*01826a49SYabin Cui }
1998*01826a49SYabin Cui ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
1999*01826a49SYabin Cui
2000*01826a49SYabin Cui /* Loop on each block */
2001*01826a49SYabin Cui while (1)
2002*01826a49SYabin Cui {
2003*01826a49SYabin Cui size_t blockSize = ZSTDv01_getcBlockSize(ip, remainingSize, &blockProperties);
2004*01826a49SYabin Cui if (ZSTDv01_isError(blockSize)) {
2005*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, blockSize);
2006*01826a49SYabin Cui return;
2007*01826a49SYabin Cui }
2008*01826a49SYabin Cui
2009*01826a49SYabin Cui ip += ZSTD_blockHeaderSize;
2010*01826a49SYabin Cui remainingSize -= ZSTD_blockHeaderSize;
2011*01826a49SYabin Cui if (blockSize > remainingSize) {
2012*01826a49SYabin Cui ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2013*01826a49SYabin Cui return;
2014*01826a49SYabin Cui }
2015*01826a49SYabin Cui
2016*01826a49SYabin Cui if (blockSize == 0) break; /* bt_end */
2017*01826a49SYabin Cui
2018*01826a49SYabin Cui ip += blockSize;
2019*01826a49SYabin Cui remainingSize -= blockSize;
2020*01826a49SYabin Cui nbBlocks++;
2021*01826a49SYabin Cui }
2022*01826a49SYabin Cui
2023*01826a49SYabin Cui *cSize = ip - (const BYTE*)src;
2024*01826a49SYabin Cui *dBound = nbBlocks * BLOCKSIZE;
2025*01826a49SYabin Cui }
2026*01826a49SYabin Cui
2027*01826a49SYabin Cui /*******************************
2028*01826a49SYabin Cui * Streaming Decompression API
2029*01826a49SYabin Cui *******************************/
2030*01826a49SYabin Cui
ZSTDv01_resetDCtx(ZSTDv01_Dctx * dctx)2031*01826a49SYabin Cui size_t ZSTDv01_resetDCtx(ZSTDv01_Dctx* dctx)
2032*01826a49SYabin Cui {
2033*01826a49SYabin Cui dctx->expected = ZSTD_frameHeaderSize;
2034*01826a49SYabin Cui dctx->phase = 0;
2035*01826a49SYabin Cui dctx->previousDstEnd = NULL;
2036*01826a49SYabin Cui dctx->base = NULL;
2037*01826a49SYabin Cui return 0;
2038*01826a49SYabin Cui }
2039*01826a49SYabin Cui
ZSTDv01_createDCtx(void)2040*01826a49SYabin Cui ZSTDv01_Dctx* ZSTDv01_createDCtx(void)
2041*01826a49SYabin Cui {
2042*01826a49SYabin Cui ZSTDv01_Dctx* dctx = (ZSTDv01_Dctx*)malloc(sizeof(ZSTDv01_Dctx));
2043*01826a49SYabin Cui if (dctx==NULL) return NULL;
2044*01826a49SYabin Cui ZSTDv01_resetDCtx(dctx);
2045*01826a49SYabin Cui return dctx;
2046*01826a49SYabin Cui }
2047*01826a49SYabin Cui
ZSTDv01_freeDCtx(ZSTDv01_Dctx * dctx)2048*01826a49SYabin Cui size_t ZSTDv01_freeDCtx(ZSTDv01_Dctx* dctx)
2049*01826a49SYabin Cui {
2050*01826a49SYabin Cui free(dctx);
2051*01826a49SYabin Cui return 0;
2052*01826a49SYabin Cui }
2053*01826a49SYabin Cui
ZSTDv01_nextSrcSizeToDecompress(ZSTDv01_Dctx * dctx)2054*01826a49SYabin Cui size_t ZSTDv01_nextSrcSizeToDecompress(ZSTDv01_Dctx* dctx)
2055*01826a49SYabin Cui {
2056*01826a49SYabin Cui return ((dctx_t*)dctx)->expected;
2057*01826a49SYabin Cui }
2058*01826a49SYabin Cui
ZSTDv01_decompressContinue(ZSTDv01_Dctx * dctx,void * dst,size_t maxDstSize,const void * src,size_t srcSize)2059*01826a49SYabin Cui size_t ZSTDv01_decompressContinue(ZSTDv01_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2060*01826a49SYabin Cui {
2061*01826a49SYabin Cui dctx_t* ctx = (dctx_t*)dctx;
2062*01826a49SYabin Cui
2063*01826a49SYabin Cui /* Sanity check */
2064*01826a49SYabin Cui if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
2065*01826a49SYabin Cui if (dst != ctx->previousDstEnd) /* not contiguous */
2066*01826a49SYabin Cui ctx->base = dst;
2067*01826a49SYabin Cui
2068*01826a49SYabin Cui /* Decompress : frame header */
2069*01826a49SYabin Cui if (ctx->phase == 0)
2070*01826a49SYabin Cui {
2071*01826a49SYabin Cui /* Check frame magic header */
2072*01826a49SYabin Cui U32 magicNumber = ZSTD_readBE32(src);
2073*01826a49SYabin Cui if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2074*01826a49SYabin Cui ctx->phase = 1;
2075*01826a49SYabin Cui ctx->expected = ZSTD_blockHeaderSize;
2076*01826a49SYabin Cui return 0;
2077*01826a49SYabin Cui }
2078*01826a49SYabin Cui
2079*01826a49SYabin Cui /* Decompress : block header */
2080*01826a49SYabin Cui if (ctx->phase == 1)
2081*01826a49SYabin Cui {
2082*01826a49SYabin Cui blockProperties_t bp;
2083*01826a49SYabin Cui size_t blockSize = ZSTDv01_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
2084*01826a49SYabin Cui if (ZSTDv01_isError(blockSize)) return blockSize;
2085*01826a49SYabin Cui if (bp.blockType == bt_end)
2086*01826a49SYabin Cui {
2087*01826a49SYabin Cui ctx->expected = 0;
2088*01826a49SYabin Cui ctx->phase = 0;
2089*01826a49SYabin Cui }
2090*01826a49SYabin Cui else
2091*01826a49SYabin Cui {
2092*01826a49SYabin Cui ctx->expected = blockSize;
2093*01826a49SYabin Cui ctx->bType = bp.blockType;
2094*01826a49SYabin Cui ctx->phase = 2;
2095*01826a49SYabin Cui }
2096*01826a49SYabin Cui
2097*01826a49SYabin Cui return 0;
2098*01826a49SYabin Cui }
2099*01826a49SYabin Cui
2100*01826a49SYabin Cui /* Decompress : block content */
2101*01826a49SYabin Cui {
2102*01826a49SYabin Cui size_t rSize;
2103*01826a49SYabin Cui switch(ctx->bType)
2104*01826a49SYabin Cui {
2105*01826a49SYabin Cui case bt_compressed:
2106*01826a49SYabin Cui rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
2107*01826a49SYabin Cui break;
2108*01826a49SYabin Cui case bt_raw :
2109*01826a49SYabin Cui rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
2110*01826a49SYabin Cui break;
2111*01826a49SYabin Cui case bt_rle :
2112*01826a49SYabin Cui return ERROR(GENERIC); /* not yet handled */
2113*01826a49SYabin Cui break;
2114*01826a49SYabin Cui case bt_end : /* should never happen (filtered at phase 1) */
2115*01826a49SYabin Cui rSize = 0;
2116*01826a49SYabin Cui break;
2117*01826a49SYabin Cui default:
2118*01826a49SYabin Cui return ERROR(GENERIC);
2119*01826a49SYabin Cui }
2120*01826a49SYabin Cui ctx->phase = 1;
2121*01826a49SYabin Cui ctx->expected = ZSTD_blockHeaderSize;
2122*01826a49SYabin Cui if (ZSTDv01_isError(rSize)) return rSize;
2123*01826a49SYabin Cui ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
2124*01826a49SYabin Cui return rSize;
2125*01826a49SYabin Cui }
2126*01826a49SYabin Cui
2127*01826a49SYabin Cui }
2128