xref: /freebsd/sys/contrib/zstd/lib/legacy/zstd_v07.c (revision 4f52dfbb8d6c4d446500c5b097e3806ec219fbd4)
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 <stddef.h>     /* size_t, ptrdiff_t */
14 #include <string.h>     /* memcpy */
15 #include <stdlib.h>     /* malloc, free, qsort */
16 
17 #ifndef XXH_STATIC_LINKING_ONLY
18 #  define XXH_STATIC_LINKING_ONLY    /* XXH64_state_t */
19 #endif
20 #include "xxhash.h"                  /* XXH64_* */
21 #include "zstd_v07.h"
22 
23 #define FSEv07_STATIC_LINKING_ONLY   /* FSEv07_MIN_TABLELOG */
24 #define HUFv07_STATIC_LINKING_ONLY   /* HUFv07_TABLELOG_ABSOLUTEMAX */
25 #define ZSTDv07_STATIC_LINKING_ONLY
26 
27 #include "error_private.h"
28 
29 
30 #ifdef ZSTDv07_STATIC_LINKING_ONLY
31 
32 /* ====================================================================================
33  * The definitions in this section are considered experimental.
34  * They should never be used with a dynamic library, as they may change in the future.
35  * They are provided for advanced usages.
36  * Use them only in association with static linking.
37  * ==================================================================================== */
38 
39 /*--- Constants ---*/
40 #define ZSTDv07_MAGIC_SKIPPABLE_START  0x184D2A50U
41 
42 #define ZSTDv07_WINDOWLOG_MAX_32  25
43 #define ZSTDv07_WINDOWLOG_MAX_64  27
44 #define ZSTDv07_WINDOWLOG_MAX    ((U32)(MEM_32bits() ? ZSTDv07_WINDOWLOG_MAX_32 : ZSTDv07_WINDOWLOG_MAX_64))
45 #define ZSTDv07_WINDOWLOG_MIN     18
46 #define ZSTDv07_CHAINLOG_MAX     (ZSTDv07_WINDOWLOG_MAX+1)
47 #define ZSTDv07_CHAINLOG_MIN       4
48 #define ZSTDv07_HASHLOG_MAX       ZSTDv07_WINDOWLOG_MAX
49 #define ZSTDv07_HASHLOG_MIN       12
50 #define ZSTDv07_HASHLOG3_MAX      17
51 #define ZSTDv07_SEARCHLOG_MAX    (ZSTDv07_WINDOWLOG_MAX-1)
52 #define ZSTDv07_SEARCHLOG_MIN      1
53 #define ZSTDv07_SEARCHLENGTH_MAX   7
54 #define ZSTDv07_SEARCHLENGTH_MIN   3
55 #define ZSTDv07_TARGETLENGTH_MIN   4
56 #define ZSTDv07_TARGETLENGTH_MAX 999
57 
58 #define ZSTDv07_FRAMEHEADERSIZE_MAX 18    /* for static allocation */
59 static const size_t ZSTDv07_frameHeaderSize_min = 5;
60 static const size_t ZSTDv07_frameHeaderSize_max = ZSTDv07_FRAMEHEADERSIZE_MAX;
61 static const size_t ZSTDv07_skippableHeaderSize = 8;  /* magic number + skippable frame length */
62 
63 
64 /* custom memory allocation functions */
65 typedef void* (*ZSTDv07_allocFunction) (void* opaque, size_t size);
66 typedef void  (*ZSTDv07_freeFunction) (void* opaque, void* address);
67 typedef struct { ZSTDv07_allocFunction customAlloc; ZSTDv07_freeFunction customFree; void* opaque; } ZSTDv07_customMem;
68 
69 
70 /*--- Advanced Decompression functions ---*/
71 
72 /*! ZSTDv07_estimateDCtxSize() :
73  *  Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */
74 ZSTDLIBv07_API size_t ZSTDv07_estimateDCtxSize(void);
75 
76 /*! ZSTDv07_createDCtx_advanced() :
77  *  Create a ZSTD decompression context using external alloc and free functions */
78 ZSTDLIBv07_API ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem);
79 
80 /*! ZSTDv07_sizeofDCtx() :
81  *  Gives the amount of memory used by a given ZSTDv07_DCtx */
82 ZSTDLIBv07_API size_t ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx* dctx);
83 
84 
85 /* ******************************************************************
86 *  Buffer-less streaming functions (synchronous mode)
87 ********************************************************************/
88 
89 ZSTDLIBv07_API size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx);
90 ZSTDLIBv07_API size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize);
91 ZSTDLIBv07_API void   ZSTDv07_copyDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* preparedDCtx);
92 
93 ZSTDLIBv07_API size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx);
94 ZSTDLIBv07_API size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
95 
96 /*
97   Buffer-less streaming decompression (synchronous mode)
98 
99   A ZSTDv07_DCtx object is required to track streaming operations.
100   Use ZSTDv07_createDCtx() / ZSTDv07_freeDCtx() to manage it.
101   A ZSTDv07_DCtx object can be re-used multiple times.
102 
103   First optional operation is to retrieve frame parameters, using ZSTDv07_getFrameParams(), which doesn't consume the input.
104   It can provide the minimum size of rolling buffer required to properly decompress data (`windowSize`),
105   and optionally the final size of uncompressed content.
106   (Note : content size is an optional info that may not be present. 0 means : content size unknown)
107   Frame parameters are extracted from the beginning of compressed frame.
108   The amount of data to read is variable, from ZSTDv07_frameHeaderSize_min to ZSTDv07_frameHeaderSize_max (so if `srcSize` >= ZSTDv07_frameHeaderSize_max, it will always work)
109   If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
110   Result : 0 when successful, it means the ZSTDv07_frameParams structure has been filled.
111           >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
112            errorCode, which can be tested using ZSTDv07_isError()
113 
114   Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().
115   Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().
116 
117   Then use ZSTDv07_nextSrcSizeToDecompress() and ZSTDv07_decompressContinue() alternatively.
118   ZSTDv07_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv07_decompressContinue().
119   ZSTDv07_decompressContinue() requires this exact amount of bytes, or it will fail.
120 
121   @result of ZSTDv07_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity).
122   It can be zero, which is not an error; it just means ZSTDv07_decompressContinue() has decoded some header.
123 
124   ZSTDv07_decompressContinue() needs previous data blocks during decompression, up to `windowSize`.
125   They should preferably be located contiguously, prior to current block.
126   Alternatively, a round buffer of sufficient size is also possible. Sufficient size is determined by frame parameters.
127   ZSTDv07_decompressContinue() is very sensitive to contiguity,
128   if 2 blocks don't follow each other, make sure that either the compressor breaks contiguity at the same place,
129     or that previous contiguous segment is large enough to properly handle maximum back-reference.
130 
131   A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.
132   Context can then be reset to start a new decompression.
133 
134 
135   == Special case : skippable frames ==
136 
137   Skippable frames allow the integration of user-defined data into a flow of concatenated frames.
138   Skippable frames will be ignored (skipped) by a decompressor. The format of skippable frame is following:
139   a) Skippable frame ID - 4 Bytes, Little endian format, any value from 0x184D2A50 to 0x184D2A5F
140   b) Frame Size - 4 Bytes, Little endian format, unsigned 32-bits
141   c) Frame Content - any content (User Data) of length equal to Frame Size
142   For skippable frames ZSTDv07_decompressContinue() always returns 0.
143   For skippable frames ZSTDv07_getFrameParams() returns fparamsPtr->windowLog==0 what means that a frame is skippable.
144   It also returns Frame Size as fparamsPtr->frameContentSize.
145 */
146 
147 
148 /* **************************************
149 *  Block functions
150 ****************************************/
151 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
152     Frame metadata cost is typically ~18 bytes, which can be non-negligible for very small blocks (< 100 bytes).
153     User will have to take in charge required information to regenerate data, such as compressed and content sizes.
154 
155     A few rules to respect :
156     - Compressing and decompressing require a context structure
157       + Use ZSTDv07_createCCtx() and ZSTDv07_createDCtx()
158     - It is necessary to init context before starting
159       + compression : ZSTDv07_compressBegin()
160       + decompression : ZSTDv07_decompressBegin()
161       + variants _usingDict() are also allowed
162       + copyCCtx() and copyDCtx() work too
163     - Block size is limited, it must be <= ZSTDv07_getBlockSizeMax()
164       + If you need to compress more, cut data into multiple blocks
165       + Consider using the regular ZSTDv07_compress() instead, as frame metadata costs become negligible when source size is large.
166     - When a block is considered not compressible enough, ZSTDv07_compressBlock() result will be zero.
167       In which case, nothing is produced into `dst`.
168       + User must test for such outcome and deal directly with uncompressed data
169       + ZSTDv07_decompressBlock() doesn't accept uncompressed data as input !!!
170       + In case of multiple successive blocks, decoder must be informed of uncompressed block existence to follow proper history.
171         Use ZSTDv07_insertBlock() in such a case.
172 */
173 
174 #define ZSTDv07_BLOCKSIZE_ABSOLUTEMAX (128 * 1024)   /* define, for static allocation */
175 ZSTDLIBv07_API size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
176 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize);  /**< insert block into `dctx` history. Useful for uncompressed blocks */
177 
178 
179 #endif   /* ZSTDv07_STATIC_LINKING_ONLY */
180 
181 
182 /* ******************************************************************
183    mem.h
184    low-level memory access routines
185    Copyright (C) 2013-2015, Yann Collet.
186 
187    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
188 
189    Redistribution and use in source and binary forms, with or without
190    modification, are permitted provided that the following conditions are
191    met:
192 
193        * Redistributions of source code must retain the above copyright
194    notice, this list of conditions and the following disclaimer.
195        * Redistributions in binary form must reproduce the above
196    copyright notice, this list of conditions and the following disclaimer
197    in the documentation and/or other materials provided with the
198    distribution.
199 
200    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
201    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
202    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
203    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
204    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
205    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
206    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
207    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
208    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
209    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
210    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
211 
212     You can contact the author at :
213     - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
214     - Public forum : https://groups.google.com/forum/#!forum/lz4c
215 ****************************************************************** */
216 #ifndef MEM_H_MODULE
217 #define MEM_H_MODULE
218 
219 #if defined (__cplusplus)
220 extern "C" {
221 #endif
222 
223 /*-****************************************
224 *  Compiler specifics
225 ******************************************/
226 #if defined(_MSC_VER)   /* Visual Studio */
227 #   include <stdlib.h>  /* _byteswap_ulong */
228 #   include <intrin.h>  /* _byteswap_* */
229 #endif
230 #if defined(__GNUC__)
231 #  define MEM_STATIC static __attribute__((unused))
232 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
233 #  define MEM_STATIC static inline
234 #elif defined(_MSC_VER)
235 #  define MEM_STATIC static __inline
236 #else
237 #  define MEM_STATIC static  /* this version may generate warnings for unused static functions; disable the relevant warning */
238 #endif
239 
240 
241 /*-**************************************************************
242 *  Basic Types
243 *****************************************************************/
244 #if  !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
245 # include <stdint.h>
246   typedef  uint8_t BYTE;
247   typedef uint16_t U16;
248   typedef  int16_t S16;
249   typedef uint32_t U32;
250   typedef  int32_t S32;
251   typedef uint64_t U64;
252   typedef  int64_t S64;
253 #else
254   typedef unsigned char       BYTE;
255   typedef unsigned short      U16;
256   typedef   signed short      S16;
257   typedef unsigned int        U32;
258   typedef   signed int        S32;
259   typedef unsigned long long  U64;
260   typedef   signed long long  S64;
261 #endif
262 
263 
264 /*-**************************************************************
265 *  Memory I/O
266 *****************************************************************/
267 /* MEM_FORCE_MEMORY_ACCESS :
268  * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
269  * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
270  * The below switch allow to select different access method for improved performance.
271  * Method 0 (default) : use `memcpy()`. Safe and portable.
272  * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
273  *            This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
274  * Method 2 : direct access. This method is portable but violate C standard.
275  *            It can generate buggy code on targets depending on alignment.
276  *            In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
277  * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
278  * Prefer these methods in priority order (0 > 1 > 2)
279  */
280 #ifndef MEM_FORCE_MEMORY_ACCESS   /* can be defined externally, on command line for example */
281 #  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__) )
282 #    define MEM_FORCE_MEMORY_ACCESS 2
283 #  elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
284   (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
285 #    define MEM_FORCE_MEMORY_ACCESS 1
286 #  endif
287 #endif
288 
289 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
290 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
291 
292 MEM_STATIC unsigned MEM_isLittleEndian(void)
293 {
294     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
295     return one.c[0];
296 }
297 
298 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
299 
300 /* violates C standard, by lying on structure alignment.
301 Only use if no other choice to achieve best performance on target platform */
302 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
303 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
304 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
305 
306 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
307 
308 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
309 
310 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
311 /* currently only defined for gcc and icc */
312 typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign;
313 
314 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
315 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
316 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
317 
318 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
319 
320 #else
321 
322 /* default method, safe and standard.
323    can sometimes prove slower */
324 
325 MEM_STATIC U16 MEM_read16(const void* memPtr)
326 {
327     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
328 }
329 
330 MEM_STATIC U32 MEM_read32(const void* memPtr)
331 {
332     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
333 }
334 
335 MEM_STATIC U64 MEM_read64(const void* memPtr)
336 {
337     U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
338 }
339 
340 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
341 {
342     memcpy(memPtr, &value, sizeof(value));
343 }
344 
345 #endif /* MEM_FORCE_MEMORY_ACCESS */
346 
347 MEM_STATIC U32 MEM_swap32(U32 in)
348 {
349 #if defined(_MSC_VER)     /* Visual Studio */
350     return _byteswap_ulong(in);
351 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
352     return __builtin_bswap32(in);
353 #else
354     return  ((in << 24) & 0xff000000 ) |
355             ((in <<  8) & 0x00ff0000 ) |
356             ((in >>  8) & 0x0000ff00 ) |
357             ((in >> 24) & 0x000000ff );
358 #endif
359 }
360 
361 MEM_STATIC U64 MEM_swap64(U64 in)
362 {
363 #if defined(_MSC_VER)     /* Visual Studio */
364     return _byteswap_uint64(in);
365 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
366     return __builtin_bswap64(in);
367 #else
368     return  ((in << 56) & 0xff00000000000000ULL) |
369             ((in << 40) & 0x00ff000000000000ULL) |
370             ((in << 24) & 0x0000ff0000000000ULL) |
371             ((in << 8)  & 0x000000ff00000000ULL) |
372             ((in >> 8)  & 0x00000000ff000000ULL) |
373             ((in >> 24) & 0x0000000000ff0000ULL) |
374             ((in >> 40) & 0x000000000000ff00ULL) |
375             ((in >> 56) & 0x00000000000000ffULL);
376 #endif
377 }
378 
379 
380 /*=== Little endian r/w ===*/
381 
382 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
383 {
384     if (MEM_isLittleEndian())
385         return MEM_read16(memPtr);
386     else {
387         const BYTE* p = (const BYTE*)memPtr;
388         return (U16)(p[0] + (p[1]<<8));
389     }
390 }
391 
392 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
393 {
394     if (MEM_isLittleEndian()) {
395         MEM_write16(memPtr, val);
396     } else {
397         BYTE* p = (BYTE*)memPtr;
398         p[0] = (BYTE)val;
399         p[1] = (BYTE)(val>>8);
400     }
401 }
402 
403 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
404 {
405     if (MEM_isLittleEndian())
406         return MEM_read32(memPtr);
407     else
408         return MEM_swap32(MEM_read32(memPtr));
409 }
410 
411 
412 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
413 {
414     if (MEM_isLittleEndian())
415         return MEM_read64(memPtr);
416     else
417         return MEM_swap64(MEM_read64(memPtr));
418 }
419 
420 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
421 {
422     if (MEM_32bits())
423         return (size_t)MEM_readLE32(memPtr);
424     else
425         return (size_t)MEM_readLE64(memPtr);
426 }
427 
428 
429 
430 #if defined (__cplusplus)
431 }
432 #endif
433 
434 #endif /* MEM_H_MODULE */
435 /* ******************************************************************
436    bitstream
437    Part of FSE library
438    header file (to include)
439    Copyright (C) 2013-2016, Yann Collet.
440 
441    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
442 
443    Redistribution and use in source and binary forms, with or without
444    modification, are permitted provided that the following conditions are
445    met:
446 
447        * Redistributions of source code must retain the above copyright
448    notice, this list of conditions and the following disclaimer.
449        * Redistributions in binary form must reproduce the above
450    copyright notice, this list of conditions and the following disclaimer
451    in the documentation and/or other materials provided with the
452    distribution.
453 
454    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
455    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
456    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
457    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
458    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
459    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
460    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
461    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
462    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
463    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
464    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
465 
466    You can contact the author at :
467    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
468 ****************************************************************** */
469 #ifndef BITSTREAM_H_MODULE
470 #define BITSTREAM_H_MODULE
471 
472 #if defined (__cplusplus)
473 extern "C" {
474 #endif
475 
476 
477 /*
478 *  This API consists of small unitary functions, which must be inlined for best performance.
479 *  Since link-time-optimization is not available for all compilers,
480 *  these functions are defined into a .h to be included.
481 */
482 
483 
484 /*=========================================
485 *  Target specific
486 =========================================*/
487 #if defined(__BMI__) && defined(__GNUC__)
488 #  include <immintrin.h>   /* support for bextr (experimental) */
489 #endif
490 
491 /*-********************************************
492 *  bitStream decoding API (read backward)
493 **********************************************/
494 typedef struct
495 {
496     size_t   bitContainer;
497     unsigned bitsConsumed;
498     const char* ptr;
499     const char* start;
500 } BITv07_DStream_t;
501 
502 typedef enum { BITv07_DStream_unfinished = 0,
503                BITv07_DStream_endOfBuffer = 1,
504                BITv07_DStream_completed = 2,
505                BITv07_DStream_overflow = 3 } BITv07_DStream_status;  /* result of BITv07_reloadDStream() */
506                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
507 
508 MEM_STATIC size_t   BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
509 MEM_STATIC size_t   BITv07_readBits(BITv07_DStream_t* bitD, unsigned nbBits);
510 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD);
511 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* bitD);
512 
513 
514 
515 /*-****************************************
516 *  unsafe API
517 ******************************************/
518 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, unsigned nbBits);
519 /* faster, but works only if nbBits >= 1 */
520 
521 
522 
523 /*-**************************************************************
524 *  Internal functions
525 ****************************************************************/
526 MEM_STATIC unsigned BITv07_highbit32 (U32 val)
527 {
528 #   if defined(_MSC_VER)   /* Visual */
529     unsigned long r=0;
530     _BitScanReverse ( &r, val );
531     return (unsigned) r;
532 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */
533     return 31 - __builtin_clz (val);
534 #   else   /* Software version */
535     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 };
536     U32 v = val;
537     v |= v >> 1;
538     v |= v >> 2;
539     v |= v >> 4;
540     v |= v >> 8;
541     v |= v >> 16;
542     return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
543 #   endif
544 }
545 
546 
547 
548 /*-********************************************************
549 * bitStream decoding
550 **********************************************************/
551 /*! BITv07_initDStream() :
552 *   Initialize a BITv07_DStream_t.
553 *   `bitD` : a pointer to an already allocated BITv07_DStream_t structure.
554 *   `srcSize` must be the *exact* size of the bitStream, in bytes.
555 *   @return : size of stream (== srcSize) or an errorCode if a problem is detected
556 */
557 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
558 {
559     if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
560 
561     if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
562         bitD->start = (const char*)srcBuffer;
563         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
564         bitD->bitContainer = MEM_readLEST(bitD->ptr);
565         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
566           bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
567           if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
568     } else {
569         bitD->start = (const char*)srcBuffer;
570         bitD->ptr   = bitD->start;
571         bitD->bitContainer = *(const BYTE*)(bitD->start);
572         switch(srcSize)
573         {
574             case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
575             case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
576             case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
577             case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
578             case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
579             case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8; /* fall-through */
580             default: break;
581         }
582         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
583           bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
584           if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
585         bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
586     }
587 
588     return srcSize;
589 }
590 
591 
592  MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits)
593 {
594     U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
595     return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
596 }
597 
598 /*! BITv07_lookBitsFast() :
599 *   unsafe version; only works only if nbBits >= 1 */
600 MEM_STATIC size_t BITv07_lookBitsFast(const BITv07_DStream_t* bitD, U32 nbBits)
601 {
602     U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
603     return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
604 }
605 
606 MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits)
607 {
608     bitD->bitsConsumed += nbBits;
609 }
610 
611 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits)
612 {
613     size_t const value = BITv07_lookBits(bitD, nbBits);
614     BITv07_skipBits(bitD, nbBits);
615     return value;
616 }
617 
618 /*! BITv07_readBitsFast() :
619 *   unsafe version; only works only if nbBits >= 1 */
620 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, U32 nbBits)
621 {
622     size_t const value = BITv07_lookBitsFast(bitD, nbBits);
623     BITv07_skipBits(bitD, nbBits);
624     return value;
625 }
626 
627 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD)
628 {
629     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should not happen => corruption detected */
630         return BITv07_DStream_overflow;
631 
632     if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
633         bitD->ptr -= bitD->bitsConsumed >> 3;
634         bitD->bitsConsumed &= 7;
635         bitD->bitContainer = MEM_readLEST(bitD->ptr);
636         return BITv07_DStream_unfinished;
637     }
638     if (bitD->ptr == bitD->start) {
639         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv07_DStream_endOfBuffer;
640         return BITv07_DStream_completed;
641     }
642     {   U32 nbBytes = bitD->bitsConsumed >> 3;
643         BITv07_DStream_status result = BITv07_DStream_unfinished;
644         if (bitD->ptr - nbBytes < bitD->start) {
645             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
646             result = BITv07_DStream_endOfBuffer;
647         }
648         bitD->ptr -= nbBytes;
649         bitD->bitsConsumed -= nbBytes*8;
650         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
651         return result;
652     }
653 }
654 
655 /*! BITv07_endOfDStream() :
656 *   @return Tells if DStream has exactly reached its end (all bits consumed).
657 */
658 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* DStream)
659 {
660     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
661 }
662 
663 #if defined (__cplusplus)
664 }
665 #endif
666 
667 #endif /* BITSTREAM_H_MODULE */
668 /* ******************************************************************
669    FSE : Finite State Entropy codec
670    Public Prototypes declaration
671    Copyright (C) 2013-2016, Yann Collet.
672 
673    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
674 
675    Redistribution and use in source and binary forms, with or without
676    modification, are permitted provided that the following conditions are
677    met:
678 
679        * Redistributions of source code must retain the above copyright
680    notice, this list of conditions and the following disclaimer.
681        * Redistributions in binary form must reproduce the above
682    copyright notice, this list of conditions and the following disclaimer
683    in the documentation and/or other materials provided with the
684    distribution.
685 
686    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
687    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
688    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
689    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
690    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
691    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
692    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
693    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
694    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
695    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
696    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
697 
698    You can contact the author at :
699    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
700 ****************************************************************** */
701 #ifndef FSEv07_H
702 #define FSEv07_H
703 
704 #if defined (__cplusplus)
705 extern "C" {
706 #endif
707 
708 
709 
710 /*-****************************************
711 *  FSE simple functions
712 ******************************************/
713 
714 /*! FSEv07_decompress():
715     Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
716     into already allocated destination buffer 'dst', of size 'dstCapacity'.
717     @return : size of regenerated data (<= maxDstSize),
718               or an error code, which can be tested using FSEv07_isError() .
719 
720     ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!
721     Why ? : making this distinction requires a header.
722     Header management is intentionally delegated to the user layer, which can better manage special cases.
723 */
724 size_t FSEv07_decompress(void* dst,  size_t dstCapacity,
725                 const void* cSrc, size_t cSrcSize);
726 
727 
728 /* Error Management */
729 unsigned    FSEv07_isError(size_t code);        /* tells if a return value is an error code */
730 const char* FSEv07_getErrorName(size_t code);   /* provides error code string (useful for debugging) */
731 
732 
733 /*-*****************************************
734 *  FSE detailed API
735 ******************************************/
736 /*!
737 FSEv07_decompress() does the following:
738 1. read normalized counters with readNCount()
739 2. build decoding table 'DTable' from normalized counters
740 3. decode the data stream using decoding table 'DTable'
741 
742 The following API allows targeting specific sub-functions for advanced tasks.
743 For example, it's possible to compress several blocks using the same 'CTable',
744 or to save and provide normalized distribution using external method.
745 */
746 
747 
748 /* *** DECOMPRESSION *** */
749 
750 /*! FSEv07_readNCount():
751     Read compactly saved 'normalizedCounter' from 'rBuffer'.
752     @return : size read from 'rBuffer',
753               or an errorCode, which can be tested using FSEv07_isError().
754               maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
755 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
756 
757 /*! Constructor and Destructor of FSEv07_DTable.
758     Note that its size depends on 'tableLog' */
759 typedef unsigned FSEv07_DTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
760 FSEv07_DTable* FSEv07_createDTable(unsigned tableLog);
761 void        FSEv07_freeDTable(FSEv07_DTable* dt);
762 
763 /*! FSEv07_buildDTable():
764     Builds 'dt', which must be already allocated, using FSEv07_createDTable().
765     return : 0, or an errorCode, which can be tested using FSEv07_isError() */
766 size_t FSEv07_buildDTable (FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
767 
768 /*! FSEv07_decompress_usingDTable():
769     Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
770     into `dst` which must be already allocated.
771     @return : size of regenerated data (necessarily <= `dstCapacity`),
772               or an errorCode, which can be tested using FSEv07_isError() */
773 size_t FSEv07_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv07_DTable* dt);
774 
775 /*!
776 Tutorial :
777 ----------
778 (Note : these functions only decompress FSE-compressed blocks.
779  If block is uncompressed, use memcpy() instead
780  If block is a single repeated byte, use memset() instead )
781 
782 The first step is to obtain the normalized frequencies of symbols.
783 This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().
784 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
785 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
786 or size the table to handle worst case situations (typically 256).
787 FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
788 The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.
789 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
790 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
791 
792 The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.
793 This is performed by the function FSEv07_buildDTable().
794 The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().
795 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
796 
797 `FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().
798 `cSrcSize` must be strictly correct, otherwise decompression will fail.
799 FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
800 If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)
801 */
802 
803 
804 #ifdef FSEv07_STATIC_LINKING_ONLY
805 
806 
807 /* *****************************************
808 *  Static allocation
809 *******************************************/
810 /* FSE buffer bounds */
811 #define FSEv07_NCOUNTBOUND 512
812 #define FSEv07_BLOCKBOUND(size) (size + (size>>7))
813 
814 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
815 #define FSEv07_DTABLE_SIZE_U32(maxTableLog)                   (1 + (1<<maxTableLog))
816 
817 
818 /* *****************************************
819 *  FSE advanced API
820 *******************************************/
821 size_t FSEv07_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
822 /**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr  */
823 
824 unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus);
825 /**< same as FSEv07_optimalTableLog(), which used `minus==2` */
826 
827 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits);
828 /**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
829 
830 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, unsigned char symbolValue);
831 /**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */
832 
833 
834 
835 /* *****************************************
836 *  FSE symbol decompression API
837 *******************************************/
838 typedef struct
839 {
840     size_t      state;
841     const void* table;   /* precise table may vary, depending on U16 */
842 } FSEv07_DState_t;
843 
844 
845 static void     FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt);
846 
847 static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
848 
849 
850 
851 /* *****************************************
852 *  FSE unsafe API
853 *******************************************/
854 static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
855 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
856 
857 
858 /* ======    Decompression    ====== */
859 
860 typedef struct {
861     U16 tableLog;
862     U16 fastMode;
863 } FSEv07_DTableHeader;   /* sizeof U32 */
864 
865 typedef struct
866 {
867     unsigned short newState;
868     unsigned char  symbol;
869     unsigned char  nbBits;
870 } FSEv07_decode_t;   /* size == U32 */
871 
872 MEM_STATIC void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt)
873 {
874     const void* ptr = dt;
875     const FSEv07_DTableHeader* const DTableH = (const FSEv07_DTableHeader*)ptr;
876     DStatePtr->state = BITv07_readBits(bitD, DTableH->tableLog);
877     BITv07_reloadDStream(bitD);
878     DStatePtr->table = dt + 1;
879 }
880 
881 MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr)
882 {
883     FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
884     return DInfo.symbol;
885 }
886 
887 MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
888 {
889     FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
890     U32 const nbBits = DInfo.nbBits;
891     size_t const lowBits = BITv07_readBits(bitD, nbBits);
892     DStatePtr->state = DInfo.newState + lowBits;
893 }
894 
895 MEM_STATIC BYTE FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
896 {
897     FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
898     U32 const nbBits = DInfo.nbBits;
899     BYTE const symbol = DInfo.symbol;
900     size_t const lowBits = BITv07_readBits(bitD, nbBits);
901 
902     DStatePtr->state = DInfo.newState + lowBits;
903     return symbol;
904 }
905 
906 /*! FSEv07_decodeSymbolFast() :
907     unsafe, only works if no symbol has a probability > 50% */
908 MEM_STATIC BYTE FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
909 {
910     FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
911     U32 const nbBits = DInfo.nbBits;
912     BYTE const symbol = DInfo.symbol;
913     size_t const lowBits = BITv07_readBitsFast(bitD, nbBits);
914 
915     DStatePtr->state = DInfo.newState + lowBits;
916     return symbol;
917 }
918 
919 
920 
921 #ifndef FSEv07_COMMONDEFS_ONLY
922 
923 /* **************************************************************
924 *  Tuning parameters
925 ****************************************************************/
926 /*!MEMORY_USAGE :
927 *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
928 *  Increasing memory usage improves compression ratio
929 *  Reduced memory usage can improve speed, due to cache effect
930 *  Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
931 #define FSEv07_MAX_MEMORY_USAGE 14
932 #define FSEv07_DEFAULT_MEMORY_USAGE 13
933 
934 /*!FSEv07_MAX_SYMBOL_VALUE :
935 *  Maximum symbol value authorized.
936 *  Required for proper stack allocation */
937 #define FSEv07_MAX_SYMBOL_VALUE 255
938 
939 
940 /* **************************************************************
941 *  template functions type & suffix
942 ****************************************************************/
943 #define FSEv07_FUNCTION_TYPE BYTE
944 #define FSEv07_FUNCTION_EXTENSION
945 #define FSEv07_DECODE_TYPE FSEv07_decode_t
946 
947 
948 #endif   /* !FSEv07_COMMONDEFS_ONLY */
949 
950 
951 /* ***************************************************************
952 *  Constants
953 *****************************************************************/
954 #define FSEv07_MAX_TABLELOG  (FSEv07_MAX_MEMORY_USAGE-2)
955 #define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)
956 #define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)
957 #define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)
958 #define FSEv07_MIN_TABLELOG 5
959 
960 #define FSEv07_TABLELOG_ABSOLUTE_MAX 15
961 #if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX
962 #  error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"
963 #endif
964 
965 #define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
966 
967 
968 #endif /* FSEv07_STATIC_LINKING_ONLY */
969 
970 
971 #if defined (__cplusplus)
972 }
973 #endif
974 
975 #endif  /* FSEv07_H */
976 /* ******************************************************************
977    Huffman coder, part of New Generation Entropy library
978    header file
979    Copyright (C) 2013-2016, Yann Collet.
980 
981    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
982 
983    Redistribution and use in source and binary forms, with or without
984    modification, are permitted provided that the following conditions are
985    met:
986 
987        * Redistributions of source code must retain the above copyright
988    notice, this list of conditions and the following disclaimer.
989        * Redistributions in binary form must reproduce the above
990    copyright notice, this list of conditions and the following disclaimer
991    in the documentation and/or other materials provided with the
992    distribution.
993 
994    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
995    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
996    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
997    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
998    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
999    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1000    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1001    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1002    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1003    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1004    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1005 
1006    You can contact the author at :
1007    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1008 ****************************************************************** */
1009 #ifndef HUFv07_H_298734234
1010 #define HUFv07_H_298734234
1011 
1012 #if defined (__cplusplus)
1013 extern "C" {
1014 #endif
1015 
1016 
1017 
1018 /* *** simple functions *** */
1019 /**
1020 HUFv07_decompress() :
1021     Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1022     into already allocated buffer 'dst', of minimum size 'dstSize'.
1023     `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
1024     Note : in contrast with FSE, HUFv07_decompress can regenerate
1025            RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1026            because it knows size to regenerate.
1027     @return : size of regenerated data (== dstSize),
1028               or an error code, which can be tested using HUFv07_isError()
1029 */
1030 size_t HUFv07_decompress(void* dst,  size_t dstSize,
1031                 const void* cSrc, size_t cSrcSize);
1032 
1033 
1034 /* ****************************************
1035 *  Tool functions
1036 ******************************************/
1037 #define HUFv07_BLOCKSIZE_MAX (128 * 1024)
1038 
1039 /* Error Management */
1040 unsigned    HUFv07_isError(size_t code);        /**< tells if a return value is an error code */
1041 const char* HUFv07_getErrorName(size_t code);   /**< provides error code string (useful for debugging) */
1042 
1043 
1044 /* *** Advanced function *** */
1045 
1046 
1047 #ifdef HUFv07_STATIC_LINKING_ONLY
1048 
1049 
1050 /* *** Constants *** */
1051 #define HUFv07_TABLELOG_ABSOLUTEMAX  16   /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */
1052 #define HUFv07_TABLELOG_MAX  12           /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */
1053 #define HUFv07_TABLELOG_DEFAULT  11       /* tableLog by default, when not specified */
1054 #define HUFv07_SYMBOLVALUE_MAX 255
1055 #if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX)
1056 #  error "HUFv07_TABLELOG_MAX is too large !"
1057 #endif
1058 
1059 
1060 /* ****************************************
1061 *  Static allocation
1062 ******************************************/
1063 /* HUF buffer bounds */
1064 #define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8)   /* only true if incompressible pre-filtered with fast heuristic */
1065 
1066 /* static allocation of HUF's DTable */
1067 typedef U32 HUFv07_DTable;
1068 #define HUFv07_DTABLE_SIZE(maxTableLog)   (1 + (1<<(maxTableLog)))
1069 #define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1070         HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
1071 #define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1072         HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
1073 
1074 
1075 /* ****************************************
1076 *  Advanced decompression functions
1077 ******************************************/
1078 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
1079 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
1080 
1081 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< decodes RLE and uncompressed */
1082 size_t HUFv07_decompress4X_hufOnly(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< considers RLE and uncompressed as errors */
1083 size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
1084 size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
1085 
1086 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
1087 size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< single-symbol decoder */
1088 size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /**< double-symbols decoder */
1089 
1090 
1091 /* ****************************************
1092 *  HUF detailed API
1093 ******************************************/
1094 /*!
1095 The following API allows targeting specific sub-functions for advanced tasks.
1096 For example, it's possible to compress several blocks using the same 'CTable',
1097 or to save and regenerate 'CTable' using external methods.
1098 */
1099 /* FSEv07_count() : find it within "fse.h" */
1100 
1101 /*! HUFv07_readStats() :
1102     Read compact Huffman tree, saved by HUFv07_writeCTable().
1103     `huffWeight` is destination buffer.
1104     @return : size read from `src` , or an error Code .
1105     Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */
1106 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1107                      U32* nbSymbolsPtr, U32* tableLogPtr,
1108                      const void* src, size_t srcSize);
1109 
1110 
1111 /*
1112 HUFv07_decompress() does the following:
1113 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1114 2. build Huffman table from save, using HUFv07_readDTableXn()
1115 3. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable
1116 */
1117 
1118 /** HUFv07_selectDecoder() :
1119 *   Tells which decoder is likely to decode faster,
1120 *   based on a set of pre-determined metrics.
1121 *   @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
1122 *   Assumption : 0 < cSrcSize < dstSize <= 128 KB */
1123 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize);
1124 
1125 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1126 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1127 
1128 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1129 size_t HUFv07_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1130 size_t HUFv07_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1131 
1132 
1133 /* single stream variants */
1134 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
1135 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-symbol decoder */
1136 
1137 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1138 size_t HUFv07_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1139 size_t HUFv07_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1140 
1141 
1142 #endif /* HUFv07_STATIC_LINKING_ONLY */
1143 
1144 
1145 #if defined (__cplusplus)
1146 }
1147 #endif
1148 
1149 #endif   /* HUFv07_H_298734234 */
1150 /*
1151    Common functions of New Generation Entropy library
1152    Copyright (C) 2016, Yann Collet.
1153 
1154    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1155 
1156    Redistribution and use in source and binary forms, with or without
1157    modification, are permitted provided that the following conditions are
1158    met:
1159 
1160        * Redistributions of source code must retain the above copyright
1161    notice, this list of conditions and the following disclaimer.
1162        * Redistributions in binary form must reproduce the above
1163    copyright notice, this list of conditions and the following disclaimer
1164    in the documentation and/or other materials provided with the
1165    distribution.
1166 
1167    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1168    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1169    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1170    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1171    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1172    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1173    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1174    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1175    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1176    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1177    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1178 
1179     You can contact the author at :
1180     - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1181     - Public forum : https://groups.google.com/forum/#!forum/lz4c
1182 *************************************************************************** */
1183 
1184 
1185 
1186 /*-****************************************
1187 *  FSE Error Management
1188 ******************************************/
1189 unsigned FSEv07_isError(size_t code) { return ERR_isError(code); }
1190 
1191 const char* FSEv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1192 
1193 
1194 /* **************************************************************
1195 *  HUF Error Management
1196 ****************************************************************/
1197 unsigned HUFv07_isError(size_t code) { return ERR_isError(code); }
1198 
1199 const char* HUFv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1200 
1201 
1202 /*-**************************************************************
1203 *  FSE NCount encoding-decoding
1204 ****************************************************************/
1205 static short FSEv07_abs(short a) { return (short)(a<0 ? -a : a); }
1206 
1207 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1208                  const void* headerBuffer, size_t hbSize)
1209 {
1210     const BYTE* const istart = (const BYTE*) headerBuffer;
1211     const BYTE* const iend = istart + hbSize;
1212     const BYTE* ip = istart;
1213     int nbBits;
1214     int remaining;
1215     int threshold;
1216     U32 bitStream;
1217     int bitCount;
1218     unsigned charnum = 0;
1219     int previous0 = 0;
1220 
1221     if (hbSize < 4) return ERROR(srcSize_wrong);
1222     bitStream = MEM_readLE32(ip);
1223     nbBits = (bitStream & 0xF) + FSEv07_MIN_TABLELOG;   /* extract tableLog */
1224     if (nbBits > FSEv07_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1225     bitStream >>= 4;
1226     bitCount = 4;
1227     *tableLogPtr = nbBits;
1228     remaining = (1<<nbBits)+1;
1229     threshold = 1<<nbBits;
1230     nbBits++;
1231 
1232     while ((remaining>1) && (charnum<=*maxSVPtr)) {
1233         if (previous0) {
1234             unsigned n0 = charnum;
1235             while ((bitStream & 0xFFFF) == 0xFFFF) {
1236                 n0+=24;
1237                 if (ip < iend-5) {
1238                     ip+=2;
1239                     bitStream = MEM_readLE32(ip) >> bitCount;
1240                 } else {
1241                     bitStream >>= 16;
1242                     bitCount+=16;
1243             }   }
1244             while ((bitStream & 3) == 3) {
1245                 n0+=3;
1246                 bitStream>>=2;
1247                 bitCount+=2;
1248             }
1249             n0 += bitStream & 3;
1250             bitCount += 2;
1251             if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1252             while (charnum < n0) normalizedCounter[charnum++] = 0;
1253             if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1254                 ip += bitCount>>3;
1255                 bitCount &= 7;
1256                 bitStream = MEM_readLE32(ip) >> bitCount;
1257             }
1258             else
1259                 bitStream >>= 2;
1260         }
1261         {   short const max = (short)((2*threshold-1)-remaining);
1262             short count;
1263 
1264             if ((bitStream & (threshold-1)) < (U32)max) {
1265                 count = (short)(bitStream & (threshold-1));
1266                 bitCount   += nbBits-1;
1267             } else {
1268                 count = (short)(bitStream & (2*threshold-1));
1269                 if (count >= threshold) count -= max;
1270                 bitCount   += nbBits;
1271             }
1272 
1273             count--;   /* extra accuracy */
1274             remaining -= FSEv07_abs(count);
1275             normalizedCounter[charnum++] = count;
1276             previous0 = !count;
1277             while (remaining < threshold) {
1278                 nbBits--;
1279                 threshold >>= 1;
1280             }
1281 
1282             if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1283                 ip += bitCount>>3;
1284                 bitCount &= 7;
1285             } else {
1286                 bitCount -= (int)(8 * (iend - 4 - ip));
1287                 ip = iend - 4;
1288             }
1289             bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1290     }   }   /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1291     if (remaining != 1) return ERROR(GENERIC);
1292     *maxSVPtr = charnum-1;
1293 
1294     ip += (bitCount+7)>>3;
1295     if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1296     return ip-istart;
1297 }
1298 
1299 
1300 /*! HUFv07_readStats() :
1301     Read compact Huffman tree, saved by HUFv07_writeCTable().
1302     `huffWeight` is destination buffer.
1303     @return : size read from `src` , or an error Code .
1304     Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() .
1305 */
1306 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1307                      U32* nbSymbolsPtr, U32* tableLogPtr,
1308                      const void* src, size_t srcSize)
1309 {
1310     U32 weightTotal;
1311     const BYTE* ip = (const BYTE*) src;
1312     size_t iSize;
1313     size_t oSize;
1314 
1315     if (!srcSize) return ERROR(srcSize_wrong);
1316     iSize = ip[0];
1317     //memset(huffWeight, 0, hwSize);   /* is not necessary, even though some analyzer complain ... */
1318 
1319     if (iSize >= 128)  { /* special header */
1320         if (iSize >= (242)) {  /* RLE */
1321             static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1322             oSize = l[iSize-242];
1323             memset(huffWeight, 1, hwSize);
1324             iSize = 0;
1325         }
1326         else {   /* Incompressible */
1327             oSize = iSize - 127;
1328             iSize = ((oSize+1)/2);
1329             if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1330             if (oSize >= hwSize) return ERROR(corruption_detected);
1331             ip += 1;
1332             {   U32 n;
1333                 for (n=0; n<oSize; n+=2) {
1334                     huffWeight[n]   = ip[n/2] >> 4;
1335                     huffWeight[n+1] = ip[n/2] & 15;
1336     }   }   }   }
1337     else  {   /* header compressed with FSE (normal case) */
1338         if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1339         oSize = FSEv07_decompress(huffWeight, hwSize-1, ip+1, iSize);   /* max (hwSize-1) values decoded, as last one is implied */
1340         if (FSEv07_isError(oSize)) return oSize;
1341     }
1342 
1343     /* collect weight stats */
1344     memset(rankStats, 0, (HUFv07_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
1345     weightTotal = 0;
1346     {   U32 n; for (n=0; n<oSize; n++) {
1347             if (huffWeight[n] >= HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1348             rankStats[huffWeight[n]]++;
1349             weightTotal += (1 << huffWeight[n]) >> 1;
1350     }   }
1351     if (weightTotal == 0) return ERROR(corruption_detected);
1352 
1353     /* get last non-null symbol weight (implied, total must be 2^n) */
1354     {   U32 const tableLog = BITv07_highbit32(weightTotal) + 1;
1355         if (tableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1356         *tableLogPtr = tableLog;
1357         /* determine last weight */
1358         {   U32 const total = 1 << tableLog;
1359             U32 const rest = total - weightTotal;
1360             U32 const verif = 1 << BITv07_highbit32(rest);
1361             U32 const lastWeight = BITv07_highbit32(rest) + 1;
1362             if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
1363             huffWeight[oSize] = (BYTE)lastWeight;
1364             rankStats[lastWeight]++;
1365     }   }
1366 
1367     /* check tree construction validity */
1368     if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected);   /* by construction : at least 2 elts of rank 1, must be even */
1369 
1370     /* results */
1371     *nbSymbolsPtr = (U32)(oSize+1);
1372     return iSize+1;
1373 }
1374 /* ******************************************************************
1375    FSE : Finite State Entropy decoder
1376    Copyright (C) 2013-2015, Yann Collet.
1377 
1378    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1379 
1380    Redistribution and use in source and binary forms, with or without
1381    modification, are permitted provided that the following conditions are
1382    met:
1383 
1384        * Redistributions of source code must retain the above copyright
1385    notice, this list of conditions and the following disclaimer.
1386        * Redistributions in binary form must reproduce the above
1387    copyright notice, this list of conditions and the following disclaimer
1388    in the documentation and/or other materials provided with the
1389    distribution.
1390 
1391    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1392    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1393    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1394    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1395    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1396    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1397    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1398    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1399    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1400    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1401    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1402 
1403     You can contact the author at :
1404     - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1405     - Public forum : https://groups.google.com/forum/#!forum/lz4c
1406 ****************************************************************** */
1407 
1408 
1409 /* **************************************************************
1410 *  Compiler specifics
1411 ****************************************************************/
1412 #ifdef _MSC_VER    /* Visual Studio */
1413 #  define FORCE_INLINE static __forceinline
1414 #  include <intrin.h>                    /* For Visual 2005 */
1415 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1416 #  pragma warning(disable : 4214)        /* disable: C4214: non-int bitfields */
1417 #else
1418 #  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
1419 #    ifdef __GNUC__
1420 #      define FORCE_INLINE static inline __attribute__((always_inline))
1421 #    else
1422 #      define FORCE_INLINE static inline
1423 #    endif
1424 #  else
1425 #    define FORCE_INLINE static
1426 #  endif /* __STDC_VERSION__ */
1427 #endif
1428 
1429 
1430 /* **************************************************************
1431 *  Error Management
1432 ****************************************************************/
1433 #define FSEv07_isError ERR_isError
1434 #define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1435 
1436 
1437 /* **************************************************************
1438 *  Complex types
1439 ****************************************************************/
1440 typedef U32 DTable_max_t[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG)];
1441 
1442 
1443 /* **************************************************************
1444 *  Templates
1445 ****************************************************************/
1446 /*
1447   designed to be included
1448   for type-specific functions (template emulation in C)
1449   Objective is to write these functions only once, for improved maintenance
1450 */
1451 
1452 /* safety checks */
1453 #ifndef FSEv07_FUNCTION_EXTENSION
1454 #  error "FSEv07_FUNCTION_EXTENSION must be defined"
1455 #endif
1456 #ifndef FSEv07_FUNCTION_TYPE
1457 #  error "FSEv07_FUNCTION_TYPE must be defined"
1458 #endif
1459 
1460 /* Function names */
1461 #define FSEv07_CAT(X,Y) X##Y
1462 #define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y)
1463 #define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y)
1464 
1465 
1466 /* Function templates */
1467 FSEv07_DTable* FSEv07_createDTable (unsigned tableLog)
1468 {
1469     if (tableLog > FSEv07_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv07_TABLELOG_ABSOLUTE_MAX;
1470     return (FSEv07_DTable*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1471 }
1472 
1473 void FSEv07_freeDTable (FSEv07_DTable* dt)
1474 {
1475     free(dt);
1476 }
1477 
1478 size_t FSEv07_buildDTable(FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1479 {
1480     void* const tdPtr = dt+1;   /* because *dt is unsigned, 32-bits aligned on 32-bits */
1481     FSEv07_DECODE_TYPE* const tableDecode = (FSEv07_DECODE_TYPE*) (tdPtr);
1482     U16 symbolNext[FSEv07_MAX_SYMBOL_VALUE+1];
1483 
1484     U32 const maxSV1 = maxSymbolValue + 1;
1485     U32 const tableSize = 1 << tableLog;
1486     U32 highThreshold = tableSize-1;
1487 
1488     /* Sanity Checks */
1489     if (maxSymbolValue > FSEv07_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1490     if (tableLog > FSEv07_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1491 
1492     /* Init, lay down lowprob symbols */
1493     {   FSEv07_DTableHeader DTableH;
1494         DTableH.tableLog = (U16)tableLog;
1495         DTableH.fastMode = 1;
1496         {   S16 const largeLimit= (S16)(1 << (tableLog-1));
1497             U32 s;
1498             for (s=0; s<maxSV1; s++) {
1499                 if (normalizedCounter[s]==-1) {
1500                     tableDecode[highThreshold--].symbol = (FSEv07_FUNCTION_TYPE)s;
1501                     symbolNext[s] = 1;
1502                 } else {
1503                     if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1504                     symbolNext[s] = normalizedCounter[s];
1505         }   }   }
1506         memcpy(dt, &DTableH, sizeof(DTableH));
1507     }
1508 
1509     /* Spread symbols */
1510     {   U32 const tableMask = tableSize-1;
1511         U32 const step = FSEv07_TABLESTEP(tableSize);
1512         U32 s, position = 0;
1513         for (s=0; s<maxSV1; s++) {
1514             int i;
1515             for (i=0; i<normalizedCounter[s]; i++) {
1516                 tableDecode[position].symbol = (FSEv07_FUNCTION_TYPE)s;
1517                 position = (position + step) & tableMask;
1518                 while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
1519         }   }
1520 
1521         if (position!=0) return ERROR(GENERIC);   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1522     }
1523 
1524     /* Build Decoding table */
1525     {   U32 u;
1526         for (u=0; u<tableSize; u++) {
1527             FSEv07_FUNCTION_TYPE const symbol = (FSEv07_FUNCTION_TYPE)(tableDecode[u].symbol);
1528             U16 nextState = symbolNext[symbol]++;
1529             tableDecode[u].nbBits = (BYTE) (tableLog - BITv07_highbit32 ((U32)nextState) );
1530             tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1531     }   }
1532 
1533     return 0;
1534 }
1535 
1536 
1537 
1538 #ifndef FSEv07_COMMONDEFS_ONLY
1539 
1540 /*-*******************************************************
1541 *  Decompression (Byte symbols)
1542 *********************************************************/
1543 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, BYTE symbolValue)
1544 {
1545     void* ptr = dt;
1546     FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1547     void* dPtr = dt + 1;
1548     FSEv07_decode_t* const cell = (FSEv07_decode_t*)dPtr;
1549 
1550     DTableH->tableLog = 0;
1551     DTableH->fastMode = 0;
1552 
1553     cell->newState = 0;
1554     cell->symbol = symbolValue;
1555     cell->nbBits = 0;
1556 
1557     return 0;
1558 }
1559 
1560 
1561 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits)
1562 {
1563     void* ptr = dt;
1564     FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1565     void* dPtr = dt + 1;
1566     FSEv07_decode_t* const dinfo = (FSEv07_decode_t*)dPtr;
1567     const unsigned tableSize = 1 << nbBits;
1568     const unsigned tableMask = tableSize - 1;
1569     const unsigned maxSV1 = tableMask+1;
1570     unsigned s;
1571 
1572     /* Sanity checks */
1573     if (nbBits < 1) return ERROR(GENERIC);         /* min size */
1574 
1575     /* Build Decoding Table */
1576     DTableH->tableLog = (U16)nbBits;
1577     DTableH->fastMode = 1;
1578     for (s=0; s<maxSV1; s++) {
1579         dinfo[s].newState = 0;
1580         dinfo[s].symbol = (BYTE)s;
1581         dinfo[s].nbBits = (BYTE)nbBits;
1582     }
1583 
1584     return 0;
1585 }
1586 
1587 FORCE_INLINE size_t FSEv07_decompress_usingDTable_generic(
1588           void* dst, size_t maxDstSize,
1589     const void* cSrc, size_t cSrcSize,
1590     const FSEv07_DTable* dt, const unsigned fast)
1591 {
1592     BYTE* const ostart = (BYTE*) dst;
1593     BYTE* op = ostart;
1594     BYTE* const omax = op + maxDstSize;
1595     BYTE* const olimit = omax-3;
1596 
1597     BITv07_DStream_t bitD;
1598     FSEv07_DState_t state1;
1599     FSEv07_DState_t state2;
1600 
1601     /* Init */
1602     { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);   /* replaced last arg by maxCompressed Size */
1603       if (FSEv07_isError(errorCode)) return errorCode; }
1604 
1605     FSEv07_initDState(&state1, &bitD, dt);
1606     FSEv07_initDState(&state2, &bitD, dt);
1607 
1608 #define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1609 
1610     /* 4 symbols per loop */
1611     for ( ; (BITv07_reloadDStream(&bitD)==BITv07_DStream_unfinished) && (op<olimit) ; op+=4) {
1612         op[0] = FSEv07_GETSYMBOL(&state1);
1613 
1614         if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1615             BITv07_reloadDStream(&bitD);
1616 
1617         op[1] = FSEv07_GETSYMBOL(&state2);
1618 
1619         if (FSEv07_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1620             { if (BITv07_reloadDStream(&bitD) > BITv07_DStream_unfinished) { op+=2; break; } }
1621 
1622         op[2] = FSEv07_GETSYMBOL(&state1);
1623 
1624         if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1625             BITv07_reloadDStream(&bitD);
1626 
1627         op[3] = FSEv07_GETSYMBOL(&state2);
1628     }
1629 
1630     /* tail */
1631     /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1632     while (1) {
1633         if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1634 
1635         *op++ = FSEv07_GETSYMBOL(&state1);
1636 
1637         if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1638             *op++ = FSEv07_GETSYMBOL(&state2);
1639             break;
1640         }
1641 
1642         if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1643 
1644         *op++ = FSEv07_GETSYMBOL(&state2);
1645 
1646         if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1647             *op++ = FSEv07_GETSYMBOL(&state1);
1648             break;
1649     }   }
1650 
1651     return op-ostart;
1652 }
1653 
1654 
1655 size_t FSEv07_decompress_usingDTable(void* dst, size_t originalSize,
1656                             const void* cSrc, size_t cSrcSize,
1657                             const FSEv07_DTable* dt)
1658 {
1659     const void* ptr = dt;
1660     const FSEv07_DTableHeader* DTableH = (const FSEv07_DTableHeader*)ptr;
1661     const U32 fastMode = DTableH->fastMode;
1662 
1663     /* select fast mode (static) */
1664     if (fastMode) return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1665     return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1666 }
1667 
1668 
1669 size_t FSEv07_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1670 {
1671     const BYTE* const istart = (const BYTE*)cSrc;
1672     const BYTE* ip = istart;
1673     short counting[FSEv07_MAX_SYMBOL_VALUE+1];
1674     DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
1675     unsigned tableLog;
1676     unsigned maxSymbolValue = FSEv07_MAX_SYMBOL_VALUE;
1677 
1678     if (cSrcSize<2) return ERROR(srcSize_wrong);   /* too small input size */
1679 
1680     /* normal FSE decoding mode */
1681     {   size_t const NCountLength = FSEv07_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1682         if (FSEv07_isError(NCountLength)) return NCountLength;
1683         if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong);   /* too small input size */
1684         ip += NCountLength;
1685         cSrcSize -= NCountLength;
1686     }
1687 
1688     { size_t const errorCode = FSEv07_buildDTable (dt, counting, maxSymbolValue, tableLog);
1689       if (FSEv07_isError(errorCode)) return errorCode; }
1690 
1691     return FSEv07_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);   /* always return, even if it is an error code */
1692 }
1693 
1694 
1695 
1696 #endif   /* FSEv07_COMMONDEFS_ONLY */
1697 
1698 /* ******************************************************************
1699    Huffman decoder, part of New Generation Entropy library
1700    Copyright (C) 2013-2016, 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     - FSE+HUF 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 /* **************************************************************
1751 *  Error Management
1752 ****************************************************************/
1753 #define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1754 
1755 
1756 /*-***************************/
1757 /*  generic DTableDesc       */
1758 /*-***************************/
1759 
1760 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
1761 
1762 static DTableDesc HUFv07_getDTableDesc(const HUFv07_DTable* table)
1763 {
1764     DTableDesc dtd;
1765     memcpy(&dtd, table, sizeof(dtd));
1766     return dtd;
1767 }
1768 
1769 
1770 /*-***************************/
1771 /*  single-symbol decoding   */
1772 /*-***************************/
1773 
1774 typedef struct { BYTE byte; BYTE nbBits; } HUFv07_DEltX2;   /* single-symbol decoding */
1775 
1776 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
1777 {
1778     BYTE huffWeight[HUFv07_SYMBOLVALUE_MAX + 1];
1779     U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];   /* large enough for values from 0 to 16 */
1780     U32 tableLog = 0;
1781     U32 nbSymbols = 0;
1782     size_t iSize;
1783     void* const dtPtr = DTable + 1;
1784     HUFv07_DEltX2* const dt = (HUFv07_DEltX2*)dtPtr;
1785 
1786     HUFv07_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUFv07_DTable));
1787     //memset(huffWeight, 0, sizeof(huffWeight));   /* is not necessary, even though some analyzer complain ... */
1788 
1789     iSize = HUFv07_readStats(huffWeight, HUFv07_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1790     if (HUFv07_isError(iSize)) return iSize;
1791 
1792     /* Table header */
1793     {   DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1794         if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge);   /* DTable too small, huffman tree cannot fit in */
1795         dtd.tableType = 0;
1796         dtd.tableLog = (BYTE)tableLog;
1797         memcpy(DTable, &dtd, sizeof(dtd));
1798     }
1799 
1800     /* Prepare ranks */
1801     {   U32 n, nextRankStart = 0;
1802         for (n=1; n<tableLog+1; n++) {
1803             U32 current = nextRankStart;
1804             nextRankStart += (rankVal[n] << (n-1));
1805             rankVal[n] = current;
1806     }   }
1807 
1808     /* fill DTable */
1809     {   U32 n;
1810         for (n=0; n<nbSymbols; n++) {
1811             U32 const w = huffWeight[n];
1812             U32 const length = (1 << w) >> 1;
1813             U32 i;
1814             HUFv07_DEltX2 D;
1815             D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1816             for (i = rankVal[w]; i < rankVal[w] + length; i++)
1817                 dt[i] = D;
1818             rankVal[w] += length;
1819     }   }
1820 
1821     return iSize;
1822 }
1823 
1824 
1825 static BYTE HUFv07_decodeSymbolX2(BITv07_DStream_t* Dstream, const HUFv07_DEltX2* dt, const U32 dtLog)
1826 {
1827     size_t const val = BITv07_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1828     BYTE const c = dt[val].byte;
1829     BITv07_skipBits(Dstream, dt[val].nbBits);
1830     return c;
1831 }
1832 
1833 #define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1834     *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1835 
1836 #define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1837     if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1838         HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1839 
1840 #define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1841     if (MEM_64bits()) \
1842         HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1843 
1844 static inline size_t HUFv07_decodeStreamX2(BYTE* p, BITv07_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv07_DEltX2* const dt, const U32 dtLog)
1845 {
1846     BYTE* const pStart = p;
1847 
1848     /* up to 4 symbols at a time */
1849     while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-4)) {
1850         HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1851         HUFv07_DECODE_SYMBOLX2_1(p, bitDPtr);
1852         HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1853         HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1854     }
1855 
1856     /* closer to the end */
1857     while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd))
1858         HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1859 
1860     /* no more data to retrieve from bitstream, hence no need to reload */
1861     while (p < pEnd)
1862         HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1863 
1864     return pEnd-pStart;
1865 }
1866 
1867 static size_t HUFv07_decompress1X2_usingDTable_internal(
1868           void* dst,  size_t dstSize,
1869     const void* cSrc, size_t cSrcSize,
1870     const HUFv07_DTable* DTable)
1871 {
1872     BYTE* op = (BYTE*)dst;
1873     BYTE* const oend = op + dstSize;
1874     const void* dtPtr = DTable + 1;
1875     const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1876     BITv07_DStream_t bitD;
1877     DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1878     U32 const dtLog = dtd.tableLog;
1879 
1880     { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
1881       if (HUFv07_isError(errorCode)) return errorCode; }
1882 
1883     HUFv07_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1884 
1885     /* check */
1886     if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
1887 
1888     return dstSize;
1889 }
1890 
1891 size_t HUFv07_decompress1X2_usingDTable(
1892           void* dst,  size_t dstSize,
1893     const void* cSrc, size_t cSrcSize,
1894     const HUFv07_DTable* DTable)
1895 {
1896     DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1897     if (dtd.tableType != 0) return ERROR(GENERIC);
1898     return HUFv07_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
1899 }
1900 
1901 size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1902 {
1903     const BYTE* ip = (const BYTE*) cSrc;
1904 
1905     size_t const hSize = HUFv07_readDTableX2 (DCtx, cSrc, cSrcSize);
1906     if (HUFv07_isError(hSize)) return hSize;
1907     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1908     ip += hSize; cSrcSize -= hSize;
1909 
1910     return HUFv07_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
1911 }
1912 
1913 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1914 {
1915     HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
1916     return HUFv07_decompress1X2_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
1917 }
1918 
1919 
1920 static size_t HUFv07_decompress4X2_usingDTable_internal(
1921           void* dst,  size_t dstSize,
1922     const void* cSrc, size_t cSrcSize,
1923     const HUFv07_DTable* DTable)
1924 {
1925     /* Check */
1926     if (cSrcSize < 10) return ERROR(corruption_detected);  /* strict minimum : jump table + 1 byte per stream */
1927 
1928     {   const BYTE* const istart = (const BYTE*) cSrc;
1929         BYTE* const ostart = (BYTE*) dst;
1930         BYTE* const oend = ostart + dstSize;
1931         const void* const dtPtr = DTable + 1;
1932         const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1933 
1934         /* Init */
1935         BITv07_DStream_t bitD1;
1936         BITv07_DStream_t bitD2;
1937         BITv07_DStream_t bitD3;
1938         BITv07_DStream_t bitD4;
1939         size_t const length1 = MEM_readLE16(istart);
1940         size_t const length2 = MEM_readLE16(istart+2);
1941         size_t const length3 = MEM_readLE16(istart+4);
1942         size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
1943         const BYTE* const istart1 = istart + 6;  /* jumpTable */
1944         const BYTE* const istart2 = istart1 + length1;
1945         const BYTE* const istart3 = istart2 + length2;
1946         const BYTE* const istart4 = istart3 + length3;
1947         const size_t segmentSize = (dstSize+3) / 4;
1948         BYTE* const opStart2 = ostart + segmentSize;
1949         BYTE* const opStart3 = opStart2 + segmentSize;
1950         BYTE* const opStart4 = opStart3 + segmentSize;
1951         BYTE* op1 = ostart;
1952         BYTE* op2 = opStart2;
1953         BYTE* op3 = opStart3;
1954         BYTE* op4 = opStart4;
1955         U32 endSignal;
1956         DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1957         U32 const dtLog = dtd.tableLog;
1958 
1959         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
1960         { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
1961           if (HUFv07_isError(errorCode)) return errorCode; }
1962         { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
1963           if (HUFv07_isError(errorCode)) return errorCode; }
1964         { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
1965           if (HUFv07_isError(errorCode)) return errorCode; }
1966         { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
1967           if (HUFv07_isError(errorCode)) return errorCode; }
1968 
1969         /* 16-32 symbols per loop (4-8 symbols per stream) */
1970         endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1971         for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
1972             HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
1973             HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
1974             HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
1975             HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
1976             HUFv07_DECODE_SYMBOLX2_1(op1, &bitD1);
1977             HUFv07_DECODE_SYMBOLX2_1(op2, &bitD2);
1978             HUFv07_DECODE_SYMBOLX2_1(op3, &bitD3);
1979             HUFv07_DECODE_SYMBOLX2_1(op4, &bitD4);
1980             HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
1981             HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
1982             HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
1983             HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
1984             HUFv07_DECODE_SYMBOLX2_0(op1, &bitD1);
1985             HUFv07_DECODE_SYMBOLX2_0(op2, &bitD2);
1986             HUFv07_DECODE_SYMBOLX2_0(op3, &bitD3);
1987             HUFv07_DECODE_SYMBOLX2_0(op4, &bitD4);
1988             endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1989         }
1990 
1991         /* check corruption */
1992         if (op1 > opStart2) return ERROR(corruption_detected);
1993         if (op2 > opStart3) return ERROR(corruption_detected);
1994         if (op3 > opStart4) return ERROR(corruption_detected);
1995         /* note : op4 supposed already verified within main loop */
1996 
1997         /* finish bitStreams one by one */
1998         HUFv07_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1999         HUFv07_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2000         HUFv07_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2001         HUFv07_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
2002 
2003         /* check */
2004         endSignal = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2005         if (!endSignal) return ERROR(corruption_detected);
2006 
2007         /* decoded size */
2008         return dstSize;
2009     }
2010 }
2011 
2012 
2013 size_t HUFv07_decompress4X2_usingDTable(
2014           void* dst,  size_t dstSize,
2015     const void* cSrc, size_t cSrcSize,
2016     const HUFv07_DTable* DTable)
2017 {
2018     DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2019     if (dtd.tableType != 0) return ERROR(GENERIC);
2020     return HUFv07_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2021 }
2022 
2023 
2024 size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2025 {
2026     const BYTE* ip = (const BYTE*) cSrc;
2027 
2028     size_t const hSize = HUFv07_readDTableX2 (dctx, cSrc, cSrcSize);
2029     if (HUFv07_isError(hSize)) return hSize;
2030     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2031     ip += hSize; cSrcSize -= hSize;
2032 
2033     return HUFv07_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx);
2034 }
2035 
2036 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2037 {
2038     HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
2039     return HUFv07_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2040 }
2041 
2042 
2043 /* *************************/
2044 /* double-symbols decoding */
2045 /* *************************/
2046 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv07_DEltX4;  /* double-symbols decoding */
2047 
2048 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
2049 
2050 static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2051                            const U32* rankValOrigin, const int minWeight,
2052                            const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2053                            U32 nbBitsBaseline, U16 baseSeq)
2054 {
2055     HUFv07_DEltX4 DElt;
2056     U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2057 
2058     /* get pre-calculated rankVal */
2059     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2060 
2061     /* fill skipped values */
2062     if (minWeight>1) {
2063         U32 i, skipSize = rankVal[minWeight];
2064         MEM_writeLE16(&(DElt.sequence), baseSeq);
2065         DElt.nbBits   = (BYTE)(consumed);
2066         DElt.length   = 1;
2067         for (i = 0; i < skipSize; i++)
2068             DTable[i] = DElt;
2069     }
2070 
2071     /* fill DTable */
2072     { U32 s; for (s=0; s<sortedListSize; s++) {   /* note : sortedSymbols already skipped */
2073         const U32 symbol = sortedSymbols[s].symbol;
2074         const U32 weight = sortedSymbols[s].weight;
2075         const U32 nbBits = nbBitsBaseline - weight;
2076         const U32 length = 1 << (sizeLog-nbBits);
2077         const U32 start = rankVal[weight];
2078         U32 i = start;
2079         const U32 end = start + length;
2080 
2081         MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2082         DElt.nbBits = (BYTE)(nbBits + consumed);
2083         DElt.length = 2;
2084         do { DTable[i++] = DElt; } while (i<end);   /* since length >= 1 */
2085 
2086         rankVal[weight] += length;
2087     }}
2088 }
2089 
2090 typedef U32 rankVal_t[HUFv07_TABLELOG_ABSOLUTEMAX][HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2091 
2092 static void HUFv07_fillDTableX4(HUFv07_DEltX4* DTable, const U32 targetLog,
2093                            const sortedSymbol_t* sortedList, const U32 sortedListSize,
2094                            const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2095                            const U32 nbBitsBaseline)
2096 {
2097     U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2098     const int scaleLog = nbBitsBaseline - targetLog;   /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2099     const U32 minBits  = nbBitsBaseline - maxWeight;
2100     U32 s;
2101 
2102     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2103 
2104     /* fill DTable */
2105     for (s=0; s<sortedListSize; s++) {
2106         const U16 symbol = sortedList[s].symbol;
2107         const U32 weight = sortedList[s].weight;
2108         const U32 nbBits = nbBitsBaseline - weight;
2109         const U32 start = rankVal[weight];
2110         const U32 length = 1 << (targetLog-nbBits);
2111 
2112         if (targetLog-nbBits >= minBits) {   /* enough room for a second symbol */
2113             U32 sortedRank;
2114             int minWeight = nbBits + scaleLog;
2115             if (minWeight < 1) minWeight = 1;
2116             sortedRank = rankStart[minWeight];
2117             HUFv07_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2118                            rankValOrigin[nbBits], minWeight,
2119                            sortedList+sortedRank, sortedListSize-sortedRank,
2120                            nbBitsBaseline, symbol);
2121         } else {
2122             HUFv07_DEltX4 DElt;
2123             MEM_writeLE16(&(DElt.sequence), symbol);
2124             DElt.nbBits = (BYTE)(nbBits);
2125             DElt.length = 1;
2126             {   U32 u;
2127                 const U32 end = start + length;
2128                 for (u = start; u < end; u++) DTable[u] = DElt;
2129         }   }
2130         rankVal[weight] += length;
2131     }
2132 }
2133 
2134 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
2135 {
2136     BYTE weightList[HUFv07_SYMBOLVALUE_MAX + 1];
2137     sortedSymbol_t sortedSymbol[HUFv07_SYMBOLVALUE_MAX + 1];
2138     U32 rankStats[HUFv07_TABLELOG_ABSOLUTEMAX + 1] = { 0 };
2139     U32 rankStart0[HUFv07_TABLELOG_ABSOLUTEMAX + 2] = { 0 };
2140     U32* const rankStart = rankStart0+1;
2141     rankVal_t rankVal;
2142     U32 tableLog, maxW, sizeOfSort, nbSymbols;
2143     DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2144     U32 const maxTableLog = dtd.maxTableLog;
2145     size_t iSize;
2146     void* dtPtr = DTable+1;   /* force compiler to avoid strict-aliasing */
2147     HUFv07_DEltX4* const dt = (HUFv07_DEltX4*)dtPtr;
2148 
2149     HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4) == sizeof(HUFv07_DTable));   /* if compilation fails here, assertion is false */
2150     if (maxTableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge);
2151     //memset(weightList, 0, sizeof(weightList));   /* is not necessary, even though some analyzer complain ... */
2152 
2153     iSize = HUFv07_readStats(weightList, HUFv07_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2154     if (HUFv07_isError(iSize)) return iSize;
2155 
2156     /* check result */
2157     if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge);   /* DTable can't fit code depth */
2158 
2159     /* find maxWeight */
2160     for (maxW = tableLog; rankStats[maxW]==0; maxW--) {}  /* necessarily finds a solution before 0 */
2161 
2162     /* Get start index of each weight */
2163     {   U32 w, nextRankStart = 0;
2164         for (w=1; w<maxW+1; w++) {
2165             U32 current = nextRankStart;
2166             nextRankStart += rankStats[w];
2167             rankStart[w] = current;
2168         }
2169         rankStart[0] = nextRankStart;   /* put all 0w symbols at the end of sorted list*/
2170         sizeOfSort = nextRankStart;
2171     }
2172 
2173     /* sort symbols by weight */
2174     {   U32 s;
2175         for (s=0; s<nbSymbols; s++) {
2176             U32 const w = weightList[s];
2177             U32 const r = rankStart[w]++;
2178             sortedSymbol[r].symbol = (BYTE)s;
2179             sortedSymbol[r].weight = (BYTE)w;
2180         }
2181         rankStart[0] = 0;   /* forget 0w symbols; this is beginning of weight(1) */
2182     }
2183 
2184     /* Build rankVal */
2185     {   U32* const rankVal0 = rankVal[0];
2186         {   int const rescale = (maxTableLog-tableLog) - 1;   /* tableLog <= maxTableLog */
2187             U32 nextRankVal = 0;
2188             U32 w;
2189             for (w=1; w<maxW+1; w++) {
2190                 U32 current = nextRankVal;
2191                 nextRankVal += rankStats[w] << (w+rescale);
2192                 rankVal0[w] = current;
2193         }   }
2194         {   U32 const minBits = tableLog+1 - maxW;
2195             U32 consumed;
2196             for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
2197                 U32* const rankValPtr = rankVal[consumed];
2198                 U32 w;
2199                 for (w = 1; w < maxW+1; w++) {
2200                     rankValPtr[w] = rankVal0[w] >> consumed;
2201     }   }   }   }
2202 
2203     HUFv07_fillDTableX4(dt, maxTableLog,
2204                    sortedSymbol, sizeOfSort,
2205                    rankStart0, rankVal, maxW,
2206                    tableLog+1);
2207 
2208     dtd.tableLog = (BYTE)maxTableLog;
2209     dtd.tableType = 1;
2210     memcpy(DTable, &dtd, sizeof(dtd));
2211     return iSize;
2212 }
2213 
2214 
2215 static U32 HUFv07_decodeSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2216 {
2217     const size_t val = BITv07_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2218     memcpy(op, dt+val, 2);
2219     BITv07_skipBits(DStream, dt[val].nbBits);
2220     return dt[val].length;
2221 }
2222 
2223 static U32 HUFv07_decodeLastSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2224 {
2225     const size_t val = BITv07_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2226     memcpy(op, dt+val, 1);
2227     if (dt[val].length==1) BITv07_skipBits(DStream, dt[val].nbBits);
2228     else {
2229         if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2230             BITv07_skipBits(DStream, dt[val].nbBits);
2231             if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2232                 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 */
2233     }   }
2234     return 1;
2235 }
2236 
2237 
2238 #define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2239     ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2240 
2241 #define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2242     if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
2243         ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2244 
2245 #define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2246     if (MEM_64bits()) \
2247         ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2248 
2249 static inline size_t HUFv07_decodeStreamX4(BYTE* p, BITv07_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv07_DEltX4* const dt, const U32 dtLog)
2250 {
2251     BYTE* const pStart = p;
2252 
2253     /* up to 8 symbols at a time */
2254     while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd-7)) {
2255         HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2256         HUFv07_DECODE_SYMBOLX4_1(p, bitDPtr);
2257         HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2258         HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2259     }
2260 
2261     /* closer to end : up to 2 symbols at a time */
2262     while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-2))
2263         HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2264 
2265     while (p <= pEnd-2)
2266         HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);   /* no need to reload : reached the end of DStream */
2267 
2268     if (p < pEnd)
2269         p += HUFv07_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2270 
2271     return p-pStart;
2272 }
2273 
2274 
2275 static size_t HUFv07_decompress1X4_usingDTable_internal(
2276           void* dst,  size_t dstSize,
2277     const void* cSrc, size_t cSrcSize,
2278     const HUFv07_DTable* DTable)
2279 {
2280     BITv07_DStream_t bitD;
2281 
2282     /* Init */
2283     {   size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
2284         if (HUFv07_isError(errorCode)) return errorCode;
2285     }
2286 
2287     /* decode */
2288     {   BYTE* const ostart = (BYTE*) dst;
2289         BYTE* const oend = ostart + dstSize;
2290         const void* const dtPtr = DTable+1;   /* force compiler to not use strict-aliasing */
2291         const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2292         DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2293         HUFv07_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog);
2294     }
2295 
2296     /* check */
2297     if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
2298 
2299     /* decoded size */
2300     return dstSize;
2301 }
2302 
2303 size_t HUFv07_decompress1X4_usingDTable(
2304           void* dst,  size_t dstSize,
2305     const void* cSrc, size_t cSrcSize,
2306     const HUFv07_DTable* DTable)
2307 {
2308     DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2309     if (dtd.tableType != 1) return ERROR(GENERIC);
2310     return HUFv07_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2311 }
2312 
2313 size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2314 {
2315     const BYTE* ip = (const BYTE*) cSrc;
2316 
2317     size_t const hSize = HUFv07_readDTableX4 (DCtx, cSrc, cSrcSize);
2318     if (HUFv07_isError(hSize)) return hSize;
2319     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2320     ip += hSize; cSrcSize -= hSize;
2321 
2322     return HUFv07_decompress1X4_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
2323 }
2324 
2325 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2326 {
2327     HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2328     return HUFv07_decompress1X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2329 }
2330 
2331 static size_t HUFv07_decompress4X4_usingDTable_internal(
2332           void* dst,  size_t dstSize,
2333     const void* cSrc, size_t cSrcSize,
2334     const HUFv07_DTable* DTable)
2335 {
2336     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
2337 
2338     {   const BYTE* const istart = (const BYTE*) cSrc;
2339         BYTE* const ostart = (BYTE*) dst;
2340         BYTE* const oend = ostart + dstSize;
2341         const void* const dtPtr = DTable+1;
2342         const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2343 
2344         /* Init */
2345         BITv07_DStream_t bitD1;
2346         BITv07_DStream_t bitD2;
2347         BITv07_DStream_t bitD3;
2348         BITv07_DStream_t bitD4;
2349         size_t const length1 = MEM_readLE16(istart);
2350         size_t const length2 = MEM_readLE16(istart+2);
2351         size_t const length3 = MEM_readLE16(istart+4);
2352         size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
2353         const BYTE* const istart1 = istart + 6;  /* jumpTable */
2354         const BYTE* const istart2 = istart1 + length1;
2355         const BYTE* const istart3 = istart2 + length2;
2356         const BYTE* const istart4 = istart3 + length3;
2357         size_t const segmentSize = (dstSize+3) / 4;
2358         BYTE* const opStart2 = ostart + segmentSize;
2359         BYTE* const opStart3 = opStart2 + segmentSize;
2360         BYTE* const opStart4 = opStart3 + segmentSize;
2361         BYTE* op1 = ostart;
2362         BYTE* op2 = opStart2;
2363         BYTE* op3 = opStart3;
2364         BYTE* op4 = opStart4;
2365         U32 endSignal;
2366         DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2367         U32 const dtLog = dtd.tableLog;
2368 
2369         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
2370         { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
2371           if (HUFv07_isError(errorCode)) return errorCode; }
2372         { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
2373           if (HUFv07_isError(errorCode)) return errorCode; }
2374         { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
2375           if (HUFv07_isError(errorCode)) return errorCode; }
2376         { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
2377           if (HUFv07_isError(errorCode)) return errorCode; }
2378 
2379         /* 16-32 symbols per loop (4-8 symbols per stream) */
2380         endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2381         for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
2382             HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2383             HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2384             HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2385             HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2386             HUFv07_DECODE_SYMBOLX4_1(op1, &bitD1);
2387             HUFv07_DECODE_SYMBOLX4_1(op2, &bitD2);
2388             HUFv07_DECODE_SYMBOLX4_1(op3, &bitD3);
2389             HUFv07_DECODE_SYMBOLX4_1(op4, &bitD4);
2390             HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2391             HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2392             HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2393             HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2394             HUFv07_DECODE_SYMBOLX4_0(op1, &bitD1);
2395             HUFv07_DECODE_SYMBOLX4_0(op2, &bitD2);
2396             HUFv07_DECODE_SYMBOLX4_0(op3, &bitD3);
2397             HUFv07_DECODE_SYMBOLX4_0(op4, &bitD4);
2398 
2399             endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2400         }
2401 
2402         /* check corruption */
2403         if (op1 > opStart2) return ERROR(corruption_detected);
2404         if (op2 > opStart3) return ERROR(corruption_detected);
2405         if (op3 > opStart4) return ERROR(corruption_detected);
2406         /* note : op4 supposed already verified within main loop */
2407 
2408         /* finish bitStreams one by one */
2409         HUFv07_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2410         HUFv07_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2411         HUFv07_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2412         HUFv07_decodeStreamX4(op4, &bitD4, oend,     dt, dtLog);
2413 
2414         /* check */
2415         { U32 const endCheck = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2416           if (!endCheck) return ERROR(corruption_detected); }
2417 
2418         /* decoded size */
2419         return dstSize;
2420     }
2421 }
2422 
2423 
2424 size_t HUFv07_decompress4X4_usingDTable(
2425           void* dst,  size_t dstSize,
2426     const void* cSrc, size_t cSrcSize,
2427     const HUFv07_DTable* DTable)
2428 {
2429     DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2430     if (dtd.tableType != 1) return ERROR(GENERIC);
2431     return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2432 }
2433 
2434 
2435 size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2436 {
2437     const BYTE* ip = (const BYTE*) cSrc;
2438 
2439     size_t hSize = HUFv07_readDTableX4 (dctx, cSrc, cSrcSize);
2440     if (HUFv07_isError(hSize)) return hSize;
2441     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2442     ip += hSize; cSrcSize -= hSize;
2443 
2444     return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
2445 }
2446 
2447 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2448 {
2449     HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2450     return HUFv07_decompress4X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2451 }
2452 
2453 
2454 /* ********************************/
2455 /* Generic decompression selector */
2456 /* ********************************/
2457 
2458 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize,
2459                                     const void* cSrc, size_t cSrcSize,
2460                                     const HUFv07_DTable* DTable)
2461 {
2462     DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2463     return dtd.tableType ? HUFv07_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2464                            HUFv07_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2465 }
2466 
2467 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize,
2468                                     const void* cSrc, size_t cSrcSize,
2469                                     const HUFv07_DTable* DTable)
2470 {
2471     DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2472     return dtd.tableType ? HUFv07_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2473                            HUFv07_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2474 }
2475 
2476 
2477 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2478 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2479 {
2480     /* single, double, quad */
2481     {{0,0}, {1,1}, {2,2}},  /* Q==0 : impossible */
2482     {{0,0}, {1,1}, {2,2}},  /* Q==1 : impossible */
2483     {{  38,130}, {1313, 74}, {2151, 38}},   /* Q == 2 : 12-18% */
2484     {{ 448,128}, {1353, 74}, {2238, 41}},   /* Q == 3 : 18-25% */
2485     {{ 556,128}, {1353, 74}, {2238, 47}},   /* Q == 4 : 25-32% */
2486     {{ 714,128}, {1418, 74}, {2436, 53}},   /* Q == 5 : 32-38% */
2487     {{ 883,128}, {1437, 74}, {2464, 61}},   /* Q == 6 : 38-44% */
2488     {{ 897,128}, {1515, 75}, {2622, 68}},   /* Q == 7 : 44-50% */
2489     {{ 926,128}, {1613, 75}, {2730, 75}},   /* Q == 8 : 50-56% */
2490     {{ 947,128}, {1729, 77}, {3359, 77}},   /* Q == 9 : 56-62% */
2491     {{1107,128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
2492     {{1177,128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
2493     {{1242,128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
2494     {{1349,128}, {2644,106}, {5260,106}},   /* Q ==13 : 81-87% */
2495     {{1455,128}, {2422,124}, {4174,124}},   /* Q ==14 : 87-93% */
2496     {{ 722,128}, {1891,145}, {1936,146}},   /* Q ==15 : 93-99% */
2497 };
2498 
2499 /** HUFv07_selectDecoder() :
2500 *   Tells which decoder is likely to decode faster,
2501 *   based on a set of pre-determined metrics.
2502 *   @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
2503 *   Assumption : 0 < cSrcSize < dstSize <= 128 KB */
2504 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize)
2505 {
2506     /* decoder timing evaluation */
2507     U32 const Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
2508     U32 const D256 = (U32)(dstSize >> 8);
2509     U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
2510     U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
2511     DTime1 += DTime1 >> 3;  /* advantage to algorithm using less memory, for cache eviction */
2512 
2513     return DTime1 < DTime0;
2514 }
2515 
2516 
2517 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2518 
2519 size_t HUFv07_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2520 {
2521     static const decompressionAlgo decompress[2] = { HUFv07_decompress4X2, HUFv07_decompress4X4 };
2522 
2523     /* validation checks */
2524     if (dstSize == 0) return ERROR(dstSize_tooSmall);
2525     if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
2526     if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
2527     if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
2528 
2529     {   U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2530         return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2531     }
2532 
2533     //return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize);   /* multi-streams single-symbol decoding */
2534     //return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize);   /* multi-streams double-symbols decoding */
2535 }
2536 
2537 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2538 {
2539     /* validation checks */
2540     if (dstSize == 0) return ERROR(dstSize_tooSmall);
2541     if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
2542     if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
2543     if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
2544 
2545     {   U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2546         return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2547                         HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2548     }
2549 }
2550 
2551 size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2552 {
2553     /* validation checks */
2554     if (dstSize == 0) return ERROR(dstSize_tooSmall);
2555     if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected);   /* invalid */
2556 
2557     {   U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2558         return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2559                         HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2560     }
2561 }
2562 
2563 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2564 {
2565     /* validation checks */
2566     if (dstSize == 0) return ERROR(dstSize_tooSmall);
2567     if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
2568     if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
2569     if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
2570 
2571     {   U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2572         return algoNb ? HUFv07_decompress1X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2573                         HUFv07_decompress1X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2574     }
2575 }
2576 /*
2577     Common functions of Zstd compression library
2578     Copyright (C) 2015-2016, Yann Collet.
2579 
2580     BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2581 
2582     Redistribution and use in source and binary forms, with or without
2583     modification, are permitted provided that the following conditions are
2584     met:
2585     * Redistributions of source code must retain the above copyright
2586     notice, this list of conditions and the following disclaimer.
2587     * Redistributions in binary form must reproduce the above
2588     copyright notice, this list of conditions and the following disclaimer
2589     in the documentation and/or other materials provided with the
2590     distribution.
2591     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2592     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2593     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2594     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2595     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2596     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2597     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2598     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2599     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2600     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2601     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2602 
2603     You can contact the author at :
2604     - zstd homepage : http://www.zstd.net/
2605 */
2606 
2607 
2608 
2609 /*-****************************************
2610 *  ZSTD Error Management
2611 ******************************************/
2612 /*! ZSTDv07_isError() :
2613 *   tells if a return value is an error code */
2614 unsigned ZSTDv07_isError(size_t code) { return ERR_isError(code); }
2615 
2616 /*! ZSTDv07_getErrorName() :
2617 *   provides error code string from function result (useful for debugging) */
2618 const char* ZSTDv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
2619 
2620 
2621 
2622 /* **************************************************************
2623 *  ZBUFF Error Management
2624 ****************************************************************/
2625 unsigned ZBUFFv07_isError(size_t errorCode) { return ERR_isError(errorCode); }
2626 
2627 const char* ZBUFFv07_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2628 
2629 
2630 
2631 void* ZSTDv07_defaultAllocFunction(void* opaque, size_t size)
2632 {
2633     void* address = malloc(size);
2634     (void)opaque;
2635     /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2636     return address;
2637 }
2638 
2639 void ZSTDv07_defaultFreeFunction(void* opaque, void* address)
2640 {
2641     (void)opaque;
2642     /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2643     free(address);
2644 }
2645 /*
2646     zstd_internal - common functions to include
2647     Header File for include
2648     Copyright (C) 2014-2016, Yann Collet.
2649 
2650     BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2651 
2652     Redistribution and use in source and binary forms, with or without
2653     modification, are permitted provided that the following conditions are
2654     met:
2655     * Redistributions of source code must retain the above copyright
2656     notice, this list of conditions and the following disclaimer.
2657     * Redistributions in binary form must reproduce the above
2658     copyright notice, this list of conditions and the following disclaimer
2659     in the documentation and/or other materials provided with the
2660     distribution.
2661     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2662     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2663     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2664     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2665     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2666     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2667     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2668     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2669     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2670     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2671     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2672 
2673     You can contact the author at :
2674     - zstd homepage : https://www.zstd.net
2675 */
2676 #ifndef ZSTDv07_CCOMMON_H_MODULE
2677 #define ZSTDv07_CCOMMON_H_MODULE
2678 
2679 
2680 /*-*************************************
2681 *  Common macros
2682 ***************************************/
2683 #define MIN(a,b) ((a)<(b) ? (a) : (b))
2684 #define MAX(a,b) ((a)>(b) ? (a) : (b))
2685 
2686 
2687 /*-*************************************
2688 *  Common constants
2689 ***************************************/
2690 #define ZSTDv07_OPT_NUM    (1<<12)
2691 #define ZSTDv07_DICT_MAGIC  0xEC30A437   /* v0.7 */
2692 
2693 #define ZSTDv07_REP_NUM    3
2694 #define ZSTDv07_REP_INIT   ZSTDv07_REP_NUM
2695 #define ZSTDv07_REP_MOVE   (ZSTDv07_REP_NUM-1)
2696 static const U32 repStartValue[ZSTDv07_REP_NUM] = { 1, 4, 8 };
2697 
2698 #define KB *(1 <<10)
2699 #define MB *(1 <<20)
2700 #define GB *(1U<<30)
2701 
2702 #define BIT7 128
2703 #define BIT6  64
2704 #define BIT5  32
2705 #define BIT4  16
2706 #define BIT1   2
2707 #define BIT0   1
2708 
2709 #define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10
2710 static const size_t ZSTDv07_fcs_fieldSize[4] = { 0, 2, 4, 8 };
2711 static const size_t ZSTDv07_did_fieldSize[4] = { 0, 1, 2, 4 };
2712 
2713 #define ZSTDv07_BLOCKHEADERSIZE 3   /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
2714 static const size_t ZSTDv07_blockHeaderSize = ZSTDv07_BLOCKHEADERSIZE;
2715 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2716 
2717 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2718 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
2719 
2720 #define HufLog 12
2721 typedef enum { lbt_huffman, lbt_repeat, lbt_raw, lbt_rle } litBlockType_t;
2722 
2723 #define LONGNBSEQ 0x7F00
2724 
2725 #define MINMATCH 3
2726 #define EQUAL_READ32 4
2727 
2728 #define Litbits  8
2729 #define MaxLit ((1<<Litbits) - 1)
2730 #define MaxML  52
2731 #define MaxLL  35
2732 #define MaxOff 28
2733 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
2734 #define MLFSELog    9
2735 #define LLFSELog    9
2736 #define OffFSELog   8
2737 
2738 #define FSEv07_ENCODING_RAW     0
2739 #define FSEv07_ENCODING_RLE     1
2740 #define FSEv07_ENCODING_STATIC  2
2741 #define FSEv07_ENCODING_DYNAMIC 3
2742 
2743 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2744                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
2745                                      13,14,15,16 };
2746 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2747                                              2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
2748                                             -1,-1,-1,-1 };
2749 static const U32 LL_defaultNormLog = 6;
2750 
2751 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2752                                       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2753                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
2754                                      12,13,14,15,16 };
2755 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2756                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2757                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
2758                                             -1,-1,-1,-1,-1 };
2759 static const U32 ML_defaultNormLog = 6;
2760 
2761 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2762                                               1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
2763 static const U32 OF_defaultNormLog = 5;
2764 
2765 
2766 /*-*******************************************
2767 *  Shared functions to include for inlining
2768 *********************************************/
2769 static void ZSTDv07_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2770 #define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; }
2771 
2772 /*! ZSTDv07_wildcopy() :
2773 *   custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
2774 #define WILDCOPY_OVERLENGTH 8
2775 MEM_STATIC void ZSTDv07_wildcopy(void* dst, const void* src, ptrdiff_t length)
2776 {
2777     const BYTE* ip = (const BYTE*)src;
2778     BYTE* op = (BYTE*)dst;
2779     BYTE* const oend = op + length;
2780     do
2781         COPY8(op, ip)
2782     while (op < oend);
2783 }
2784 
2785 
2786 /*-*******************************************
2787 *  Private interfaces
2788 *********************************************/
2789 typedef struct ZSTDv07_stats_s ZSTDv07_stats_t;
2790 
2791 typedef struct {
2792     U32 off;
2793     U32 len;
2794 } ZSTDv07_match_t;
2795 
2796 typedef struct {
2797     U32 price;
2798     U32 off;
2799     U32 mlen;
2800     U32 litlen;
2801     U32 rep[ZSTDv07_REP_INIT];
2802 } ZSTDv07_optimal_t;
2803 
2804 struct ZSTDv07_stats_s { U32 unused; };
2805 
2806 typedef struct {
2807     void* buffer;
2808     U32*  offsetStart;
2809     U32*  offset;
2810     BYTE* offCodeStart;
2811     BYTE* litStart;
2812     BYTE* lit;
2813     U16*  litLengthStart;
2814     U16*  litLength;
2815     BYTE* llCodeStart;
2816     U16*  matchLengthStart;
2817     U16*  matchLength;
2818     BYTE* mlCodeStart;
2819     U32   longLengthID;   /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
2820     U32   longLengthPos;
2821     /* opt */
2822     ZSTDv07_optimal_t* priceTable;
2823     ZSTDv07_match_t* matchTable;
2824     U32* matchLengthFreq;
2825     U32* litLengthFreq;
2826     U32* litFreq;
2827     U32* offCodeFreq;
2828     U32  matchLengthSum;
2829     U32  matchSum;
2830     U32  litLengthSum;
2831     U32  litSum;
2832     U32  offCodeSum;
2833     U32  log2matchLengthSum;
2834     U32  log2matchSum;
2835     U32  log2litLengthSum;
2836     U32  log2litSum;
2837     U32  log2offCodeSum;
2838     U32  factor;
2839     U32  cachedPrice;
2840     U32  cachedLitLength;
2841     const BYTE* cachedLiterals;
2842     ZSTDv07_stats_t stats;
2843 } seqStore_t;
2844 
2845 void ZSTDv07_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
2846 
2847 /* custom memory allocation functions */
2848 static const ZSTDv07_customMem defaultCustomMem = { ZSTDv07_defaultAllocFunction, ZSTDv07_defaultFreeFunction, NULL };
2849 
2850 #endif   /* ZSTDv07_CCOMMON_H_MODULE */
2851 /*
2852     zstd - standard compression library
2853     Copyright (C) 2014-2016, Yann Collet.
2854 
2855     BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2856 
2857     Redistribution and use in source and binary forms, with or without
2858     modification, are permitted provided that the following conditions are
2859     met:
2860     * Redistributions of source code must retain the above copyright
2861     notice, this list of conditions and the following disclaimer.
2862     * Redistributions in binary form must reproduce the above
2863     copyright notice, this list of conditions and the following disclaimer
2864     in the documentation and/or other materials provided with the
2865     distribution.
2866     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2867     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2868     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2869     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2870     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2871     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2872     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2873     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2874     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2875     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2876     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2877 
2878     You can contact the author at :
2879     - zstd homepage : http://www.zstd.net
2880 */
2881 
2882 /* ***************************************************************
2883 *  Tuning parameters
2884 *****************************************************************/
2885 /*!
2886  * HEAPMODE :
2887  * Select how default decompression function ZSTDv07_decompress() will allocate memory,
2888  * in memory stack (0), or in memory heap (1, requires malloc())
2889  */
2890 #ifndef ZSTDv07_HEAPMODE
2891 #  define ZSTDv07_HEAPMODE 1
2892 #endif
2893 
2894 
2895 /*-*******************************************************
2896 *  Compiler specifics
2897 *********************************************************/
2898 #ifdef _MSC_VER    /* Visual Studio */
2899 #  include <intrin.h>                    /* For Visual 2005 */
2900 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
2901 #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
2902 #  pragma warning(disable : 4100)        /* disable: C4100: unreferenced formal parameter */
2903 #endif
2904 
2905 
2906 /*-*************************************
2907 *  Macros
2908 ***************************************/
2909 #define ZSTDv07_isError ERR_isError   /* for inlining */
2910 #define FSEv07_isError  ERR_isError
2911 #define HUFv07_isError  ERR_isError
2912 
2913 
2914 /*_*******************************************************
2915 *  Memory operations
2916 **********************************************************/
2917 static void ZSTDv07_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2918 
2919 
2920 /*-*************************************************************
2921 *   Context management
2922 ***************************************************************/
2923 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2924                ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
2925                ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTDv07_dStage;
2926 
2927 struct ZSTDv07_DCtx_s
2928 {
2929     FSEv07_DTable LLTable[FSEv07_DTABLE_SIZE_U32(LLFSELog)];
2930     FSEv07_DTable OffTable[FSEv07_DTABLE_SIZE_U32(OffFSELog)];
2931     FSEv07_DTable MLTable[FSEv07_DTABLE_SIZE_U32(MLFSELog)];
2932     HUFv07_DTable hufTable[HUFv07_DTABLE_SIZE(HufLog)];  /* can accommodate HUFv07_decompress4X */
2933     const void* previousDstEnd;
2934     const void* base;
2935     const void* vBase;
2936     const void* dictEnd;
2937     size_t expected;
2938     U32 rep[3];
2939     ZSTDv07_frameParams fParams;
2940     blockType_t bType;   /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2941     ZSTDv07_dStage stage;
2942     U32 litEntropy;
2943     U32 fseEntropy;
2944     XXH64_state_t xxhState;
2945     size_t headerSize;
2946     U32 dictID;
2947     const BYTE* litPtr;
2948     ZSTDv07_customMem customMem;
2949     size_t litSize;
2950     BYTE litBuffer[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
2951     BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
2952 };  /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */
2953 
2954 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx);
2955 
2956 size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx* dctx) { return sizeof(*dctx); }
2957 
2958 size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx); }
2959 
2960 size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx)
2961 {
2962     dctx->expected = ZSTDv07_frameHeaderSize_min;
2963     dctx->stage = ZSTDds_getFrameHeaderSize;
2964     dctx->previousDstEnd = NULL;
2965     dctx->base = NULL;
2966     dctx->vBase = NULL;
2967     dctx->dictEnd = NULL;
2968     dctx->hufTable[0] = (HUFv07_DTable)((HufLog)*0x1000001);
2969     dctx->litEntropy = dctx->fseEntropy = 0;
2970     dctx->dictID = 0;
2971     { int i; for (i=0; i<ZSTDv07_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; }
2972     return 0;
2973 }
2974 
2975 ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem)
2976 {
2977     ZSTDv07_DCtx* dctx;
2978 
2979     if (!customMem.customAlloc && !customMem.customFree)
2980         customMem = defaultCustomMem;
2981 
2982     if (!customMem.customAlloc || !customMem.customFree)
2983         return NULL;
2984 
2985     dctx = (ZSTDv07_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTDv07_DCtx));
2986     if (!dctx) return NULL;
2987     memcpy(&dctx->customMem, &customMem, sizeof(ZSTDv07_customMem));
2988     ZSTDv07_decompressBegin(dctx);
2989     return dctx;
2990 }
2991 
2992 ZSTDv07_DCtx* ZSTDv07_createDCtx(void)
2993 {
2994     return ZSTDv07_createDCtx_advanced(defaultCustomMem);
2995 }
2996 
2997 size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx* dctx)
2998 {
2999     if (dctx==NULL) return 0;   /* support free on NULL */
3000     dctx->customMem.customFree(dctx->customMem.opaque, dctx);
3001     return 0;   /* reserved as a potential error code in the future */
3002 }
3003 
3004 void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dstDCtx, const ZSTDv07_DCtx* srcDCtx)
3005 {
3006     memcpy(dstDCtx, srcDCtx,
3007            sizeof(ZSTDv07_DCtx) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH + ZSTDv07_frameHeaderSize_max));  /* no need to copy workspace */
3008 }
3009 
3010 
3011 /*-*************************************************************
3012 *   Decompression section
3013 ***************************************************************/
3014 
3015 /* Frame format description
3016    Frame Header -  [ Block Header - Block ] - Frame End
3017    1) Frame Header
3018       - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h)
3019       - 1 byte  - Frame Descriptor
3020    2) Block Header
3021       - 3 bytes, starting with a 2-bits descriptor
3022                  Uncompressed, Compressed, Frame End, unused
3023    3) Block
3024       See Block Format Description
3025    4) Frame End
3026       - 3 bytes, compatible with Block Header
3027 */
3028 
3029 
3030 /* Frame Header :
3031 
3032    1 byte - FrameHeaderDescription :
3033    bit 0-1 : dictID (0, 1, 2 or 4 bytes)
3034    bit 2   : checksumFlag
3035    bit 3   : reserved (must be zero)
3036    bit 4   : reserved (unused, can be any value)
3037    bit 5   : Single Segment (if 1, WindowLog byte is not present)
3038    bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
3039              if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
3040 
3041    Optional : WindowLog (0 or 1 byte)
3042    bit 0-2 : octal Fractional (1/8th)
3043    bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
3044 
3045    Optional : dictID (0, 1, 2 or 4 bytes)
3046    Automatic adaptation
3047    0 : no dictID
3048    1 : 1 - 255
3049    2 : 256 - 65535
3050    4 : all other values
3051 
3052    Optional : content size (0, 1, 2, 4 or 8 bytes)
3053    0 : unknown          (fcfs==0 and swl==0)
3054    1 : 0-255 bytes      (fcfs==0 and swl==1)
3055    2 : 256 - 65535+256  (fcfs==1)
3056    4 : 0 - 4GB-1        (fcfs==2)
3057    8 : 0 - 16EB-1       (fcfs==3)
3058 */
3059 
3060 
3061 /* Compressed Block, format description
3062 
3063    Block = Literal Section - Sequences Section
3064    Prerequisite : size of (compressed) block, maximum size of regenerated data
3065 
3066    1) Literal Section
3067 
3068    1.1) Header : 1-5 bytes
3069         flags: 2 bits
3070             00 compressed by Huff0
3071             01 unused
3072             10 is Raw (uncompressed)
3073             11 is Rle
3074             Note : using 01 => Huff0 with precomputed table ?
3075             Note : delta map ? => compressed ?
3076 
3077    1.1.1) Huff0-compressed literal block : 3-5 bytes
3078             srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3079             srcSize < 1 KB => 3 bytes (2-2-10-10)
3080             srcSize < 16KB => 4 bytes (2-2-14-14)
3081             else           => 5 bytes (2-2-18-18)
3082             big endian convention
3083 
3084    1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
3085         size :  5 bits: (IS_RAW<<6) + (0<<4) + size
3086                12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
3087                         size&255
3088                20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3089                         size>>8&255
3090                         size&255
3091 
3092    1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3093         size :  5 bits: (IS_RLE<<6) + (0<<4) + size
3094                12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3095                         size&255
3096                20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3097                         size>>8&255
3098                         size&255
3099 
3100    1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3101             srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3102             srcSize < 1 KB => 3 bytes (2-2-10-10)
3103             srcSize < 16KB => 4 bytes (2-2-14-14)
3104             else           => 5 bytes (2-2-18-18)
3105             big endian convention
3106 
3107         1- CTable available (stored into workspace ?)
3108         2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3109 
3110 
3111    1.2) Literal block content
3112 
3113    1.2.1) Huff0 block, using sizes from header
3114         See Huff0 format
3115 
3116    1.2.2) Huff0 block, using prepared table
3117 
3118    1.2.3) Raw content
3119 
3120    1.2.4) single byte
3121 
3122 
3123    2) Sequences section
3124       TO DO
3125 */
3126 
3127 /** ZSTDv07_frameHeaderSize() :
3128 *   srcSize must be >= ZSTDv07_frameHeaderSize_min.
3129 *   @return : size of the Frame Header */
3130 static size_t ZSTDv07_frameHeaderSize(const void* src, size_t srcSize)
3131 {
3132     if (srcSize < ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);
3133     {   BYTE const fhd = ((const BYTE*)src)[4];
3134         U32 const dictID= fhd & 3;
3135         U32 const directMode = (fhd >> 5) & 1;
3136         U32 const fcsId = fhd >> 6;
3137         return ZSTDv07_frameHeaderSize_min + !directMode + ZSTDv07_did_fieldSize[dictID] + ZSTDv07_fcs_fieldSize[fcsId]
3138                 + (directMode && !ZSTDv07_fcs_fieldSize[fcsId]);
3139     }
3140 }
3141 
3142 
3143 /** ZSTDv07_getFrameParams() :
3144 *   decode Frame Header, or require larger `srcSize`.
3145 *   @return : 0, `fparamsPtr` is correctly filled,
3146 *            >0, `srcSize` is too small, result is expected `srcSize`,
3147 *             or an error code, which can be tested using ZSTDv07_isError() */
3148 size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams* fparamsPtr, const void* src, size_t srcSize)
3149 {
3150     const BYTE* ip = (const BYTE*)src;
3151 
3152     if (srcSize < ZSTDv07_frameHeaderSize_min) return ZSTDv07_frameHeaderSize_min;
3153     if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3154         if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3155             if (srcSize < ZSTDv07_skippableHeaderSize) return ZSTDv07_skippableHeaderSize; /* magic number + skippable frame length */
3156             memset(fparamsPtr, 0, sizeof(*fparamsPtr));
3157             fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);
3158             fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
3159             return 0;
3160         }
3161         return ERROR(prefix_unknown);
3162     }
3163 
3164     /* ensure there is enough `srcSize` to fully read/decode frame header */
3165     { size_t const fhsize = ZSTDv07_frameHeaderSize(src, srcSize);
3166       if (srcSize < fhsize) return fhsize; }
3167 
3168     {   BYTE const fhdByte = ip[4];
3169         size_t pos = 5;
3170         U32 const dictIDSizeCode = fhdByte&3;
3171         U32 const checksumFlag = (fhdByte>>2)&1;
3172         U32 const directMode = (fhdByte>>5)&1;
3173         U32 const fcsID = fhdByte>>6;
3174         U32 const windowSizeMax = 1U << ZSTDv07_WINDOWLOG_MAX;
3175         U32 windowSize = 0;
3176         U32 dictID = 0;
3177         U64 frameContentSize = 0;
3178         if ((fhdByte & 0x08) != 0) return ERROR(frameParameter_unsupported);   /* reserved bits, which must be zero */
3179         if (!directMode) {
3180             BYTE const wlByte = ip[pos++];
3181             U32 const windowLog = (wlByte >> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN;
3182             if (windowLog > ZSTDv07_WINDOWLOG_MAX) return ERROR(frameParameter_unsupported);
3183             windowSize = (1U << windowLog);
3184             windowSize += (windowSize >> 3) * (wlByte&7);
3185         }
3186 
3187         switch(dictIDSizeCode)
3188         {
3189             default:   /* impossible */
3190             case 0 : break;
3191             case 1 : dictID = ip[pos]; pos++; break;
3192             case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
3193             case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
3194         }
3195         switch(fcsID)
3196         {
3197             default:   /* impossible */
3198             case 0 : if (directMode) frameContentSize = ip[pos]; break;
3199             case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
3200             case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
3201             case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
3202         }
3203         if (!windowSize) windowSize = (U32)frameContentSize;
3204         if (windowSize > windowSizeMax) return ERROR(frameParameter_unsupported);
3205         fparamsPtr->frameContentSize = frameContentSize;
3206         fparamsPtr->windowSize = windowSize;
3207         fparamsPtr->dictID = dictID;
3208         fparamsPtr->checksumFlag = checksumFlag;
3209     }
3210     return 0;
3211 }
3212 
3213 
3214 /** ZSTDv07_getDecompressedSize() :
3215 *   compatible with legacy mode
3216 *   @return : decompressed size if known, 0 otherwise
3217               note : 0 can mean any of the following :
3218                    - decompressed size is not provided within frame header
3219                    - frame header unknown / not supported
3220                    - frame header not completely provided (`srcSize` too small) */
3221 unsigned long long ZSTDv07_getDecompressedSize(const void* src, size_t srcSize)
3222 {
3223     {   ZSTDv07_frameParams fparams;
3224         size_t const frResult = ZSTDv07_getFrameParams(&fparams, src, srcSize);
3225         if (frResult!=0) return 0;
3226         return fparams.frameContentSize;
3227     }
3228 }
3229 
3230 
3231 /** ZSTDv07_decodeFrameHeader() :
3232 *   `srcSize` must be the size provided by ZSTDv07_frameHeaderSize().
3233 *   @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */
3234 static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx* dctx, const void* src, size_t srcSize)
3235 {
3236     size_t const result = ZSTDv07_getFrameParams(&(dctx->fParams), src, srcSize);
3237     if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
3238     if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
3239     return result;
3240 }
3241 
3242 
3243 typedef struct
3244 {
3245     blockType_t blockType;
3246     U32 origSize;
3247 } blockProperties_t;
3248 
3249 /*! ZSTDv07_getcBlockSize() :
3250 *   Provides the size of compressed block from block header `src` */
3251 size_t ZSTDv07_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
3252 {
3253     const BYTE* const in = (const BYTE* const)src;
3254     U32 cSize;
3255 
3256     if (srcSize < ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3257 
3258     bpPtr->blockType = (blockType_t)((*in) >> 6);
3259     cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
3260     bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
3261 
3262     if (bpPtr->blockType == bt_end) return 0;
3263     if (bpPtr->blockType == bt_rle) return 1;
3264     return cSize;
3265 }
3266 
3267 
3268 static size_t ZSTDv07_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3269 {
3270     if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
3271     memcpy(dst, src, srcSize);
3272     return srcSize;
3273 }
3274 
3275 
3276 /*! ZSTDv07_decodeLiteralsBlock() :
3277     @return : nb of bytes read from src (< srcSize ) */
3278 size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx* dctx,
3279                           const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
3280 {
3281     const BYTE* const istart = (const BYTE*) src;
3282 
3283     if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3284 
3285     switch((litBlockType_t)(istart[0]>> 6))
3286     {
3287     case lbt_huffman:
3288         {   size_t litSize, litCSize, singleStream=0;
3289             U32 lhSize = (istart[0] >> 4) & 3;
3290             if (srcSize < 5) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3291             switch(lhSize)
3292             {
3293             case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3294                 /* 2 - 2 - 10 - 10 */
3295                 lhSize=3;
3296                 singleStream = istart[0] & 16;
3297                 litSize  = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3298                 litCSize = ((istart[1] &  3) << 8) + istart[2];
3299                 break;
3300             case 2:
3301                 /* 2 - 2 - 14 - 14 */
3302                 lhSize=4;
3303                 litSize  = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3304                 litCSize = ((istart[2] & 63) <<  8) + istart[3];
3305                 break;
3306             case 3:
3307                 /* 2 - 2 - 18 - 18 */
3308                 lhSize=5;
3309                 litSize  = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3310                 litCSize = ((istart[2] &  3) << 16) + (istart[3] << 8) + istart[4];
3311                 break;
3312             }
3313             if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3314             if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3315 
3316             if (HUFv07_isError(singleStream ?
3317                             HUFv07_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3318                             HUFv07_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3319                 return ERROR(corruption_detected);
3320 
3321             dctx->litPtr = dctx->litBuffer;
3322             dctx->litSize = litSize;
3323             dctx->litEntropy = 1;
3324             memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3325             return litCSize + lhSize;
3326         }
3327     case lbt_repeat:
3328         {   size_t litSize, litCSize;
3329             U32 lhSize = ((istart[0]) >> 4) & 3;
3330             if (lhSize != 1)  /* only case supported for now : small litSize, single stream */
3331                 return ERROR(corruption_detected);
3332             if (dctx->litEntropy==0)
3333                 return ERROR(dictionary_corrupted);
3334 
3335             /* 2 - 2 - 10 - 10 */
3336             lhSize=3;
3337             litSize  = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3338             litCSize = ((istart[1] &  3) << 8) + istart[2];
3339             if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3340 
3341             {   size_t const errorCode = HUFv07_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTable);
3342                 if (HUFv07_isError(errorCode)) return ERROR(corruption_detected);
3343             }
3344             dctx->litPtr = dctx->litBuffer;
3345             dctx->litSize = litSize;
3346             memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3347             return litCSize + lhSize;
3348         }
3349     case lbt_raw:
3350         {   size_t litSize;
3351             U32 lhSize = ((istart[0]) >> 4) & 3;
3352             switch(lhSize)
3353             {
3354             case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3355                 lhSize=1;
3356                 litSize = istart[0] & 31;
3357                 break;
3358             case 2:
3359                 litSize = ((istart[0] & 15) << 8) + istart[1];
3360                 break;
3361             case 3:
3362                 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3363                 break;
3364             }
3365 
3366             if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */
3367                 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3368                 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3369                 dctx->litPtr = dctx->litBuffer;
3370                 dctx->litSize = litSize;
3371                 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3372                 return lhSize+litSize;
3373             }
3374             /* direct reference into compressed stream */
3375             dctx->litPtr = istart+lhSize;
3376             dctx->litSize = litSize;
3377             return lhSize+litSize;
3378         }
3379     case lbt_rle:
3380         {   size_t litSize;
3381             U32 lhSize = ((istart[0]) >> 4) & 3;
3382             switch(lhSize)
3383             {
3384             case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3385                 lhSize = 1;
3386                 litSize = istart[0] & 31;
3387                 break;
3388             case 2:
3389                 litSize = ((istart[0] & 15) << 8) + istart[1];
3390                 break;
3391             case 3:
3392                 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3393                 if (srcSize<4) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3394                 break;
3395             }
3396             if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3397             memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3398             dctx->litPtr = dctx->litBuffer;
3399             dctx->litSize = litSize;
3400             return lhSize+1;
3401         }
3402     default:
3403         return ERROR(corruption_detected);   /* impossible */
3404     }
3405 }
3406 
3407 
3408 /*! ZSTDv07_buildSeqTable() :
3409     @return : nb bytes read from src,
3410               or an error code if it fails, testable with ZSTDv07_isError()
3411 */
3412 size_t ZSTDv07_buildSeqTable(FSEv07_DTable* DTable, U32 type, U32 max, U32 maxLog,
3413                                  const void* src, size_t srcSize,
3414                                  const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3415 {
3416     switch(type)
3417     {
3418     case FSEv07_ENCODING_RLE :
3419         if (!srcSize) return ERROR(srcSize_wrong);
3420         if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3421         FSEv07_buildDTable_rle(DTable, *(const BYTE*)src);   /* if *src > max, data is corrupted */
3422         return 1;
3423     case FSEv07_ENCODING_RAW :
3424         FSEv07_buildDTable(DTable, defaultNorm, max, defaultLog);
3425         return 0;
3426     case FSEv07_ENCODING_STATIC:
3427         if (!flagRepeatTable) return ERROR(corruption_detected);
3428         return 0;
3429     default :   /* impossible */
3430     case FSEv07_ENCODING_DYNAMIC :
3431         {   U32 tableLog;
3432             S16 norm[MaxSeq+1];
3433             size_t const headerSize = FSEv07_readNCount(norm, &max, &tableLog, src, srcSize);
3434             if (FSEv07_isError(headerSize)) return ERROR(corruption_detected);
3435             if (tableLog > maxLog) return ERROR(corruption_detected);
3436             FSEv07_buildDTable(DTable, norm, max, tableLog);
3437             return headerSize;
3438     }   }
3439 }
3440 
3441 
3442 size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr,
3443                              FSEv07_DTable* DTableLL, FSEv07_DTable* DTableML, FSEv07_DTable* DTableOffb, U32 flagRepeatTable,
3444                              const void* src, size_t srcSize)
3445 {
3446     const BYTE* const istart = (const BYTE* const)src;
3447     const BYTE* const iend = istart + srcSize;
3448     const BYTE* ip = istart;
3449 
3450     /* check */
3451     if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3452 
3453     /* SeqHead */
3454     {   int nbSeq = *ip++;
3455         if (!nbSeq) { *nbSeqPtr=0; return 1; }
3456         if (nbSeq > 0x7F) {
3457             if (nbSeq == 0xFF) {
3458                 if (ip+2 > iend) return ERROR(srcSize_wrong);
3459                 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3460             } else {
3461                 if (ip >= iend) return ERROR(srcSize_wrong);
3462                 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3463             }
3464         }
3465         *nbSeqPtr = nbSeq;
3466     }
3467 
3468     /* FSE table descriptors */
3469     {   U32 const LLtype  = *ip >> 6;
3470         U32 const OFtype = (*ip >> 4) & 3;
3471         U32 const MLtype  = (*ip >> 2) & 3;
3472         ip++;
3473 
3474         /* check */
3475         if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3476 
3477         /* Build DTables */
3478         {   size_t const llhSize = ZSTDv07_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3479             if (ZSTDv07_isError(llhSize)) return ERROR(corruption_detected);
3480             ip += llhSize;
3481         }
3482         {   size_t const ofhSize = ZSTDv07_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3483             if (ZSTDv07_isError(ofhSize)) return ERROR(corruption_detected);
3484             ip += ofhSize;
3485         }
3486         {   size_t const mlhSize = ZSTDv07_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3487             if (ZSTDv07_isError(mlhSize)) return ERROR(corruption_detected);
3488             ip += mlhSize;
3489     }   }
3490 
3491     return ip-istart;
3492 }
3493 
3494 
3495 typedef struct {
3496     size_t litLength;
3497     size_t matchLength;
3498     size_t offset;
3499 } seq_t;
3500 
3501 typedef struct {
3502     BITv07_DStream_t DStream;
3503     FSEv07_DState_t stateLL;
3504     FSEv07_DState_t stateOffb;
3505     FSEv07_DState_t stateML;
3506     size_t prevOffset[ZSTDv07_REP_INIT];
3507 } seqState_t;
3508 
3509 
3510 static seq_t ZSTDv07_decodeSequence(seqState_t* seqState)
3511 {
3512     seq_t seq;
3513 
3514     U32 const llCode = FSEv07_peekSymbol(&(seqState->stateLL));
3515     U32 const mlCode = FSEv07_peekSymbol(&(seqState->stateML));
3516     U32 const ofCode = FSEv07_peekSymbol(&(seqState->stateOffb));   /* <= maxOff, by table construction */
3517 
3518     U32 const llBits = LL_bits[llCode];
3519     U32 const mlBits = ML_bits[mlCode];
3520     U32 const ofBits = ofCode;
3521     U32 const totalBits = llBits+mlBits+ofBits;
3522 
3523     static const U32 LL_base[MaxLL+1] = {
3524                              0,  1,  2,  3,  4,  5,  6,  7,  8,  9,   10,    11,    12,    13,    14,     15,
3525                             16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3526                             0x2000, 0x4000, 0x8000, 0x10000 };
3527 
3528     static const U32 ML_base[MaxML+1] = {
3529                              3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13,   14,    15,    16,    17,    18,
3530                             19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,   30,    31,    32,    33,    34,
3531                             35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3532                             0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3533 
3534     static const U32 OF_base[MaxOff+1] = {
3535                  0,        1,       1,       5,     0xD,     0x1D,     0x3D,     0x7D,
3536                  0xFD,   0x1FD,   0x3FD,   0x7FD,   0xFFD,   0x1FFD,   0x3FFD,   0x7FFD,
3537                  0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3538                  0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3539 
3540     /* sequence */
3541     {   size_t offset;
3542         if (!ofCode)
3543             offset = 0;
3544         else {
3545             offset = OF_base[ofCode] + BITv07_readBits(&(seqState->DStream), ofBits);   /* <=  (ZSTDv07_WINDOWLOG_MAX-1) bits */
3546             if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));
3547         }
3548 
3549         if (ofCode <= 1) {
3550             if ((llCode == 0) & (offset <= 1)) offset = 1-offset;
3551             if (offset) {
3552                 size_t const temp = seqState->prevOffset[offset];
3553                 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
3554                 seqState->prevOffset[1] = seqState->prevOffset[0];
3555                 seqState->prevOffset[0] = offset = temp;
3556             } else {
3557                 offset = seqState->prevOffset[0];
3558             }
3559         } else {
3560             seqState->prevOffset[2] = seqState->prevOffset[1];
3561             seqState->prevOffset[1] = seqState->prevOffset[0];
3562             seqState->prevOffset[0] = offset;
3563         }
3564         seq.offset = offset;
3565     }
3566 
3567     seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BITv07_readBits(&(seqState->DStream), mlBits) : 0);   /* <=  16 bits */
3568     if (MEM_32bits() && (mlBits+llBits>24)) BITv07_reloadDStream(&(seqState->DStream));
3569 
3570     seq.litLength = LL_base[llCode] + ((llCode>15) ? BITv07_readBits(&(seqState->DStream), llBits) : 0);   /* <=  16 bits */
3571     if (MEM_32bits() ||
3572        (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv07_reloadDStream(&(seqState->DStream));
3573 
3574     /* ANS state update */
3575     FSEv07_updateState(&(seqState->stateLL), &(seqState->DStream));   /* <=  9 bits */
3576     FSEv07_updateState(&(seqState->stateML), &(seqState->DStream));   /* <=  9 bits */
3577     if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));     /* <= 18 bits */
3578     FSEv07_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <=  8 bits */
3579 
3580     return seq;
3581 }
3582 
3583 
3584 static
3585 size_t ZSTDv07_execSequence(BYTE* op,
3586                                 BYTE* const oend, seq_t sequence,
3587                                 const BYTE** litPtr, const BYTE* const litLimit,
3588                                 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3589 {
3590     BYTE* const oLitEnd = op + sequence.litLength;
3591     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3592     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
3593     BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH;
3594     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3595     const BYTE* match = oLitEnd - sequence.offset;
3596 
3597     /* check */
3598     if ((oLitEnd>oend_w) | (oMatchEnd>oend)) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
3599     if (iLitEnd > litLimit) return ERROR(corruption_detected);   /* over-read beyond lit buffer */
3600 
3601     /* copy Literals */
3602     ZSTDv07_wildcopy(op, *litPtr, sequence.litLength);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3603     op = oLitEnd;
3604     *litPtr = iLitEnd;   /* update for next sequence */
3605 
3606     /* copy Match */
3607     if (sequence.offset > (size_t)(oLitEnd - base)) {
3608         /* offset beyond prefix */
3609         if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3610         match = dictEnd - (base-match);
3611         if (match + sequence.matchLength <= dictEnd) {
3612             memmove(oLitEnd, match, sequence.matchLength);
3613             return sequenceLength;
3614         }
3615         /* span extDict & currentPrefixSegment */
3616         {   size_t const length1 = dictEnd - match;
3617             memmove(oLitEnd, match, length1);
3618             op = oLitEnd + length1;
3619             sequence.matchLength -= length1;
3620             match = base;
3621             if (op > oend_w || sequence.matchLength < MINMATCH) {
3622               while (op < oMatchEnd) *op++ = *match++;
3623               return sequenceLength;
3624             }
3625     }   }
3626     /* Requirement: op <= oend_w */
3627 
3628     /* match within prefix */
3629     if (sequence.offset < 8) {
3630         /* close range match, overlap */
3631         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
3632         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* substracted */
3633         int const sub2 = dec64table[sequence.offset];
3634         op[0] = match[0];
3635         op[1] = match[1];
3636         op[2] = match[2];
3637         op[3] = match[3];
3638         match += dec32table[sequence.offset];
3639         ZSTDv07_copy4(op+4, match);
3640         match -= sub2;
3641     } else {
3642         ZSTDv07_copy8(op, match);
3643     }
3644     op += 8; match += 8;
3645 
3646     if (oMatchEnd > oend-(16-MINMATCH)) {
3647         if (op < oend_w) {
3648             ZSTDv07_wildcopy(op, match, oend_w - op);
3649             match += oend_w - op;
3650             op = oend_w;
3651         }
3652         while (op < oMatchEnd) *op++ = *match++;
3653     } else {
3654         ZSTDv07_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
3655     }
3656     return sequenceLength;
3657 }
3658 
3659 
3660 static size_t ZSTDv07_decompressSequences(
3661                                ZSTDv07_DCtx* dctx,
3662                                void* dst, size_t maxDstSize,
3663                          const void* seqStart, size_t seqSize)
3664 {
3665     const BYTE* ip = (const BYTE*)seqStart;
3666     const BYTE* const iend = ip + seqSize;
3667     BYTE* const ostart = (BYTE* const)dst;
3668     BYTE* const oend = ostart + maxDstSize;
3669     BYTE* op = ostart;
3670     const BYTE* litPtr = dctx->litPtr;
3671     const BYTE* const litEnd = litPtr + dctx->litSize;
3672     FSEv07_DTable* DTableLL = dctx->LLTable;
3673     FSEv07_DTable* DTableML = dctx->MLTable;
3674     FSEv07_DTable* DTableOffb = dctx->OffTable;
3675     const BYTE* const base = (const BYTE*) (dctx->base);
3676     const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3677     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3678     int nbSeq;
3679 
3680     /* Build Decoding Tables */
3681     {   size_t const seqHSize = ZSTDv07_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize);
3682         if (ZSTDv07_isError(seqHSize)) return seqHSize;
3683         ip += seqHSize;
3684     }
3685 
3686     /* Regen sequences */
3687     if (nbSeq) {
3688         seqState_t seqState;
3689         dctx->fseEntropy = 1;
3690         { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; }
3691         { size_t const errorCode = BITv07_initDStream(&(seqState.DStream), ip, iend-ip);
3692           if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3693         FSEv07_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3694         FSEv07_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3695         FSEv07_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3696 
3697         for ( ; (BITv07_reloadDStream(&(seqState.DStream)) <= BITv07_DStream_completed) && nbSeq ; ) {
3698             nbSeq--;
3699             {   seq_t const sequence = ZSTDv07_decodeSequence(&seqState);
3700                 size_t const oneSeqSize = ZSTDv07_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3701                 if (ZSTDv07_isError(oneSeqSize)) return oneSeqSize;
3702                 op += oneSeqSize;
3703         }   }
3704 
3705         /* check if reached exact end */
3706         if (nbSeq) return ERROR(corruption_detected);
3707         /* save reps for next block */
3708         { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
3709     }
3710 
3711     /* last literal segment */
3712     {   size_t const lastLLSize = litEnd - litPtr;
3713         //if (litPtr > litEnd) return ERROR(corruption_detected);   /* too many literals already used */
3714         if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
3715         memcpy(op, litPtr, lastLLSize);
3716         op += lastLLSize;
3717     }
3718 
3719     return op-ostart;
3720 }
3721 
3722 
3723 static void ZSTDv07_checkContinuity(ZSTDv07_DCtx* dctx, const void* dst)
3724 {
3725     if (dst != dctx->previousDstEnd) {   /* not contiguous */
3726         dctx->dictEnd = dctx->previousDstEnd;
3727         dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3728         dctx->base = dst;
3729         dctx->previousDstEnd = dst;
3730     }
3731 }
3732 
3733 
3734 static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx* dctx,
3735                             void* dst, size_t dstCapacity,
3736                       const void* src, size_t srcSize)
3737 {   /* blockType == blockCompressed */
3738     const BYTE* ip = (const BYTE*)src;
3739 
3740     if (srcSize >= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong);
3741 
3742     /* Decode literals sub-block */
3743     {   size_t const litCSize = ZSTDv07_decodeLiteralsBlock(dctx, src, srcSize);
3744         if (ZSTDv07_isError(litCSize)) return litCSize;
3745         ip += litCSize;
3746         srcSize -= litCSize;
3747     }
3748     return ZSTDv07_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3749 }
3750 
3751 
3752 size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx,
3753                             void* dst, size_t dstCapacity,
3754                       const void* src, size_t srcSize)
3755 {
3756     size_t dSize;
3757     ZSTDv07_checkContinuity(dctx, dst);
3758     dSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3759     dctx->previousDstEnd = (char*)dst + dSize;
3760     return dSize;
3761 }
3762 
3763 
3764 /** ZSTDv07_insertBlock() :
3765     insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
3766 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize)
3767 {
3768     ZSTDv07_checkContinuity(dctx, blockStart);
3769     dctx->previousDstEnd = (const char*)blockStart + blockSize;
3770     return blockSize;
3771 }
3772 
3773 
3774 size_t ZSTDv07_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length)
3775 {
3776     if (length > dstCapacity) return ERROR(dstSize_tooSmall);
3777     memset(dst, byte, length);
3778     return length;
3779 }
3780 
3781 
3782 /*! ZSTDv07_decompressFrame() :
3783 *   `dctx` must be properly initialized */
3784 static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx* dctx,
3785                                  void* dst, size_t dstCapacity,
3786                                  const void* src, size_t srcSize)
3787 {
3788     const BYTE* ip = (const BYTE*)src;
3789     const BYTE* const iend = ip + srcSize;
3790     BYTE* const ostart = (BYTE* const)dst;
3791     BYTE* const oend = ostart + dstCapacity;
3792     BYTE* op = ostart;
3793     size_t remainingSize = srcSize;
3794 
3795     /* check */
3796     if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3797 
3798     /* Frame Header */
3799     {   size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3800         if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3801         if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3802         if (ZSTDv07_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3803         ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3804     }
3805 
3806     /* Loop on each block */
3807     while (1) {
3808         size_t decodedSize;
3809         blockProperties_t blockProperties;
3810         size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, iend-ip, &blockProperties);
3811         if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3812 
3813         ip += ZSTDv07_blockHeaderSize;
3814         remainingSize -= ZSTDv07_blockHeaderSize;
3815         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3816 
3817         switch(blockProperties.blockType)
3818         {
3819         case bt_compressed:
3820             decodedSize = ZSTDv07_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3821             break;
3822         case bt_raw :
3823             decodedSize = ZSTDv07_copyRawBlock(op, oend-op, ip, cBlockSize);
3824             break;
3825         case bt_rle :
3826             decodedSize = ZSTDv07_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
3827             break;
3828         case bt_end :
3829             /* end of frame */
3830             if (remainingSize) return ERROR(srcSize_wrong);
3831             decodedSize = 0;
3832             break;
3833         default:
3834             return ERROR(GENERIC);   /* impossible */
3835         }
3836         if (blockProperties.blockType == bt_end) break;   /* bt_end */
3837 
3838         if (ZSTDv07_isError(decodedSize)) return decodedSize;
3839         if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
3840         op += decodedSize;
3841         ip += cBlockSize;
3842         remainingSize -= cBlockSize;
3843     }
3844 
3845     return op-ostart;
3846 }
3847 
3848 
3849 /*! ZSTDv07_decompress_usingPreparedDCtx() :
3850 *   Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
3851 *   It avoids reloading the dictionary each time.
3852 *   `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict().
3853 *   Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
3854 size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* refDCtx,
3855                                          void* dst, size_t dstCapacity,
3856                                    const void* src, size_t srcSize)
3857 {
3858     ZSTDv07_copyDCtx(dctx, refDCtx);
3859     ZSTDv07_checkContinuity(dctx, dst);
3860     return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3861 }
3862 
3863 
3864 size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx* dctx,
3865                                  void* dst, size_t dstCapacity,
3866                                  const void* src, size_t srcSize,
3867                                  const void* dict, size_t dictSize)
3868 {
3869     ZSTDv07_decompressBegin_usingDict(dctx, dict, dictSize);
3870     ZSTDv07_checkContinuity(dctx, dst);
3871     return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3872 }
3873 
3874 
3875 size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3876 {
3877     return ZSTDv07_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3878 }
3879 
3880 
3881 size_t ZSTDv07_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3882 {
3883 #if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1)
3884     size_t regenSize;
3885     ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx();
3886     if (dctx==NULL) return ERROR(memory_allocation);
3887     regenSize = ZSTDv07_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3888     ZSTDv07_freeDCtx(dctx);
3889     return regenSize;
3890 #else   /* stack mode */
3891     ZSTDv07_DCtx dctx;
3892     return ZSTDv07_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3893 #endif
3894 }
3895 
3896 size_t ZSTDv07_findFrameCompressedSize(const void* src, size_t srcSize)
3897 {
3898     const BYTE* ip = (const BYTE*)src;
3899     size_t remainingSize = srcSize;
3900 
3901     /* check */
3902     if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3903 
3904     /* Frame Header */
3905     {   size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3906         if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3907         if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) return ERROR(prefix_unknown);
3908         if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3909         ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3910     }
3911 
3912     /* Loop on each block */
3913     while (1) {
3914         blockProperties_t blockProperties;
3915         size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, remainingSize, &blockProperties);
3916         if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3917 
3918         ip += ZSTDv07_blockHeaderSize;
3919         remainingSize -= ZSTDv07_blockHeaderSize;
3920 
3921         if (blockProperties.blockType == bt_end) break;
3922 
3923         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3924 
3925         ip += cBlockSize;
3926         remainingSize -= cBlockSize;
3927     }
3928 
3929     return ip - (const BYTE*)src;
3930 }
3931 
3932 /*_******************************
3933 *  Streaming Decompression API
3934 ********************************/
3935 size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx)
3936 {
3937     return dctx->expected;
3938 }
3939 
3940 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx)
3941 {
3942     return dctx->stage == ZSTDds_skipFrame;
3943 }
3944 
3945 /** ZSTDv07_decompressContinue() :
3946 *   @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
3947 *             or an error code, which can be tested using ZSTDv07_isError() */
3948 size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3949 {
3950     /* Sanity check */
3951     if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3952     if (dstCapacity) ZSTDv07_checkContinuity(dctx, dst);
3953 
3954     switch (dctx->stage)
3955     {
3956     case ZSTDds_getFrameHeaderSize :
3957         if (srcSize != ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);   /* impossible */
3958         if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3959             memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
3960             dctx->expected = ZSTDv07_skippableHeaderSize - ZSTDv07_frameHeaderSize_min; /* magic number + skippable frame length */
3961             dctx->stage = ZSTDds_decodeSkippableHeader;
3962             return 0;
3963         }
3964         dctx->headerSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3965         if (ZSTDv07_isError(dctx->headerSize)) return dctx->headerSize;
3966         memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
3967         if (dctx->headerSize > ZSTDv07_frameHeaderSize_min) {
3968             dctx->expected = dctx->headerSize - ZSTDv07_frameHeaderSize_min;
3969             dctx->stage = ZSTDds_decodeFrameHeader;
3970             return 0;
3971         }
3972         dctx->expected = 0;   /* not necessary to copy more */
3973 	/* fall-through */
3974     case ZSTDds_decodeFrameHeader:
3975         {   size_t result;
3976             memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
3977             result = ZSTDv07_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
3978             if (ZSTDv07_isError(result)) return result;
3979             dctx->expected = ZSTDv07_blockHeaderSize;
3980             dctx->stage = ZSTDds_decodeBlockHeader;
3981             return 0;
3982         }
3983     case ZSTDds_decodeBlockHeader:
3984         {   blockProperties_t bp;
3985             size_t const cBlockSize = ZSTDv07_getcBlockSize(src, ZSTDv07_blockHeaderSize, &bp);
3986             if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3987             if (bp.blockType == bt_end) {
3988                 if (dctx->fParams.checksumFlag) {
3989                     U64 const h64 = XXH64_digest(&dctx->xxhState);
3990                     U32 const h32 = (U32)(h64>>11) & ((1<<22)-1);
3991                     const BYTE* const ip = (const BYTE*)src;
3992                     U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16);
3993                     if (check32 != h32) return ERROR(checksum_wrong);
3994                 }
3995                 dctx->expected = 0;
3996                 dctx->stage = ZSTDds_getFrameHeaderSize;
3997             } else {
3998                 dctx->expected = cBlockSize;
3999                 dctx->bType = bp.blockType;
4000                 dctx->stage = ZSTDds_decompressBlock;
4001             }
4002             return 0;
4003         }
4004     case ZSTDds_decompressBlock:
4005         {   size_t rSize;
4006             switch(dctx->bType)
4007             {
4008             case bt_compressed:
4009                 rSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
4010                 break;
4011             case bt_raw :
4012                 rSize = ZSTDv07_copyRawBlock(dst, dstCapacity, src, srcSize);
4013                 break;
4014             case bt_rle :
4015                 return ERROR(GENERIC);   /* not yet handled */
4016                 break;
4017             case bt_end :   /* should never happen (filtered at phase 1) */
4018                 rSize = 0;
4019                 break;
4020             default:
4021                 return ERROR(GENERIC);   /* impossible */
4022             }
4023             dctx->stage = ZSTDds_decodeBlockHeader;
4024             dctx->expected = ZSTDv07_blockHeaderSize;
4025             dctx->previousDstEnd = (char*)dst + rSize;
4026             if (ZSTDv07_isError(rSize)) return rSize;
4027             if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
4028             return rSize;
4029         }
4030     case ZSTDds_decodeSkippableHeader:
4031         {   memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
4032             dctx->expected = MEM_readLE32(dctx->headerBuffer + 4);
4033             dctx->stage = ZSTDds_skipFrame;
4034             return 0;
4035         }
4036     case ZSTDds_skipFrame:
4037         {   dctx->expected = 0;
4038             dctx->stage = ZSTDds_getFrameHeaderSize;
4039             return 0;
4040         }
4041     default:
4042         return ERROR(GENERIC);   /* impossible */
4043     }
4044 }
4045 
4046 
4047 static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4048 {
4049     dctx->dictEnd = dctx->previousDstEnd;
4050     dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
4051     dctx->base = dict;
4052     dctx->previousDstEnd = (const char*)dict + dictSize;
4053     return 0;
4054 }
4055 
4056 static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx* dctx, const void* const dict, size_t const dictSize)
4057 {
4058     const BYTE* dictPtr = (const BYTE*)dict;
4059     const BYTE* const dictEnd = dictPtr + dictSize;
4060 
4061     {   size_t const hSize = HUFv07_readDTableX4(dctx->hufTable, dict, dictSize);
4062         if (HUFv07_isError(hSize)) return ERROR(dictionary_corrupted);
4063         dictPtr += hSize;
4064     }
4065 
4066     {   short offcodeNCount[MaxOff+1];
4067         U32 offcodeMaxValue=MaxOff, offcodeLog;
4068         size_t const offcodeHeaderSize = FSEv07_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
4069         if (FSEv07_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
4070         if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
4071         { size_t const errorCode = FSEv07_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
4072           if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4073         dictPtr += offcodeHeaderSize;
4074     }
4075 
4076     {   short matchlengthNCount[MaxML+1];
4077         unsigned matchlengthMaxValue = MaxML, matchlengthLog;
4078         size_t const matchlengthHeaderSize = FSEv07_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
4079         if (FSEv07_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
4080         if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
4081         { size_t const errorCode = FSEv07_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
4082           if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4083         dictPtr += matchlengthHeaderSize;
4084     }
4085 
4086     {   short litlengthNCount[MaxLL+1];
4087         unsigned litlengthMaxValue = MaxLL, litlengthLog;
4088         size_t const litlengthHeaderSize = FSEv07_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
4089         if (FSEv07_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
4090         if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
4091         { size_t const errorCode = FSEv07_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
4092           if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4093         dictPtr += litlengthHeaderSize;
4094     }
4095 
4096     if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
4097     dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] == 0 || dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
4098     dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] == 0 || dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
4099     dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] == 0 || dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
4100     dictPtr += 12;
4101 
4102     dctx->litEntropy = dctx->fseEntropy = 1;
4103     return dictPtr - (const BYTE*)dict;
4104 }
4105 
4106 static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4107 {
4108     if (dictSize < 8) return ZSTDv07_refDictContent(dctx, dict, dictSize);
4109     {   U32 const magic = MEM_readLE32(dict);
4110         if (magic != ZSTDv07_DICT_MAGIC) {
4111             return ZSTDv07_refDictContent(dctx, dict, dictSize);   /* pure content mode */
4112     }   }
4113     dctx->dictID = MEM_readLE32((const char*)dict + 4);
4114 
4115     /* load entropy tables */
4116     dict = (const char*)dict + 8;
4117     dictSize -= 8;
4118     {   size_t const eSize = ZSTDv07_loadEntropy(dctx, dict, dictSize);
4119         if (ZSTDv07_isError(eSize)) return ERROR(dictionary_corrupted);
4120         dict = (const char*)dict + eSize;
4121         dictSize -= eSize;
4122     }
4123 
4124     /* reference dictionary content */
4125     return ZSTDv07_refDictContent(dctx, dict, dictSize);
4126 }
4127 
4128 
4129 size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4130 {
4131     { size_t const errorCode = ZSTDv07_decompressBegin(dctx);
4132       if (ZSTDv07_isError(errorCode)) return errorCode; }
4133 
4134     if (dict && dictSize) {
4135         size_t const errorCode = ZSTDv07_decompress_insertDictionary(dctx, dict, dictSize);
4136         if (ZSTDv07_isError(errorCode)) return ERROR(dictionary_corrupted);
4137     }
4138 
4139     return 0;
4140 }
4141 
4142 
4143 struct ZSTDv07_DDict_s {
4144     void* dict;
4145     size_t dictSize;
4146     ZSTDv07_DCtx* refContext;
4147 };  /* typedef'd tp ZSTDv07_CDict within zstd.h */
4148 
4149 ZSTDv07_DDict* ZSTDv07_createDDict_advanced(const void* dict, size_t dictSize, ZSTDv07_customMem customMem)
4150 {
4151     if (!customMem.customAlloc && !customMem.customFree)
4152         customMem = defaultCustomMem;
4153 
4154     if (!customMem.customAlloc || !customMem.customFree)
4155         return NULL;
4156 
4157     {   ZSTDv07_DDict* const ddict = (ZSTDv07_DDict*) customMem.customAlloc(customMem.opaque, sizeof(*ddict));
4158         void* const dictContent = customMem.customAlloc(customMem.opaque, dictSize);
4159         ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx_advanced(customMem);
4160 
4161         if (!dictContent || !ddict || !dctx) {
4162             customMem.customFree(customMem.opaque, dictContent);
4163             customMem.customFree(customMem.opaque, ddict);
4164             customMem.customFree(customMem.opaque, dctx);
4165             return NULL;
4166         }
4167 
4168         memcpy(dictContent, dict, dictSize);
4169         {   size_t const errorCode = ZSTDv07_decompressBegin_usingDict(dctx, dictContent, dictSize);
4170             if (ZSTDv07_isError(errorCode)) {
4171                 customMem.customFree(customMem.opaque, dictContent);
4172                 customMem.customFree(customMem.opaque, ddict);
4173                 customMem.customFree(customMem.opaque, dctx);
4174                 return NULL;
4175         }   }
4176 
4177         ddict->dict = dictContent;
4178         ddict->dictSize = dictSize;
4179         ddict->refContext = dctx;
4180         return ddict;
4181     }
4182 }
4183 
4184 /*! ZSTDv07_createDDict() :
4185 *   Create a digested dictionary, ready to start decompression without startup delay.
4186 *   `dict` can be released after `ZSTDv07_DDict` creation */
4187 ZSTDv07_DDict* ZSTDv07_createDDict(const void* dict, size_t dictSize)
4188 {
4189     ZSTDv07_customMem const allocator = { NULL, NULL, NULL };
4190     return ZSTDv07_createDDict_advanced(dict, dictSize, allocator);
4191 }
4192 
4193 size_t ZSTDv07_freeDDict(ZSTDv07_DDict* ddict)
4194 {
4195     ZSTDv07_freeFunction const cFree = ddict->refContext->customMem.customFree;
4196     void* const opaque = ddict->refContext->customMem.opaque;
4197     ZSTDv07_freeDCtx(ddict->refContext);
4198     cFree(opaque, ddict->dict);
4199     cFree(opaque, ddict);
4200     return 0;
4201 }
4202 
4203 /*! ZSTDv07_decompress_usingDDict() :
4204 *   Decompression using a pre-digested Dictionary
4205 *   Use dictionary without significant overhead. */
4206 ZSTDLIBv07_API size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx* dctx,
4207                                            void* dst, size_t dstCapacity,
4208                                      const void* src, size_t srcSize,
4209                                      const ZSTDv07_DDict* ddict)
4210 {
4211     return ZSTDv07_decompress_usingPreparedDCtx(dctx, ddict->refContext,
4212                                            dst, dstCapacity,
4213                                            src, srcSize);
4214 }
4215 /*
4216     Buffered version of Zstd compression library
4217     Copyright (C) 2015-2016, Yann Collet.
4218 
4219     BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
4220 
4221     Redistribution and use in source and binary forms, with or without
4222     modification, are permitted provided that the following conditions are
4223     met:
4224     * Redistributions of source code must retain the above copyright
4225     notice, this list of conditions and the following disclaimer.
4226     * Redistributions in binary form must reproduce the above
4227     copyright notice, this list of conditions and the following disclaimer
4228     in the documentation and/or other materials provided with the
4229     distribution.
4230     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4231     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
4232     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
4233     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
4234     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4235     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
4236     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
4237     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
4238     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
4239     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
4240     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4241 
4242     You can contact the author at :
4243     - zstd homepage : http://www.zstd.net/
4244 */
4245 
4246 
4247 
4248 /*-***************************************************************************
4249 *  Streaming decompression howto
4250 *
4251 *  A ZBUFFv07_DCtx object is required to track streaming operations.
4252 *  Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources.
4253 *  Use ZBUFFv07_decompressInit() to start a new decompression operation,
4254 *   or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary.
4255 *  Note that ZBUFFv07_DCtx objects can be re-init multiple times.
4256 *
4257 *  Use ZBUFFv07_decompressContinue() repetitively to consume your input.
4258 *  *srcSizePtr and *dstCapacityPtr can be any size.
4259 *  The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
4260 *  Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
4261 *  The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
4262 *  @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
4263 *            or 0 when a frame is completely decoded,
4264 *            or an error code, which can be tested using ZBUFFv07_isError().
4265 *
4266 *  Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize()
4267 *  output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
4268 *  input  : ZBUFFv07_recommendedDInSize == 128KB + 3;
4269 *           just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
4270 * *******************************************************************************/
4271 
4272 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
4273                ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv07_dStage;
4274 
4275 /* *** Resource management *** */
4276 struct ZBUFFv07_DCtx_s {
4277     ZSTDv07_DCtx* zd;
4278     ZSTDv07_frameParams fParams;
4279     ZBUFFv07_dStage stage;
4280     char*  inBuff;
4281     size_t inBuffSize;
4282     size_t inPos;
4283     char*  outBuff;
4284     size_t outBuffSize;
4285     size_t outStart;
4286     size_t outEnd;
4287     size_t blockSize;
4288     BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
4289     size_t lhSize;
4290     ZSTDv07_customMem customMem;
4291 };   /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */
4292 
4293 ZSTDLIBv07_API ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem);
4294 
4295 ZBUFFv07_DCtx* ZBUFFv07_createDCtx(void)
4296 {
4297     return ZBUFFv07_createDCtx_advanced(defaultCustomMem);
4298 }
4299 
4300 ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem)
4301 {
4302     ZBUFFv07_DCtx* zbd;
4303 
4304     if (!customMem.customAlloc && !customMem.customFree)
4305         customMem = defaultCustomMem;
4306 
4307     if (!customMem.customAlloc || !customMem.customFree)
4308         return NULL;
4309 
4310     zbd = (ZBUFFv07_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFFv07_DCtx));
4311     if (zbd==NULL) return NULL;
4312     memset(zbd, 0, sizeof(ZBUFFv07_DCtx));
4313     memcpy(&zbd->customMem, &customMem, sizeof(ZSTDv07_customMem));
4314     zbd->zd = ZSTDv07_createDCtx_advanced(customMem);
4315     if (zbd->zd == NULL) { ZBUFFv07_freeDCtx(zbd); return NULL; }
4316     zbd->stage = ZBUFFds_init;
4317     return zbd;
4318 }
4319 
4320 size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx* zbd)
4321 {
4322     if (zbd==NULL) return 0;   /* support free on null */
4323     ZSTDv07_freeDCtx(zbd->zd);
4324     if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4325     if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4326     zbd->customMem.customFree(zbd->customMem.opaque, zbd);
4327     return 0;
4328 }
4329 
4330 
4331 /* *** Initialization *** */
4332 
4333 size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx* zbd, const void* dict, size_t dictSize)
4334 {
4335     zbd->stage = ZBUFFds_loadHeader;
4336     zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
4337     return ZSTDv07_decompressBegin_usingDict(zbd->zd, dict, dictSize);
4338 }
4339 
4340 size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx* zbd)
4341 {
4342     return ZBUFFv07_decompressInitDictionary(zbd, NULL, 0);
4343 }
4344 
4345 
4346 /* internal util function */
4347 MEM_STATIC size_t ZBUFFv07_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
4348 {
4349     size_t const length = MIN(dstCapacity, srcSize);
4350     memcpy(dst, src, length);
4351     return length;
4352 }
4353 
4354 
4355 /* *** Decompression *** */
4356 
4357 size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx* zbd,
4358                                 void* dst, size_t* dstCapacityPtr,
4359                           const void* src, size_t* srcSizePtr)
4360 {
4361     const char* const istart = (const char*)src;
4362     const char* const iend = istart + *srcSizePtr;
4363     const char* ip = istart;
4364     char* const ostart = (char*)dst;
4365     char* const oend = ostart + *dstCapacityPtr;
4366     char* op = ostart;
4367     U32 notDone = 1;
4368 
4369     while (notDone) {
4370         switch(zbd->stage)
4371         {
4372         case ZBUFFds_init :
4373             return ERROR(init_missing);
4374 
4375         case ZBUFFds_loadHeader :
4376             {   size_t const hSize = ZSTDv07_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
4377                 if (ZSTDv07_isError(hSize)) return hSize;
4378                 if (hSize != 0) {
4379                     size_t const toLoad = hSize - zbd->lhSize;   /* if hSize!=0, hSize > zbd->lhSize */
4380                     if (toLoad > (size_t)(iend-ip)) {   /* not enough input to load full header */
4381                         memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
4382                         zbd->lhSize += iend-ip;
4383                         *dstCapacityPtr = 0;
4384                         return (hSize - zbd->lhSize) + ZSTDv07_blockHeaderSize;   /* remaining header bytes + next block header */
4385                     }
4386                     memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
4387                     break;
4388             }   }
4389 
4390             /* Consume header */
4391             {   size_t const h1Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);  /* == ZSTDv07_frameHeaderSize_min */
4392                 size_t const h1Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4393                 if (ZSTDv07_isError(h1Result)) return h1Result;
4394                 if (h1Size < zbd->lhSize) {   /* long header */
4395                     size_t const h2Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4396                     size_t const h2Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4397                     if (ZSTDv07_isError(h2Result)) return h2Result;
4398             }   }
4399 
4400             zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN);
4401 
4402             /* Frame header instruct buffer sizes */
4403             {   size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX);
4404                 zbd->blockSize = blockSize;
4405                 if (zbd->inBuffSize < blockSize) {
4406                     zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4407                     zbd->inBuffSize = blockSize;
4408                     zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize);
4409                     if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4410                 }
4411                 {   size_t const neededOutSize = zbd->fParams.windowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
4412                     if (zbd->outBuffSize < neededOutSize) {
4413                         zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4414                         zbd->outBuffSize = neededOutSize;
4415                         zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize);
4416                         if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4417             }   }   }
4418             zbd->stage = ZBUFFds_read;
4419             /* pass-through */
4420 	    /* fall-through */
4421         case ZBUFFds_read:
4422             {   size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4423                 if (neededInSize==0) {  /* end of frame */
4424                     zbd->stage = ZBUFFds_init;
4425                     notDone = 0;
4426                     break;
4427                 }
4428                 if ((size_t)(iend-ip) >= neededInSize) {  /* decode directly from src */
4429                     const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4430                     size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4431                         zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart),
4432                         ip, neededInSize);
4433                     if (ZSTDv07_isError(decodedSize)) return decodedSize;
4434                     ip += neededInSize;
4435                     if (!decodedSize && !isSkipFrame) break;   /* this was just a header */
4436                     zbd->outEnd = zbd->outStart +  decodedSize;
4437                     zbd->stage = ZBUFFds_flush;
4438                     break;
4439                 }
4440                 if (ip==iend) { notDone = 0; break; }   /* no more input */
4441                 zbd->stage = ZBUFFds_load;
4442             }
4443 	    /* fall-through */
4444         case ZBUFFds_load:
4445             {   size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4446                 size_t const toLoad = neededInSize - zbd->inPos;   /* should always be <= remaining space within inBuff */
4447                 size_t loadedSize;
4448                 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected);   /* should never happen */
4449                 loadedSize = ZBUFFv07_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4450                 ip += loadedSize;
4451                 zbd->inPos += loadedSize;
4452                 if (loadedSize < toLoad) { notDone = 0; break; }   /* not enough input, wait for more */
4453 
4454                 /* decode loaded input */
4455                 {  const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4456                    size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4457                         zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4458                         zbd->inBuff, neededInSize);
4459                     if (ZSTDv07_isError(decodedSize)) return decodedSize;
4460                     zbd->inPos = 0;   /* input is consumed */
4461                     if (!decodedSize && !isSkipFrame) { zbd->stage = ZBUFFds_read; break; }   /* this was just a header */
4462                     zbd->outEnd = zbd->outStart +  decodedSize;
4463                     zbd->stage = ZBUFFds_flush;
4464                     /* break; */
4465                     /* pass-through */
4466                 }
4467 	    }
4468 	    /* fall-through */
4469         case ZBUFFds_flush:
4470             {   size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4471                 size_t const flushedSize = ZBUFFv07_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4472                 op += flushedSize;
4473                 zbd->outStart += flushedSize;
4474                 if (flushedSize == toFlushSize) {
4475                     zbd->stage = ZBUFFds_read;
4476                     if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4477                         zbd->outStart = zbd->outEnd = 0;
4478                     break;
4479                 }
4480                 /* cannot flush everything */
4481                 notDone = 0;
4482                 break;
4483             }
4484         default: return ERROR(GENERIC);   /* impossible */
4485     }   }
4486 
4487     /* result */
4488     *srcSizePtr = ip-istart;
4489     *dstCapacityPtr = op-ostart;
4490     {   size_t nextSrcSizeHint = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4491         nextSrcSizeHint -= zbd->inPos;   /* already loaded*/
4492         return nextSrcSizeHint;
4493     }
4494 }
4495 
4496 
4497 
4498 /* *************************************
4499 *  Tool functions
4500 ***************************************/
4501 size_t ZBUFFv07_recommendedDInSize(void)  { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + ZSTDv07_blockHeaderSize /* block header size*/ ; }
4502 size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX; }
4503