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