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