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