2 * Copyright (c) Yann Collet, Meta Platforms, Inc. and affiliates.
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.
13 #include <stddef.h> /* size_t, ptrdiff_t */
14 #include <string.h> /* memcpy */
15 #include <stdlib.h> /* malloc, free, qsort */
17 #ifndef XXH_STATIC_LINKING_ONLY
18 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
20 #include "../common/xxhash.h" /* XXH64_* */
23 #define FSEv07_STATIC_LINKING_ONLY /* FSEv07_MIN_TABLELOG */
24 #define HUFv07_STATIC_LINKING_ONLY /* HUFv07_TABLELOG_ABSOLUTEMAX */
25 #define ZSTDv07_STATIC_LINKING_ONLY
27 #include "../common/error_private.h"
30 #ifdef ZSTDv07_STATIC_LINKING_ONLY
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 * ==================================================================================== */
40 #define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U
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
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 */
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;
70 /*--- Advanced Decompression functions ---*/
72 /*! ZSTDv07_estimateDCtxSize() :
73 * Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */
74 ZSTDLIBv07_API size_t ZSTDv07_estimateDCtxSize(void);
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);
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);
85 /* ******************************************************************
86 * Buffer-less streaming functions (synchronous mode)
87 ********************************************************************/
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);
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);
97 Buffer-less streaming decompression (synchronous mode)
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.
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()
114 Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().
115 Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().
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.
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.
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.
131 A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.
132 Context can then be reset to start a new decompression.
135 == Special case : skippable frames ==
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.
148 /* **************************************
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.
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.
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 */
179 #endif /* ZSTDv07_STATIC_LINKING_ONLY */
182 /* ******************************************************************
184 low-level memory access routines
185 Copyright (C) 2013-2015, Yann Collet.
187 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
189 Redistribution and use in source and binary forms, with or without
190 modification, are permitted provided that the following conditions are
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
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.
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 ****************************************************************** */
219 #if defined (__cplusplus)
223 /*-****************************************
225 ******************************************/
226 #if defined(_MSC_VER) /* Visual Studio */
227 # include <stdlib.h> /* _byteswap_ulong */
228 # include <intrin.h> /* _byteswap_* */
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
237 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
241 /*-**************************************************************
243 *****************************************************************/
244 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
246 # include <inttypes.h>
248 # include <stdint.h> /* intptr_t */
250 typedef uint8_t BYTE;
251 typedef uint16_t U16;
253 typedef uint32_t U32;
255 typedef uint64_t U64;
258 typedef unsigned char BYTE;
259 typedef unsigned short U16;
260 typedef signed short S16;
261 typedef unsigned int U32;
262 typedef signed int S32;
263 typedef unsigned long long U64;
264 typedef signed long long S64;
268 /*-**************************************************************
270 *****************************************************************/
272 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
273 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
275 MEM_STATIC unsigned MEM_isLittleEndian(void)
277 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
281 MEM_STATIC U16 MEM_read16(const void* memPtr)
283 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
286 MEM_STATIC U32 MEM_read32(const void* memPtr)
288 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
291 MEM_STATIC U64 MEM_read64(const void* memPtr)
293 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
296 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
298 memcpy(memPtr, &value, sizeof(value));
301 MEM_STATIC U32 MEM_swap32(U32 in)
303 #if defined(_MSC_VER) /* Visual Studio */
304 return _byteswap_ulong(in);
305 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
306 return __builtin_bswap32(in);
308 return ((in << 24) & 0xff000000 ) |
309 ((in << 8) & 0x00ff0000 ) |
310 ((in >> 8) & 0x0000ff00 ) |
311 ((in >> 24) & 0x000000ff );
315 MEM_STATIC U64 MEM_swap64(U64 in)
317 #if defined(_MSC_VER) /* Visual Studio */
318 return _byteswap_uint64(in);
319 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
320 return __builtin_bswap64(in);
322 return ((in << 56) & 0xff00000000000000ULL) |
323 ((in << 40) & 0x00ff000000000000ULL) |
324 ((in << 24) & 0x0000ff0000000000ULL) |
325 ((in << 8) & 0x000000ff00000000ULL) |
326 ((in >> 8) & 0x00000000ff000000ULL) |
327 ((in >> 24) & 0x0000000000ff0000ULL) |
328 ((in >> 40) & 0x000000000000ff00ULL) |
329 ((in >> 56) & 0x00000000000000ffULL);
334 /*=== Little endian r/w ===*/
336 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
338 if (MEM_isLittleEndian())
339 return MEM_read16(memPtr);
341 const BYTE* p = (const BYTE*)memPtr;
342 return (U16)(p[0] + (p[1]<<8));
346 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
348 if (MEM_isLittleEndian()) {
349 MEM_write16(memPtr, val);
351 BYTE* p = (BYTE*)memPtr;
353 p[1] = (BYTE)(val>>8);
357 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
359 if (MEM_isLittleEndian())
360 return MEM_read32(memPtr);
362 return MEM_swap32(MEM_read32(memPtr));
366 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
368 if (MEM_isLittleEndian())
369 return MEM_read64(memPtr);
371 return MEM_swap64(MEM_read64(memPtr));
374 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
377 return (size_t)MEM_readLE32(memPtr);
379 return (size_t)MEM_readLE64(memPtr);
384 #if defined (__cplusplus)
388 #endif /* MEM_H_MODULE */
389 /* ******************************************************************
392 header file (to include)
393 Copyright (C) 2013-2016, Yann Collet.
395 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
397 Redistribution and use in source and binary forms, with or without
398 modification, are permitted provided that the following conditions are
401 * Redistributions of source code must retain the above copyright
402 notice, this list of conditions and the following disclaimer.
403 * Redistributions in binary form must reproduce the above
404 copyright notice, this list of conditions and the following disclaimer
405 in the documentation and/or other materials provided with the
408 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
409 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
410 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
411 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
412 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
413 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
414 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
415 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
416 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
417 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
418 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
420 You can contact the author at :
421 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
422 ****************************************************************** */
423 #ifndef BITSTREAM_H_MODULE
424 #define BITSTREAM_H_MODULE
426 #if defined (__cplusplus)
432 * This API consists of small unitary functions, which must be inlined for best performance.
433 * Since link-time-optimization is not available for all compilers,
434 * these functions are defined into a .h to be included.
438 /*=========================================
440 =========================================*/
441 #if defined(__BMI__) && defined(__GNUC__)
442 # include <immintrin.h> /* support for bextr (experimental) */
445 /*-********************************************
446 * bitStream decoding API (read backward)
447 **********************************************/
451 unsigned bitsConsumed;
456 typedef enum { BITv07_DStream_unfinished = 0,
457 BITv07_DStream_endOfBuffer = 1,
458 BITv07_DStream_completed = 2,
459 BITv07_DStream_overflow = 3 } BITv07_DStream_status; /* result of BITv07_reloadDStream() */
460 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
462 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
463 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, unsigned nbBits);
464 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD);
465 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* bitD);
469 /*-****************************************
471 ******************************************/
472 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, unsigned nbBits);
473 /* faster, but works only if nbBits >= 1 */
477 /*-**************************************************************
479 ****************************************************************/
480 MEM_STATIC unsigned BITv07_highbit32 (U32 val)
482 # if defined(_MSC_VER) /* Visual */
484 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
485 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
486 return __builtin_clz (val) ^ 31;
487 # else /* Software version */
488 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 };
495 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
501 /*-********************************************************
503 **********************************************************/
504 /*! BITv07_initDStream() :
505 * Initialize a BITv07_DStream_t.
506 * `bitD` : a pointer to an already allocated BITv07_DStream_t structure.
507 * `srcSize` must be the *exact* size of the bitStream, in bytes.
508 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
510 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
512 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
514 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
515 bitD->start = (const char*)srcBuffer;
516 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
517 bitD->bitContainer = MEM_readLEST(bitD->ptr);
518 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
519 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
520 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
522 bitD->start = (const char*)srcBuffer;
523 bitD->ptr = bitD->start;
524 bitD->bitContainer = *(const BYTE*)(bitD->start);
527 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
528 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
529 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
530 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
531 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
532 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */
535 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
536 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
537 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
538 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
545 MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits)
547 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
548 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
551 /*! BITv07_lookBitsFast() :
552 * unsafe version; only works if nbBits >= 1 */
553 MEM_STATIC size_t BITv07_lookBitsFast(const BITv07_DStream_t* bitD, U32 nbBits)
555 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
556 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
559 MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits)
561 bitD->bitsConsumed += nbBits;
564 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits)
566 size_t const value = BITv07_lookBits(bitD, nbBits);
567 BITv07_skipBits(bitD, nbBits);
571 /*! BITv07_readBitsFast() :
572 * unsafe version; only works if nbBits >= 1 */
573 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, U32 nbBits)
575 size_t const value = BITv07_lookBitsFast(bitD, nbBits);
576 BITv07_skipBits(bitD, nbBits);
580 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD)
582 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */
583 return BITv07_DStream_overflow;
585 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
586 bitD->ptr -= bitD->bitsConsumed >> 3;
587 bitD->bitsConsumed &= 7;
588 bitD->bitContainer = MEM_readLEST(bitD->ptr);
589 return BITv07_DStream_unfinished;
591 if (bitD->ptr == bitD->start) {
592 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv07_DStream_endOfBuffer;
593 return BITv07_DStream_completed;
595 { U32 nbBytes = bitD->bitsConsumed >> 3;
596 BITv07_DStream_status result = BITv07_DStream_unfinished;
597 if (bitD->ptr - nbBytes < bitD->start) {
598 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
599 result = BITv07_DStream_endOfBuffer;
601 bitD->ptr -= nbBytes;
602 bitD->bitsConsumed -= nbBytes*8;
603 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
608 /*! BITv07_endOfDStream() :
609 * @return Tells if DStream has exactly reached its end (all bits consumed).
611 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* DStream)
613 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
616 #if defined (__cplusplus)
620 #endif /* BITSTREAM_H_MODULE */
621 /* ******************************************************************
622 FSE : Finite State Entropy codec
623 Public Prototypes declaration
624 Copyright (C) 2013-2016, Yann Collet.
626 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
628 Redistribution and use in source and binary forms, with or without
629 modification, are permitted provided that the following conditions are
632 * Redistributions of source code must retain the above copyright
633 notice, this list of conditions and the following disclaimer.
634 * Redistributions in binary form must reproduce the above
635 copyright notice, this list of conditions and the following disclaimer
636 in the documentation and/or other materials provided with the
639 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
640 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
641 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
642 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
643 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
644 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
645 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
646 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
647 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
648 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
649 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
651 You can contact the author at :
652 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
653 ****************************************************************** */
657 #if defined (__cplusplus)
663 /*-****************************************
664 * FSE simple functions
665 ******************************************/
667 /*! FSEv07_decompress():
668 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
669 into already allocated destination buffer 'dst', of size 'dstCapacity'.
670 @return : size of regenerated data (<= maxDstSize),
671 or an error code, which can be tested using FSEv07_isError() .
673 ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!
674 Why ? : making this distinction requires a header.
675 Header management is intentionally delegated to the user layer, which can better manage special cases.
677 size_t FSEv07_decompress(void* dst, size_t dstCapacity,
678 const void* cSrc, size_t cSrcSize);
681 /* Error Management */
682 unsigned FSEv07_isError(size_t code); /* tells if a return value is an error code */
683 const char* FSEv07_getErrorName(size_t code); /* provides error code string (useful for debugging) */
686 /*-*****************************************
688 ******************************************/
690 FSEv07_decompress() does the following:
691 1. read normalized counters with readNCount()
692 2. build decoding table 'DTable' from normalized counters
693 3. decode the data stream using decoding table 'DTable'
695 The following API allows targeting specific sub-functions for advanced tasks.
696 For example, it's possible to compress several blocks using the same 'CTable',
697 or to save and provide normalized distribution using external method.
701 /* *** DECOMPRESSION *** */
703 /*! FSEv07_readNCount():
704 Read compactly saved 'normalizedCounter' from 'rBuffer'.
705 @return : size read from 'rBuffer',
706 or an errorCode, which can be tested using FSEv07_isError().
707 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
708 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
710 /*! Constructor and Destructor of FSEv07_DTable.
711 Note that its size depends on 'tableLog' */
712 typedef unsigned FSEv07_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
713 FSEv07_DTable* FSEv07_createDTable(unsigned tableLog);
714 void FSEv07_freeDTable(FSEv07_DTable* dt);
716 /*! FSEv07_buildDTable():
717 Builds 'dt', which must be already allocated, using FSEv07_createDTable().
718 return : 0, or an errorCode, which can be tested using FSEv07_isError() */
719 size_t FSEv07_buildDTable (FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
721 /*! FSEv07_decompress_usingDTable():
722 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
723 into `dst` which must be already allocated.
724 @return : size of regenerated data (necessarily <= `dstCapacity`),
725 or an errorCode, which can be tested using FSEv07_isError() */
726 size_t FSEv07_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv07_DTable* dt);
731 (Note : these functions only decompress FSE-compressed blocks.
732 If block is uncompressed, use memcpy() instead
733 If block is a single repeated byte, use memset() instead )
735 The first step is to obtain the normalized frequencies of symbols.
736 This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().
737 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
738 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
739 or size the table to handle worst case situations (typically 256).
740 FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
741 The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.
742 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
743 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
745 The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.
746 This is performed by the function FSEv07_buildDTable().
747 The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().
748 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
750 `FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().
751 `cSrcSize` must be strictly correct, otherwise decompression will fail.
752 FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
753 If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)
757 #ifdef FSEv07_STATIC_LINKING_ONLY
760 /* *****************************************
762 *******************************************/
763 /* FSE buffer bounds */
764 #define FSEv07_NCOUNTBOUND 512
765 #define FSEv07_BLOCKBOUND(size) (size + (size>>7))
767 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
768 #define FSEv07_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
771 /* *****************************************
773 *******************************************/
774 size_t FSEv07_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
775 /**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
777 unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus);
778 /**< same as FSEv07_optimalTableLog(), which used `minus==2` */
780 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits);
781 /**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
783 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, unsigned char symbolValue);
784 /**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */
788 /* *****************************************
789 * FSE symbol decompression API
790 *******************************************/
794 const void* table; /* precise table may vary, depending on U16 */
798 static void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt);
800 static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
804 /* *****************************************
806 *******************************************/
807 static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
808 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
811 /* ====== Decompression ====== */
816 } FSEv07_DTableHeader; /* sizeof U32 */
820 unsigned short newState;
821 unsigned char symbol;
822 unsigned char nbBits;
823 } FSEv07_decode_t; /* size == U32 */
825 MEM_STATIC void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt)
827 const void* ptr = dt;
828 const FSEv07_DTableHeader* const DTableH = (const FSEv07_DTableHeader*)ptr;
829 DStatePtr->state = BITv07_readBits(bitD, DTableH->tableLog);
830 BITv07_reloadDStream(bitD);
831 DStatePtr->table = dt + 1;
834 MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr)
836 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
840 MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
842 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
843 U32 const nbBits = DInfo.nbBits;
844 size_t const lowBits = BITv07_readBits(bitD, nbBits);
845 DStatePtr->state = DInfo.newState + lowBits;
848 MEM_STATIC BYTE FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
850 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
851 U32 const nbBits = DInfo.nbBits;
852 BYTE const symbol = DInfo.symbol;
853 size_t const lowBits = BITv07_readBits(bitD, nbBits);
855 DStatePtr->state = DInfo.newState + lowBits;
859 /*! FSEv07_decodeSymbolFast() :
860 unsafe, only works if no symbol has a probability > 50% */
861 MEM_STATIC BYTE FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
863 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
864 U32 const nbBits = DInfo.nbBits;
865 BYTE const symbol = DInfo.symbol;
866 size_t const lowBits = BITv07_readBitsFast(bitD, nbBits);
868 DStatePtr->state = DInfo.newState + lowBits;
874 #ifndef FSEv07_COMMONDEFS_ONLY
876 /* **************************************************************
878 ****************************************************************/
880 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
881 * Increasing memory usage improves compression ratio
882 * Reduced memory usage can improve speed, due to cache effect
883 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
884 #define FSEv07_MAX_MEMORY_USAGE 14
885 #define FSEv07_DEFAULT_MEMORY_USAGE 13
887 /*!FSEv07_MAX_SYMBOL_VALUE :
888 * Maximum symbol value authorized.
889 * Required for proper stack allocation */
890 #define FSEv07_MAX_SYMBOL_VALUE 255
893 /* **************************************************************
894 * template functions type & suffix
895 ****************************************************************/
896 #define FSEv07_FUNCTION_TYPE BYTE
897 #define FSEv07_FUNCTION_EXTENSION
898 #define FSEv07_DECODE_TYPE FSEv07_decode_t
901 #endif /* !FSEv07_COMMONDEFS_ONLY */
904 /* ***************************************************************
906 *****************************************************************/
907 #define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2)
908 #define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)
909 #define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)
910 #define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)
911 #define FSEv07_MIN_TABLELOG 5
913 #define FSEv07_TABLELOG_ABSOLUTE_MAX 15
914 #if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX
915 # error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"
918 #define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
921 #endif /* FSEv07_STATIC_LINKING_ONLY */
924 #if defined (__cplusplus)
928 #endif /* FSEv07_H */
929 /* ******************************************************************
930 Huffman coder, part of New Generation Entropy library
932 Copyright (C) 2013-2016, Yann Collet.
934 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
936 Redistribution and use in source and binary forms, with or without
937 modification, are permitted provided that the following conditions are
940 * Redistributions of source code must retain the above copyright
941 notice, this list of conditions and the following disclaimer.
942 * Redistributions in binary form must reproduce the above
943 copyright notice, this list of conditions and the following disclaimer
944 in the documentation and/or other materials provided with the
947 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
948 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
949 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
950 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
951 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
952 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
953 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
954 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
955 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
956 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
957 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
959 You can contact the author at :
960 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
961 ****************************************************************** */
962 #ifndef HUFv07_H_298734234
963 #define HUFv07_H_298734234
965 #if defined (__cplusplus)
971 /* *** simple functions *** */
973 HUFv07_decompress() :
974 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
975 into already allocated buffer 'dst', of minimum size 'dstSize'.
976 `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
977 Note : in contrast with FSE, HUFv07_decompress can regenerate
978 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
979 because it knows size to regenerate.
980 @return : size of regenerated data (== dstSize),
981 or an error code, which can be tested using HUFv07_isError()
983 size_t HUFv07_decompress(void* dst, size_t dstSize,
984 const void* cSrc, size_t cSrcSize);
987 /* ****************************************
989 ******************************************/
990 #define HUFv07_BLOCKSIZE_MAX (128 * 1024)
992 /* Error Management */
993 unsigned HUFv07_isError(size_t code); /**< tells if a return value is an error code */
994 const char* HUFv07_getErrorName(size_t code); /**< provides error code string (useful for debugging) */
997 /* *** Advanced function *** */
1000 #ifdef HUFv07_STATIC_LINKING_ONLY
1003 /* *** Constants *** */
1004 #define HUFv07_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */
1005 #define HUFv07_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */
1006 #define HUFv07_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */
1007 #define HUFv07_SYMBOLVALUE_MAX 255
1008 #if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX)
1009 # error "HUFv07_TABLELOG_MAX is too large !"
1013 /* ****************************************
1015 ******************************************/
1016 /* HUF buffer bounds */
1017 #define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1019 /* static allocation of HUF's DTable */
1020 typedef U32 HUFv07_DTable;
1021 #define HUFv07_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog)))
1022 #define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1023 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
1024 #define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1025 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
1028 /* ****************************************
1029 * Advanced decompression functions
1030 ******************************************/
1031 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1032 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1034 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< decodes RLE and uncompressed */
1035 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 */
1036 size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1037 size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1039 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
1040 size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1041 size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1044 /* ****************************************
1046 ******************************************/
1048 The following API allows targeting specific sub-functions for advanced tasks.
1049 For example, it's possible to compress several blocks using the same 'CTable',
1050 or to save and regenerate 'CTable' using external methods.
1052 /* FSEv07_count() : find it within "fse.h" */
1054 /*! HUFv07_readStats() :
1055 Read compact Huffman tree, saved by HUFv07_writeCTable().
1056 `huffWeight` is destination buffer.
1057 @return : size read from `src` , or an error Code .
1058 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */
1059 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1060 U32* nbSymbolsPtr, U32* tableLogPtr,
1061 const void* src, size_t srcSize);
1065 HUFv07_decompress() does the following:
1066 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1067 2. build Huffman table from save, using HUFv07_readDTableXn()
1068 3. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable
1071 /** HUFv07_selectDecoder() :
1072 * Tells which decoder is likely to decode faster,
1073 * based on a set of pre-determined metrics.
1074 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
1075 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
1076 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize);
1078 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1079 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1081 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1082 size_t HUFv07_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1083 size_t HUFv07_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1086 /* single stream variants */
1087 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1088 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1090 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1091 size_t HUFv07_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1092 size_t HUFv07_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1095 #endif /* HUFv07_STATIC_LINKING_ONLY */
1098 #if defined (__cplusplus)
1102 #endif /* HUFv07_H_298734234 */
1104 Common functions of New Generation Entropy library
1105 Copyright (C) 2016, Yann Collet.
1107 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1109 Redistribution and use in source and binary forms, with or without
1110 modification, are permitted provided that the following conditions are
1113 * Redistributions of source code must retain the above copyright
1114 notice, this list of conditions and the following disclaimer.
1115 * Redistributions in binary form must reproduce the above
1116 copyright notice, this list of conditions and the following disclaimer
1117 in the documentation and/or other materials provided with the
1120 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1121 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1122 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1123 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1124 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1125 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1126 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1127 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1128 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1129 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1130 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1132 You can contact the author at :
1133 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1134 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1135 *************************************************************************** */
1139 /*-****************************************
1140 * FSE Error Management
1141 ******************************************/
1142 unsigned FSEv07_isError(size_t code) { return ERR_isError(code); }
1144 const char* FSEv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1147 /* **************************************************************
1148 * HUF Error Management
1149 ****************************************************************/
1150 unsigned HUFv07_isError(size_t code) { return ERR_isError(code); }
1152 const char* HUFv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1155 /*-**************************************************************
1156 * FSE NCount encoding-decoding
1157 ****************************************************************/
1158 static short FSEv07_abs(short a) { return (short)(a<0 ? -a : a); }
1160 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1161 const void* headerBuffer, size_t hbSize)
1163 const BYTE* const istart = (const BYTE*) headerBuffer;
1164 const BYTE* const iend = istart + hbSize;
1165 const BYTE* ip = istart;
1171 unsigned charnum = 0;
1174 if (hbSize < 4) return ERROR(srcSize_wrong);
1175 bitStream = MEM_readLE32(ip);
1176 nbBits = (bitStream & 0xF) + FSEv07_MIN_TABLELOG; /* extract tableLog */
1177 if (nbBits > FSEv07_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1180 *tableLogPtr = nbBits;
1181 remaining = (1<<nbBits)+1;
1182 threshold = 1<<nbBits;
1185 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1187 unsigned n0 = charnum;
1188 while ((bitStream & 0xFFFF) == 0xFFFF) {
1192 bitStream = MEM_readLE32(ip) >> bitCount;
1197 while ((bitStream & 3) == 3) {
1202 n0 += bitStream & 3;
1204 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1205 while (charnum < n0) normalizedCounter[charnum++] = 0;
1206 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1209 bitStream = MEM_readLE32(ip) >> bitCount;
1214 { short const max = (short)((2*threshold-1)-remaining);
1217 if ((bitStream & (threshold-1)) < (U32)max) {
1218 count = (short)(bitStream & (threshold-1));
1219 bitCount += nbBits-1;
1221 count = (short)(bitStream & (2*threshold-1));
1222 if (count >= threshold) count -= max;
1226 count--; /* extra accuracy */
1227 remaining -= FSEv07_abs(count);
1228 normalizedCounter[charnum++] = count;
1230 while (remaining < threshold) {
1235 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1239 bitCount -= (int)(8 * (iend - 4 - ip));
1242 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1243 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1244 if (remaining != 1) return ERROR(GENERIC);
1245 *maxSVPtr = charnum-1;
1247 ip += (bitCount+7)>>3;
1248 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1253 /*! HUFv07_readStats() :
1254 Read compact Huffman tree, saved by HUFv07_writeCTable().
1255 `huffWeight` is destination buffer.
1256 @return : size read from `src` , or an error Code .
1257 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() .
1259 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1260 U32* nbSymbolsPtr, U32* tableLogPtr,
1261 const void* src, size_t srcSize)
1264 const BYTE* ip = (const BYTE*) src;
1268 if (!srcSize) return ERROR(srcSize_wrong);
1270 /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */
1272 if (iSize >= 128) { /* special header */
1273 if (iSize >= (242)) { /* RLE */
1274 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1275 oSize = l[iSize-242];
1276 memset(huffWeight, 1, hwSize);
1279 else { /* Incompressible */
1280 oSize = iSize - 127;
1281 iSize = ((oSize+1)/2);
1282 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1283 if (oSize >= hwSize) return ERROR(corruption_detected);
1286 for (n=0; n<oSize; n+=2) {
1287 huffWeight[n] = ip[n/2] >> 4;
1288 huffWeight[n+1] = ip[n/2] & 15;
1290 else { /* header compressed with FSE (normal case) */
1291 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1292 oSize = FSEv07_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1293 if (FSEv07_isError(oSize)) return oSize;
1296 /* collect weight stats */
1297 memset(rankStats, 0, (HUFv07_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
1299 { U32 n; for (n=0; n<oSize; n++) {
1300 if (huffWeight[n] >= HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1301 rankStats[huffWeight[n]]++;
1302 weightTotal += (1 << huffWeight[n]) >> 1;
1304 if (weightTotal == 0) return ERROR(corruption_detected);
1306 /* get last non-null symbol weight (implied, total must be 2^n) */
1307 { U32 const tableLog = BITv07_highbit32(weightTotal) + 1;
1308 if (tableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1309 *tableLogPtr = tableLog;
1310 /* determine last weight */
1311 { U32 const total = 1 << tableLog;
1312 U32 const rest = total - weightTotal;
1313 U32 const verif = 1 << BITv07_highbit32(rest);
1314 U32 const lastWeight = BITv07_highbit32(rest) + 1;
1315 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1316 huffWeight[oSize] = (BYTE)lastWeight;
1317 rankStats[lastWeight]++;
1320 /* check tree construction validity */
1321 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1324 *nbSymbolsPtr = (U32)(oSize+1);
1327 /* ******************************************************************
1328 FSE : Finite State Entropy decoder
1329 Copyright (C) 2013-2015, Yann Collet.
1331 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1333 Redistribution and use in source and binary forms, with or without
1334 modification, are permitted provided that the following conditions are
1337 * Redistributions of source code must retain the above copyright
1338 notice, this list of conditions and the following disclaimer.
1339 * Redistributions in binary form must reproduce the above
1340 copyright notice, this list of conditions and the following disclaimer
1341 in the documentation and/or other materials provided with the
1344 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1345 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1346 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1347 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1348 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1349 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1350 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1351 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1352 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1353 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1354 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1356 You can contact the author at :
1357 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1358 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1359 ****************************************************************** */
1362 /* **************************************************************
1363 * Compiler specifics
1364 ****************************************************************/
1365 #ifdef _MSC_VER /* Visual Studio */
1366 # define FORCE_INLINE static __forceinline
1367 # include <intrin.h> /* For Visual 2005 */
1368 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1369 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1371 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1373 # define FORCE_INLINE static inline __attribute__((always_inline))
1375 # define FORCE_INLINE static inline
1378 # define FORCE_INLINE static
1379 # endif /* __STDC_VERSION__ */
1383 /* **************************************************************
1385 ****************************************************************/
1386 #define FSEv07_isError ERR_isError
1387 #define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1390 /* **************************************************************
1392 ****************************************************************/
1393 typedef U32 DTable_max_t[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG)];
1396 /* **************************************************************
1398 ****************************************************************/
1400 designed to be included
1401 for type-specific functions (template emulation in C)
1402 Objective is to write these functions only once, for improved maintenance
1406 #ifndef FSEv07_FUNCTION_EXTENSION
1407 # error "FSEv07_FUNCTION_EXTENSION must be defined"
1409 #ifndef FSEv07_FUNCTION_TYPE
1410 # error "FSEv07_FUNCTION_TYPE must be defined"
1413 /* Function names */
1414 #define FSEv07_CAT(X,Y) X##Y
1415 #define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y)
1416 #define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y)
1419 /* Function templates */
1420 FSEv07_DTable* FSEv07_createDTable (unsigned tableLog)
1422 if (tableLog > FSEv07_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv07_TABLELOG_ABSOLUTE_MAX;
1423 return (FSEv07_DTable*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1426 void FSEv07_freeDTable (FSEv07_DTable* dt)
1431 size_t FSEv07_buildDTable(FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1433 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1434 FSEv07_DECODE_TYPE* const tableDecode = (FSEv07_DECODE_TYPE*) (tdPtr);
1435 U16 symbolNext[FSEv07_MAX_SYMBOL_VALUE+1];
1437 U32 const maxSV1 = maxSymbolValue + 1;
1438 U32 const tableSize = 1 << tableLog;
1439 U32 highThreshold = tableSize-1;
1442 if (maxSymbolValue > FSEv07_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1443 if (tableLog > FSEv07_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1445 /* Init, lay down lowprob symbols */
1446 { FSEv07_DTableHeader DTableH;
1447 DTableH.tableLog = (U16)tableLog;
1448 DTableH.fastMode = 1;
1449 { S16 const largeLimit= (S16)(1 << (tableLog-1));
1451 for (s=0; s<maxSV1; s++) {
1452 if (normalizedCounter[s]==-1) {
1453 tableDecode[highThreshold--].symbol = (FSEv07_FUNCTION_TYPE)s;
1456 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1457 symbolNext[s] = normalizedCounter[s];
1459 memcpy(dt, &DTableH, sizeof(DTableH));
1462 /* Spread symbols */
1463 { U32 const tableMask = tableSize-1;
1464 U32 const step = FSEv07_TABLESTEP(tableSize);
1465 U32 s, position = 0;
1466 for (s=0; s<maxSV1; s++) {
1468 for (i=0; i<normalizedCounter[s]; i++) {
1469 tableDecode[position].symbol = (FSEv07_FUNCTION_TYPE)s;
1470 position = (position + step) & tableMask;
1471 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1474 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1477 /* Build Decoding table */
1479 for (u=0; u<tableSize; u++) {
1480 FSEv07_FUNCTION_TYPE const symbol = (FSEv07_FUNCTION_TYPE)(tableDecode[u].symbol);
1481 U16 nextState = symbolNext[symbol]++;
1482 tableDecode[u].nbBits = (BYTE) (tableLog - BITv07_highbit32 ((U32)nextState) );
1483 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1491 #ifndef FSEv07_COMMONDEFS_ONLY
1493 /*-*******************************************************
1494 * Decompression (Byte symbols)
1495 *********************************************************/
1496 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, BYTE symbolValue)
1499 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1500 void* dPtr = dt + 1;
1501 FSEv07_decode_t* const cell = (FSEv07_decode_t*)dPtr;
1503 DTableH->tableLog = 0;
1504 DTableH->fastMode = 0;
1507 cell->symbol = symbolValue;
1514 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits)
1517 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1518 void* dPtr = dt + 1;
1519 FSEv07_decode_t* const dinfo = (FSEv07_decode_t*)dPtr;
1520 const unsigned tableSize = 1 << nbBits;
1521 const unsigned tableMask = tableSize - 1;
1522 const unsigned maxSV1 = tableMask+1;
1526 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1528 /* Build Decoding Table */
1529 DTableH->tableLog = (U16)nbBits;
1530 DTableH->fastMode = 1;
1531 for (s=0; s<maxSV1; s++) {
1532 dinfo[s].newState = 0;
1533 dinfo[s].symbol = (BYTE)s;
1534 dinfo[s].nbBits = (BYTE)nbBits;
1540 FORCE_INLINE size_t FSEv07_decompress_usingDTable_generic(
1541 void* dst, size_t maxDstSize,
1542 const void* cSrc, size_t cSrcSize,
1543 const FSEv07_DTable* dt, const unsigned fast)
1545 BYTE* const ostart = (BYTE*) dst;
1547 BYTE* const omax = op + maxDstSize;
1548 BYTE* const olimit = omax-3;
1550 BITv07_DStream_t bitD;
1551 FSEv07_DState_t state1;
1552 FSEv07_DState_t state2;
1555 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1556 if (FSEv07_isError(errorCode)) return errorCode; }
1558 FSEv07_initDState(&state1, &bitD, dt);
1559 FSEv07_initDState(&state2, &bitD, dt);
1561 #define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1563 /* 4 symbols per loop */
1564 for ( ; (BITv07_reloadDStream(&bitD)==BITv07_DStream_unfinished) && (op<olimit) ; op+=4) {
1565 op[0] = FSEv07_GETSYMBOL(&state1);
1567 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1568 BITv07_reloadDStream(&bitD);
1570 op[1] = FSEv07_GETSYMBOL(&state2);
1572 if (FSEv07_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1573 { if (BITv07_reloadDStream(&bitD) > BITv07_DStream_unfinished) { op+=2; break; } }
1575 op[2] = FSEv07_GETSYMBOL(&state1);
1577 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1578 BITv07_reloadDStream(&bitD);
1580 op[3] = FSEv07_GETSYMBOL(&state2);
1584 /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1586 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1588 *op++ = FSEv07_GETSYMBOL(&state1);
1590 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1591 *op++ = FSEv07_GETSYMBOL(&state2);
1595 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1597 *op++ = FSEv07_GETSYMBOL(&state2);
1599 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1600 *op++ = FSEv07_GETSYMBOL(&state1);
1608 size_t FSEv07_decompress_usingDTable(void* dst, size_t originalSize,
1609 const void* cSrc, size_t cSrcSize,
1610 const FSEv07_DTable* dt)
1612 const void* ptr = dt;
1613 const FSEv07_DTableHeader* DTableH = (const FSEv07_DTableHeader*)ptr;
1614 const U32 fastMode = DTableH->fastMode;
1616 /* select fast mode (static) */
1617 if (fastMode) return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1618 return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1622 size_t FSEv07_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1624 const BYTE* const istart = (const BYTE*)cSrc;
1625 const BYTE* ip = istart;
1626 short counting[FSEv07_MAX_SYMBOL_VALUE+1];
1627 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1629 unsigned maxSymbolValue = FSEv07_MAX_SYMBOL_VALUE;
1631 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1633 /* normal FSE decoding mode */
1634 { size_t const NCountLength = FSEv07_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1635 if (FSEv07_isError(NCountLength)) return NCountLength;
1636 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1638 cSrcSize -= NCountLength;
1641 { size_t const errorCode = FSEv07_buildDTable (dt, counting, maxSymbolValue, tableLog);
1642 if (FSEv07_isError(errorCode)) return errorCode; }
1644 return FSEv07_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */
1649 #endif /* FSEv07_COMMONDEFS_ONLY */
1651 /* ******************************************************************
1652 Huffman decoder, part of New Generation Entropy library
1653 Copyright (C) 2013-2016, Yann Collet.
1655 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1657 Redistribution and use in source and binary forms, with or without
1658 modification, are permitted provided that the following conditions are
1661 * Redistributions of source code must retain the above copyright
1662 notice, this list of conditions and the following disclaimer.
1663 * Redistributions in binary form must reproduce the above
1664 copyright notice, this list of conditions and the following disclaimer
1665 in the documentation and/or other materials provided with the
1668 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1669 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1670 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1671 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1672 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1673 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1674 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1675 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1676 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1677 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1678 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1680 You can contact the author at :
1681 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1682 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1683 ****************************************************************** */
1685 /* **************************************************************
1686 * Compiler specifics
1687 ****************************************************************/
1688 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1689 /* inline is defined */
1690 #elif defined(_MSC_VER)
1691 # define inline __inline
1693 # define inline /* disable inline */
1697 #ifdef _MSC_VER /* Visual Studio */
1698 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1703 /* **************************************************************
1705 ****************************************************************/
1706 #define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1709 /*-***************************/
1710 /* generic DTableDesc */
1711 /*-***************************/
1713 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
1715 static DTableDesc HUFv07_getDTableDesc(const HUFv07_DTable* table)
1718 memcpy(&dtd, table, sizeof(dtd));
1723 /*-***************************/
1724 /* single-symbol decoding */
1725 /*-***************************/
1727 typedef struct { BYTE byte; BYTE nbBits; } HUFv07_DEltX2; /* single-symbol decoding */
1729 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
1731 BYTE huffWeight[HUFv07_SYMBOLVALUE_MAX + 1];
1732 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
1736 void* const dtPtr = DTable + 1;
1737 HUFv07_DEltX2* const dt = (HUFv07_DEltX2*)dtPtr;
1739 HUFv07_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUFv07_DTable));
1740 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
1742 iSize = HUFv07_readStats(huffWeight, HUFv07_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1743 if (HUFv07_isError(iSize)) return iSize;
1746 { DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1747 if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge); /* DTable too small, huffman tree cannot fit in */
1749 dtd.tableLog = (BYTE)tableLog;
1750 memcpy(DTable, &dtd, sizeof(dtd));
1754 { U32 n, nextRankStart = 0;
1755 for (n=1; n<tableLog+1; n++) {
1756 U32 current = nextRankStart;
1757 nextRankStart += (rankVal[n] << (n-1));
1758 rankVal[n] = current;
1763 for (n=0; n<nbSymbols; n++) {
1764 U32 const w = huffWeight[n];
1765 U32 const length = (1 << w) >> 1;
1768 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1769 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1771 rankVal[w] += length;
1778 static BYTE HUFv07_decodeSymbolX2(BITv07_DStream_t* Dstream, const HUFv07_DEltX2* dt, const U32 dtLog)
1780 size_t const val = BITv07_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1781 BYTE const c = dt[val].byte;
1782 BITv07_skipBits(Dstream, dt[val].nbBits);
1786 #define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1787 *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1789 #define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1790 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1791 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1793 #define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1795 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1797 static inline size_t HUFv07_decodeStreamX2(BYTE* p, BITv07_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv07_DEltX2* const dt, const U32 dtLog)
1799 BYTE* const pStart = p;
1801 /* up to 4 symbols at a time */
1802 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-4)) {
1803 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1804 HUFv07_DECODE_SYMBOLX2_1(p, bitDPtr);
1805 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1806 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1809 /* closer to the end */
1810 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd))
1811 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1813 /* no more data to retrieve from bitstream, hence no need to reload */
1815 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1820 static size_t HUFv07_decompress1X2_usingDTable_internal(
1821 void* dst, size_t dstSize,
1822 const void* cSrc, size_t cSrcSize,
1823 const HUFv07_DTable* DTable)
1825 BYTE* op = (BYTE*)dst;
1826 BYTE* const oend = op + dstSize;
1827 const void* dtPtr = DTable + 1;
1828 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1829 BITv07_DStream_t bitD;
1830 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1831 U32 const dtLog = dtd.tableLog;
1833 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
1834 if (HUFv07_isError(errorCode)) return errorCode; }
1836 HUFv07_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1839 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
1844 size_t HUFv07_decompress1X2_usingDTable(
1845 void* dst, size_t dstSize,
1846 const void* cSrc, size_t cSrcSize,
1847 const HUFv07_DTable* DTable)
1849 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1850 if (dtd.tableType != 0) return ERROR(GENERIC);
1851 return HUFv07_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
1854 size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1856 const BYTE* ip = (const BYTE*) cSrc;
1858 size_t const hSize = HUFv07_readDTableX2 (DCtx, cSrc, cSrcSize);
1859 if (HUFv07_isError(hSize)) return hSize;
1860 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1861 ip += hSize; cSrcSize -= hSize;
1863 return HUFv07_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
1866 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1868 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
1869 return HUFv07_decompress1X2_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
1873 static size_t HUFv07_decompress4X2_usingDTable_internal(
1874 void* dst, size_t dstSize,
1875 const void* cSrc, size_t cSrcSize,
1876 const HUFv07_DTable* DTable)
1879 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1881 { const BYTE* const istart = (const BYTE*) cSrc;
1882 BYTE* const ostart = (BYTE*) dst;
1883 BYTE* const oend = ostart + dstSize;
1884 const void* const dtPtr = DTable + 1;
1885 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1888 BITv07_DStream_t bitD1;
1889 BITv07_DStream_t bitD2;
1890 BITv07_DStream_t bitD3;
1891 BITv07_DStream_t bitD4;
1892 size_t const length1 = MEM_readLE16(istart);
1893 size_t const length2 = MEM_readLE16(istart+2);
1894 size_t const length3 = MEM_readLE16(istart+4);
1895 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
1896 const BYTE* const istart1 = istart + 6; /* jumpTable */
1897 const BYTE* const istart2 = istart1 + length1;
1898 const BYTE* const istart3 = istart2 + length2;
1899 const BYTE* const istart4 = istart3 + length3;
1900 const size_t segmentSize = (dstSize+3) / 4;
1901 BYTE* const opStart2 = ostart + segmentSize;
1902 BYTE* const opStart3 = opStart2 + segmentSize;
1903 BYTE* const opStart4 = opStart3 + segmentSize;
1905 BYTE* op2 = opStart2;
1906 BYTE* op3 = opStart3;
1907 BYTE* op4 = opStart4;
1909 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1910 U32 const dtLog = dtd.tableLog;
1912 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1913 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
1914 if (HUFv07_isError(errorCode)) return errorCode; }
1915 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
1916 if (HUFv07_isError(errorCode)) return errorCode; }
1917 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
1918 if (HUFv07_isError(errorCode)) return errorCode; }
1919 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
1920 if (HUFv07_isError(errorCode)) return errorCode; }
1922 /* 16-32 symbols per loop (4-8 symbols per stream) */
1923 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1924 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
1925 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
1926 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
1927 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
1928 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
1929 HUFv07_DECODE_SYMBOLX2_1(op1, &bitD1);
1930 HUFv07_DECODE_SYMBOLX2_1(op2, &bitD2);
1931 HUFv07_DECODE_SYMBOLX2_1(op3, &bitD3);
1932 HUFv07_DECODE_SYMBOLX2_1(op4, &bitD4);
1933 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
1934 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
1935 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
1936 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
1937 HUFv07_DECODE_SYMBOLX2_0(op1, &bitD1);
1938 HUFv07_DECODE_SYMBOLX2_0(op2, &bitD2);
1939 HUFv07_DECODE_SYMBOLX2_0(op3, &bitD3);
1940 HUFv07_DECODE_SYMBOLX2_0(op4, &bitD4);
1941 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1944 /* check corruption */
1945 if (op1 > opStart2) return ERROR(corruption_detected);
1946 if (op2 > opStart3) return ERROR(corruption_detected);
1947 if (op3 > opStart4) return ERROR(corruption_detected);
1948 /* note : op4 supposed already verified within main loop */
1950 /* finish bitStreams one by one */
1951 HUFv07_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1952 HUFv07_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1953 HUFv07_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1954 HUFv07_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1957 endSignal = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
1958 if (!endSignal) return ERROR(corruption_detected);
1966 size_t HUFv07_decompress4X2_usingDTable(
1967 void* dst, size_t dstSize,
1968 const void* cSrc, size_t cSrcSize,
1969 const HUFv07_DTable* DTable)
1971 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1972 if (dtd.tableType != 0) return ERROR(GENERIC);
1973 return HUFv07_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
1977 size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1979 const BYTE* ip = (const BYTE*) cSrc;
1981 size_t const hSize = HUFv07_readDTableX2 (dctx, cSrc, cSrcSize);
1982 if (HUFv07_isError(hSize)) return hSize;
1983 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1984 ip += hSize; cSrcSize -= hSize;
1986 return HUFv07_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx);
1989 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1991 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
1992 return HUFv07_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
1996 /* *************************/
1997 /* double-symbols decoding */
1998 /* *************************/
1999 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv07_DEltX4; /* double-symbols decoding */
2001 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
2003 static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2004 const U32* rankValOrigin, const int minWeight,
2005 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2006 U32 nbBitsBaseline, U16 baseSeq)
2009 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2011 /* get pre-calculated rankVal */
2012 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2014 /* fill skipped values */
2016 U32 i, skipSize = rankVal[minWeight];
2017 MEM_writeLE16(&(DElt.sequence), baseSeq);
2018 DElt.nbBits = (BYTE)(consumed);
2020 for (i = 0; i < skipSize; i++)
2025 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2026 const U32 symbol = sortedSymbols[s].symbol;
2027 const U32 weight = sortedSymbols[s].weight;
2028 const U32 nbBits = nbBitsBaseline - weight;
2029 const U32 length = 1 << (sizeLog-nbBits);
2030 const U32 start = rankVal[weight];
2032 const U32 end = start + length;
2034 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2035 DElt.nbBits = (BYTE)(nbBits + consumed);
2037 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2039 rankVal[weight] += length;
2043 typedef U32 rankVal_t[HUFv07_TABLELOG_ABSOLUTEMAX][HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2045 static void HUFv07_fillDTableX4(HUFv07_DEltX4* DTable, const U32 targetLog,
2046 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2047 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2048 const U32 nbBitsBaseline)
2050 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2051 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2052 const U32 minBits = nbBitsBaseline - maxWeight;
2055 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2058 for (s=0; s<sortedListSize; s++) {
2059 const U16 symbol = sortedList[s].symbol;
2060 const U32 weight = sortedList[s].weight;
2061 const U32 nbBits = nbBitsBaseline - weight;
2062 const U32 start = rankVal[weight];
2063 const U32 length = 1 << (targetLog-nbBits);
2065 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2067 int minWeight = nbBits + scaleLog;
2068 if (minWeight < 1) minWeight = 1;
2069 sortedRank = rankStart[minWeight];
2070 HUFv07_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2071 rankValOrigin[nbBits], minWeight,
2072 sortedList+sortedRank, sortedListSize-sortedRank,
2073 nbBitsBaseline, symbol);
2076 MEM_writeLE16(&(DElt.sequence), symbol);
2077 DElt.nbBits = (BYTE)(nbBits);
2080 const U32 end = start + length;
2081 for (u = start; u < end; u++) DTable[u] = DElt;
2083 rankVal[weight] += length;
2087 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
2089 BYTE weightList[HUFv07_SYMBOLVALUE_MAX + 1];
2090 sortedSymbol_t sortedSymbol[HUFv07_SYMBOLVALUE_MAX + 1];
2091 U32 rankStats[HUFv07_TABLELOG_ABSOLUTEMAX + 1] = { 0 };
2092 U32 rankStart0[HUFv07_TABLELOG_ABSOLUTEMAX + 2] = { 0 };
2093 U32* const rankStart = rankStart0+1;
2095 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2096 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2097 U32 const maxTableLog = dtd.maxTableLog;
2099 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */
2100 HUFv07_DEltX4* const dt = (HUFv07_DEltX4*)dtPtr;
2102 HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4) == sizeof(HUFv07_DTable)); /* if compilation fails here, assertion is false */
2103 if (maxTableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge);
2104 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */
2106 iSize = HUFv07_readStats(weightList, HUFv07_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2107 if (HUFv07_isError(iSize)) return iSize;
2110 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2112 /* find maxWeight */
2113 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2115 /* Get start index of each weight */
2116 { U32 w, nextRankStart = 0;
2117 for (w=1; w<maxW+1; w++) {
2118 U32 current = nextRankStart;
2119 nextRankStart += rankStats[w];
2120 rankStart[w] = current;
2122 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2123 sizeOfSort = nextRankStart;
2126 /* sort symbols by weight */
2128 for (s=0; s<nbSymbols; s++) {
2129 U32 const w = weightList[s];
2130 U32 const r = rankStart[w]++;
2131 sortedSymbol[r].symbol = (BYTE)s;
2132 sortedSymbol[r].weight = (BYTE)w;
2134 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2138 { U32* const rankVal0 = rankVal[0];
2139 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */
2140 U32 nextRankVal = 0;
2142 for (w=1; w<maxW+1; w++) {
2143 U32 current = nextRankVal;
2144 nextRankVal += rankStats[w] << (w+rescale);
2145 rankVal0[w] = current;
2147 { U32 const minBits = tableLog+1 - maxW;
2149 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
2150 U32* const rankValPtr = rankVal[consumed];
2152 for (w = 1; w < maxW+1; w++) {
2153 rankValPtr[w] = rankVal0[w] >> consumed;
2156 HUFv07_fillDTableX4(dt, maxTableLog,
2157 sortedSymbol, sizeOfSort,
2158 rankStart0, rankVal, maxW,
2161 dtd.tableLog = (BYTE)maxTableLog;
2163 memcpy(DTable, &dtd, sizeof(dtd));
2168 static U32 HUFv07_decodeSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2170 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2171 memcpy(op, dt+val, 2);
2172 BITv07_skipBits(DStream, dt[val].nbBits);
2173 return dt[val].length;
2176 static U32 HUFv07_decodeLastSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2178 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2179 memcpy(op, dt+val, 1);
2180 if (dt[val].length==1) BITv07_skipBits(DStream, dt[val].nbBits);
2182 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2183 BITv07_skipBits(DStream, dt[val].nbBits);
2184 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2185 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 */
2191 #define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2192 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2194 #define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2195 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
2196 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2198 #define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2200 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2202 static inline size_t HUFv07_decodeStreamX4(BYTE* p, BITv07_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv07_DEltX4* const dt, const U32 dtLog)
2204 BYTE* const pStart = p;
2206 /* up to 8 symbols at a time */
2207 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd-7)) {
2208 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2209 HUFv07_DECODE_SYMBOLX4_1(p, bitDPtr);
2210 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2211 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2214 /* closer to end : up to 2 symbols at a time */
2215 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-2))
2216 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2219 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2222 p += HUFv07_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2228 static size_t HUFv07_decompress1X4_usingDTable_internal(
2229 void* dst, size_t dstSize,
2230 const void* cSrc, size_t cSrcSize,
2231 const HUFv07_DTable* DTable)
2233 BITv07_DStream_t bitD;
2236 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
2237 if (HUFv07_isError(errorCode)) return errorCode;
2241 { BYTE* const ostart = (BYTE*) dst;
2242 BYTE* const oend = ostart + dstSize;
2243 const void* const dtPtr = DTable+1; /* force compiler to not use strict-aliasing */
2244 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2245 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2246 HUFv07_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog);
2250 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
2256 size_t HUFv07_decompress1X4_usingDTable(
2257 void* dst, size_t dstSize,
2258 const void* cSrc, size_t cSrcSize,
2259 const HUFv07_DTable* DTable)
2261 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2262 if (dtd.tableType != 1) return ERROR(GENERIC);
2263 return HUFv07_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2266 size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2268 const BYTE* ip = (const BYTE*) cSrc;
2270 size_t const hSize = HUFv07_readDTableX4 (DCtx, cSrc, cSrcSize);
2271 if (HUFv07_isError(hSize)) return hSize;
2272 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2273 ip += hSize; cSrcSize -= hSize;
2275 return HUFv07_decompress1X4_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
2278 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2280 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2281 return HUFv07_decompress1X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2284 static size_t HUFv07_decompress4X4_usingDTable_internal(
2285 void* dst, size_t dstSize,
2286 const void* cSrc, size_t cSrcSize,
2287 const HUFv07_DTable* DTable)
2289 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2291 { const BYTE* const istart = (const BYTE*) cSrc;
2292 BYTE* const ostart = (BYTE*) dst;
2293 BYTE* const oend = ostart + dstSize;
2294 const void* const dtPtr = DTable+1;
2295 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2298 BITv07_DStream_t bitD1;
2299 BITv07_DStream_t bitD2;
2300 BITv07_DStream_t bitD3;
2301 BITv07_DStream_t bitD4;
2302 size_t const length1 = MEM_readLE16(istart);
2303 size_t const length2 = MEM_readLE16(istart+2);
2304 size_t const length3 = MEM_readLE16(istart+4);
2305 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
2306 const BYTE* const istart1 = istart + 6; /* jumpTable */
2307 const BYTE* const istart2 = istart1 + length1;
2308 const BYTE* const istart3 = istart2 + length2;
2309 const BYTE* const istart4 = istart3 + length3;
2310 size_t const segmentSize = (dstSize+3) / 4;
2311 BYTE* const opStart2 = ostart + segmentSize;
2312 BYTE* const opStart3 = opStart2 + segmentSize;
2313 BYTE* const opStart4 = opStart3 + segmentSize;
2315 BYTE* op2 = opStart2;
2316 BYTE* op3 = opStart3;
2317 BYTE* op4 = opStart4;
2319 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2320 U32 const dtLog = dtd.tableLog;
2322 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2323 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
2324 if (HUFv07_isError(errorCode)) return errorCode; }
2325 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
2326 if (HUFv07_isError(errorCode)) return errorCode; }
2327 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
2328 if (HUFv07_isError(errorCode)) return errorCode; }
2329 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
2330 if (HUFv07_isError(errorCode)) return errorCode; }
2332 /* 16-32 symbols per loop (4-8 symbols per stream) */
2333 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2334 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
2335 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2336 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2337 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2338 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2339 HUFv07_DECODE_SYMBOLX4_1(op1, &bitD1);
2340 HUFv07_DECODE_SYMBOLX4_1(op2, &bitD2);
2341 HUFv07_DECODE_SYMBOLX4_1(op3, &bitD3);
2342 HUFv07_DECODE_SYMBOLX4_1(op4, &bitD4);
2343 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2344 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2345 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2346 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2347 HUFv07_DECODE_SYMBOLX4_0(op1, &bitD1);
2348 HUFv07_DECODE_SYMBOLX4_0(op2, &bitD2);
2349 HUFv07_DECODE_SYMBOLX4_0(op3, &bitD3);
2350 HUFv07_DECODE_SYMBOLX4_0(op4, &bitD4);
2352 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2355 /* check corruption */
2356 if (op1 > opStart2) return ERROR(corruption_detected);
2357 if (op2 > opStart3) return ERROR(corruption_detected);
2358 if (op3 > opStart4) return ERROR(corruption_detected);
2359 /* note : op4 supposed already verified within main loop */
2361 /* finish bitStreams one by one */
2362 HUFv07_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2363 HUFv07_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2364 HUFv07_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2365 HUFv07_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2368 { U32 const endCheck = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2369 if (!endCheck) return ERROR(corruption_detected); }
2377 size_t HUFv07_decompress4X4_usingDTable(
2378 void* dst, size_t dstSize,
2379 const void* cSrc, size_t cSrcSize,
2380 const HUFv07_DTable* DTable)
2382 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2383 if (dtd.tableType != 1) return ERROR(GENERIC);
2384 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2388 size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2390 const BYTE* ip = (const BYTE*) cSrc;
2392 size_t hSize = HUFv07_readDTableX4 (dctx, cSrc, cSrcSize);
2393 if (HUFv07_isError(hSize)) return hSize;
2394 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2395 ip += hSize; cSrcSize -= hSize;
2397 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
2400 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2402 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2403 return HUFv07_decompress4X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2407 /* ********************************/
2408 /* Generic decompression selector */
2409 /* ********************************/
2411 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize,
2412 const void* cSrc, size_t cSrcSize,
2413 const HUFv07_DTable* DTable)
2415 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2416 return dtd.tableType ? HUFv07_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2417 HUFv07_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2420 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize,
2421 const void* cSrc, size_t cSrcSize,
2422 const HUFv07_DTable* DTable)
2424 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2425 return dtd.tableType ? HUFv07_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2426 HUFv07_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2430 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2431 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2433 /* single, double, quad */
2434 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2435 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2436 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2437 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2438 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2439 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2440 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2441 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2442 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2443 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2444 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2445 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2446 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2447 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2448 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2449 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2452 /** HUFv07_selectDecoder() :
2453 * Tells which decoder is likely to decode faster,
2454 * based on a set of pre-determined metrics.
2455 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
2456 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
2457 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize)
2459 /* decoder timing evaluation */
2460 U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2461 U32 const D256 = (U32)(dstSize >> 8);
2462 U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
2463 U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
2464 DTime1 += DTime1 >> 3; /* advantage to algorithm using less memory, for cache eviction */
2466 return DTime1 < DTime0;
2470 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2472 size_t HUFv07_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2474 static const decompressionAlgo decompress[2] = { HUFv07_decompress4X2, HUFv07_decompress4X4 };
2476 /* validation checks */
2477 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2478 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2479 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2480 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2482 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2483 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2486 /* return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams single-symbol decoding */
2487 /* return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams double-symbols decoding */
2490 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2492 /* validation checks */
2493 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2494 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2495 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2496 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2498 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2499 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2500 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2504 size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2506 /* validation checks */
2507 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2508 if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected); /* invalid */
2510 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2511 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2512 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2516 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2518 /* validation checks */
2519 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2520 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2521 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2522 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2524 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2525 return algoNb ? HUFv07_decompress1X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2526 HUFv07_decompress1X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2530 Common functions of Zstd compression library
2531 Copyright (C) 2015-2016, Yann Collet.
2533 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2535 Redistribution and use in source and binary forms, with or without
2536 modification, are permitted provided that the following conditions are
2538 * Redistributions of source code must retain the above copyright
2539 notice, this list of conditions and the following disclaimer.
2540 * Redistributions in binary form must reproduce the above
2541 copyright notice, this list of conditions and the following disclaimer
2542 in the documentation and/or other materials provided with the
2544 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2545 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2546 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2547 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2548 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2549 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2550 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2551 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2552 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2553 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2554 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2556 You can contact the author at :
2557 - zstd homepage : https://facebook.github.io/zstd/
2562 /*-****************************************
2563 * ZSTD Error Management
2564 ******************************************/
2565 /*! ZSTDv07_isError() :
2566 * tells if a return value is an error code */
2567 unsigned ZSTDv07_isError(size_t code) { return ERR_isError(code); }
2569 /*! ZSTDv07_getErrorName() :
2570 * provides error code string from function result (useful for debugging) */
2571 const char* ZSTDv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
2575 /* **************************************************************
2576 * ZBUFF Error Management
2577 ****************************************************************/
2578 unsigned ZBUFFv07_isError(size_t errorCode) { return ERR_isError(errorCode); }
2580 const char* ZBUFFv07_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2584 static void* ZSTDv07_defaultAllocFunction(void* opaque, size_t size)
2586 void* address = malloc(size);
2588 /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2592 static void ZSTDv07_defaultFreeFunction(void* opaque, void* address)
2595 /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2599 zstd_internal - common functions to include
2600 Header File for include
2601 Copyright (C) 2014-2016, Yann Collet.
2603 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2605 Redistribution and use in source and binary forms, with or without
2606 modification, are permitted provided that the following conditions are
2608 * Redistributions of source code must retain the above copyright
2609 notice, this list of conditions and the following disclaimer.
2610 * Redistributions in binary form must reproduce the above
2611 copyright notice, this list of conditions and the following disclaimer
2612 in the documentation and/or other materials provided with the
2614 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2615 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2616 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2617 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2618 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2619 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2620 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2621 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2622 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2623 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2624 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2626 You can contact the author at :
2627 - zstd homepage : https://www.zstd.net
2629 #ifndef ZSTDv07_CCOMMON_H_MODULE
2630 #define ZSTDv07_CCOMMON_H_MODULE
2633 /*-*************************************
2635 ***************************************/
2636 #define MIN(a,b) ((a)<(b) ? (a) : (b))
2637 #define MAX(a,b) ((a)>(b) ? (a) : (b))
2640 /*-*************************************
2642 ***************************************/
2643 #define ZSTDv07_OPT_NUM (1<<12)
2644 #define ZSTDv07_DICT_MAGIC 0xEC30A437 /* v0.7 */
2646 #define ZSTDv07_REP_NUM 3
2647 #define ZSTDv07_REP_INIT ZSTDv07_REP_NUM
2648 #define ZSTDv07_REP_MOVE (ZSTDv07_REP_NUM-1)
2649 static const U32 repStartValue[ZSTDv07_REP_NUM] = { 1, 4, 8 };
2651 #define KB *(1 <<10)
2652 #define MB *(1 <<20)
2653 #define GB *(1U<<30)
2662 #define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10
2663 static const size_t ZSTDv07_fcs_fieldSize[4] = { 0, 2, 4, 8 };
2664 static const size_t ZSTDv07_did_fieldSize[4] = { 0, 1, 2, 4 };
2666 #define ZSTDv07_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
2667 static const size_t ZSTDv07_blockHeaderSize = ZSTDv07_BLOCKHEADERSIZE;
2668 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2670 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2671 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
2673 #define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
2674 typedef enum { lbt_huffman, lbt_repeat, lbt_raw, lbt_rle } litBlockType_t;
2676 #define LONGNBSEQ 0x7F00
2679 #define EQUAL_READ32 4
2682 #define MaxLit ((1<<Litbits) - 1)
2686 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
2691 #define FSEv07_ENCODING_RAW 0
2692 #define FSEv07_ENCODING_RLE 1
2693 #define FSEv07_ENCODING_STATIC 2
2694 #define FSEv07_ENCODING_DYNAMIC 3
2696 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2698 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2699 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
2701 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2702 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
2704 static const U32 LL_defaultNormLog = 6;
2706 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2707 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2708 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
2710 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2711 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2712 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
2714 static const U32 ML_defaultNormLog = 6;
2716 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2717 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
2718 static const U32 OF_defaultNormLog = 5;
2721 /*-*******************************************
2722 * Shared functions to include for inlining
2723 *********************************************/
2724 static void ZSTDv07_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2725 #define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; }
2727 /*! ZSTDv07_wildcopy() :
2728 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
2729 #define WILDCOPY_OVERLENGTH 8
2730 MEM_STATIC void ZSTDv07_wildcopy(void* dst, const void* src, ptrdiff_t length)
2732 const BYTE* ip = (const BYTE*)src;
2733 BYTE* op = (BYTE*)dst;
2734 BYTE* const oend = op + length;
2741 /*-*******************************************
2742 * Private interfaces
2743 *********************************************/
2744 typedef struct ZSTDv07_stats_s ZSTDv07_stats_t;
2756 U32 rep[ZSTDv07_REP_INIT];
2757 } ZSTDv07_optimal_t;
2759 struct ZSTDv07_stats_s { U32 unused; };
2768 U16* litLengthStart;
2771 U16* matchLengthStart;
2774 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
2777 ZSTDv07_optimal_t* priceTable;
2778 ZSTDv07_match_t* matchTable;
2779 U32* matchLengthFreq;
2788 U32 log2matchLengthSum;
2790 U32 log2litLengthSum;
2795 U32 cachedLitLength;
2796 const BYTE* cachedLiterals;
2797 ZSTDv07_stats_t stats;
2800 void ZSTDv07_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
2802 /* custom memory allocation functions */
2803 static const ZSTDv07_customMem defaultCustomMem = { ZSTDv07_defaultAllocFunction, ZSTDv07_defaultFreeFunction, NULL };
2805 #endif /* ZSTDv07_CCOMMON_H_MODULE */
2807 zstd - standard compression library
2808 Copyright (C) 2014-2016, Yann Collet.
2810 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2812 Redistribution and use in source and binary forms, with or without
2813 modification, are permitted provided that the following conditions are
2815 * Redistributions of source code must retain the above copyright
2816 notice, this list of conditions and the following disclaimer.
2817 * Redistributions in binary form must reproduce the above
2818 copyright notice, this list of conditions and the following disclaimer
2819 in the documentation and/or other materials provided with the
2821 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2822 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2823 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2824 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2825 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2826 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2827 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2828 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2829 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2830 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2831 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2833 You can contact the author at :
2834 - zstd homepage : https://facebook.github.io/zstd
2837 /* ***************************************************************
2839 *****************************************************************/
2842 * Select how default decompression function ZSTDv07_decompress() will allocate memory,
2843 * in memory stack (0), or in memory heap (1, requires malloc())
2845 #ifndef ZSTDv07_HEAPMODE
2846 # define ZSTDv07_HEAPMODE 1
2850 /*-*******************************************************
2851 * Compiler specifics
2852 *********************************************************/
2853 #ifdef _MSC_VER /* Visual Studio */
2854 # include <intrin.h> /* For Visual 2005 */
2855 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2856 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2857 # pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */
2861 /*-*************************************
2863 ***************************************/
2864 #define ZSTDv07_isError ERR_isError /* for inlining */
2865 #define FSEv07_isError ERR_isError
2866 #define HUFv07_isError ERR_isError
2869 /*_*******************************************************
2871 **********************************************************/
2872 static void ZSTDv07_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2875 /*-*************************************************************
2876 * Context management
2877 ***************************************************************/
2878 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2879 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
2880 ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTDv07_dStage;
2882 struct ZSTDv07_DCtx_s
2884 FSEv07_DTable LLTable[FSEv07_DTABLE_SIZE_U32(LLFSELog)];
2885 FSEv07_DTable OffTable[FSEv07_DTABLE_SIZE_U32(OffFSELog)];
2886 FSEv07_DTable MLTable[FSEv07_DTABLE_SIZE_U32(MLFSELog)];
2887 HUFv07_DTable hufTable[HUFv07_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)]; /* can accommodate HUFv07_decompress4X */
2888 const void* previousDstEnd;
2891 const void* dictEnd;
2894 ZSTDv07_frameParams fParams;
2895 blockType_t bType; /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2896 ZSTDv07_dStage stage;
2899 XXH64_state_t xxhState;
2903 ZSTDv07_customMem customMem;
2905 BYTE litBuffer[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
2906 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
2907 }; /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */
2909 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx);
2911 size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx* dctx) { return sizeof(*dctx); }
2913 size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx); }
2915 size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx)
2917 dctx->expected = ZSTDv07_frameHeaderSize_min;
2918 dctx->stage = ZSTDds_getFrameHeaderSize;
2919 dctx->previousDstEnd = NULL;
2922 dctx->dictEnd = NULL;
2923 dctx->hufTable[0] = (HUFv07_DTable)((ZSTD_HUFFDTABLE_CAPACITY_LOG)*0x1000001);
2924 dctx->litEntropy = dctx->fseEntropy = 0;
2926 { int i; for (i=0; i<ZSTDv07_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; }
2930 ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem)
2934 if (!customMem.customAlloc && !customMem.customFree)
2935 customMem = defaultCustomMem;
2937 if (!customMem.customAlloc || !customMem.customFree)
2940 dctx = (ZSTDv07_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTDv07_DCtx));
2941 if (!dctx) return NULL;
2942 memcpy(&dctx->customMem, &customMem, sizeof(ZSTDv07_customMem));
2943 ZSTDv07_decompressBegin(dctx);
2947 ZSTDv07_DCtx* ZSTDv07_createDCtx(void)
2949 return ZSTDv07_createDCtx_advanced(defaultCustomMem);
2952 size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx* dctx)
2954 if (dctx==NULL) return 0; /* support free on NULL */
2955 dctx->customMem.customFree(dctx->customMem.opaque, dctx);
2956 return 0; /* reserved as a potential error code in the future */
2959 void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dstDCtx, const ZSTDv07_DCtx* srcDCtx)
2961 memcpy(dstDCtx, srcDCtx,
2962 sizeof(ZSTDv07_DCtx) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH + ZSTDv07_frameHeaderSize_max)); /* no need to copy workspace */
2966 /*-*************************************************************
2967 * Decompression section
2968 ***************************************************************/
2970 /* Frame format description
2971 Frame Header - [ Block Header - Block ] - Frame End
2973 - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h)
2974 - 1 byte - Frame Descriptor
2976 - 3 bytes, starting with a 2-bits descriptor
2977 Uncompressed, Compressed, Frame End, unused
2979 See Block Format Description
2981 - 3 bytes, compatible with Block Header
2987 1 byte - FrameHeaderDescription :
2988 bit 0-1 : dictID (0, 1, 2 or 4 bytes)
2989 bit 2 : checksumFlag
2990 bit 3 : reserved (must be zero)
2991 bit 4 : reserved (unused, can be any value)
2992 bit 5 : Single Segment (if 1, WindowLog byte is not present)
2993 bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
2994 if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
2996 Optional : WindowLog (0 or 1 byte)
2997 bit 0-2 : octal Fractional (1/8th)
2998 bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
3000 Optional : dictID (0, 1, 2 or 4 bytes)
3001 Automatic adaptation
3005 4 : all other values
3007 Optional : content size (0, 1, 2, 4 or 8 bytes)
3008 0 : unknown (fcfs==0 and swl==0)
3009 1 : 0-255 bytes (fcfs==0 and swl==1)
3010 2 : 256 - 65535+256 (fcfs==1)
3011 4 : 0 - 4GB-1 (fcfs==2)
3012 8 : 0 - 16EB-1 (fcfs==3)
3016 /* Compressed Block, format description
3018 Block = Literal Section - Sequences Section
3019 Prerequisite : size of (compressed) block, maximum size of regenerated data
3023 1.1) Header : 1-5 bytes
3025 00 compressed by Huff0
3027 10 is Raw (uncompressed)
3029 Note : using 01 => Huff0 with precomputed table ?
3030 Note : delta map ? => compressed ?
3032 1.1.1) Huff0-compressed literal block : 3-5 bytes
3033 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3034 srcSize < 1 KB => 3 bytes (2-2-10-10)
3035 srcSize < 16KB => 4 bytes (2-2-14-14)
3036 else => 5 bytes (2-2-18-18)
3037 big endian convention
3039 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
3040 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
3041 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
3043 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3047 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3048 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
3049 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3051 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3055 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3056 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3057 srcSize < 1 KB => 3 bytes (2-2-10-10)
3058 srcSize < 16KB => 4 bytes (2-2-14-14)
3059 else => 5 bytes (2-2-18-18)
3060 big endian convention
3062 1- CTable available (stored into workspace ?)
3063 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3066 1.2) Literal block content
3068 1.2.1) Huff0 block, using sizes from header
3071 1.2.2) Huff0 block, using prepared table
3078 2) Sequences section
3082 /** ZSTDv07_frameHeaderSize() :
3083 * srcSize must be >= ZSTDv07_frameHeaderSize_min.
3084 * @return : size of the Frame Header */
3085 static size_t ZSTDv07_frameHeaderSize(const void* src, size_t srcSize)
3087 if (srcSize < ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);
3088 { BYTE const fhd = ((const BYTE*)src)[4];
3089 U32 const dictID= fhd & 3;
3090 U32 const directMode = (fhd >> 5) & 1;
3091 U32 const fcsId = fhd >> 6;
3092 return ZSTDv07_frameHeaderSize_min + !directMode + ZSTDv07_did_fieldSize[dictID] + ZSTDv07_fcs_fieldSize[fcsId]
3093 + (directMode && !ZSTDv07_fcs_fieldSize[fcsId]);
3098 /** ZSTDv07_getFrameParams() :
3099 * decode Frame Header, or require larger `srcSize`.
3100 * @return : 0, `fparamsPtr` is correctly filled,
3101 * >0, `srcSize` is too small, result is expected `srcSize`,
3102 * or an error code, which can be tested using ZSTDv07_isError() */
3103 size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams* fparamsPtr, const void* src, size_t srcSize)
3105 const BYTE* ip = (const BYTE*)src;
3107 if (srcSize < ZSTDv07_frameHeaderSize_min) return ZSTDv07_frameHeaderSize_min;
3108 memset(fparamsPtr, 0, sizeof(*fparamsPtr));
3109 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3110 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3111 if (srcSize < ZSTDv07_skippableHeaderSize) return ZSTDv07_skippableHeaderSize; /* magic number + skippable frame length */
3112 fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);
3113 fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
3116 return ERROR(prefix_unknown);
3119 /* ensure there is enough `srcSize` to fully read/decode frame header */
3120 { size_t const fhsize = ZSTDv07_frameHeaderSize(src, srcSize);
3121 if (srcSize < fhsize) return fhsize; }
3123 { BYTE const fhdByte = ip[4];
3125 U32 const dictIDSizeCode = fhdByte&3;
3126 U32 const checksumFlag = (fhdByte>>2)&1;
3127 U32 const directMode = (fhdByte>>5)&1;
3128 U32 const fcsID = fhdByte>>6;
3129 U32 const windowSizeMax = 1U << ZSTDv07_WINDOWLOG_MAX;
3132 U64 frameContentSize = 0;
3133 if ((fhdByte & 0x08) != 0) /* reserved bits, which must be zero */
3134 return ERROR(frameParameter_unsupported);
3136 BYTE const wlByte = ip[pos++];
3137 U32 const windowLog = (wlByte >> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN;
3138 if (windowLog > ZSTDv07_WINDOWLOG_MAX)
3139 return ERROR(frameParameter_unsupported);
3140 windowSize = (1U << windowLog);
3141 windowSize += (windowSize >> 3) * (wlByte&7);
3144 switch(dictIDSizeCode)
3146 default: /* impossible */
3148 case 1 : dictID = ip[pos]; pos++; break;
3149 case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
3150 case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
3154 default: /* impossible */
3155 case 0 : if (directMode) frameContentSize = ip[pos]; break;
3156 case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
3157 case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
3158 case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
3160 if (!windowSize) windowSize = (U32)frameContentSize;
3161 if (windowSize > windowSizeMax)
3162 return ERROR(frameParameter_unsupported);
3163 fparamsPtr->frameContentSize = frameContentSize;
3164 fparamsPtr->windowSize = windowSize;
3165 fparamsPtr->dictID = dictID;
3166 fparamsPtr->checksumFlag = checksumFlag;
3172 /** ZSTDv07_getDecompressedSize() :
3173 * compatible with legacy mode
3174 * @return : decompressed size if known, 0 otherwise
3175 note : 0 can mean any of the following :
3176 - decompressed size is not provided within frame header
3177 - frame header unknown / not supported
3178 - frame header not completely provided (`srcSize` too small) */
3179 unsigned long long ZSTDv07_getDecompressedSize(const void* src, size_t srcSize)
3181 ZSTDv07_frameParams fparams;
3182 size_t const frResult = ZSTDv07_getFrameParams(&fparams, src, srcSize);
3183 if (frResult!=0) return 0;
3184 return fparams.frameContentSize;
3188 /** ZSTDv07_decodeFrameHeader() :
3189 * `srcSize` must be the size provided by ZSTDv07_frameHeaderSize().
3190 * @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */
3191 static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx* dctx, const void* src, size_t srcSize)
3193 size_t const result = ZSTDv07_getFrameParams(&(dctx->fParams), src, srcSize);
3194 if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
3195 if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
3202 blockType_t blockType;
3204 } blockProperties_t;
3206 /*! ZSTDv07_getcBlockSize() :
3207 * Provides the size of compressed block from block header `src` */
3208 static size_t ZSTDv07_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
3210 const BYTE* const in = (const BYTE*)src;
3213 if (srcSize < ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3215 bpPtr->blockType = (blockType_t)((*in) >> 6);
3216 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
3217 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
3219 if (bpPtr->blockType == bt_end) return 0;
3220 if (bpPtr->blockType == bt_rle) return 1;
3225 static size_t ZSTDv07_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3227 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
3229 memcpy(dst, src, srcSize);
3235 /*! ZSTDv07_decodeLiteralsBlock() :
3236 @return : nb of bytes read from src (< srcSize ) */
3237 static size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx* dctx,
3238 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
3240 const BYTE* const istart = (const BYTE*) src;
3242 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3244 switch((litBlockType_t)(istart[0]>> 6))
3247 { size_t litSize, litCSize, singleStream=0;
3248 U32 lhSize = (istart[0] >> 4) & 3;
3249 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3252 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3253 /* 2 - 2 - 10 - 10 */
3255 singleStream = istart[0] & 16;
3256 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3257 litCSize = ((istart[1] & 3) << 8) + istart[2];
3260 /* 2 - 2 - 14 - 14 */
3262 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3263 litCSize = ((istart[2] & 63) << 8) + istart[3];
3266 /* 2 - 2 - 18 - 18 */
3268 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3269 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
3272 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3273 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3275 if (HUFv07_isError(singleStream ?
3276 HUFv07_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3277 HUFv07_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3278 return ERROR(corruption_detected);
3280 dctx->litPtr = dctx->litBuffer;
3281 dctx->litSize = litSize;
3282 dctx->litEntropy = 1;
3283 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3284 return litCSize + lhSize;
3287 { size_t litSize, litCSize;
3288 U32 lhSize = ((istart[0]) >> 4) & 3;
3289 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
3290 return ERROR(corruption_detected);
3291 if (dctx->litEntropy==0)
3292 return ERROR(dictionary_corrupted);
3294 /* 2 - 2 - 10 - 10 */
3296 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3297 litCSize = ((istart[1] & 3) << 8) + istart[2];
3298 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3300 { size_t const errorCode = HUFv07_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTable);
3301 if (HUFv07_isError(errorCode)) return ERROR(corruption_detected);
3303 dctx->litPtr = dctx->litBuffer;
3304 dctx->litSize = litSize;
3305 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3306 return litCSize + lhSize;
3310 U32 lhSize = ((istart[0]) >> 4) & 3;
3313 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3315 litSize = istart[0] & 31;
3318 litSize = ((istart[0] & 15) << 8) + istart[1];
3321 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3325 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
3326 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3327 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3328 dctx->litPtr = dctx->litBuffer;
3329 dctx->litSize = litSize;
3330 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3331 return lhSize+litSize;
3333 /* direct reference into compressed stream */
3334 dctx->litPtr = istart+lhSize;
3335 dctx->litSize = litSize;
3336 return lhSize+litSize;
3340 U32 lhSize = ((istart[0]) >> 4) & 3;
3343 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3345 litSize = istart[0] & 31;
3348 litSize = ((istart[0] & 15) << 8) + istart[1];
3351 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3352 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3355 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3356 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3357 dctx->litPtr = dctx->litBuffer;
3358 dctx->litSize = litSize;
3362 return ERROR(corruption_detected); /* impossible */
3367 /*! ZSTDv07_buildSeqTable() :
3368 @return : nb bytes read from src,
3369 or an error code if it fails, testable with ZSTDv07_isError()
3371 static size_t ZSTDv07_buildSeqTable(FSEv07_DTable* DTable, U32 type, U32 max, U32 maxLog,
3372 const void* src, size_t srcSize,
3373 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3377 case FSEv07_ENCODING_RLE :
3378 if (!srcSize) return ERROR(srcSize_wrong);
3379 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3380 FSEv07_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */
3382 case FSEv07_ENCODING_RAW :
3383 FSEv07_buildDTable(DTable, defaultNorm, max, defaultLog);
3385 case FSEv07_ENCODING_STATIC:
3386 if (!flagRepeatTable) return ERROR(corruption_detected);
3388 default : /* impossible */
3389 case FSEv07_ENCODING_DYNAMIC :
3392 size_t const headerSize = FSEv07_readNCount(norm, &max, &tableLog, src, srcSize);
3393 if (FSEv07_isError(headerSize)) return ERROR(corruption_detected);
3394 if (tableLog > maxLog) return ERROR(corruption_detected);
3395 FSEv07_buildDTable(DTable, norm, max, tableLog);
3401 static size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr,
3402 FSEv07_DTable* DTableLL, FSEv07_DTable* DTableML, FSEv07_DTable* DTableOffb, U32 flagRepeatTable,
3403 const void* src, size_t srcSize)
3405 const BYTE* const istart = (const BYTE*)src;
3406 const BYTE* const iend = istart + srcSize;
3407 const BYTE* ip = istart;
3410 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3413 { int nbSeq = *ip++;
3414 if (!nbSeq) { *nbSeqPtr=0; return 1; }
3416 if (nbSeq == 0xFF) {
3417 if (ip+2 > iend) return ERROR(srcSize_wrong);
3418 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3420 if (ip >= iend) return ERROR(srcSize_wrong);
3421 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3427 /* FSE table descriptors */
3428 if (ip + 4 > iend) return ERROR(srcSize_wrong); /* min : header byte + all 3 are "raw", hence no header, but at least xxLog bits per type */
3429 { U32 const LLtype = *ip >> 6;
3430 U32 const OFtype = (*ip >> 4) & 3;
3431 U32 const MLtype = (*ip >> 2) & 3;
3435 { size_t const llhSize = ZSTDv07_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3436 if (ZSTDv07_isError(llhSize)) return ERROR(corruption_detected);
3439 { size_t const ofhSize = ZSTDv07_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3440 if (ZSTDv07_isError(ofhSize)) return ERROR(corruption_detected);
3443 { size_t const mlhSize = ZSTDv07_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3444 if (ZSTDv07_isError(mlhSize)) return ERROR(corruption_detected);
3459 BITv07_DStream_t DStream;
3460 FSEv07_DState_t stateLL;
3461 FSEv07_DState_t stateOffb;
3462 FSEv07_DState_t stateML;
3463 size_t prevOffset[ZSTDv07_REP_INIT];
3467 static seq_t ZSTDv07_decodeSequence(seqState_t* seqState)
3471 U32 const llCode = FSEv07_peekSymbol(&(seqState->stateLL));
3472 U32 const mlCode = FSEv07_peekSymbol(&(seqState->stateML));
3473 U32 const ofCode = FSEv07_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3475 U32 const llBits = LL_bits[llCode];
3476 U32 const mlBits = ML_bits[mlCode];
3477 U32 const ofBits = ofCode;
3478 U32 const totalBits = llBits+mlBits+ofBits;
3480 static const U32 LL_base[MaxLL+1] = {
3481 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3482 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3483 0x2000, 0x4000, 0x8000, 0x10000 };
3485 static const U32 ML_base[MaxML+1] = {
3486 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
3487 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
3488 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3489 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3491 static const U32 OF_base[MaxOff+1] = {
3492 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
3493 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
3494 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3495 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3502 offset = OF_base[ofCode] + BITv07_readBits(&(seqState->DStream), ofBits); /* <= (ZSTDv07_WINDOWLOG_MAX-1) bits */
3503 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));
3507 if ((llCode == 0) & (offset <= 1)) offset = 1-offset;
3509 size_t const temp = seqState->prevOffset[offset];
3510 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
3511 seqState->prevOffset[1] = seqState->prevOffset[0];
3512 seqState->prevOffset[0] = offset = temp;
3514 offset = seqState->prevOffset[0];
3517 seqState->prevOffset[2] = seqState->prevOffset[1];
3518 seqState->prevOffset[1] = seqState->prevOffset[0];
3519 seqState->prevOffset[0] = offset;
3521 seq.offset = offset;
3524 seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BITv07_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */
3525 if (MEM_32bits() && (mlBits+llBits>24)) BITv07_reloadDStream(&(seqState->DStream));
3527 seq.litLength = LL_base[llCode] + ((llCode>15) ? BITv07_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */
3529 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv07_reloadDStream(&(seqState->DStream));
3531 /* ANS state update */
3532 FSEv07_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */
3533 FSEv07_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */
3534 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream)); /* <= 18 bits */
3535 FSEv07_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */
3542 size_t ZSTDv07_execSequence(BYTE* op,
3543 BYTE* const oend, seq_t sequence,
3544 const BYTE** litPtr, const BYTE* const litLimit,
3545 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3547 BYTE* const oLitEnd = op + sequence.litLength;
3548 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3549 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3550 BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH;
3551 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3552 const BYTE* match = oLitEnd - sequence.offset;
3556 if (sequence.litLength + WILDCOPY_OVERLENGTH > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3557 if (sequenceLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3558 assert(litLimit >= *litPtr);
3559 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);;
3562 ZSTDv07_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3564 *litPtr = iLitEnd; /* update for next sequence */
3567 if (sequence.offset > (size_t)(oLitEnd - base)) {
3568 /* offset beyond prefix */
3569 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3570 match = dictEnd - (base-match);
3571 if (match + sequence.matchLength <= dictEnd) {
3572 memmove(oLitEnd, match, sequence.matchLength);
3573 return sequenceLength;
3575 /* span extDict & currentPrefixSegment */
3576 { size_t const length1 = (size_t)(dictEnd - match);
3577 memmove(oLitEnd, match, length1);
3578 op = oLitEnd + length1;
3579 sequence.matchLength -= length1;
3581 if (op > oend_w || sequence.matchLength < MINMATCH) {
3582 while (op < oMatchEnd) *op++ = *match++;
3583 return sequenceLength;
3586 /* Requirement: op <= oend_w */
3588 /* match within prefix */
3589 if (sequence.offset < 8) {
3590 /* close range match, overlap */
3591 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3592 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
3593 int const sub2 = dec64table[sequence.offset];
3598 match += dec32table[sequence.offset];
3599 ZSTDv07_copy4(op+4, match);
3602 ZSTDv07_copy8(op, match);
3604 op += 8; match += 8;
3606 if (oMatchEnd > oend-(16-MINMATCH)) {
3608 ZSTDv07_wildcopy(op, match, oend_w - op);
3609 match += oend_w - op;
3612 while (op < oMatchEnd) *op++ = *match++;
3614 ZSTDv07_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3616 return sequenceLength;
3620 static size_t ZSTDv07_decompressSequences(
3622 void* dst, size_t maxDstSize,
3623 const void* seqStart, size_t seqSize)
3625 const BYTE* ip = (const BYTE*)seqStart;
3626 const BYTE* const iend = ip + seqSize;
3627 BYTE* const ostart = (BYTE*)dst;
3628 BYTE* const oend = ostart + maxDstSize;
3630 const BYTE* litPtr = dctx->litPtr;
3631 const BYTE* const litEnd = litPtr + dctx->litSize;
3632 FSEv07_DTable* DTableLL = dctx->LLTable;
3633 FSEv07_DTable* DTableML = dctx->MLTable;
3634 FSEv07_DTable* DTableOffb = dctx->OffTable;
3635 const BYTE* const base = (const BYTE*) (dctx->base);
3636 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3637 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3640 /* Build Decoding Tables */
3641 { size_t const seqHSize = ZSTDv07_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize);
3642 if (ZSTDv07_isError(seqHSize)) return seqHSize;
3646 /* Regen sequences */
3648 seqState_t seqState;
3649 dctx->fseEntropy = 1;
3650 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; }
3651 { size_t const errorCode = BITv07_initDStream(&(seqState.DStream), ip, iend-ip);
3652 if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3653 FSEv07_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3654 FSEv07_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3655 FSEv07_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3657 for ( ; (BITv07_reloadDStream(&(seqState.DStream)) <= BITv07_DStream_completed) && nbSeq ; ) {
3659 { seq_t const sequence = ZSTDv07_decodeSequence(&seqState);
3660 size_t const oneSeqSize = ZSTDv07_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3661 if (ZSTDv07_isError(oneSeqSize)) return oneSeqSize;
3665 /* check if reached exact end */
3666 if (nbSeq) return ERROR(corruption_detected);
3667 /* save reps for next block */
3668 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
3671 /* last literal segment */
3672 { size_t const lastLLSize = litEnd - litPtr;
3673 /* if (litPtr > litEnd) return ERROR(corruption_detected); */ /* too many literals already used */
3674 if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
3675 if (lastLLSize > 0) {
3676 memcpy(op, litPtr, lastLLSize);
3685 static void ZSTDv07_checkContinuity(ZSTDv07_DCtx* dctx, const void* dst)
3687 if (dst != dctx->previousDstEnd) { /* not contiguous */
3688 dctx->dictEnd = dctx->previousDstEnd;
3689 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3691 dctx->previousDstEnd = dst;
3696 static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx* dctx,
3697 void* dst, size_t dstCapacity,
3698 const void* src, size_t srcSize)
3699 { /* blockType == blockCompressed */
3700 const BYTE* ip = (const BYTE*)src;
3702 if (srcSize >= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong);
3704 /* Decode literals sub-block */
3705 { size_t const litCSize = ZSTDv07_decodeLiteralsBlock(dctx, src, srcSize);
3706 if (ZSTDv07_isError(litCSize)) return litCSize;
3708 srcSize -= litCSize;
3710 return ZSTDv07_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3714 size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx,
3715 void* dst, size_t dstCapacity,
3716 const void* src, size_t srcSize)
3719 ZSTDv07_checkContinuity(dctx, dst);
3720 dSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3721 dctx->previousDstEnd = (char*)dst + dSize;
3726 /** ZSTDv07_insertBlock() :
3727 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
3728 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize)
3730 ZSTDv07_checkContinuity(dctx, blockStart);
3731 dctx->previousDstEnd = (const char*)blockStart + blockSize;
3736 static size_t ZSTDv07_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length)
3738 if (length > dstCapacity) return ERROR(dstSize_tooSmall);
3740 memset(dst, byte, length);
3746 /*! ZSTDv07_decompressFrame() :
3747 * `dctx` must be properly initialized */
3748 static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx* dctx,
3749 void* dst, size_t dstCapacity,
3750 const void* src, size_t srcSize)
3752 const BYTE* ip = (const BYTE*)src;
3753 const BYTE* const iend = ip + srcSize;
3754 BYTE* const ostart = (BYTE*)dst;
3755 BYTE* const oend = ostart + dstCapacity;
3757 size_t remainingSize = srcSize;
3760 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3763 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3764 if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3765 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3766 if (ZSTDv07_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3767 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3770 /* Loop on each block */
3773 blockProperties_t blockProperties;
3774 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, iend-ip, &blockProperties);
3775 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3777 ip += ZSTDv07_blockHeaderSize;
3778 remainingSize -= ZSTDv07_blockHeaderSize;
3779 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3781 switch(blockProperties.blockType)
3784 decodedSize = ZSTDv07_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3787 decodedSize = ZSTDv07_copyRawBlock(op, oend-op, ip, cBlockSize);
3790 decodedSize = ZSTDv07_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
3794 if (remainingSize) return ERROR(srcSize_wrong);
3798 return ERROR(GENERIC); /* impossible */
3800 if (blockProperties.blockType == bt_end) break; /* bt_end */
3802 if (ZSTDv07_isError(decodedSize)) return decodedSize;
3803 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
3806 remainingSize -= cBlockSize;
3813 /*! ZSTDv07_decompress_usingPreparedDCtx() :
3814 * Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
3815 * It avoids reloading the dictionary each time.
3816 * `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict().
3817 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
3818 static size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* refDCtx,
3819 void* dst, size_t dstCapacity,
3820 const void* src, size_t srcSize)
3822 ZSTDv07_copyDCtx(dctx, refDCtx);
3823 ZSTDv07_checkContinuity(dctx, dst);
3824 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3828 size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx* dctx,
3829 void* dst, size_t dstCapacity,
3830 const void* src, size_t srcSize,
3831 const void* dict, size_t dictSize)
3833 ZSTDv07_decompressBegin_usingDict(dctx, dict, dictSize);
3834 ZSTDv07_checkContinuity(dctx, dst);
3835 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3839 size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3841 return ZSTDv07_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3845 size_t ZSTDv07_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3847 #if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1)
3849 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx();
3850 if (dctx==NULL) return ERROR(memory_allocation);
3851 regenSize = ZSTDv07_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3852 ZSTDv07_freeDCtx(dctx);
3854 #else /* stack mode */
3856 return ZSTDv07_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3860 /* ZSTD_errorFrameSizeInfoLegacy() :
3861 assumes `cSize` and `dBound` are _not_ NULL */
3862 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3865 *dBound = ZSTD_CONTENTSIZE_ERROR;
3868 void ZSTDv07_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3870 const BYTE* ip = (const BYTE*)src;
3871 size_t remainingSize = srcSize;
3872 size_t nbBlocks = 0;
3875 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) {
3876 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3881 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, srcSize);
3882 if (ZSTDv07_isError(frameHeaderSize)) {
3883 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize);
3886 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3887 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3890 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) {
3891 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3894 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3897 /* Loop on each block */
3899 blockProperties_t blockProperties;
3900 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, remainingSize, &blockProperties);
3901 if (ZSTDv07_isError(cBlockSize)) {
3902 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3906 ip += ZSTDv07_blockHeaderSize;
3907 remainingSize -= ZSTDv07_blockHeaderSize;
3909 if (blockProperties.blockType == bt_end) break;
3911 if (cBlockSize > remainingSize) {
3912 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3917 remainingSize -= cBlockSize;
3921 *cSize = ip - (const BYTE*)src;
3922 *dBound = nbBlocks * ZSTDv07_BLOCKSIZE_ABSOLUTEMAX;
3925 /*_******************************
3926 * Streaming Decompression API
3927 ********************************/
3928 size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx)
3930 return dctx->expected;
3933 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx)
3935 return dctx->stage == ZSTDds_skipFrame;
3938 /** ZSTDv07_decompressContinue() :
3939 * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
3940 * or an error code, which can be tested using ZSTDv07_isError() */
3941 size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3944 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3945 if (dstCapacity) ZSTDv07_checkContinuity(dctx, dst);
3947 switch (dctx->stage)
3949 case ZSTDds_getFrameHeaderSize :
3950 if (srcSize != ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3951 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3952 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
3953 dctx->expected = ZSTDv07_skippableHeaderSize - ZSTDv07_frameHeaderSize_min; /* magic number + skippable frame length */
3954 dctx->stage = ZSTDds_decodeSkippableHeader;
3957 dctx->headerSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3958 if (ZSTDv07_isError(dctx->headerSize)) return dctx->headerSize;
3959 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
3960 if (dctx->headerSize > ZSTDv07_frameHeaderSize_min) {
3961 dctx->expected = dctx->headerSize - ZSTDv07_frameHeaderSize_min;
3962 dctx->stage = ZSTDds_decodeFrameHeader;
3965 dctx->expected = 0; /* not necessary to copy more */
3967 case ZSTDds_decodeFrameHeader:
3969 memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
3970 result = ZSTDv07_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
3971 if (ZSTDv07_isError(result)) return result;
3972 dctx->expected = ZSTDv07_blockHeaderSize;
3973 dctx->stage = ZSTDds_decodeBlockHeader;
3976 case ZSTDds_decodeBlockHeader:
3977 { blockProperties_t bp;
3978 size_t const cBlockSize = ZSTDv07_getcBlockSize(src, ZSTDv07_blockHeaderSize, &bp);
3979 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3980 if (bp.blockType == bt_end) {
3981 if (dctx->fParams.checksumFlag) {
3982 U64 const h64 = XXH64_digest(&dctx->xxhState);
3983 U32 const h32 = (U32)(h64>>11) & ((1<<22)-1);
3984 const BYTE* const ip = (const BYTE*)src;
3985 U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16);
3986 if (check32 != h32) return ERROR(checksum_wrong);
3989 dctx->stage = ZSTDds_getFrameHeaderSize;
3991 dctx->expected = cBlockSize;
3992 dctx->bType = bp.blockType;
3993 dctx->stage = ZSTDds_decompressBlock;
3997 case ZSTDds_decompressBlock:
4002 rSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
4005 rSize = ZSTDv07_copyRawBlock(dst, dstCapacity, src, srcSize);
4008 return ERROR(GENERIC); /* not yet handled */
4010 case bt_end : /* should never happen (filtered at phase 1) */
4014 return ERROR(GENERIC); /* impossible */
4016 dctx->stage = ZSTDds_decodeBlockHeader;
4017 dctx->expected = ZSTDv07_blockHeaderSize;
4018 dctx->previousDstEnd = (char*)dst + rSize;
4019 if (ZSTDv07_isError(rSize)) return rSize;
4020 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
4023 case ZSTDds_decodeSkippableHeader:
4024 { memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
4025 dctx->expected = MEM_readLE32(dctx->headerBuffer + 4);
4026 dctx->stage = ZSTDds_skipFrame;
4029 case ZSTDds_skipFrame:
4030 { dctx->expected = 0;
4031 dctx->stage = ZSTDds_getFrameHeaderSize;
4035 return ERROR(GENERIC); /* impossible */
4040 static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4042 dctx->dictEnd = dctx->previousDstEnd;
4043 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
4045 dctx->previousDstEnd = (const char*)dict + dictSize;
4049 static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx* dctx, const void* const dict, size_t const dictSize)
4051 const BYTE* dictPtr = (const BYTE*)dict;
4052 const BYTE* const dictEnd = dictPtr + dictSize;
4054 { size_t const hSize = HUFv07_readDTableX4(dctx->hufTable, dict, dictSize);
4055 if (HUFv07_isError(hSize)) return ERROR(dictionary_corrupted);
4059 { short offcodeNCount[MaxOff+1];
4060 U32 offcodeMaxValue=MaxOff, offcodeLog;
4061 size_t const offcodeHeaderSize = FSEv07_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
4062 if (FSEv07_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
4063 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
4064 { size_t const errorCode = FSEv07_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
4065 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4066 dictPtr += offcodeHeaderSize;
4069 { short matchlengthNCount[MaxML+1];
4070 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
4071 size_t const matchlengthHeaderSize = FSEv07_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
4072 if (FSEv07_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
4073 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
4074 { size_t const errorCode = FSEv07_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
4075 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4076 dictPtr += matchlengthHeaderSize;
4079 { short litlengthNCount[MaxLL+1];
4080 unsigned litlengthMaxValue = MaxLL, litlengthLog;
4081 size_t const litlengthHeaderSize = FSEv07_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
4082 if (FSEv07_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
4083 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
4084 { size_t const errorCode = FSEv07_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
4085 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4086 dictPtr += litlengthHeaderSize;
4089 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
4090 dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] == 0 || dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
4091 dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] == 0 || dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
4092 dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] == 0 || dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
4095 dctx->litEntropy = dctx->fseEntropy = 1;
4096 return dictPtr - (const BYTE*)dict;
4099 static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4101 if (dictSize < 8) return ZSTDv07_refDictContent(dctx, dict, dictSize);
4102 { U32 const magic = MEM_readLE32(dict);
4103 if (magic != ZSTDv07_DICT_MAGIC) {
4104 return ZSTDv07_refDictContent(dctx, dict, dictSize); /* pure content mode */
4106 dctx->dictID = MEM_readLE32((const char*)dict + 4);
4108 /* load entropy tables */
4109 dict = (const char*)dict + 8;
4111 { size_t const eSize = ZSTDv07_loadEntropy(dctx, dict, dictSize);
4112 if (ZSTDv07_isError(eSize)) return ERROR(dictionary_corrupted);
4113 dict = (const char*)dict + eSize;
4117 /* reference dictionary content */
4118 return ZSTDv07_refDictContent(dctx, dict, dictSize);
4122 size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4124 { size_t const errorCode = ZSTDv07_decompressBegin(dctx);
4125 if (ZSTDv07_isError(errorCode)) return errorCode; }
4127 if (dict && dictSize) {
4128 size_t const errorCode = ZSTDv07_decompress_insertDictionary(dctx, dict, dictSize);
4129 if (ZSTDv07_isError(errorCode)) return ERROR(dictionary_corrupted);
4136 struct ZSTDv07_DDict_s {
4139 ZSTDv07_DCtx* refContext;
4140 }; /* typedef'd tp ZSTDv07_CDict within zstd.h */
4142 static ZSTDv07_DDict* ZSTDv07_createDDict_advanced(const void* dict, size_t dictSize, ZSTDv07_customMem customMem)
4144 if (!customMem.customAlloc && !customMem.customFree)
4145 customMem = defaultCustomMem;
4147 if (!customMem.customAlloc || !customMem.customFree)
4150 { ZSTDv07_DDict* const ddict = (ZSTDv07_DDict*) customMem.customAlloc(customMem.opaque, sizeof(*ddict));
4151 void* const dictContent = customMem.customAlloc(customMem.opaque, dictSize);
4152 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx_advanced(customMem);
4154 if (!dictContent || !ddict || !dctx) {
4155 customMem.customFree(customMem.opaque, dictContent);
4156 customMem.customFree(customMem.opaque, ddict);
4157 customMem.customFree(customMem.opaque, dctx);
4161 memcpy(dictContent, dict, dictSize);
4162 { size_t const errorCode = ZSTDv07_decompressBegin_usingDict(dctx, dictContent, dictSize);
4163 if (ZSTDv07_isError(errorCode)) {
4164 customMem.customFree(customMem.opaque, dictContent);
4165 customMem.customFree(customMem.opaque, ddict);
4166 customMem.customFree(customMem.opaque, dctx);
4170 ddict->dict = dictContent;
4171 ddict->dictSize = dictSize;
4172 ddict->refContext = dctx;
4177 /*! ZSTDv07_createDDict() :
4178 * Create a digested dictionary, ready to start decompression without startup delay.
4179 * `dict` can be released after `ZSTDv07_DDict` creation */
4180 ZSTDv07_DDict* ZSTDv07_createDDict(const void* dict, size_t dictSize)
4182 ZSTDv07_customMem const allocator = { NULL, NULL, NULL };
4183 return ZSTDv07_createDDict_advanced(dict, dictSize, allocator);
4186 size_t ZSTDv07_freeDDict(ZSTDv07_DDict* ddict)
4188 ZSTDv07_freeFunction const cFree = ddict->refContext->customMem.customFree;
4189 void* const opaque = ddict->refContext->customMem.opaque;
4190 ZSTDv07_freeDCtx(ddict->refContext);
4191 cFree(opaque, ddict->dict);
4192 cFree(opaque, ddict);
4196 /*! ZSTDv07_decompress_usingDDict() :
4197 * Decompression using a pre-digested Dictionary
4198 * Use dictionary without significant overhead. */
4199 ZSTDLIBv07_API size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx* dctx,
4200 void* dst, size_t dstCapacity,
4201 const void* src, size_t srcSize,
4202 const ZSTDv07_DDict* ddict)
4204 return ZSTDv07_decompress_usingPreparedDCtx(dctx, ddict->refContext,
4209 Buffered version of Zstd compression library
4210 Copyright (C) 2015-2016, Yann Collet.
4212 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
4214 Redistribution and use in source and binary forms, with or without
4215 modification, are permitted provided that the following conditions are
4217 * Redistributions of source code must retain the above copyright
4218 notice, this list of conditions and the following disclaimer.
4219 * Redistributions in binary form must reproduce the above
4220 copyright notice, this list of conditions and the following disclaimer
4221 in the documentation and/or other materials provided with the
4223 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4224 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
4225 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
4226 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
4227 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4228 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
4229 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
4230 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
4231 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
4232 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
4233 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4235 You can contact the author at :
4236 - zstd homepage : https://facebook.github.io/zstd/
4241 /*-***************************************************************************
4242 * Streaming decompression howto
4244 * A ZBUFFv07_DCtx object is required to track streaming operations.
4245 * Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources.
4246 * Use ZBUFFv07_decompressInit() to start a new decompression operation,
4247 * or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary.
4248 * Note that ZBUFFv07_DCtx objects can be re-init multiple times.
4250 * Use ZBUFFv07_decompressContinue() repetitively to consume your input.
4251 * *srcSizePtr and *dstCapacityPtr can be any size.
4252 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
4253 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
4254 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
4255 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
4256 * or 0 when a frame is completely decoded,
4257 * or an error code, which can be tested using ZBUFFv07_isError().
4259 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize()
4260 * output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
4261 * input : ZBUFFv07_recommendedDInSize == 128KB + 3;
4262 * just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
4263 * *******************************************************************************/
4265 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
4266 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv07_dStage;
4268 /* *** Resource management *** */
4269 struct ZBUFFv07_DCtx_s {
4271 ZSTDv07_frameParams fParams;
4272 ZBUFFv07_dStage stage;
4281 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
4283 ZSTDv07_customMem customMem;
4284 }; /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */
4286 ZSTDLIBv07_API ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem);
4288 ZBUFFv07_DCtx* ZBUFFv07_createDCtx(void)
4290 return ZBUFFv07_createDCtx_advanced(defaultCustomMem);
4293 ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem)
4297 if (!customMem.customAlloc && !customMem.customFree)
4298 customMem = defaultCustomMem;
4300 if (!customMem.customAlloc || !customMem.customFree)
4303 zbd = (ZBUFFv07_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFFv07_DCtx));
4304 if (zbd==NULL) return NULL;
4305 memset(zbd, 0, sizeof(ZBUFFv07_DCtx));
4306 memcpy(&zbd->customMem, &customMem, sizeof(ZSTDv07_customMem));
4307 zbd->zd = ZSTDv07_createDCtx_advanced(customMem);
4308 if (zbd->zd == NULL) { ZBUFFv07_freeDCtx(zbd); return NULL; }
4309 zbd->stage = ZBUFFds_init;
4313 size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx* zbd)
4315 if (zbd==NULL) return 0; /* support free on null */
4316 ZSTDv07_freeDCtx(zbd->zd);
4317 if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4318 if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4319 zbd->customMem.customFree(zbd->customMem.opaque, zbd);
4324 /* *** Initialization *** */
4326 size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx* zbd, const void* dict, size_t dictSize)
4328 zbd->stage = ZBUFFds_loadHeader;
4329 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
4330 return ZSTDv07_decompressBegin_usingDict(zbd->zd, dict, dictSize);
4333 size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx* zbd)
4335 return ZBUFFv07_decompressInitDictionary(zbd, NULL, 0);
4339 /* internal util function */
4340 MEM_STATIC size_t ZBUFFv07_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
4342 size_t const length = MIN(dstCapacity, srcSize);
4344 memcpy(dst, src, length);
4350 /* *** Decompression *** */
4352 size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx* zbd,
4353 void* dst, size_t* dstCapacityPtr,
4354 const void* src, size_t* srcSizePtr)
4356 const char* const istart = (const char*)src;
4357 const char* const iend = istart + *srcSizePtr;
4358 const char* ip = istart;
4359 char* const ostart = (char*)dst;
4360 char* const oend = ostart + *dstCapacityPtr;
4368 return ERROR(init_missing);
4370 case ZBUFFds_loadHeader :
4371 { size_t const hSize = ZSTDv07_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
4372 if (ZSTDv07_isError(hSize)) return hSize;
4374 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */
4375 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */
4377 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
4378 zbd->lhSize += iend-ip;
4379 *dstCapacityPtr = 0;
4380 return (hSize - zbd->lhSize) + ZSTDv07_blockHeaderSize; /* remaining header bytes + next block header */
4382 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
4386 /* Consume header */
4387 { size_t const h1Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv07_frameHeaderSize_min */
4388 size_t const h1Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4389 if (ZSTDv07_isError(h1Result)) return h1Result;
4390 if (h1Size < zbd->lhSize) { /* long header */
4391 size_t const h2Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4392 size_t const h2Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4393 if (ZSTDv07_isError(h2Result)) return h2Result;
4396 zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN);
4398 /* Frame header instruct buffer sizes */
4399 { size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX);
4400 zbd->blockSize = blockSize;
4401 if (zbd->inBuffSize < blockSize) {
4402 zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4403 zbd->inBuffSize = blockSize;
4404 zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize);
4405 if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4407 { size_t const neededOutSize = zbd->fParams.windowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
4408 if (zbd->outBuffSize < neededOutSize) {
4409 zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4410 zbd->outBuffSize = neededOutSize;
4411 zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize);
4412 if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4414 zbd->stage = ZBUFFds_read;
4418 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4419 if (neededInSize==0) { /* end of frame */
4420 zbd->stage = ZBUFFds_init;
4424 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
4425 const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4426 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4427 zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart),
4429 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4431 if (!decodedSize && !isSkipFrame) break; /* this was just a header */
4432 zbd->outEnd = zbd->outStart + decodedSize;
4433 zbd->stage = ZBUFFds_flush;
4436 if (ip==iend) { notDone = 0; break; } /* no more input */
4437 zbd->stage = ZBUFFds_load;
4441 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4442 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */
4444 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */
4445 loadedSize = ZBUFFv07_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4447 zbd->inPos += loadedSize;
4448 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
4450 /* decode loaded input */
4451 { const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4452 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4453 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4454 zbd->inBuff, neededInSize);
4455 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4456 zbd->inPos = 0; /* input is consumed */
4457 if (!decodedSize && !isSkipFrame) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */
4458 zbd->outEnd = zbd->outStart + decodedSize;
4459 zbd->stage = ZBUFFds_flush;
4466 { size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4467 size_t const flushedSize = ZBUFFv07_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4469 zbd->outStart += flushedSize;
4470 if (flushedSize == toFlushSize) {
4471 zbd->stage = ZBUFFds_read;
4472 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4473 zbd->outStart = zbd->outEnd = 0;
4476 /* cannot flush everything */
4480 default: return ERROR(GENERIC); /* impossible */
4484 *srcSizePtr = ip-istart;
4485 *dstCapacityPtr = op-ostart;
4486 { size_t nextSrcSizeHint = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4487 nextSrcSizeHint -= zbd->inPos; /* already loaded*/
4488 return nextSrcSizeHint;
4494 /* *************************************
4496 ***************************************/
4497 size_t ZBUFFv07_recommendedDInSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + ZSTDv07_blockHeaderSize /* block header size*/ ; }
4498 size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX; }