source: thirdparty/blosc/internal-complibs/zstd-0.7.4/legacy/zstd_v02.c @ 8ebc79b

Revision 8ebc79b, 134.4 KB checked in by Hal Finkel <hfinkel@…>, 8 years ago (diff)

Add the other internal compression libraries from blocs

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