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

Revision 8ebc79b, 120.8 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_v03.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 */
994
995
996#if defined (__cplusplus)
997}
998#endif
999
1000/*
1001    zstd - standard compression library
1002    Header File
1003    Copyright (C) 2014-2015, Yann Collet.
1004
1005    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1006
1007    Redistribution and use in source and binary forms, with or without
1008    modification, are permitted provided that the following conditions are
1009    met:
1010    * Redistributions of source code must retain the above copyright
1011    notice, this list of conditions and the following disclaimer.
1012    * Redistributions in binary form must reproduce the above
1013    copyright notice, this list of conditions and the following disclaimer
1014    in the documentation and/or other materials provided with the
1015    distribution.
1016    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1017    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1018    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1019    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1020    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1021    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1022    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1023    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1024    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1025    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1026    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1027
1028    You can contact the author at :
1029    - zstd source repository : https://github.com/Cyan4973/zstd
1030    - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
1031*/
1032
1033#if defined (__cplusplus)
1034extern "C" {
1035#endif
1036
1037/* *************************************
1038*  Includes
1039***************************************/
1040#include <stddef.h>   /* size_t */
1041
1042
1043/* *************************************
1044*  Version
1045***************************************/
1046#define ZSTD_VERSION_MAJOR    0    /* for breaking interface changes  */
1047#define ZSTD_VERSION_MINOR    2    /* for new (non-breaking) interface capabilities */
1048#define ZSTD_VERSION_RELEASE  2    /* for tweaks, bug-fixes, or development */
1049#define ZSTD_VERSION_NUMBER  (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
1050
1051
1052/* *************************************
1053*  Advanced functions
1054***************************************/
1055typedef struct ZSTD_CCtx_s ZSTD_CCtx;   /* incomplete type */
1056
1057#if defined (__cplusplus)
1058}
1059#endif
1060/*
1061    zstd - standard compression library
1062    Header File for static linking only
1063    Copyright (C) 2014-2015, Yann Collet.
1064
1065    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1066
1067    Redistribution and use in source and binary forms, with or without
1068    modification, are permitted provided that the following conditions are
1069    met:
1070    * Redistributions of source code must retain the above copyright
1071    notice, this list of conditions and the following disclaimer.
1072    * Redistributions in binary form must reproduce the above
1073    copyright notice, this list of conditions and the following disclaimer
1074    in the documentation and/or other materials provided with the
1075    distribution.
1076    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1077    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1078    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1079    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1080    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1081    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1082    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1083    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1084    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1085    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1086    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1087
1088    You can contact the author at :
1089    - zstd source repository : https://github.com/Cyan4973/zstd
1090    - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
1091*/
1092
1093/* The objects defined into this file should be considered experimental.
1094 * They are not labelled stable, as their prototype may change in the future.
1095 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
1096 */
1097
1098#if defined (__cplusplus)
1099extern "C" {
1100#endif
1101
1102/* *************************************
1103*  Streaming functions
1104***************************************/
1105
1106typedef struct ZSTD_DCtx_s ZSTD_DCtx;
1107
1108/*
1109  Use above functions alternatively.
1110  ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
1111  ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
1112  Result is the number of bytes regenerated within 'dst'.
1113  It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
1114*/
1115
1116/* *************************************
1117*  Prefix - version detection
1118***************************************/
1119#define ZSTD_magicNumber 0xFD2FB523   /* v0.3 */
1120
1121
1122#if defined (__cplusplus)
1123}
1124#endif
1125/* ******************************************************************
1126   FSE : Finite State Entropy coder
1127   Copyright (C) 2013-2015, Yann Collet.
1128
1129   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1130
1131   Redistribution and use in source and binary forms, with or without
1132   modification, are permitted provided that the following conditions are
1133   met:
1134
1135       * Redistributions of source code must retain the above copyright
1136   notice, this list of conditions and the following disclaimer.
1137       * Redistributions in binary form must reproduce the above
1138   copyright notice, this list of conditions and the following disclaimer
1139   in the documentation and/or other materials provided with the
1140   distribution.
1141
1142   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1143   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1144   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1145   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1146   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1147   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1148   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1149   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1150   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1151   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1152   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1153
1154    You can contact the author at :
1155    - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1156    - Public forum : https://groups.google.com/forum/#!forum/lz4c
1157****************************************************************** */
1158
1159#ifndef FSE_COMMONDEFS_ONLY
1160
1161/****************************************************************
1162*  Tuning parameters
1163****************************************************************/
1164/* MEMORY_USAGE :
1165*  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1166*  Increasing memory usage improves compression ratio
1167*  Reduced memory usage can improve speed, due to cache effect
1168*  Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1169#define FSE_MAX_MEMORY_USAGE 14
1170#define FSE_DEFAULT_MEMORY_USAGE 13
1171
1172/* FSE_MAX_SYMBOL_VALUE :
1173*  Maximum symbol value authorized.
1174*  Required for proper stack allocation */
1175#define FSE_MAX_SYMBOL_VALUE 255
1176
1177
1178/****************************************************************
1179*  template functions type & suffix
1180****************************************************************/
1181#define FSE_FUNCTION_TYPE BYTE
1182#define FSE_FUNCTION_EXTENSION
1183
1184
1185/****************************************************************
1186*  Byte symbol type
1187****************************************************************/
1188#endif   /* !FSE_COMMONDEFS_ONLY */
1189
1190
1191/****************************************************************
1192*  Compiler specifics
1193****************************************************************/
1194#ifdef _MSC_VER    /* Visual Studio */
1195#  define FORCE_INLINE static __forceinline
1196#  include <intrin.h>                    /* For Visual 2005 */
1197#  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1198#  pragma warning(disable : 4214)        /* disable: C4214: non-int bitfields */
1199#else
1200#  ifdef __GNUC__
1201#    define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
1202#    define FORCE_INLINE static inline __attribute__((always_inline))
1203#  else
1204#    define FORCE_INLINE static inline
1205#  endif
1206#endif
1207
1208
1209/****************************************************************
1210*  Includes
1211****************************************************************/
1212#include <stdlib.h>     /* malloc, free, qsort */
1213#include <string.h>     /* memcpy, memset */
1214#include <stdio.h>      /* printf (debug) */
1215
1216/****************************************************************
1217*  Constants
1218*****************************************************************/
1219#define FSE_MAX_TABLELOG  (FSE_MAX_MEMORY_USAGE-2)
1220#define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
1221#define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
1222#define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
1223#define FSE_MIN_TABLELOG 5
1224
1225#define FSE_TABLELOG_ABSOLUTE_MAX 15
1226#if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1227#error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1228#endif
1229
1230
1231/****************************************************************
1232*  Error Management
1233****************************************************************/
1234#define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1235
1236
1237/****************************************************************
1238*  Complex types
1239****************************************************************/
1240typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1241
1242
1243/****************************************************************
1244*  Templates
1245****************************************************************/
1246/*
1247  designed to be included
1248  for type-specific functions (template emulation in C)
1249  Objective is to write these functions only once, for improved maintenance
1250*/
1251
1252/* safety checks */
1253#ifndef FSE_FUNCTION_EXTENSION
1254#  error "FSE_FUNCTION_EXTENSION must be defined"
1255#endif
1256#ifndef FSE_FUNCTION_TYPE
1257#  error "FSE_FUNCTION_TYPE must be defined"
1258#endif
1259
1260/* Function names */
1261#define FSE_CAT(X,Y) X##Y
1262#define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1263#define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1264
1265
1266/* Function templates */
1267
1268#define FSE_DECODE_TYPE FSE_decode_t
1269
1270static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1271
1272static size_t FSE_buildDTable
1273(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1274{
1275    void* ptr = dt+1;
1276    FSE_DTableHeader DTableH;
1277    FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1278    const U32 tableSize = 1 << tableLog;
1279    const U32 tableMask = tableSize-1;
1280    const U32 step = FSE_tableStep(tableSize);
1281    U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1282    U32 position = 0;
1283    U32 highThreshold = tableSize-1;
1284    const S16 largeLimit= (S16)(1 << (tableLog-1));
1285    U32 noLarge = 1;
1286    U32 s;
1287
1288    /* Sanity Checks */
1289    if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1290    if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1291
1292    /* Init, lay down lowprob symbols */
1293    DTableH.tableLog = (U16)tableLog;
1294    for (s=0; s<=maxSymbolValue; s++)
1295    {
1296        if (normalizedCounter[s]==-1)
1297        {
1298            tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1299            symbolNext[s] = 1;
1300        }
1301        else
1302        {
1303            if (normalizedCounter[s] >= largeLimit) noLarge=0;
1304            symbolNext[s] = normalizedCounter[s];
1305        }
1306    }
1307
1308    /* Spread symbols */
1309    for (s=0; s<=maxSymbolValue; s++)
1310    {
1311        int i;
1312        for (i=0; i<normalizedCounter[s]; i++)
1313        {
1314            tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1315            position = (position + step) & tableMask;
1316            while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
1317        }
1318    }
1319
1320    if (position!=0) return ERROR(GENERIC);   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1321
1322    /* Build Decoding table */
1323    {
1324        U32 i;
1325        for (i=0; i<tableSize; i++)
1326        {
1327            FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1328            U16 nextState = symbolNext[symbol]++;
1329            tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1330            tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1331        }
1332    }
1333
1334    DTableH.fastMode = (U16)noLarge;
1335    memcpy(dt, &DTableH, sizeof(DTableH));
1336    return 0;
1337}
1338
1339
1340#ifndef FSE_COMMONDEFS_ONLY
1341/******************************************
1342*  FSE helper functions
1343******************************************/
1344static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1345
1346
1347/****************************************************************
1348*  FSE NCount encoding-decoding
1349****************************************************************/
1350static short FSE_abs(short a)
1351{
1352    return a<0 ? -a : a;
1353}
1354
1355static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1356                 const void* headerBuffer, size_t hbSize)
1357{
1358    const BYTE* const istart = (const BYTE*) headerBuffer;
1359    const BYTE* const iend = istart + hbSize;
1360    const BYTE* ip = istart;
1361    int nbBits;
1362    int remaining;
1363    int threshold;
1364    U32 bitStream;
1365    int bitCount;
1366    unsigned charnum = 0;
1367    int previous0 = 0;
1368
1369    if (hbSize < 4) return ERROR(srcSize_wrong);
1370    bitStream = MEM_readLE32(ip);
1371    nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG;   /* extract tableLog */
1372    if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1373    bitStream >>= 4;
1374    bitCount = 4;
1375    *tableLogPtr = nbBits;
1376    remaining = (1<<nbBits)+1;
1377    threshold = 1<<nbBits;
1378    nbBits++;
1379
1380    while ((remaining>1) && (charnum<=*maxSVPtr))
1381    {
1382        if (previous0)
1383        {
1384            unsigned n0 = charnum;
1385            while ((bitStream & 0xFFFF) == 0xFFFF)
1386            {
1387                n0+=24;
1388                if (ip < iend-5)
1389                {
1390                    ip+=2;
1391                    bitStream = MEM_readLE32(ip) >> bitCount;
1392                }
1393                else
1394                {
1395                    bitStream >>= 16;
1396                    bitCount+=16;
1397                }
1398            }
1399            while ((bitStream & 3) == 3)
1400            {
1401                n0+=3;
1402                bitStream>>=2;
1403                bitCount+=2;
1404            }
1405            n0 += bitStream & 3;
1406            bitCount += 2;
1407            if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1408            while (charnum < n0) normalizedCounter[charnum++] = 0;
1409            if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1410            {
1411                ip += bitCount>>3;
1412                bitCount &= 7;
1413                bitStream = MEM_readLE32(ip) >> bitCount;
1414            }
1415            else
1416                bitStream >>= 2;
1417        }
1418        {
1419            const short max = (short)((2*threshold-1)-remaining);
1420            short count;
1421
1422            if ((bitStream & (threshold-1)) < (U32)max)
1423            {
1424                count = (short)(bitStream & (threshold-1));
1425                bitCount   += nbBits-1;
1426            }
1427            else
1428            {
1429                count = (short)(bitStream & (2*threshold-1));
1430                if (count >= threshold) count -= max;
1431                bitCount   += nbBits;
1432            }
1433
1434            count--;   /* extra accuracy */
1435            remaining -= FSE_abs(count);
1436            normalizedCounter[charnum++] = count;
1437            previous0 = !count;
1438            while (remaining < threshold)
1439            {
1440                nbBits--;
1441                threshold >>= 1;
1442            }
1443
1444            {
1445                if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1446                {
1447                    ip += bitCount>>3;
1448                    bitCount &= 7;
1449                }
1450                else
1451                {
1452                    bitCount -= (int)(8 * (iend - 4 - ip));
1453                                        ip = iend - 4;
1454                                }
1455                bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1456            }
1457        }
1458    }
1459    if (remaining != 1) return ERROR(GENERIC);
1460    *maxSVPtr = charnum-1;
1461
1462    ip += (bitCount+7)>>3;
1463    if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1464    return ip-istart;
1465}
1466
1467
1468/*********************************************************
1469*  Decompression (Byte symbols)
1470*********************************************************/
1471static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1472{
1473    void* ptr = dt;
1474    FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1475    FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1;
1476
1477    DTableH->tableLog = 0;
1478    DTableH->fastMode = 0;
1479
1480    cell->newState = 0;
1481    cell->symbol = symbolValue;
1482    cell->nbBits = 0;
1483
1484    return 0;
1485}
1486
1487
1488static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1489{
1490    void* ptr = dt;
1491    FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1492    FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1;
1493    const unsigned tableSize = 1 << nbBits;
1494    const unsigned tableMask = tableSize - 1;
1495    const unsigned maxSymbolValue = tableMask;
1496    unsigned s;
1497
1498    /* Sanity checks */
1499    if (nbBits < 1) return ERROR(GENERIC);         /* min size */
1500
1501    /* Build Decoding Table */
1502    DTableH->tableLog = (U16)nbBits;
1503    DTableH->fastMode = 1;
1504    for (s=0; s<=maxSymbolValue; s++)
1505    {
1506        dinfo[s].newState = 0;
1507        dinfo[s].symbol = (BYTE)s;
1508        dinfo[s].nbBits = (BYTE)nbBits;
1509    }
1510
1511    return 0;
1512}
1513
1514FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1515          void* dst, size_t maxDstSize,
1516    const void* cSrc, size_t cSrcSize,
1517    const FSE_DTable* dt, const unsigned fast)
1518{
1519    BYTE* const ostart = (BYTE*) dst;
1520    BYTE* op = ostart;
1521    BYTE* const omax = op + maxDstSize;
1522    BYTE* const olimit = omax-3;
1523
1524    BIT_DStream_t bitD;
1525    FSE_DState_t state1;
1526    FSE_DState_t state2;
1527    size_t errorCode;
1528
1529    /* Init */
1530    errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize);   /* replaced last arg by maxCompressed Size */
1531    if (FSE_isError(errorCode)) return errorCode;
1532
1533    FSE_initDState(&state1, &bitD, dt);
1534    FSE_initDState(&state2, &bitD, dt);
1535
1536#define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1537
1538    /* 4 symbols per loop */
1539    for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1540    {
1541        op[0] = FSE_GETSYMBOL(&state1);
1542
1543        if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1544            BIT_reloadDStream(&bitD);
1545
1546        op[1] = FSE_GETSYMBOL(&state2);
1547
1548        if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1549            { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1550
1551        op[2] = FSE_GETSYMBOL(&state1);
1552
1553        if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1554            BIT_reloadDStream(&bitD);
1555
1556        op[3] = FSE_GETSYMBOL(&state2);
1557    }
1558
1559    /* tail */
1560    /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1561    while (1)
1562    {
1563        if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1564            break;
1565
1566        *op++ = FSE_GETSYMBOL(&state1);
1567
1568        if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1569            break;
1570
1571        *op++ = FSE_GETSYMBOL(&state2);
1572    }
1573
1574    /* end ? */
1575    if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1576        return op-ostart;
1577
1578    if (op==omax) return ERROR(dstSize_tooSmall);   /* dst buffer is full, but cSrc unfinished */
1579
1580    return ERROR(corruption_detected);
1581}
1582
1583
1584static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1585                            const void* cSrc, size_t cSrcSize,
1586                            const FSE_DTable* dt)
1587{
1588    FSE_DTableHeader DTableH;
1589    memcpy(&DTableH, dt, sizeof(DTableH));
1590
1591    /* select fast mode (static) */
1592    if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1593    return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1594}
1595
1596
1597static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1598{
1599    const BYTE* const istart = (const BYTE*)cSrc;
1600    const BYTE* ip = istart;
1601    short counting[FSE_MAX_SYMBOL_VALUE+1];
1602    DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
1603    unsigned tableLog;
1604    unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1605    size_t errorCode;
1606
1607    if (cSrcSize<2) return ERROR(srcSize_wrong);   /* too small input size */
1608
1609    /* normal FSE decoding mode */
1610    errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1611    if (FSE_isError(errorCode)) return errorCode;
1612    if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);   /* too small input size */
1613    ip += errorCode;
1614    cSrcSize -= errorCode;
1615
1616    errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1617    if (FSE_isError(errorCode)) return errorCode;
1618
1619    /* always return, even if it is an error code */
1620    return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1621}
1622
1623
1624
1625#endif   /* FSE_COMMONDEFS_ONLY */
1626/* ******************************************************************
1627   Huff0 : Huffman coder, part of New Generation Entropy library
1628   Copyright (C) 2013-2015, Yann Collet.
1629
1630   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1631
1632   Redistribution and use in source and binary forms, with or without
1633   modification, are permitted provided that the following conditions are
1634   met:
1635
1636       * Redistributions of source code must retain the above copyright
1637   notice, this list of conditions and the following disclaimer.
1638       * Redistributions in binary form must reproduce the above
1639   copyright notice, this list of conditions and the following disclaimer
1640   in the documentation and/or other materials provided with the
1641   distribution.
1642
1643   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1644   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1645   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1646   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1647   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1648   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1649   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1650   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1651   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1652   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1653   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1654
1655    You can contact the author at :
1656    - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1657    - Public forum : https://groups.google.com/forum/#!forum/lz4c
1658****************************************************************** */
1659
1660/****************************************************************
1661*  Compiler specifics
1662****************************************************************/
1663#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1664/* inline is defined */
1665#elif defined(_MSC_VER)
1666#  define inline __inline
1667#else
1668#  define inline /* disable inline */
1669#endif
1670
1671
1672#ifdef _MSC_VER    /* Visual Studio */
1673#  define FORCE_INLINE static __forceinline
1674#  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1675#else
1676#  ifdef __GNUC__
1677#    define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
1678#    define FORCE_INLINE static inline __attribute__((always_inline))
1679#  else
1680#    define FORCE_INLINE static inline
1681#  endif
1682#endif
1683
1684
1685/****************************************************************
1686*  Includes
1687****************************************************************/
1688#include <stdlib.h>     /* malloc, free, qsort */
1689#include <string.h>     /* memcpy, memset */
1690#include <stdio.h>      /* printf (debug) */
1691
1692/****************************************************************
1693*  Error Management
1694****************************************************************/
1695#define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1696
1697
1698/******************************************
1699*  Helper functions
1700******************************************/
1701static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1702
1703#define HUF_ABSOLUTEMAX_TABLELOG  16   /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1704#define HUF_MAX_TABLELOG  12           /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1705#define HUF_DEFAULT_TABLELOG  HUF_MAX_TABLELOG   /* tableLog by default, when not specified */
1706#define HUF_MAX_SYMBOL_VALUE 255
1707#if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1708#  error "HUF_MAX_TABLELOG is too large !"
1709#endif
1710
1711
1712
1713/*********************************************************
1714*  Huff0 : Huffman block decompression
1715*********************************************************/
1716typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2;   /* single-symbol decoding */
1717
1718typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4;  /* double-symbols decoding */
1719
1720typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1721
1722/*! HUF_readStats
1723    Read compact Huffman tree, saved by HUF_writeCTable
1724    @huffWeight : destination buffer
1725    @return : size read from `src`
1726*/
1727static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1728                            U32* nbSymbolsPtr, U32* tableLogPtr,
1729                            const void* src, size_t srcSize)
1730{
1731    U32 weightTotal;
1732    U32 tableLog;
1733    const BYTE* ip = (const BYTE*) src;
1734    size_t iSize = ip[0];
1735    size_t oSize;
1736    U32 n;
1737
1738    //memset(huffWeight, 0, hwSize);   /* is not necessary, even though some analyzer complain ... */
1739
1740    if (iSize >= 128)  /* special header */
1741    {
1742        if (iSize >= (242))   /* RLE */
1743        {
1744            static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1745            oSize = l[iSize-242];
1746            memset(huffWeight, 1, hwSize);
1747            iSize = 0;
1748        }
1749        else   /* Incompressible */
1750        {
1751            oSize = iSize - 127;
1752            iSize = ((oSize+1)/2);
1753            if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1754            if (oSize >= hwSize) return ERROR(corruption_detected);
1755            ip += 1;
1756            for (n=0; n<oSize; n+=2)
1757            {
1758                huffWeight[n]   = ip[n/2] >> 4;
1759                huffWeight[n+1] = ip[n/2] & 15;
1760            }
1761        }
1762    }
1763    else  /* header compressed with FSE (normal case) */
1764    {
1765        if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1766        oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize);   /* max (hwSize-1) values decoded, as last one is implied */
1767        if (FSE_isError(oSize)) return oSize;
1768    }
1769
1770    /* collect weight stats */
1771    memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1772    weightTotal = 0;
1773    for (n=0; n<oSize; n++)
1774    {
1775        if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1776        rankStats[huffWeight[n]]++;
1777        weightTotal += (1 << huffWeight[n]) >> 1;
1778    }
1779
1780    /* get last non-null symbol weight (implied, total must be 2^n) */
1781    tableLog = BIT_highbit32(weightTotal) + 1;
1782    if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1783    {
1784        U32 total = 1 << tableLog;
1785        U32 rest = total - weightTotal;
1786        U32 verif = 1 << BIT_highbit32(rest);
1787        U32 lastWeight = BIT_highbit32(rest) + 1;
1788        if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
1789        huffWeight[oSize] = (BYTE)lastWeight;
1790        rankStats[lastWeight]++;
1791    }
1792
1793    /* check tree construction validity */
1794    if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected);   /* by construction : at least 2 elts of rank 1, must be even */
1795
1796    /* results */
1797    *nbSymbolsPtr = (U32)(oSize+1);
1798    *tableLogPtr = tableLog;
1799    return iSize+1;
1800}
1801
1802
1803/**************************/
1804/* single-symbol decoding */
1805/**************************/
1806
1807static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1808{
1809    BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1810    U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];   /* large enough for values from 0 to 16 */
1811    U32 tableLog = 0;
1812    const BYTE* ip = (const BYTE*) src;
1813    size_t iSize = ip[0];
1814    U32 nbSymbols = 0;
1815    U32 n;
1816    U32 nextRankStart;
1817    void* ptr = DTable+1;
1818    HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr);
1819
1820    HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16));   /* if compilation fails here, assertion is false */
1821    //memset(huffWeight, 0, sizeof(huffWeight));   /* is not necessary, even though some analyzer complain ... */
1822
1823    iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1824    if (HUF_isError(iSize)) return iSize;
1825
1826    /* check result */
1827    if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge);   /* DTable is too small */
1828    DTable[0] = (U16)tableLog;   /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1829
1830    /* Prepare ranks */
1831    nextRankStart = 0;
1832    for (n=1; n<=tableLog; n++)
1833    {
1834        U32 current = nextRankStart;
1835        nextRankStart += (rankVal[n] << (n-1));
1836        rankVal[n] = current;
1837    }
1838
1839    /* fill DTable */
1840    for (n=0; n<nbSymbols; n++)
1841    {
1842        const U32 w = huffWeight[n];
1843        const U32 length = (1 << w) >> 1;
1844        U32 i;
1845        HUF_DEltX2 D;
1846        D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1847        for (i = rankVal[w]; i < rankVal[w] + length; i++)
1848            dt[i] = D;
1849        rankVal[w] += length;
1850    }
1851
1852    return iSize;
1853}
1854
1855static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1856{
1857        const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1858        const BYTE c = dt[val].byte;
1859        BIT_skipBits(Dstream, dt[val].nbBits);
1860        return c;
1861}
1862
1863#define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1864    *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1865
1866#define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1867    if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1868        HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1869
1870#define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1871    if (MEM_64bits()) \
1872        HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1873
1874static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1875{
1876    BYTE* const pStart = p;
1877
1878    /* up to 4 symbols at a time */
1879    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1880    {
1881        HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1882        HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1883        HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1884        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1885    }
1886
1887    /* closer to the end */
1888    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1889        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1890
1891    /* no more data to retrieve from bitstream, hence no need to reload */
1892    while (p < pEnd)
1893        HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1894
1895    return pEnd-pStart;
1896}
1897
1898
1899static size_t HUF_decompress4X2_usingDTable(
1900          void* dst,  size_t dstSize,
1901    const void* cSrc, size_t cSrcSize,
1902    const U16* DTable)
1903{
1904    if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
1905
1906    {
1907        const BYTE* const istart = (const BYTE*) cSrc;
1908        BYTE* const ostart = (BYTE*) dst;
1909        BYTE* const oend = ostart + dstSize;
1910
1911        const void* ptr = DTable;
1912        const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1913        const U32 dtLog = DTable[0];
1914        size_t errorCode;
1915
1916        /* Init */
1917        BIT_DStream_t bitD1;
1918        BIT_DStream_t bitD2;
1919        BIT_DStream_t bitD3;
1920        BIT_DStream_t bitD4;
1921        const size_t length1 = MEM_readLE16(istart);
1922        const size_t length2 = MEM_readLE16(istart+2);
1923        const size_t length3 = MEM_readLE16(istart+4);
1924        size_t length4;
1925        const BYTE* const istart1 = istart + 6;  /* jumpTable */
1926        const BYTE* const istart2 = istart1 + length1;
1927        const BYTE* const istart3 = istart2 + length2;
1928        const BYTE* const istart4 = istart3 + length3;
1929        const size_t segmentSize = (dstSize+3) / 4;
1930        BYTE* const opStart2 = ostart + segmentSize;
1931        BYTE* const opStart3 = opStart2 + segmentSize;
1932        BYTE* const opStart4 = opStart3 + segmentSize;
1933        BYTE* op1 = ostart;
1934        BYTE* op2 = opStart2;
1935        BYTE* op3 = opStart3;
1936        BYTE* op4 = opStart4;
1937        U32 endSignal;
1938
1939        length4 = cSrcSize - (length1 + length2 + length3 + 6);
1940        if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
1941        errorCode = BIT_initDStream(&bitD1, istart1, length1);
1942        if (HUF_isError(errorCode)) return errorCode;
1943        errorCode = BIT_initDStream(&bitD2, istart2, length2);
1944        if (HUF_isError(errorCode)) return errorCode;
1945        errorCode = BIT_initDStream(&bitD3, istart3, length3);
1946        if (HUF_isError(errorCode)) return errorCode;
1947        errorCode = BIT_initDStream(&bitD4, istart4, length4);
1948        if (HUF_isError(errorCode)) return errorCode;
1949
1950        /* 16-32 symbols per loop (4-8 symbols per stream) */
1951        endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1952        for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1953        {
1954            HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1955            HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1956            HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1957            HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1958            HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1959            HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1960            HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1961            HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1962            HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1963            HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1964            HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1965            HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1966            HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1967            HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1968            HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1969            HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1970
1971            endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1972        }
1973
1974        /* check corruption */
1975        if (op1 > opStart2) return ERROR(corruption_detected);
1976        if (op2 > opStart3) return ERROR(corruption_detected);
1977        if (op3 > opStart4) return ERROR(corruption_detected);
1978        /* note : op4 supposed already verified within main loop */
1979
1980        /* finish bitStreams one by one */
1981        HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1982        HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1983        HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1984        HUF_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
1985
1986        /* check */
1987        endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1988        if (!endSignal) return ERROR(corruption_detected);
1989
1990        /* decoded size */
1991        return dstSize;
1992    }
1993}
1994
1995
1996static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1997{
1998    HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1999    const BYTE* ip = (const BYTE*) cSrc;
2000    size_t errorCode;
2001
2002    errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
2003    if (HUF_isError(errorCode)) return errorCode;
2004    if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2005    ip += errorCode;
2006    cSrcSize -= errorCode;
2007
2008    return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2009}
2010
2011
2012/***************************/
2013/* double-symbols decoding */
2014/***************************/
2015
2016static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2017                           const U32* rankValOrigin, const int minWeight,
2018                           const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2019                           U32 nbBitsBaseline, U16 baseSeq)
2020{
2021    HUF_DEltX4 DElt;
2022    U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
2023    U32 s;
2024
2025    /* get pre-calculated rankVal */
2026    memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2027
2028    /* fill skipped values */
2029    if (minWeight>1)
2030    {
2031        U32 i, skipSize = rankVal[minWeight];
2032        MEM_writeLE16(&(DElt.sequence), baseSeq);
2033        DElt.nbBits   = (BYTE)(consumed);
2034        DElt.length   = 1;
2035        for (i = 0; i < skipSize; i++)
2036            DTable[i] = DElt;
2037    }
2038
2039    /* fill DTable */
2040    for (s=0; s<sortedListSize; s++)   /* note : sortedSymbols already skipped */
2041    {
2042        const U32 symbol = sortedSymbols[s].symbol;
2043        const U32 weight = sortedSymbols[s].weight;
2044        const U32 nbBits = nbBitsBaseline - weight;
2045        const U32 length = 1 << (sizeLog-nbBits);
2046        const U32 start = rankVal[weight];
2047        U32 i = start;
2048        const U32 end = start + length;
2049
2050        MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2051        DElt.nbBits = (BYTE)(nbBits + consumed);
2052        DElt.length = 2;
2053        do { DTable[i++] = DElt; } while (i<end);   /* since length >= 1 */
2054
2055        rankVal[weight] += length;
2056    }
2057}
2058
2059typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
2060
2061static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
2062                           const sortedSymbol_t* sortedList, const U32 sortedListSize,
2063                           const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2064                           const U32 nbBitsBaseline)
2065{
2066    U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
2067    const int scaleLog = nbBitsBaseline - targetLog;   /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2068    const U32 minBits  = nbBitsBaseline - maxWeight;
2069    U32 s;
2070
2071    memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2072
2073    /* fill DTable */
2074    for (s=0; s<sortedListSize; s++)
2075    {
2076        const U16 symbol = sortedList[s].symbol;
2077        const U32 weight = sortedList[s].weight;
2078        const U32 nbBits = nbBitsBaseline - weight;
2079        const U32 start = rankVal[weight];
2080        const U32 length = 1 << (targetLog-nbBits);
2081
2082        if (targetLog-nbBits >= minBits)   /* enough room for a second symbol */
2083        {
2084            U32 sortedRank;
2085            int minWeight = nbBits + scaleLog;
2086            if (minWeight < 1) minWeight = 1;
2087            sortedRank = rankStart[minWeight];
2088            HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2089                           rankValOrigin[nbBits], minWeight,
2090                           sortedList+sortedRank, sortedListSize-sortedRank,
2091                           nbBitsBaseline, symbol);
2092        }
2093        else
2094        {
2095            U32 i;
2096            const U32 end = start + length;
2097            HUF_DEltX4 DElt;
2098
2099            MEM_writeLE16(&(DElt.sequence), symbol);
2100            DElt.nbBits   = (BYTE)(nbBits);
2101            DElt.length   = 1;
2102            for (i = start; i < end; i++)
2103                DTable[i] = DElt;
2104        }
2105        rankVal[weight] += length;
2106    }
2107}
2108
2109static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2110{
2111    BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
2112    sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
2113    U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2114    U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2115    U32* const rankStart = rankStart0+1;
2116    rankVal_t rankVal;
2117    U32 tableLog, maxW, sizeOfSort, nbSymbols;
2118    const U32 memLog = DTable[0];
2119    const BYTE* ip = (const BYTE*) src;
2120    size_t iSize = ip[0];
2121    void* ptr = DTable;
2122    HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
2123
2124    HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32));   /* if compilation fails here, assertion is false */
2125    if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2126    //memset(weightList, 0, sizeof(weightList));   /* is not necessary, even though some analyzer complain ... */
2127
2128    iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2129    if (HUF_isError(iSize)) return iSize;
2130
2131    /* check result */
2132    if (tableLog > memLog) return ERROR(tableLog_tooLarge);   /* DTable can't fit code depth */
2133
2134    /* find maxWeight */
2135    for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2136        { if (!maxW) return ERROR(GENERIC); }  /* necessarily finds a solution before maxW==0 */
2137
2138    /* Get start index of each weight */
2139    {
2140        U32 w, nextRankStart = 0;
2141        for (w=1; w<=maxW; w++)
2142        {
2143            U32 current = nextRankStart;
2144            nextRankStart += rankStats[w];
2145            rankStart[w] = current;
2146        }
2147        rankStart[0] = nextRankStart;   /* put all 0w symbols at the end of sorted list*/
2148        sizeOfSort = nextRankStart;
2149    }
2150
2151    /* sort symbols by weight */
2152    {
2153        U32 s;
2154        for (s=0; s<nbSymbols; s++)
2155        {
2156            U32 w = weightList[s];
2157            U32 r = rankStart[w]++;
2158            sortedSymbol[r].symbol = (BYTE)s;
2159            sortedSymbol[r].weight = (BYTE)w;
2160        }
2161        rankStart[0] = 0;   /* forget 0w symbols; this is beginning of weight(1) */
2162    }
2163
2164        /* Build rankVal */
2165    {
2166        const U32 minBits = tableLog+1 - maxW;
2167        U32 nextRankVal = 0;
2168        U32 w, consumed;
2169        const int rescale = (memLog-tableLog) - 1;   /* tableLog <= memLog */
2170        U32* rankVal0 = rankVal[0];
2171        for (w=1; w<=maxW; w++)
2172        {
2173            U32 current = nextRankVal;
2174            nextRankVal += rankStats[w] << (w+rescale);
2175            rankVal0[w] = current;
2176        }
2177        for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2178        {
2179            U32* rankValPtr = rankVal[consumed];
2180            for (w = 1; w <= maxW; w++)
2181            {
2182                rankValPtr[w] = rankVal0[w] >> consumed;
2183            }
2184        }
2185    }
2186
2187    HUF_fillDTableX4(dt, memLog,
2188                   sortedSymbol, sizeOfSort,
2189                   rankStart0, rankVal, maxW,
2190                   tableLog+1);
2191
2192    return iSize;
2193}
2194
2195
2196static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2197{
2198    const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2199    memcpy(op, dt+val, 2);
2200    BIT_skipBits(DStream, dt[val].nbBits);
2201    return dt[val].length;
2202}
2203
2204static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2205{
2206    const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2207    memcpy(op, dt+val, 1);
2208    if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2209    else
2210    {
2211        if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2212        {
2213            BIT_skipBits(DStream, dt[val].nbBits);
2214            if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2215                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 */
2216        }
2217    }
2218    return 1;
2219}
2220
2221
2222#define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2223    ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2224
2225#define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2226    if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2227        ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2228
2229#define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2230    if (MEM_64bits()) \
2231        ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2232
2233static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2234{
2235    BYTE* const pStart = p;
2236
2237    /* up to 8 symbols at a time */
2238    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2239    {
2240        HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2241        HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2242        HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2243        HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2244    }
2245
2246    /* closer to the end */
2247    while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2248        HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2249
2250    while (p <= pEnd-2)
2251        HUF_DECODE_SYMBOLX4_0(p, bitDPtr);   /* no need to reload : reached the end of DStream */
2252
2253    if (p < pEnd)
2254        p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2255
2256    return p-pStart;
2257}
2258
2259
2260
2261static size_t HUF_decompress4X4_usingDTable(
2262          void* dst,  size_t dstSize,
2263    const void* cSrc, size_t cSrcSize,
2264    const U32* DTable)
2265{
2266    if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
2267
2268    {
2269        const BYTE* const istart = (const BYTE*) cSrc;
2270        BYTE* const ostart = (BYTE*) dst;
2271        BYTE* const oend = ostart + dstSize;
2272
2273        const void* ptr = DTable;
2274        const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2275        const U32 dtLog = DTable[0];
2276        size_t errorCode;
2277
2278        /* Init */
2279        BIT_DStream_t bitD1;
2280        BIT_DStream_t bitD2;
2281        BIT_DStream_t bitD3;
2282        BIT_DStream_t bitD4;
2283        const size_t length1 = MEM_readLE16(istart);
2284        const size_t length2 = MEM_readLE16(istart+2);
2285        const size_t length3 = MEM_readLE16(istart+4);
2286        size_t length4;
2287        const BYTE* const istart1 = istart + 6;  /* jumpTable */
2288        const BYTE* const istart2 = istart1 + length1;
2289        const BYTE* const istart3 = istart2 + length2;
2290        const BYTE* const istart4 = istart3 + length3;
2291        const size_t segmentSize = (dstSize+3) / 4;
2292        BYTE* const opStart2 = ostart + segmentSize;
2293        BYTE* const opStart3 = opStart2 + segmentSize;
2294        BYTE* const opStart4 = opStart3 + segmentSize;
2295        BYTE* op1 = ostart;
2296        BYTE* op2 = opStart2;
2297        BYTE* op3 = opStart3;
2298        BYTE* op4 = opStart4;
2299        U32 endSignal;
2300
2301        length4 = cSrcSize - (length1 + length2 + length3 + 6);
2302        if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
2303        errorCode = BIT_initDStream(&bitD1, istart1, length1);
2304        if (HUF_isError(errorCode)) return errorCode;
2305        errorCode = BIT_initDStream(&bitD2, istart2, length2);
2306        if (HUF_isError(errorCode)) return errorCode;
2307        errorCode = BIT_initDStream(&bitD3, istart3, length3);
2308        if (HUF_isError(errorCode)) return errorCode;
2309        errorCode = BIT_initDStream(&bitD4, istart4, length4);
2310        if (HUF_isError(errorCode)) return errorCode;
2311
2312        /* 16-32 symbols per loop (4-8 symbols per stream) */
2313        endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2314        for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2315        {
2316            HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2317            HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2318            HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2319            HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2320            HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2321            HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2322            HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2323            HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2324            HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2325            HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2326            HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2327            HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2328            HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2329            HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2330            HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2331            HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2332
2333            endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2334        }
2335
2336        /* check corruption */
2337        if (op1 > opStart2) return ERROR(corruption_detected);
2338        if (op2 > opStart3) return ERROR(corruption_detected);
2339        if (op3 > opStart4) return ERROR(corruption_detected);
2340        /* note : op4 supposed already verified within main loop */
2341
2342        /* finish bitStreams one by one */
2343        HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2344        HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2345        HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2346        HUF_decodeStreamX4(op4, &bitD4, oend,     dt, dtLog);
2347
2348        /* check */
2349        endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2350        if (!endSignal) return ERROR(corruption_detected);
2351
2352        /* decoded size */
2353        return dstSize;
2354    }
2355}
2356
2357
2358static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2359{
2360    HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2361    const BYTE* ip = (const BYTE*) cSrc;
2362
2363    size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2364    if (HUF_isError(hSize)) return hSize;
2365    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2366    ip += hSize;
2367    cSrcSize -= hSize;
2368
2369    return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2370}
2371
2372
2373/**********************************/
2374/* Generic decompression selector */
2375/**********************************/
2376
2377typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2378static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2379{
2380    /* single, double, quad */
2381    {{0,0}, {1,1}, {2,2}},  /* Q==0 : impossible */
2382    {{0,0}, {1,1}, {2,2}},  /* Q==1 : impossible */
2383    {{  38,130}, {1313, 74}, {2151, 38}},   /* Q == 2 : 12-18% */
2384    {{ 448,128}, {1353, 74}, {2238, 41}},   /* Q == 3 : 18-25% */
2385    {{ 556,128}, {1353, 74}, {2238, 47}},   /* Q == 4 : 25-32% */
2386    {{ 714,128}, {1418, 74}, {2436, 53}},   /* Q == 5 : 32-38% */
2387    {{ 883,128}, {1437, 74}, {2464, 61}},   /* Q == 6 : 38-44% */
2388    {{ 897,128}, {1515, 75}, {2622, 68}},   /* Q == 7 : 44-50% */
2389    {{ 926,128}, {1613, 75}, {2730, 75}},   /* Q == 8 : 50-56% */
2390    {{ 947,128}, {1729, 77}, {3359, 77}},   /* Q == 9 : 56-62% */
2391    {{1107,128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
2392    {{1177,128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
2393    {{1242,128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
2394    {{1349,128}, {2644,106}, {5260,106}},   /* Q ==13 : 81-87% */
2395    {{1455,128}, {2422,124}, {4174,124}},   /* Q ==14 : 87-93% */
2396    {{ 722,128}, {1891,145}, {1936,146}},   /* Q ==15 : 93-99% */
2397};
2398
2399typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2400
2401static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2402{
2403    static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2404    /* estimate decompression time */
2405    U32 Q;
2406    const U32 D256 = (U32)(dstSize >> 8);
2407    U32 Dtime[3];
2408    U32 algoNb = 0;
2409    int n;
2410
2411    /* validation checks */
2412    if (dstSize == 0) return ERROR(dstSize_tooSmall);
2413    if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
2414    if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
2415    if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
2416
2417    /* decoder timing evaluation */
2418    Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
2419    for (n=0; n<3; n++)
2420        Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2421
2422    Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2423
2424    if (Dtime[1] < Dtime[0]) algoNb = 1;
2425
2426    return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2427
2428    //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize);   /* multi-streams single-symbol decoding */
2429    //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize);   /* multi-streams double-symbols decoding */
2430    //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize);   /* multi-streams quad-symbols decoding */
2431}
2432/*
2433    zstd - standard compression library
2434    Copyright (C) 2014-2015, Yann Collet.
2435
2436    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2437
2438    Redistribution and use in source and binary forms, with or without
2439    modification, are permitted provided that the following conditions are
2440    met:
2441    * Redistributions of source code must retain the above copyright
2442    notice, this list of conditions and the following disclaimer.
2443    * Redistributions in binary form must reproduce the above
2444    copyright notice, this list of conditions and the following disclaimer
2445    in the documentation and/or other materials provided with the
2446    distribution.
2447    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2448    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2449    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2450    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2451    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2452    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2453    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2454    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2455    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2456    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2457    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2458
2459    You can contact the author at :
2460    - zstd source repository : https://github.com/Cyan4973/zstd
2461    - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2462*/
2463
2464/* ***************************************************************
2465*  Tuning parameters
2466*****************************************************************/
2467/*!
2468*  MEMORY_USAGE :
2469*  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2470*  Increasing memory usage improves compression ratio
2471*  Reduced memory usage can improve speed, due to cache effect
2472*/
2473#define ZSTD_MEMORY_USAGE 17
2474
2475/*!
2476 * HEAPMODE :
2477 * Select how default compression functions will allocate memory for their hash table,
2478 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2479 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2480 */
2481#ifndef ZSTD_HEAPMODE
2482#  define ZSTD_HEAPMODE 1
2483#endif /* ZSTD_HEAPMODE */
2484
2485/*!
2486*  LEGACY_SUPPORT :
2487*  decompressor can decode older formats (starting from Zstd 0.1+)
2488*/
2489#ifndef ZSTD_LEGACY_SUPPORT
2490#  define ZSTD_LEGACY_SUPPORT 1
2491#endif
2492
2493
2494/* *******************************************************
2495*  Includes
2496*********************************************************/
2497#include <stdlib.h>      /* calloc */
2498#include <string.h>      /* memcpy, memmove */
2499#include <stdio.h>       /* debug : printf */
2500
2501
2502/* *******************************************************
2503*  Compiler specifics
2504*********************************************************/
2505#ifdef __AVX2__
2506#  include <immintrin.h>   /* AVX2 intrinsics */
2507#endif
2508
2509#ifdef _MSC_VER    /* Visual Studio */
2510#  define FORCE_INLINE static __forceinline
2511#  include <intrin.h>                    /* For Visual 2005 */
2512#  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
2513#  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
2514#else
2515#  define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
2516#  ifdef __GNUC__
2517#    define FORCE_INLINE static inline __attribute__((always_inline))
2518#  else
2519#    define FORCE_INLINE static inline
2520#  endif
2521#endif
2522
2523
2524/* *******************************************************
2525*  Constants
2526*********************************************************/
2527#define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2528#define HASH_TABLESIZE (1 << HASH_LOG)
2529#define HASH_MASK (HASH_TABLESIZE - 1)
2530
2531#define KNUTH 2654435761
2532
2533#define BIT7 128
2534#define BIT6  64
2535#define BIT5  32
2536#define BIT4  16
2537#define BIT1   2
2538#define BIT0   1
2539
2540#define KB *(1 <<10)
2541#define MB *(1 <<20)
2542#define GB *(1U<<30)
2543
2544#define BLOCKSIZE (128 KB)                 /* define, for static allocation */
2545#define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2546#define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2547#define IS_RAW BIT0
2548#define IS_RLE BIT1
2549
2550#define WORKPLACESIZE (BLOCKSIZE*3)
2551#define MINMATCH 4
2552#define MLbits   7
2553#define LLbits   6
2554#define Offbits  5
2555#define MaxML  ((1<<MLbits )-1)
2556#define MaxLL  ((1<<LLbits )-1)
2557#define MaxOff   31
2558#define LitFSELog  11
2559#define MLFSELog   10
2560#define LLFSELog   10
2561#define OffFSELog   9
2562#define MAX(a,b) ((a)<(b)?(b):(a))
2563#define MaxSeq MAX(MaxLL, MaxML)
2564
2565#define LITERAL_NOENTROPY 63
2566#define COMMAND_NOENTROPY 7   /* to remove */
2567
2568static const size_t ZSTD_blockHeaderSize = 3;
2569static const size_t ZSTD_frameHeaderSize = 4;
2570
2571
2572/* *******************************************************
2573*  Memory operations
2574**********************************************************/
2575static void   ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2576
2577static void   ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2578
2579#define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2580
2581/*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2582static void ZSTD_wildcopy(void* dst, const void* src, size_t length)
2583{
2584    const BYTE* ip = (const BYTE*)src;
2585    BYTE* op = (BYTE*)dst;
2586    BYTE* const oend = op + length;
2587    do COPY8(op, ip) while (op < oend);
2588}
2589
2590
2591/* **************************************
2592*  Local structures
2593****************************************/
2594typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2595
2596typedef struct
2597{
2598    blockType_t blockType;
2599    U32 origSize;
2600} blockProperties_t;
2601
2602typedef struct {
2603    void* buffer;
2604    U32*  offsetStart;
2605    U32*  offset;
2606    BYTE* offCodeStart;
2607    BYTE* offCode;
2608    BYTE* litStart;
2609    BYTE* lit;
2610    BYTE* litLengthStart;
2611    BYTE* litLength;
2612    BYTE* matchLengthStart;
2613    BYTE* matchLength;
2614    BYTE* dumpsStart;
2615    BYTE* dumps;
2616} seqStore_t;
2617
2618
2619/* *************************************
2620*  Error Management
2621***************************************/
2622/*! ZSTD_isError
2623*   tells if a return value is an error code */
2624static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2625
2626
2627/* *************************************
2628*  Function body to include
2629***************************************/
2630static size_t ZSTD_read_ARCH(const void* p) { size_t r; memcpy(&r, p, sizeof(r)); return r; }
2631
2632MEM_STATIC unsigned ZSTD_NbCommonBytes (register size_t val)
2633{
2634    if (MEM_isLittleEndian())
2635    {
2636        if (MEM_64bits())
2637        {
2638#       if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
2639            unsigned long r = 0;
2640            _BitScanForward64( &r, (U64)val );
2641            return (int)(r>>3);
2642#       elif defined(__GNUC__) && (__GNUC__ >= 3) && !defined(LZ4_FORCE_SW_BITCOUNT)
2643            return (__builtin_ctzll((U64)val) >> 3);
2644#       else
2645            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 };
2646            return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
2647#       endif
2648        }
2649        else /* 32 bits */
2650        {
2651#       if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
2652            unsigned long r;
2653            _BitScanForward( &r, (U32)val );
2654            return (int)(r>>3);
2655#       elif defined(__GNUC__) && (__GNUC__ >= 3) && !defined(LZ4_FORCE_SW_BITCOUNT)
2656            return (__builtin_ctz((U32)val) >> 3);
2657#       else
2658            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 };
2659            return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
2660#       endif
2661        }
2662    }
2663    else   /* Big Endian CPU */
2664    {
2665        if (MEM_32bits())
2666        {
2667#       if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
2668            unsigned long r = 0;
2669            _BitScanReverse64( &r, val );
2670            return (unsigned)(r>>3);
2671#       elif defined(__GNUC__) && (__GNUC__ >= 3) && !defined(LZ4_FORCE_SW_BITCOUNT)
2672            return (__builtin_clzll(val) >> 3);
2673#       else
2674            unsigned r;
2675            const unsigned n32 = sizeof(size_t)*4;   /* calculate this way due to compiler complaining in 32-bits mode */
2676            if (!(val>>n32)) { r=4; } else { r=0; val>>=n32; }
2677            if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
2678            r += (!val);
2679            return r;
2680#       endif
2681        }
2682        else /* 32 bits */
2683        {
2684#       if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
2685            unsigned long r = 0;
2686            _BitScanReverse( &r, (unsigned long)val );
2687            return (unsigned)(r>>3);
2688#       elif defined(__GNUC__) && (__GNUC__ >= 3) && !defined(LZ4_FORCE_SW_BITCOUNT)
2689            return (__builtin_clz((U32)val) >> 3);
2690#       else
2691            unsigned r;
2692            if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
2693            r += (!val);
2694            return r;
2695#       endif
2696        }
2697    }
2698}
2699
2700
2701MEM_STATIC size_t ZSTD_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
2702{
2703    const BYTE* const pStart = pIn;
2704
2705    while ((pIn<pInLimit-(sizeof(size_t)-1)))
2706    {
2707        size_t diff = ZSTD_read_ARCH(pMatch) ^ ZSTD_read_ARCH(pIn);
2708        if (!diff) { pIn+=sizeof(size_t); pMatch+=sizeof(size_t); continue; }
2709        pIn += ZSTD_NbCommonBytes(diff);
2710        return (size_t)(pIn - pStart);
2711    }
2712
2713    if (MEM_32bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
2714    if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
2715    if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
2716    return (size_t)(pIn - pStart);
2717}
2718
2719
2720/* *************************************************************
2721*   Decompression section
2722***************************************************************/
2723struct ZSTD_DCtx_s
2724{
2725    U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2726    U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2727    U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2728    void* previousDstEnd;
2729    void* base;
2730    size_t expected;
2731    blockType_t bType;
2732    U32 phase;
2733    const BYTE* litPtr;
2734    size_t litBufSize;
2735    size_t litSize;
2736    BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2737};   /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2738
2739
2740static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2741{
2742    const BYTE* const in = (const BYTE* const)src;
2743    BYTE headerFlags;
2744    U32 cSize;
2745
2746    if (srcSize < 3) return ERROR(srcSize_wrong);
2747
2748    headerFlags = *in;
2749    cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2750
2751    bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2752    bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2753
2754    if (bpPtr->blockType == bt_end) return 0;
2755    if (bpPtr->blockType == bt_rle) return 1;
2756    return cSize;
2757}
2758
2759static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2760{
2761    if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2762    memcpy(dst, src, srcSize);
2763    return srcSize;
2764}
2765
2766
2767/** ZSTD_decompressLiterals
2768    @return : nb of bytes read from src, or an error code*/
2769static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2770                                const void* src, size_t srcSize)
2771{
2772    const BYTE* ip = (const BYTE*)src;
2773
2774    const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2775    const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2776
2777    if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2778    if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2779
2780    if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2781
2782    *maxDstSizePtr = litSize;
2783    return litCSize + 5;
2784}
2785
2786
2787/** ZSTD_decodeLiteralsBlock
2788    @return : nb of bytes read from src (< srcSize )*/
2789static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2790                          const void* src, size_t srcSize)
2791{
2792    ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2793    const BYTE* const istart = (const BYTE* const)src;
2794
2795    /* any compressed block with literals segment must be at least this size */
2796    if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2797
2798    switch(*istart & 3)
2799    {
2800    default:
2801    case 0:
2802        {
2803            size_t litSize = BLOCKSIZE;
2804            const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2805            dctx->litPtr = dctx->litBuffer;
2806            dctx->litBufSize = BLOCKSIZE;
2807            dctx->litSize = litSize;
2808            return readSize;   /* works if it's an error too */
2809        }
2810    case IS_RAW:
2811        {
2812            const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2813            if (litSize > srcSize-11)   /* risk of reading too far with wildcopy */
2814            {
2815                                if (litSize > srcSize-3) return ERROR(corruption_detected);
2816                                memcpy(dctx->litBuffer, istart, litSize);
2817                                dctx->litPtr = dctx->litBuffer;
2818                                dctx->litBufSize = BLOCKSIZE;
2819                                dctx->litSize = litSize;
2820                                return litSize+3;
2821                        }
2822                        /* direct reference into compressed stream */
2823            dctx->litPtr = istart+3;
2824            dctx->litBufSize = srcSize-3;
2825            dctx->litSize = litSize;
2826            return litSize+3;
2827        }
2828    case IS_RLE:
2829        {
2830            const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2831            if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2832            memset(dctx->litBuffer, istart[3], litSize);
2833            dctx->litPtr = dctx->litBuffer;
2834            dctx->litBufSize = BLOCKSIZE;
2835            dctx->litSize = litSize;
2836            return 4;
2837        }
2838    }
2839}
2840
2841
2842static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2843                         FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2844                         const void* src, size_t srcSize)
2845{
2846    const BYTE* const istart = (const BYTE* const)src;
2847    const BYTE* ip = istart;
2848    const BYTE* const iend = istart + srcSize;
2849    U32 LLtype, Offtype, MLtype;
2850    U32 LLlog, Offlog, MLlog;
2851    size_t dumpsLength;
2852
2853    /* check */
2854    if (srcSize < 5) return ERROR(srcSize_wrong);
2855
2856    /* SeqHead */
2857    *nbSeq = MEM_readLE16(ip); ip+=2;
2858    LLtype  = *ip >> 6;
2859    Offtype = (*ip >> 4) & 3;
2860    MLtype  = (*ip >> 2) & 3;
2861    if (*ip & 2)
2862    {
2863        dumpsLength  = ip[2];
2864        dumpsLength += ip[1] << 8;
2865        ip += 3;
2866    }
2867    else
2868    {
2869        dumpsLength  = ip[1];
2870        dumpsLength += (ip[0] & 1) << 8;
2871        ip += 2;
2872    }
2873    *dumpsPtr = ip;
2874    ip += dumpsLength;
2875    *dumpsLengthPtr = dumpsLength;
2876
2877    /* check */
2878    if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2879
2880    /* sequences */
2881    {
2882        S16 norm[MaxML+1];    /* assumption : MaxML >= MaxLL and MaxOff */
2883        size_t headerSize;
2884
2885        /* Build DTables */
2886        switch(LLtype)
2887        {
2888        U32 max;
2889        case bt_rle :
2890            LLlog = 0;
2891            FSE_buildDTable_rle(DTableLL, *ip++); break;
2892        case bt_raw :
2893            LLlog = LLbits;
2894            FSE_buildDTable_raw(DTableLL, LLbits); break;
2895        default :
2896            max = MaxLL;
2897            headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2898            if (FSE_isError(headerSize)) return ERROR(GENERIC);
2899            if (LLlog > LLFSELog) return ERROR(corruption_detected);
2900            ip += headerSize;
2901            FSE_buildDTable(DTableLL, norm, max, LLlog);
2902        }
2903
2904        switch(Offtype)
2905        {
2906        U32 max;
2907        case bt_rle :
2908            Offlog = 0;
2909            if (ip > iend-2) return ERROR(srcSize_wrong);   /* min : "raw", hence no header, but at least xxLog bits */
2910            FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2911            break;
2912        case bt_raw :
2913            Offlog = Offbits;
2914            FSE_buildDTable_raw(DTableOffb, Offbits); break;
2915        default :
2916            max = MaxOff;
2917            headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2918            if (FSE_isError(headerSize)) return ERROR(GENERIC);
2919            if (Offlog > OffFSELog) return ERROR(corruption_detected);
2920            ip += headerSize;
2921            FSE_buildDTable(DTableOffb, norm, max, Offlog);
2922        }
2923
2924        switch(MLtype)
2925        {
2926        U32 max;
2927        case bt_rle :
2928            MLlog = 0;
2929            if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2930            FSE_buildDTable_rle(DTableML, *ip++); break;
2931        case bt_raw :
2932            MLlog = MLbits;
2933            FSE_buildDTable_raw(DTableML, MLbits); break;
2934        default :
2935            max = MaxML;
2936            headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2937            if (FSE_isError(headerSize)) return ERROR(GENERIC);
2938            if (MLlog > MLFSELog) return ERROR(corruption_detected);
2939            ip += headerSize;
2940            FSE_buildDTable(DTableML, norm, max, MLlog);
2941        }
2942    }
2943
2944    return ip-istart;
2945}
2946
2947
2948typedef struct {
2949    size_t litLength;
2950    size_t offset;
2951    size_t matchLength;
2952} seq_t;
2953
2954typedef struct {
2955    BIT_DStream_t DStream;
2956    FSE_DState_t stateLL;
2957    FSE_DState_t stateOffb;
2958    FSE_DState_t stateML;
2959    size_t prevOffset;
2960    const BYTE* dumps;
2961    const BYTE* dumpsEnd;
2962} seqState_t;
2963
2964
2965static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2966{
2967    size_t litLength;
2968    size_t prevOffset;
2969    size_t offset;
2970    size_t matchLength;
2971    const BYTE* dumps = seqState->dumps;
2972    const BYTE* const de = seqState->dumpsEnd;
2973
2974    /* Literal length */
2975    litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2976    prevOffset = litLength ? seq->offset : seqState->prevOffset;
2977    seqState->prevOffset = seq->offset;
2978    if (litLength == MaxLL)
2979    {
2980        U32 add = *dumps++;
2981        if (add < 255) litLength += add;
2982        else
2983        {
2984            litLength = MEM_readLE32(dumps) & 0xFFFFFF;  /* no pb : dumps is always followed by seq tables > 1 byte */
2985            dumps += 3;
2986        }
2987        if (dumps >= de) dumps = de-1;   /* late correction, to avoid read overflow (data is now corrupted anyway) */
2988    }
2989
2990    /* Offset */
2991    {
2992        static const size_t offsetPrefix[MaxOff+1] = {  /* note : size_t faster than U32 */
2993                1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2994                512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2995                524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2996        U32 offsetCode, nbBits;
2997        offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream));   /* <= maxOff, by table construction */
2998        if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2999        nbBits = offsetCode - 1;
3000        if (offsetCode==0) nbBits = 0;   /* cmove */
3001        offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
3002        if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3003        if (offsetCode==0) offset = prevOffset;   /* cmove */
3004    }
3005
3006    /* MatchLength */
3007    matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3008    if (matchLength == MaxML)
3009    {
3010        U32 add = *dumps++;
3011        if (add < 255) matchLength += add;
3012        else
3013        {
3014            matchLength = MEM_readLE32(dumps) & 0xFFFFFF;  /* no pb : dumps is always followed by seq tables > 1 byte */
3015            dumps += 3;
3016        }
3017        if (dumps >= de) dumps = de-1;   /* late correction, to avoid read overflow (data is now corrupted anyway) */
3018    }
3019    matchLength += MINMATCH;
3020
3021    /* save result */
3022    seq->litLength = litLength;
3023    seq->offset = offset;
3024    seq->matchLength = matchLength;
3025    seqState->dumps = dumps;
3026}
3027
3028
3029static size_t ZSTD_execSequence(BYTE* op,
3030                                seq_t sequence,
3031                                const BYTE** litPtr, const BYTE* const litLimit,
3032                                BYTE* const base, BYTE* const oend)
3033{
3034    static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* added */
3035    static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11};   /* substracted */
3036    const BYTE* const ostart = op;
3037    BYTE* const oLitEnd = op + sequence.litLength;
3038    BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength;   /* risk : address space overflow (32-bits) */
3039    BYTE* const oend_8 = oend-8;
3040    const BYTE* const litEnd = *litPtr + sequence.litLength;
3041
3042    /* checks */
3043    if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);   /* last match must start at a minimum distance of 8 from oend */
3044    if (oMatchEnd > oend) return ERROR(dstSize_tooSmall);   /* overwrite beyond dst buffer */
3045    if (litEnd > litLimit-8) return ERROR(corruption_detected);   /* overRead beyond lit buffer */
3046
3047    /* copy Literals */
3048    ZSTD_wildcopy(op, *litPtr, sequence.litLength);   /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3049    op = oLitEnd;
3050    *litPtr = litEnd;   /* update for next sequence */
3051
3052    /* copy Match */
3053    {
3054        const BYTE* match = op - sequence.offset;
3055
3056        /* check */
3057        if (sequence.offset > (size_t)op) return ERROR(corruption_detected);   /* address space overflow test (this test seems kept by clang optimizer) */
3058        //if (match > op) return ERROR(corruption_detected);   /* address space overflow test (is clang optimizer removing this test ?) */
3059        if (match < base) return ERROR(corruption_detected);
3060
3061        /* close range match, overlap */
3062        if (sequence.offset < 8)
3063        {
3064            const int dec64 = dec64table[sequence.offset];
3065            op[0] = match[0];
3066            op[1] = match[1];
3067            op[2] = match[2];
3068            op[3] = match[3];
3069            match += dec32table[sequence.offset];
3070            ZSTD_copy4(op+4, match);
3071            match -= dec64;
3072        }
3073        else
3074        {
3075            ZSTD_copy8(op, match);
3076        }
3077        op += 8; match += 8;
3078
3079        if (oMatchEnd > oend-12)
3080        {
3081            if (op < oend_8)
3082            {
3083                ZSTD_wildcopy(op, match, oend_8 - op);
3084                match += oend_8 - op;
3085                op = oend_8;
3086            }
3087            while (op < oMatchEnd) *op++ = *match++;
3088        }
3089        else
3090        {
3091            ZSTD_wildcopy(op, match, sequence.matchLength-8);   /* works even if matchLength < 8 */
3092        }
3093    }
3094
3095    return oMatchEnd - ostart;
3096}
3097
3098static size_t ZSTD_decompressSequences(
3099                               void* ctx,
3100                               void* dst, size_t maxDstSize,
3101                         const void* seqStart, size_t seqSize)
3102{
3103    ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
3104    const BYTE* ip = (const BYTE*)seqStart;
3105    const BYTE* const iend = ip + seqSize;
3106    BYTE* const ostart = (BYTE* const)dst;
3107    BYTE* op = ostart;
3108    BYTE* const oend = ostart + maxDstSize;
3109    size_t errorCode, dumpsLength;
3110    const BYTE* litPtr = dctx->litPtr;
3111    const BYTE* const litMax = litPtr + dctx->litBufSize;
3112    const BYTE* const litEnd = litPtr + dctx->litSize;
3113    int nbSeq;
3114    const BYTE* dumps;
3115    U32* DTableLL = dctx->LLTable;
3116    U32* DTableML = dctx->MLTable;
3117    U32* DTableOffb = dctx->OffTable;
3118    BYTE* const base = (BYTE*) (dctx->base);
3119
3120    /* Build Decoding Tables */
3121    errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3122                                      DTableLL, DTableML, DTableOffb,
3123                                      ip, iend-ip);
3124    if (ZSTD_isError(errorCode)) return errorCode;
3125    ip += errorCode;
3126
3127    /* Regen sequences */
3128    {
3129        seq_t sequence;
3130        seqState_t seqState;
3131
3132        memset(&sequence, 0, sizeof(sequence));
3133        seqState.dumps = dumps;
3134        seqState.dumpsEnd = dumps + dumpsLength;
3135        seqState.prevOffset = sequence.offset = 4;
3136        errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
3137        if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3138        FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3139        FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3140        FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3141
3142        for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
3143        {
3144            size_t oneSeqSize;
3145            nbSeq--;
3146            ZSTD_decodeSequence(&sequence, &seqState);
3147            oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litMax, base, oend);
3148            if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
3149            op += oneSeqSize;
3150        }
3151
3152        /* check if reached exact end */
3153        if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected);   /* requested too much : data is corrupted */
3154        if (nbSeq<0) return ERROR(corruption_detected);   /* requested too many sequences : data is corrupted */
3155
3156        /* last literal segment */
3157        {
3158            size_t lastLLSize = litEnd - litPtr;
3159            if (litPtr > litEnd) return ERROR(corruption_detected);
3160            if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3161            if (op != litPtr) memmove(op, litPtr, lastLLSize);
3162            op += lastLLSize;
3163        }
3164    }
3165
3166    return op-ostart;
3167}
3168
3169
3170static size_t ZSTD_decompressBlock(
3171                            void* ctx,
3172                            void* dst, size_t maxDstSize,
3173                      const void* src, size_t srcSize)
3174{
3175    /* blockType == blockCompressed */
3176    const BYTE* ip = (const BYTE*)src;
3177
3178    /* Decode literals sub-block */
3179    size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
3180    if (ZSTD_isError(litCSize)) return litCSize;
3181    ip += litCSize;
3182    srcSize -= litCSize;
3183
3184    return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
3185}
3186
3187
3188static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3189{
3190    const BYTE* ip = (const BYTE*)src;
3191    const BYTE* iend = ip + srcSize;
3192    BYTE* const ostart = (BYTE* const)dst;
3193    BYTE* op = ostart;
3194    BYTE* const oend = ostart + maxDstSize;
3195    size_t remainingSize = srcSize;
3196    U32 magicNumber;
3197    blockProperties_t blockProperties;
3198
3199    /* Frame Header */
3200    if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3201    magicNumber = MEM_readLE32(src);
3202    if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3203    ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
3204
3205    /* Loop on each block */
3206    while (1)
3207    {
3208        size_t decodedSize=0;
3209        size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
3210        if (ZSTD_isError(cBlockSize)) return cBlockSize;
3211
3212        ip += ZSTD_blockHeaderSize;
3213        remainingSize -= ZSTD_blockHeaderSize;
3214        if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3215
3216        switch(blockProperties.blockType)
3217        {
3218        case bt_compressed:
3219            decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
3220            break;
3221        case bt_raw :
3222            decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
3223            break;
3224        case bt_rle :
3225            return ERROR(GENERIC);   /* not yet supported */
3226            break;
3227        case bt_end :
3228            /* end of frame */
3229            if (remainingSize) return ERROR(srcSize_wrong);
3230            break;
3231        default:
3232            return ERROR(GENERIC);   /* impossible */
3233        }
3234        if (cBlockSize == 0) break;   /* bt_end */
3235
3236        if (ZSTD_isError(decodedSize)) return decodedSize;
3237        op += decodedSize;
3238        ip += cBlockSize;
3239        remainingSize -= cBlockSize;
3240    }
3241
3242    return op-ostart;
3243}
3244
3245static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3246{
3247    ZSTD_DCtx ctx;
3248    ctx.base = dst;
3249    return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
3250}
3251
3252
3253/*******************************
3254*  Streaming Decompression API
3255*******************************/
3256
3257static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
3258{
3259    dctx->expected = ZSTD_frameHeaderSize;
3260    dctx->phase = 0;
3261    dctx->previousDstEnd = NULL;
3262    dctx->base = NULL;
3263    return 0;
3264}
3265
3266static ZSTD_DCtx* ZSTD_createDCtx(void)
3267{
3268    ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
3269    if (dctx==NULL) return NULL;
3270    ZSTD_resetDCtx(dctx);
3271    return dctx;
3272}
3273
3274static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3275{
3276    free(dctx);
3277    return 0;
3278}
3279
3280static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3281{
3282    return dctx->expected;
3283}
3284
3285static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3286{
3287    /* Sanity check */
3288    if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3289    if (dst != ctx->previousDstEnd)  /* not contiguous */
3290        ctx->base = dst;
3291
3292    /* Decompress : frame header */
3293    if (ctx->phase == 0)
3294    {
3295        /* Check frame magic header */
3296        U32 magicNumber = MEM_readLE32(src);
3297        if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3298        ctx->phase = 1;
3299        ctx->expected = ZSTD_blockHeaderSize;
3300        return 0;
3301    }
3302
3303    /* Decompress : block header */
3304    if (ctx->phase == 1)
3305    {
3306        blockProperties_t bp;
3307        size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3308        if (ZSTD_isError(blockSize)) return blockSize;
3309        if (bp.blockType == bt_end)
3310        {
3311            ctx->expected = 0;
3312            ctx->phase = 0;
3313        }
3314        else
3315        {
3316            ctx->expected = blockSize;
3317            ctx->bType = bp.blockType;
3318            ctx->phase = 2;
3319        }
3320
3321        return 0;
3322    }
3323
3324    /* Decompress : block content */
3325    {
3326        size_t rSize;
3327        switch(ctx->bType)
3328        {
3329        case bt_compressed:
3330            rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3331            break;
3332        case bt_raw :
3333            rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3334            break;
3335        case bt_rle :
3336            return ERROR(GENERIC);   /* not yet handled */
3337            break;
3338        case bt_end :   /* should never happen (filtered at phase 1) */
3339            rSize = 0;
3340            break;
3341        default:
3342            return ERROR(GENERIC);
3343        }
3344        ctx->phase = 1;
3345        ctx->expected = ZSTD_blockHeaderSize;
3346        ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3347        return rSize;
3348    }
3349
3350}
3351
3352
3353/* wrapper layer */
3354
3355unsigned ZSTDv03_isError(size_t code)
3356{
3357        return ZSTD_isError(code);
3358}
3359
3360size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3361                     const void* src, size_t compressedSize)
3362{
3363        return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3364}
3365
3366ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3367{
3368        return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3369}
3370
3371size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3372{
3373        return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3374}
3375
3376size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3377{
3378        return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3379}
3380
3381size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3382{
3383        return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3384}
3385
3386size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3387{
3388        return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);
3389}
Note: See TracBrowser for help on using the repository browser.