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/compiler.h"
28 #include "../common/error_private.h"
31 #ifdef ZSTDv07_STATIC_LINKING_ONLY
33 /* ====================================================================================
34 * The definitions in this section are considered experimental.
35 * They should never be used with a dynamic library, as they may change in the future.
36 * They are provided for advanced usages.
37 * Use them only in association with static linking.
38 * ==================================================================================== */
41 #define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U
43 #define ZSTDv07_WINDOWLOG_MAX_32 25
44 #define ZSTDv07_WINDOWLOG_MAX_64 27
45 #define ZSTDv07_WINDOWLOG_MAX ((U32)(MEM_32bits() ? ZSTDv07_WINDOWLOG_MAX_32 : ZSTDv07_WINDOWLOG_MAX_64))
46 #define ZSTDv07_WINDOWLOG_MIN 18
47 #define ZSTDv07_CHAINLOG_MAX (ZSTDv07_WINDOWLOG_MAX+1)
48 #define ZSTDv07_CHAINLOG_MIN 4
49 #define ZSTDv07_HASHLOG_MAX ZSTDv07_WINDOWLOG_MAX
50 #define ZSTDv07_HASHLOG_MIN 12
51 #define ZSTDv07_HASHLOG3_MAX 17
52 #define ZSTDv07_SEARCHLOG_MAX (ZSTDv07_WINDOWLOG_MAX-1)
53 #define ZSTDv07_SEARCHLOG_MIN 1
54 #define ZSTDv07_SEARCHLENGTH_MAX 7
55 #define ZSTDv07_SEARCHLENGTH_MIN 3
56 #define ZSTDv07_TARGETLENGTH_MIN 4
57 #define ZSTDv07_TARGETLENGTH_MAX 999
59 #define ZSTDv07_FRAMEHEADERSIZE_MAX 18 /* for static allocation */
60 static const size_t ZSTDv07_frameHeaderSize_min = 5;
61 static const size_t ZSTDv07_frameHeaderSize_max = ZSTDv07_FRAMEHEADERSIZE_MAX;
62 static const size_t ZSTDv07_skippableHeaderSize = 8; /* magic number + skippable frame length */
65 /* custom memory allocation functions */
66 typedef void* (*ZSTDv07_allocFunction) (void* opaque, size_t size);
67 typedef void (*ZSTDv07_freeFunction) (void* opaque, void* address);
68 typedef struct { ZSTDv07_allocFunction customAlloc; ZSTDv07_freeFunction customFree; void* opaque; } ZSTDv07_customMem;
71 /*--- Advanced Decompression functions ---*/
73 /*! ZSTDv07_estimateDCtxSize() :
74 * Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */
75 ZSTDLIBv07_API size_t ZSTDv07_estimateDCtxSize(void);
77 /*! ZSTDv07_createDCtx_advanced() :
78 * Create a ZSTD decompression context using external alloc and free functions */
79 ZSTDLIBv07_API ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem);
81 /*! ZSTDv07_sizeofDCtx() :
82 * Gives the amount of memory used by a given ZSTDv07_DCtx */
83 ZSTDLIBv07_API size_t ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx* dctx);
86 /* ******************************************************************
87 * Buffer-less streaming functions (synchronous mode)
88 ********************************************************************/
90 ZSTDLIBv07_API size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx);
91 ZSTDLIBv07_API size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize);
92 ZSTDLIBv07_API void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* preparedDCtx);
94 ZSTDLIBv07_API size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx);
95 ZSTDLIBv07_API size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
98 Buffer-less streaming decompression (synchronous mode)
100 A ZSTDv07_DCtx object is required to track streaming operations.
101 Use ZSTDv07_createDCtx() / ZSTDv07_freeDCtx() to manage it.
102 A ZSTDv07_DCtx object can be re-used multiple times.
104 First optional operation is to retrieve frame parameters, using ZSTDv07_getFrameParams(), which doesn't consume the input.
105 It can provide the minimum size of rolling buffer required to properly decompress data (`windowSize`),
106 and optionally the final size of uncompressed content.
107 (Note : content size is an optional info that may not be present. 0 means : content size unknown)
108 Frame parameters are extracted from the beginning of compressed frame.
109 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)
110 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
111 Result : 0 when successful, it means the ZSTDv07_frameParams structure has been filled.
112 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
113 errorCode, which can be tested using ZSTDv07_isError()
115 Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().
116 Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().
118 Then use ZSTDv07_nextSrcSizeToDecompress() and ZSTDv07_decompressContinue() alternatively.
119 ZSTDv07_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv07_decompressContinue().
120 ZSTDv07_decompressContinue() requires this exact amount of bytes, or it will fail.
122 @result of ZSTDv07_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity).
123 It can be zero, which is not an error; it just means ZSTDv07_decompressContinue() has decoded some header.
125 ZSTDv07_decompressContinue() needs previous data blocks during decompression, up to `windowSize`.
126 They should preferably be located contiguously, prior to current block.
127 Alternatively, a round buffer of sufficient size is also possible. Sufficient size is determined by frame parameters.
128 ZSTDv07_decompressContinue() is very sensitive to contiguity,
129 if 2 blocks don't follow each other, make sure that either the compressor breaks contiguity at the same place,
130 or that previous contiguous segment is large enough to properly handle maximum back-reference.
132 A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.
133 Context can then be reset to start a new decompression.
136 == Special case : skippable frames ==
138 Skippable frames allow the integration of user-defined data into a flow of concatenated frames.
139 Skippable frames will be ignored (skipped) by a decompressor. The format of skippable frame is following:
140 a) Skippable frame ID - 4 Bytes, Little endian format, any value from 0x184D2A50 to 0x184D2A5F
141 b) Frame Size - 4 Bytes, Little endian format, unsigned 32-bits
142 c) Frame Content - any content (User Data) of length equal to Frame Size
143 For skippable frames ZSTDv07_decompressContinue() always returns 0.
144 For skippable frames ZSTDv07_getFrameParams() returns fparamsPtr->windowLog==0 what means that a frame is skippable.
145 It also returns Frame Size as fparamsPtr->frameContentSize.
149 /* **************************************
151 ****************************************/
152 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
153 Frame metadata cost is typically ~18 bytes, which can be non-negligible for very small blocks (< 100 bytes).
154 User will have to take in charge required information to regenerate data, such as compressed and content sizes.
156 A few rules to respect :
157 - Compressing and decompressing require a context structure
158 + Use ZSTDv07_createCCtx() and ZSTDv07_createDCtx()
159 - It is necessary to init context before starting
160 + compression : ZSTDv07_compressBegin()
161 + decompression : ZSTDv07_decompressBegin()
162 + variants _usingDict() are also allowed
163 + copyCCtx() and copyDCtx() work too
164 - Block size is limited, it must be <= ZSTDv07_getBlockSizeMax()
165 + If you need to compress more, cut data into multiple blocks
166 + Consider using the regular ZSTDv07_compress() instead, as frame metadata costs become negligible when source size is large.
167 - When a block is considered not compressible enough, ZSTDv07_compressBlock() result will be zero.
168 In which case, nothing is produced into `dst`.
169 + User must test for such outcome and deal directly with uncompressed data
170 + ZSTDv07_decompressBlock() doesn't accept uncompressed data as input !!!
171 + In case of multiple successive blocks, decoder must be informed of uncompressed block existence to follow proper history.
172 Use ZSTDv07_insertBlock() in such a case.
175 #define ZSTDv07_BLOCKSIZE_ABSOLUTEMAX (128 * 1024) /* define, for static allocation */
176 ZSTDLIBv07_API size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
177 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize); /**< insert block into `dctx` history. Useful for uncompressed blocks */
180 #endif /* ZSTDv07_STATIC_LINKING_ONLY */
183 /* ******************************************************************
185 low-level memory access routines
186 Copyright (C) 2013-2015, Yann Collet.
188 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
190 Redistribution and use in source and binary forms, with or without
191 modification, are permitted provided that the following conditions are
194 * Redistributions of source code must retain the above copyright
195 notice, this list of conditions and the following disclaimer.
196 * Redistributions in binary form must reproduce the above
197 copyright notice, this list of conditions and the following disclaimer
198 in the documentation and/or other materials provided with the
201 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
202 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
203 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
204 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
205 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
206 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
207 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
208 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
209 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
210 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
211 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
213 You can contact the author at :
214 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
215 - Public forum : https://groups.google.com/forum/#!forum/lz4c
216 ****************************************************************** */
220 #if defined (__cplusplus)
224 /*-****************************************
226 ******************************************/
227 #if defined(_MSC_VER) /* Visual Studio */
228 # include <stdlib.h> /* _byteswap_ulong */
229 # include <intrin.h> /* _byteswap_* */
233 /*-**************************************************************
235 *****************************************************************/
236 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
238 # include <inttypes.h>
240 # include <stdint.h> /* intptr_t */
242 typedef uint8_t BYTE;
243 typedef uint16_t U16;
245 typedef uint32_t U32;
247 typedef uint64_t U64;
250 typedef unsigned char BYTE;
251 typedef unsigned short U16;
252 typedef signed short S16;
253 typedef unsigned int U32;
254 typedef signed int S32;
255 typedef unsigned long long U64;
256 typedef signed long long S64;
260 /*-**************************************************************
262 *****************************************************************/
264 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
265 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
267 MEM_STATIC unsigned MEM_isLittleEndian(void)
269 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
273 MEM_STATIC U16 MEM_read16(const void* memPtr)
275 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
278 MEM_STATIC U32 MEM_read32(const void* memPtr)
280 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
283 MEM_STATIC U64 MEM_read64(const void* memPtr)
285 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
288 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
290 memcpy(memPtr, &value, sizeof(value));
293 MEM_STATIC U32 MEM_swap32(U32 in)
295 #if defined(_MSC_VER) /* Visual Studio */
296 return _byteswap_ulong(in);
297 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
298 return __builtin_bswap32(in);
300 return ((in << 24) & 0xff000000 ) |
301 ((in << 8) & 0x00ff0000 ) |
302 ((in >> 8) & 0x0000ff00 ) |
303 ((in >> 24) & 0x000000ff );
307 MEM_STATIC U64 MEM_swap64(U64 in)
309 #if defined(_MSC_VER) /* Visual Studio */
310 return _byteswap_uint64(in);
311 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
312 return __builtin_bswap64(in);
314 return ((in << 56) & 0xff00000000000000ULL) |
315 ((in << 40) & 0x00ff000000000000ULL) |
316 ((in << 24) & 0x0000ff0000000000ULL) |
317 ((in << 8) & 0x000000ff00000000ULL) |
318 ((in >> 8) & 0x00000000ff000000ULL) |
319 ((in >> 24) & 0x0000000000ff0000ULL) |
320 ((in >> 40) & 0x000000000000ff00ULL) |
321 ((in >> 56) & 0x00000000000000ffULL);
326 /*=== Little endian r/w ===*/
328 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
330 if (MEM_isLittleEndian())
331 return MEM_read16(memPtr);
333 const BYTE* p = (const BYTE*)memPtr;
334 return (U16)(p[0] + (p[1]<<8));
338 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
340 if (MEM_isLittleEndian()) {
341 MEM_write16(memPtr, val);
343 BYTE* p = (BYTE*)memPtr;
345 p[1] = (BYTE)(val>>8);
349 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
351 if (MEM_isLittleEndian())
352 return MEM_read32(memPtr);
354 return MEM_swap32(MEM_read32(memPtr));
358 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
360 if (MEM_isLittleEndian())
361 return MEM_read64(memPtr);
363 return MEM_swap64(MEM_read64(memPtr));
366 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
369 return (size_t)MEM_readLE32(memPtr);
371 return (size_t)MEM_readLE64(memPtr);
376 #if defined (__cplusplus)
380 #endif /* MEM_H_MODULE */
381 /* ******************************************************************
384 header file (to include)
385 Copyright (C) 2013-2016, Yann Collet.
387 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
389 Redistribution and use in source and binary forms, with or without
390 modification, are permitted provided that the following conditions are
393 * Redistributions of source code must retain the above copyright
394 notice, this list of conditions and the following disclaimer.
395 * Redistributions in binary form must reproduce the above
396 copyright notice, this list of conditions and the following disclaimer
397 in the documentation and/or other materials provided with the
400 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
401 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
402 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
403 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
404 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
405 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
406 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
407 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
408 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
409 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
410 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
412 You can contact the author at :
413 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
414 ****************************************************************** */
415 #ifndef BITSTREAM_H_MODULE
416 #define BITSTREAM_H_MODULE
418 #if defined (__cplusplus)
424 * This API consists of small unitary functions, which must be inlined for best performance.
425 * Since link-time-optimization is not available for all compilers,
426 * these functions are defined into a .h to be included.
430 /*=========================================
432 =========================================*/
433 #if defined(__BMI__) && defined(__GNUC__)
434 # include <immintrin.h> /* support for bextr (experimental) */
437 /*-********************************************
438 * bitStream decoding API (read backward)
439 **********************************************/
443 unsigned bitsConsumed;
448 typedef enum { BITv07_DStream_unfinished = 0,
449 BITv07_DStream_endOfBuffer = 1,
450 BITv07_DStream_completed = 2,
451 BITv07_DStream_overflow = 3 } BITv07_DStream_status; /* result of BITv07_reloadDStream() */
452 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
454 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
455 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, unsigned nbBits);
456 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD);
457 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* bitD);
461 /*-****************************************
463 ******************************************/
464 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, unsigned nbBits);
465 /* faster, but works only if nbBits >= 1 */
469 /*-**************************************************************
471 ****************************************************************/
472 MEM_STATIC unsigned BITv07_highbit32 (U32 val)
474 # if defined(_MSC_VER) /* Visual */
476 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
477 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
478 return __builtin_clz (val) ^ 31;
479 # else /* Software version */
480 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 };
487 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
493 /*-********************************************************
495 **********************************************************/
496 /*! BITv07_initDStream() :
497 * Initialize a BITv07_DStream_t.
498 * `bitD` : a pointer to an already allocated BITv07_DStream_t structure.
499 * `srcSize` must be the *exact* size of the bitStream, in bytes.
500 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
502 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
504 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
506 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
507 bitD->start = (const char*)srcBuffer;
508 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
509 bitD->bitContainer = MEM_readLEST(bitD->ptr);
510 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
511 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
512 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
514 bitD->start = (const char*)srcBuffer;
515 bitD->ptr = bitD->start;
516 bitD->bitContainer = *(const BYTE*)(bitD->start);
519 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
520 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
521 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
522 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
523 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
524 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */
527 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
528 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
529 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
530 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
537 MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits)
539 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
540 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
543 /*! BITv07_lookBitsFast() :
544 * unsafe version; only works if nbBits >= 1 */
545 MEM_STATIC size_t BITv07_lookBitsFast(const BITv07_DStream_t* bitD, U32 nbBits)
547 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
548 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
551 MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits)
553 bitD->bitsConsumed += nbBits;
556 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits)
558 size_t const value = BITv07_lookBits(bitD, nbBits);
559 BITv07_skipBits(bitD, nbBits);
563 /*! BITv07_readBitsFast() :
564 * unsafe version; only works if nbBits >= 1 */
565 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, U32 nbBits)
567 size_t const value = BITv07_lookBitsFast(bitD, nbBits);
568 BITv07_skipBits(bitD, nbBits);
572 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD)
574 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */
575 return BITv07_DStream_overflow;
577 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
578 bitD->ptr -= bitD->bitsConsumed >> 3;
579 bitD->bitsConsumed &= 7;
580 bitD->bitContainer = MEM_readLEST(bitD->ptr);
581 return BITv07_DStream_unfinished;
583 if (bitD->ptr == bitD->start) {
584 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv07_DStream_endOfBuffer;
585 return BITv07_DStream_completed;
587 { U32 nbBytes = bitD->bitsConsumed >> 3;
588 BITv07_DStream_status result = BITv07_DStream_unfinished;
589 if (bitD->ptr - nbBytes < bitD->start) {
590 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
591 result = BITv07_DStream_endOfBuffer;
593 bitD->ptr -= nbBytes;
594 bitD->bitsConsumed -= nbBytes*8;
595 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
600 /*! BITv07_endOfDStream() :
601 * @return Tells if DStream has exactly reached its end (all bits consumed).
603 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* DStream)
605 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
608 #if defined (__cplusplus)
612 #endif /* BITSTREAM_H_MODULE */
613 /* ******************************************************************
614 FSE : Finite State Entropy codec
615 Public Prototypes declaration
616 Copyright (C) 2013-2016, Yann Collet.
618 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
620 Redistribution and use in source and binary forms, with or without
621 modification, are permitted provided that the following conditions are
624 * Redistributions of source code must retain the above copyright
625 notice, this list of conditions and the following disclaimer.
626 * Redistributions in binary form must reproduce the above
627 copyright notice, this list of conditions and the following disclaimer
628 in the documentation and/or other materials provided with the
631 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
632 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
633 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
634 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
635 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
636 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
637 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
638 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
639 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
640 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
641 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
643 You can contact the author at :
644 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
645 ****************************************************************** */
649 #if defined (__cplusplus)
655 /*-****************************************
656 * FSE simple functions
657 ******************************************/
659 /*! FSEv07_decompress():
660 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
661 into already allocated destination buffer 'dst', of size 'dstCapacity'.
662 @return : size of regenerated data (<= maxDstSize),
663 or an error code, which can be tested using FSEv07_isError() .
665 ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!
666 Why ? : making this distinction requires a header.
667 Header management is intentionally delegated to the user layer, which can better manage special cases.
669 size_t FSEv07_decompress(void* dst, size_t dstCapacity,
670 const void* cSrc, size_t cSrcSize);
673 /* Error Management */
674 unsigned FSEv07_isError(size_t code); /* tells if a return value is an error code */
675 const char* FSEv07_getErrorName(size_t code); /* provides error code string (useful for debugging) */
678 /*-*****************************************
680 ******************************************/
682 FSEv07_decompress() does the following:
683 1. read normalized counters with readNCount()
684 2. build decoding table 'DTable' from normalized counters
685 3. decode the data stream using decoding table 'DTable'
687 The following API allows targeting specific sub-functions for advanced tasks.
688 For example, it's possible to compress several blocks using the same 'CTable',
689 or to save and provide normalized distribution using external method.
693 /* *** DECOMPRESSION *** */
695 /*! FSEv07_readNCount():
696 Read compactly saved 'normalizedCounter' from 'rBuffer'.
697 @return : size read from 'rBuffer',
698 or an errorCode, which can be tested using FSEv07_isError().
699 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
700 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
702 /*! Constructor and Destructor of FSEv07_DTable.
703 Note that its size depends on 'tableLog' */
704 typedef unsigned FSEv07_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
705 FSEv07_DTable* FSEv07_createDTable(unsigned tableLog);
706 void FSEv07_freeDTable(FSEv07_DTable* dt);
708 /*! FSEv07_buildDTable():
709 Builds 'dt', which must be already allocated, using FSEv07_createDTable().
710 return : 0, or an errorCode, which can be tested using FSEv07_isError() */
711 size_t FSEv07_buildDTable (FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
713 /*! FSEv07_decompress_usingDTable():
714 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
715 into `dst` which must be already allocated.
716 @return : size of regenerated data (necessarily <= `dstCapacity`),
717 or an errorCode, which can be tested using FSEv07_isError() */
718 size_t FSEv07_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv07_DTable* dt);
723 (Note : these functions only decompress FSE-compressed blocks.
724 If block is uncompressed, use memcpy() instead
725 If block is a single repeated byte, use memset() instead )
727 The first step is to obtain the normalized frequencies of symbols.
728 This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().
729 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
730 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
731 or size the table to handle worst case situations (typically 256).
732 FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
733 The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.
734 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
735 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
737 The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.
738 This is performed by the function FSEv07_buildDTable().
739 The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().
740 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
742 `FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().
743 `cSrcSize` must be strictly correct, otherwise decompression will fail.
744 FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
745 If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)
749 #ifdef FSEv07_STATIC_LINKING_ONLY
752 /* *****************************************
754 *******************************************/
755 /* FSE buffer bounds */
756 #define FSEv07_NCOUNTBOUND 512
757 #define FSEv07_BLOCKBOUND(size) (size + (size>>7))
759 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
760 #define FSEv07_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
763 /* *****************************************
765 *******************************************/
766 size_t FSEv07_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
767 /**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
769 unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus);
770 /**< same as FSEv07_optimalTableLog(), which used `minus==2` */
772 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits);
773 /**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
775 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, unsigned char symbolValue);
776 /**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */
780 /* *****************************************
781 * FSE symbol decompression API
782 *******************************************/
786 const void* table; /* precise table may vary, depending on U16 */
790 static void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt);
792 static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
796 /* *****************************************
798 *******************************************/
799 static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
800 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
803 /* ====== Decompression ====== */
808 } FSEv07_DTableHeader; /* sizeof U32 */
812 unsigned short newState;
813 unsigned char symbol;
814 unsigned char nbBits;
815 } FSEv07_decode_t; /* size == U32 */
817 MEM_STATIC void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt)
819 const void* ptr = dt;
820 const FSEv07_DTableHeader* const DTableH = (const FSEv07_DTableHeader*)ptr;
821 DStatePtr->state = BITv07_readBits(bitD, DTableH->tableLog);
822 BITv07_reloadDStream(bitD);
823 DStatePtr->table = dt + 1;
826 MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr)
828 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
832 MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
834 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
835 U32 const nbBits = DInfo.nbBits;
836 size_t const lowBits = BITv07_readBits(bitD, nbBits);
837 DStatePtr->state = DInfo.newState + lowBits;
840 MEM_STATIC BYTE FSEv07_decodeSymbol(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 BYTE const symbol = DInfo.symbol;
845 size_t const lowBits = BITv07_readBits(bitD, nbBits);
847 DStatePtr->state = DInfo.newState + lowBits;
851 /*! FSEv07_decodeSymbolFast() :
852 unsafe, only works if no symbol has a probability > 50% */
853 MEM_STATIC BYTE FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
855 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
856 U32 const nbBits = DInfo.nbBits;
857 BYTE const symbol = DInfo.symbol;
858 size_t const lowBits = BITv07_readBitsFast(bitD, nbBits);
860 DStatePtr->state = DInfo.newState + lowBits;
866 #ifndef FSEv07_COMMONDEFS_ONLY
868 /* **************************************************************
870 ****************************************************************/
872 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
873 * Increasing memory usage improves compression ratio
874 * Reduced memory usage can improve speed, due to cache effect
875 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
876 #define FSEv07_MAX_MEMORY_USAGE 14
877 #define FSEv07_DEFAULT_MEMORY_USAGE 13
879 /*!FSEv07_MAX_SYMBOL_VALUE :
880 * Maximum symbol value authorized.
881 * Required for proper stack allocation */
882 #define FSEv07_MAX_SYMBOL_VALUE 255
885 /* **************************************************************
886 * template functions type & suffix
887 ****************************************************************/
888 #define FSEv07_FUNCTION_TYPE BYTE
889 #define FSEv07_FUNCTION_EXTENSION
890 #define FSEv07_DECODE_TYPE FSEv07_decode_t
893 #endif /* !FSEv07_COMMONDEFS_ONLY */
896 /* ***************************************************************
898 *****************************************************************/
899 #define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2)
900 #define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)
901 #define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)
902 #define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)
903 #define FSEv07_MIN_TABLELOG 5
905 #define FSEv07_TABLELOG_ABSOLUTE_MAX 15
906 #if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX
907 # error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"
910 #define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
913 #endif /* FSEv07_STATIC_LINKING_ONLY */
916 #if defined (__cplusplus)
920 #endif /* FSEv07_H */
921 /* ******************************************************************
922 Huffman coder, part of New Generation Entropy library
924 Copyright (C) 2013-2016, Yann Collet.
926 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
928 Redistribution and use in source and binary forms, with or without
929 modification, are permitted provided that the following conditions are
932 * Redistributions of source code must retain the above copyright
933 notice, this list of conditions and the following disclaimer.
934 * Redistributions in binary form must reproduce the above
935 copyright notice, this list of conditions and the following disclaimer
936 in the documentation and/or other materials provided with the
939 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
940 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
941 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
942 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
943 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
944 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
945 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
946 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
947 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
948 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
949 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
951 You can contact the author at :
952 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
953 ****************************************************************** */
954 #ifndef HUFv07_H_298734234
955 #define HUFv07_H_298734234
957 #if defined (__cplusplus)
963 /* *** simple functions *** */
965 HUFv07_decompress() :
966 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
967 into already allocated buffer 'dst', of minimum size 'dstSize'.
968 `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
969 Note : in contrast with FSE, HUFv07_decompress can regenerate
970 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
971 because it knows size to regenerate.
972 @return : size of regenerated data (== dstSize),
973 or an error code, which can be tested using HUFv07_isError()
975 size_t HUFv07_decompress(void* dst, size_t dstSize,
976 const void* cSrc, size_t cSrcSize);
979 /* ****************************************
981 ******************************************/
982 #define HUFv07_BLOCKSIZE_MAX (128 * 1024)
984 /* Error Management */
985 unsigned HUFv07_isError(size_t code); /**< tells if a return value is an error code */
986 const char* HUFv07_getErrorName(size_t code); /**< provides error code string (useful for debugging) */
989 /* *** Advanced function *** */
992 #ifdef HUFv07_STATIC_LINKING_ONLY
995 /* *** Constants *** */
996 #define HUFv07_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */
997 #define HUFv07_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */
998 #define HUFv07_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */
999 #define HUFv07_SYMBOLVALUE_MAX 255
1000 #if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX)
1001 # error "HUFv07_TABLELOG_MAX is too large !"
1005 /* ****************************************
1007 ******************************************/
1008 /* HUF buffer bounds */
1009 #define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1011 /* static allocation of HUF's DTable */
1012 typedef U32 HUFv07_DTable;
1013 #define HUFv07_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog)))
1014 #define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1015 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
1016 #define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1017 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
1020 /* ****************************************
1021 * Advanced decompression functions
1022 ******************************************/
1023 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1024 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1026 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< decodes RLE and uncompressed */
1027 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 */
1028 size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1029 size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1031 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
1032 size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1033 size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1036 /* ****************************************
1038 ******************************************/
1040 The following API allows targeting specific sub-functions for advanced tasks.
1041 For example, it's possible to compress several blocks using the same 'CTable',
1042 or to save and regenerate 'CTable' using external methods.
1044 /* FSEv07_count() : find it within "fse.h" */
1046 /*! HUFv07_readStats() :
1047 Read compact Huffman tree, saved by HUFv07_writeCTable().
1048 `huffWeight` is destination buffer.
1049 @return : size read from `src` , or an error Code .
1050 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */
1051 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1052 U32* nbSymbolsPtr, U32* tableLogPtr,
1053 const void* src, size_t srcSize);
1057 HUFv07_decompress() does the following:
1058 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1059 2. build Huffman table from save, using HUFv07_readDTableXn()
1060 3. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable
1063 /** HUFv07_selectDecoder() :
1064 * Tells which decoder is likely to decode faster,
1065 * based on a set of pre-determined metrics.
1066 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
1067 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
1068 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize);
1070 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1071 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1073 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1074 size_t HUFv07_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1075 size_t HUFv07_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1078 /* single stream variants */
1079 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1080 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1082 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1083 size_t HUFv07_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1084 size_t HUFv07_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1087 #endif /* HUFv07_STATIC_LINKING_ONLY */
1090 #if defined (__cplusplus)
1094 #endif /* HUFv07_H_298734234 */
1096 Common functions of New Generation Entropy library
1097 Copyright (C) 2016, Yann Collet.
1099 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1101 Redistribution and use in source and binary forms, with or without
1102 modification, are permitted provided that the following conditions are
1105 * Redistributions of source code must retain the above copyright
1106 notice, this list of conditions and the following disclaimer.
1107 * Redistributions in binary form must reproduce the above
1108 copyright notice, this list of conditions and the following disclaimer
1109 in the documentation and/or other materials provided with the
1112 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1113 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1114 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1115 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1116 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1117 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1118 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1119 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1120 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1121 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1122 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1124 You can contact the author at :
1125 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1126 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1127 *************************************************************************** */
1131 /*-****************************************
1132 * FSE Error Management
1133 ******************************************/
1134 unsigned FSEv07_isError(size_t code) { return ERR_isError(code); }
1136 const char* FSEv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1139 /* **************************************************************
1140 * HUF Error Management
1141 ****************************************************************/
1142 unsigned HUFv07_isError(size_t code) { return ERR_isError(code); }
1144 const char* HUFv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1147 /*-**************************************************************
1148 * FSE NCount encoding-decoding
1149 ****************************************************************/
1150 static short FSEv07_abs(short a) { return (short)(a<0 ? -a : a); }
1152 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1153 const void* headerBuffer, size_t hbSize)
1155 const BYTE* const istart = (const BYTE*) headerBuffer;
1156 const BYTE* const iend = istart + hbSize;
1157 const BYTE* ip = istart;
1163 unsigned charnum = 0;
1166 if (hbSize < 4) return ERROR(srcSize_wrong);
1167 bitStream = MEM_readLE32(ip);
1168 nbBits = (bitStream & 0xF) + FSEv07_MIN_TABLELOG; /* extract tableLog */
1169 if (nbBits > FSEv07_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1172 *tableLogPtr = nbBits;
1173 remaining = (1<<nbBits)+1;
1174 threshold = 1<<nbBits;
1177 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1179 unsigned n0 = charnum;
1180 while ((bitStream & 0xFFFF) == 0xFFFF) {
1184 bitStream = MEM_readLE32(ip) >> bitCount;
1189 while ((bitStream & 3) == 3) {
1194 n0 += bitStream & 3;
1196 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1197 while (charnum < n0) normalizedCounter[charnum++] = 0;
1198 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1201 bitStream = MEM_readLE32(ip) >> bitCount;
1206 { short const max = (short)((2*threshold-1)-remaining);
1209 if ((bitStream & (threshold-1)) < (U32)max) {
1210 count = (short)(bitStream & (threshold-1));
1211 bitCount += nbBits-1;
1213 count = (short)(bitStream & (2*threshold-1));
1214 if (count >= threshold) count -= max;
1218 count--; /* extra accuracy */
1219 remaining -= FSEv07_abs(count);
1220 normalizedCounter[charnum++] = count;
1222 while (remaining < threshold) {
1227 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1231 bitCount -= (int)(8 * (iend - 4 - ip));
1234 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1235 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1236 if (remaining != 1) return ERROR(GENERIC);
1237 *maxSVPtr = charnum-1;
1239 ip += (bitCount+7)>>3;
1240 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1245 /*! HUFv07_readStats() :
1246 Read compact Huffman tree, saved by HUFv07_writeCTable().
1247 `huffWeight` is destination buffer.
1248 @return : size read from `src` , or an error Code .
1249 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() .
1251 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1252 U32* nbSymbolsPtr, U32* tableLogPtr,
1253 const void* src, size_t srcSize)
1256 const BYTE* ip = (const BYTE*) src;
1260 if (!srcSize) return ERROR(srcSize_wrong);
1262 /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */
1264 if (iSize >= 128) { /* special header */
1265 if (iSize >= (242)) { /* RLE */
1266 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1267 oSize = l[iSize-242];
1268 memset(huffWeight, 1, hwSize);
1271 else { /* Incompressible */
1272 oSize = iSize - 127;
1273 iSize = ((oSize+1)/2);
1274 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1275 if (oSize >= hwSize) return ERROR(corruption_detected);
1278 for (n=0; n<oSize; n+=2) {
1279 huffWeight[n] = ip[n/2] >> 4;
1280 huffWeight[n+1] = ip[n/2] & 15;
1282 else { /* header compressed with FSE (normal case) */
1283 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1284 oSize = FSEv07_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1285 if (FSEv07_isError(oSize)) return oSize;
1288 /* collect weight stats */
1289 memset(rankStats, 0, (HUFv07_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
1291 { U32 n; for (n=0; n<oSize; n++) {
1292 if (huffWeight[n] >= HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1293 rankStats[huffWeight[n]]++;
1294 weightTotal += (1 << huffWeight[n]) >> 1;
1296 if (weightTotal == 0) return ERROR(corruption_detected);
1298 /* get last non-null symbol weight (implied, total must be 2^n) */
1299 { U32 const tableLog = BITv07_highbit32(weightTotal) + 1;
1300 if (tableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1301 *tableLogPtr = tableLog;
1302 /* determine last weight */
1303 { U32 const total = 1 << tableLog;
1304 U32 const rest = total - weightTotal;
1305 U32 const verif = 1 << BITv07_highbit32(rest);
1306 U32 const lastWeight = BITv07_highbit32(rest) + 1;
1307 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1308 huffWeight[oSize] = (BYTE)lastWeight;
1309 rankStats[lastWeight]++;
1312 /* check tree construction validity */
1313 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1316 *nbSymbolsPtr = (U32)(oSize+1);
1319 /* ******************************************************************
1320 FSE : Finite State Entropy decoder
1321 Copyright (C) 2013-2015, Yann Collet.
1323 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1325 Redistribution and use in source and binary forms, with or without
1326 modification, are permitted provided that the following conditions are
1329 * Redistributions of source code must retain the above copyright
1330 notice, this list of conditions and the following disclaimer.
1331 * Redistributions in binary form must reproduce the above
1332 copyright notice, this list of conditions and the following disclaimer
1333 in the documentation and/or other materials provided with the
1336 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1337 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1338 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1339 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1340 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1341 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1342 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1343 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1344 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1345 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1346 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1348 You can contact the author at :
1349 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1350 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1351 ****************************************************************** */
1354 /* **************************************************************
1355 * Compiler specifics
1356 ****************************************************************/
1357 #ifdef _MSC_VER /* Visual Studio */
1358 # define FORCE_INLINE static __forceinline
1359 # include <intrin.h> /* For Visual 2005 */
1360 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1361 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1363 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1365 # define FORCE_INLINE static inline __attribute__((always_inline))
1367 # define FORCE_INLINE static inline
1370 # define FORCE_INLINE static
1371 # endif /* __STDC_VERSION__ */
1375 /* **************************************************************
1377 ****************************************************************/
1378 #define FSEv07_isError ERR_isError
1379 #define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1382 /* **************************************************************
1384 ****************************************************************/
1385 typedef U32 DTable_max_t[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG)];
1388 /* **************************************************************
1390 ****************************************************************/
1392 designed to be included
1393 for type-specific functions (template emulation in C)
1394 Objective is to write these functions only once, for improved maintenance
1398 #ifndef FSEv07_FUNCTION_EXTENSION
1399 # error "FSEv07_FUNCTION_EXTENSION must be defined"
1401 #ifndef FSEv07_FUNCTION_TYPE
1402 # error "FSEv07_FUNCTION_TYPE must be defined"
1405 /* Function names */
1406 #define FSEv07_CAT(X,Y) X##Y
1407 #define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y)
1408 #define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y)
1411 /* Function templates */
1412 FSEv07_DTable* FSEv07_createDTable (unsigned tableLog)
1414 if (tableLog > FSEv07_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv07_TABLELOG_ABSOLUTE_MAX;
1415 return (FSEv07_DTable*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1418 void FSEv07_freeDTable (FSEv07_DTable* dt)
1423 size_t FSEv07_buildDTable(FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1425 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1426 FSEv07_DECODE_TYPE* const tableDecode = (FSEv07_DECODE_TYPE*) (tdPtr);
1427 U16 symbolNext[FSEv07_MAX_SYMBOL_VALUE+1];
1429 U32 const maxSV1 = maxSymbolValue + 1;
1430 U32 const tableSize = 1 << tableLog;
1431 U32 highThreshold = tableSize-1;
1434 if (maxSymbolValue > FSEv07_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1435 if (tableLog > FSEv07_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1437 /* Init, lay down lowprob symbols */
1438 { FSEv07_DTableHeader DTableH;
1439 DTableH.tableLog = (U16)tableLog;
1440 DTableH.fastMode = 1;
1441 { S16 const largeLimit= (S16)(1 << (tableLog-1));
1443 for (s=0; s<maxSV1; s++) {
1444 if (normalizedCounter[s]==-1) {
1445 tableDecode[highThreshold--].symbol = (FSEv07_FUNCTION_TYPE)s;
1448 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1449 symbolNext[s] = normalizedCounter[s];
1451 memcpy(dt, &DTableH, sizeof(DTableH));
1454 /* Spread symbols */
1455 { U32 const tableMask = tableSize-1;
1456 U32 const step = FSEv07_TABLESTEP(tableSize);
1457 U32 s, position = 0;
1458 for (s=0; s<maxSV1; s++) {
1460 for (i=0; i<normalizedCounter[s]; i++) {
1461 tableDecode[position].symbol = (FSEv07_FUNCTION_TYPE)s;
1462 position = (position + step) & tableMask;
1463 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1466 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1469 /* Build Decoding table */
1471 for (u=0; u<tableSize; u++) {
1472 FSEv07_FUNCTION_TYPE const symbol = (FSEv07_FUNCTION_TYPE)(tableDecode[u].symbol);
1473 U16 nextState = symbolNext[symbol]++;
1474 tableDecode[u].nbBits = (BYTE) (tableLog - BITv07_highbit32 ((U32)nextState) );
1475 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1483 #ifndef FSEv07_COMMONDEFS_ONLY
1485 /*-*******************************************************
1486 * Decompression (Byte symbols)
1487 *********************************************************/
1488 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, BYTE symbolValue)
1491 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1492 void* dPtr = dt + 1;
1493 FSEv07_decode_t* const cell = (FSEv07_decode_t*)dPtr;
1495 DTableH->tableLog = 0;
1496 DTableH->fastMode = 0;
1499 cell->symbol = symbolValue;
1506 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits)
1509 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1510 void* dPtr = dt + 1;
1511 FSEv07_decode_t* const dinfo = (FSEv07_decode_t*)dPtr;
1512 const unsigned tableSize = 1 << nbBits;
1513 const unsigned tableMask = tableSize - 1;
1514 const unsigned maxSV1 = tableMask+1;
1518 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1520 /* Build Decoding Table */
1521 DTableH->tableLog = (U16)nbBits;
1522 DTableH->fastMode = 1;
1523 for (s=0; s<maxSV1; s++) {
1524 dinfo[s].newState = 0;
1525 dinfo[s].symbol = (BYTE)s;
1526 dinfo[s].nbBits = (BYTE)nbBits;
1532 FORCE_INLINE size_t FSEv07_decompress_usingDTable_generic(
1533 void* dst, size_t maxDstSize,
1534 const void* cSrc, size_t cSrcSize,
1535 const FSEv07_DTable* dt, const unsigned fast)
1537 BYTE* const ostart = (BYTE*) dst;
1539 BYTE* const omax = op + maxDstSize;
1540 BYTE* const olimit = omax-3;
1542 BITv07_DStream_t bitD;
1543 FSEv07_DState_t state1;
1544 FSEv07_DState_t state2;
1547 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1548 if (FSEv07_isError(errorCode)) return errorCode; }
1550 FSEv07_initDState(&state1, &bitD, dt);
1551 FSEv07_initDState(&state2, &bitD, dt);
1553 #define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1555 /* 4 symbols per loop */
1556 for ( ; (BITv07_reloadDStream(&bitD)==BITv07_DStream_unfinished) && (op<olimit) ; op+=4) {
1557 op[0] = FSEv07_GETSYMBOL(&state1);
1559 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1560 BITv07_reloadDStream(&bitD);
1562 op[1] = FSEv07_GETSYMBOL(&state2);
1564 if (FSEv07_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1565 { if (BITv07_reloadDStream(&bitD) > BITv07_DStream_unfinished) { op+=2; break; } }
1567 op[2] = FSEv07_GETSYMBOL(&state1);
1569 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1570 BITv07_reloadDStream(&bitD);
1572 op[3] = FSEv07_GETSYMBOL(&state2);
1576 /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1578 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1580 *op++ = FSEv07_GETSYMBOL(&state1);
1582 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1583 *op++ = FSEv07_GETSYMBOL(&state2);
1587 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1589 *op++ = FSEv07_GETSYMBOL(&state2);
1591 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1592 *op++ = FSEv07_GETSYMBOL(&state1);
1600 size_t FSEv07_decompress_usingDTable(void* dst, size_t originalSize,
1601 const void* cSrc, size_t cSrcSize,
1602 const FSEv07_DTable* dt)
1604 const void* ptr = dt;
1605 const FSEv07_DTableHeader* DTableH = (const FSEv07_DTableHeader*)ptr;
1606 const U32 fastMode = DTableH->fastMode;
1608 /* select fast mode (static) */
1609 if (fastMode) return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1610 return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1614 size_t FSEv07_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1616 const BYTE* const istart = (const BYTE*)cSrc;
1617 const BYTE* ip = istart;
1618 short counting[FSEv07_MAX_SYMBOL_VALUE+1];
1619 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1621 unsigned maxSymbolValue = FSEv07_MAX_SYMBOL_VALUE;
1623 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1625 /* normal FSE decoding mode */
1626 { size_t const NCountLength = FSEv07_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1627 if (FSEv07_isError(NCountLength)) return NCountLength;
1628 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1630 cSrcSize -= NCountLength;
1633 { size_t const errorCode = FSEv07_buildDTable (dt, counting, maxSymbolValue, tableLog);
1634 if (FSEv07_isError(errorCode)) return errorCode; }
1636 return FSEv07_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */
1641 #endif /* FSEv07_COMMONDEFS_ONLY */
1643 /* ******************************************************************
1644 Huffman decoder, part of New Generation Entropy library
1645 Copyright (C) 2013-2016, Yann Collet.
1647 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1649 Redistribution and use in source and binary forms, with or without
1650 modification, are permitted provided that the following conditions are
1653 * Redistributions of source code must retain the above copyright
1654 notice, this list of conditions and the following disclaimer.
1655 * Redistributions in binary form must reproduce the above
1656 copyright notice, this list of conditions and the following disclaimer
1657 in the documentation and/or other materials provided with the
1660 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1661 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1662 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1663 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1664 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1665 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1666 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1667 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1668 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1669 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1670 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1672 You can contact the author at :
1673 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1674 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1675 ****************************************************************** */
1677 /* **************************************************************
1678 * Compiler specifics
1679 ****************************************************************/
1680 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1681 /* inline is defined */
1682 #elif defined(_MSC_VER)
1683 # define inline __inline
1685 # define inline /* disable inline */
1689 #ifdef _MSC_VER /* Visual Studio */
1690 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1695 /* **************************************************************
1697 ****************************************************************/
1698 #define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1701 /*-***************************/
1702 /* generic DTableDesc */
1703 /*-***************************/
1705 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
1707 static DTableDesc HUFv07_getDTableDesc(const HUFv07_DTable* table)
1710 memcpy(&dtd, table, sizeof(dtd));
1715 /*-***************************/
1716 /* single-symbol decoding */
1717 /*-***************************/
1719 typedef struct { BYTE byte; BYTE nbBits; } HUFv07_DEltX2; /* single-symbol decoding */
1721 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
1723 BYTE huffWeight[HUFv07_SYMBOLVALUE_MAX + 1];
1724 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
1728 void* const dtPtr = DTable + 1;
1729 HUFv07_DEltX2* const dt = (HUFv07_DEltX2*)dtPtr;
1731 HUFv07_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUFv07_DTable));
1732 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
1734 iSize = HUFv07_readStats(huffWeight, HUFv07_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1735 if (HUFv07_isError(iSize)) return iSize;
1738 { DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1739 if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge); /* DTable too small, huffman tree cannot fit in */
1741 dtd.tableLog = (BYTE)tableLog;
1742 memcpy(DTable, &dtd, sizeof(dtd));
1746 { U32 n, nextRankStart = 0;
1747 for (n=1; n<tableLog+1; n++) {
1748 U32 current = nextRankStart;
1749 nextRankStart += (rankVal[n] << (n-1));
1750 rankVal[n] = current;
1755 for (n=0; n<nbSymbols; n++) {
1756 U32 const w = huffWeight[n];
1757 U32 const length = (1 << w) >> 1;
1760 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1761 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1763 rankVal[w] += length;
1770 static BYTE HUFv07_decodeSymbolX2(BITv07_DStream_t* Dstream, const HUFv07_DEltX2* dt, const U32 dtLog)
1772 size_t const val = BITv07_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1773 BYTE const c = dt[val].byte;
1774 BITv07_skipBits(Dstream, dt[val].nbBits);
1778 #define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1779 *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1781 #define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1782 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1783 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1785 #define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1787 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1789 static inline size_t HUFv07_decodeStreamX2(BYTE* p, BITv07_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv07_DEltX2* const dt, const U32 dtLog)
1791 BYTE* const pStart = p;
1793 /* up to 4 symbols at a time */
1794 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-4)) {
1795 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1796 HUFv07_DECODE_SYMBOLX2_1(p, bitDPtr);
1797 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1798 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1801 /* closer to the end */
1802 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd))
1803 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1805 /* no more data to retrieve from bitstream, hence no need to reload */
1807 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1812 static size_t HUFv07_decompress1X2_usingDTable_internal(
1813 void* dst, size_t dstSize,
1814 const void* cSrc, size_t cSrcSize,
1815 const HUFv07_DTable* DTable)
1817 BYTE* op = (BYTE*)dst;
1818 BYTE* const oend = op + dstSize;
1819 const void* dtPtr = DTable + 1;
1820 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1821 BITv07_DStream_t bitD;
1822 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1823 U32 const dtLog = dtd.tableLog;
1825 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
1826 if (HUFv07_isError(errorCode)) return errorCode; }
1828 HUFv07_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1831 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
1836 size_t HUFv07_decompress1X2_usingDTable(
1837 void* dst, size_t dstSize,
1838 const void* cSrc, size_t cSrcSize,
1839 const HUFv07_DTable* DTable)
1841 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1842 if (dtd.tableType != 0) return ERROR(GENERIC);
1843 return HUFv07_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
1846 size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1848 const BYTE* ip = (const BYTE*) cSrc;
1850 size_t const hSize = HUFv07_readDTableX2 (DCtx, cSrc, cSrcSize);
1851 if (HUFv07_isError(hSize)) return hSize;
1852 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1853 ip += hSize; cSrcSize -= hSize;
1855 return HUFv07_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
1858 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1860 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
1861 return HUFv07_decompress1X2_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
1865 static size_t HUFv07_decompress4X2_usingDTable_internal(
1866 void* dst, size_t dstSize,
1867 const void* cSrc, size_t cSrcSize,
1868 const HUFv07_DTable* DTable)
1871 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1873 { const BYTE* const istart = (const BYTE*) cSrc;
1874 BYTE* const ostart = (BYTE*) dst;
1875 BYTE* const oend = ostart + dstSize;
1876 const void* const dtPtr = DTable + 1;
1877 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1880 BITv07_DStream_t bitD1;
1881 BITv07_DStream_t bitD2;
1882 BITv07_DStream_t bitD3;
1883 BITv07_DStream_t bitD4;
1884 size_t const length1 = MEM_readLE16(istart);
1885 size_t const length2 = MEM_readLE16(istart+2);
1886 size_t const length3 = MEM_readLE16(istart+4);
1887 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
1888 const BYTE* const istart1 = istart + 6; /* jumpTable */
1889 const BYTE* const istart2 = istart1 + length1;
1890 const BYTE* const istart3 = istart2 + length2;
1891 const BYTE* const istart4 = istart3 + length3;
1892 const size_t segmentSize = (dstSize+3) / 4;
1893 BYTE* const opStart2 = ostart + segmentSize;
1894 BYTE* const opStart3 = opStart2 + segmentSize;
1895 BYTE* const opStart4 = opStart3 + segmentSize;
1897 BYTE* op2 = opStart2;
1898 BYTE* op3 = opStart3;
1899 BYTE* op4 = opStart4;
1901 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1902 U32 const dtLog = dtd.tableLog;
1904 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1905 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
1906 if (HUFv07_isError(errorCode)) return errorCode; }
1907 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
1908 if (HUFv07_isError(errorCode)) return errorCode; }
1909 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
1910 if (HUFv07_isError(errorCode)) return errorCode; }
1911 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
1912 if (HUFv07_isError(errorCode)) return errorCode; }
1914 /* 16-32 symbols per loop (4-8 symbols per stream) */
1915 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1916 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
1917 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
1918 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
1919 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
1920 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
1921 HUFv07_DECODE_SYMBOLX2_1(op1, &bitD1);
1922 HUFv07_DECODE_SYMBOLX2_1(op2, &bitD2);
1923 HUFv07_DECODE_SYMBOLX2_1(op3, &bitD3);
1924 HUFv07_DECODE_SYMBOLX2_1(op4, &bitD4);
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_0(op1, &bitD1);
1930 HUFv07_DECODE_SYMBOLX2_0(op2, &bitD2);
1931 HUFv07_DECODE_SYMBOLX2_0(op3, &bitD3);
1932 HUFv07_DECODE_SYMBOLX2_0(op4, &bitD4);
1933 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1936 /* check corruption */
1937 if (op1 > opStart2) return ERROR(corruption_detected);
1938 if (op2 > opStart3) return ERROR(corruption_detected);
1939 if (op3 > opStart4) return ERROR(corruption_detected);
1940 /* note : op4 supposed already verified within main loop */
1942 /* finish bitStreams one by one */
1943 HUFv07_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1944 HUFv07_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1945 HUFv07_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1946 HUFv07_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1949 endSignal = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
1950 if (!endSignal) return ERROR(corruption_detected);
1958 size_t HUFv07_decompress4X2_usingDTable(
1959 void* dst, size_t dstSize,
1960 const void* cSrc, size_t cSrcSize,
1961 const HUFv07_DTable* DTable)
1963 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1964 if (dtd.tableType != 0) return ERROR(GENERIC);
1965 return HUFv07_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
1969 size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1971 const BYTE* ip = (const BYTE*) cSrc;
1973 size_t const hSize = HUFv07_readDTableX2 (dctx, cSrc, cSrcSize);
1974 if (HUFv07_isError(hSize)) return hSize;
1975 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1976 ip += hSize; cSrcSize -= hSize;
1978 return HUFv07_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx);
1981 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1983 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
1984 return HUFv07_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
1988 /* *************************/
1989 /* double-symbols decoding */
1990 /* *************************/
1991 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv07_DEltX4; /* double-symbols decoding */
1993 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1995 static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1996 const U32* rankValOrigin, const int minWeight,
1997 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1998 U32 nbBitsBaseline, U16 baseSeq)
2001 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2003 /* get pre-calculated rankVal */
2004 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2006 /* fill skipped values */
2008 U32 i, skipSize = rankVal[minWeight];
2009 MEM_writeLE16(&(DElt.sequence), baseSeq);
2010 DElt.nbBits = (BYTE)(consumed);
2012 for (i = 0; i < skipSize; i++)
2017 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2018 const U32 symbol = sortedSymbols[s].symbol;
2019 const U32 weight = sortedSymbols[s].weight;
2020 const U32 nbBits = nbBitsBaseline - weight;
2021 const U32 length = 1 << (sizeLog-nbBits);
2022 const U32 start = rankVal[weight];
2024 const U32 end = start + length;
2026 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2027 DElt.nbBits = (BYTE)(nbBits + consumed);
2029 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2031 rankVal[weight] += length;
2035 typedef U32 rankVal_t[HUFv07_TABLELOG_ABSOLUTEMAX][HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2037 static void HUFv07_fillDTableX4(HUFv07_DEltX4* DTable, const U32 targetLog,
2038 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2039 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2040 const U32 nbBitsBaseline)
2042 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2043 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2044 const U32 minBits = nbBitsBaseline - maxWeight;
2047 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2050 for (s=0; s<sortedListSize; s++) {
2051 const U16 symbol = sortedList[s].symbol;
2052 const U32 weight = sortedList[s].weight;
2053 const U32 nbBits = nbBitsBaseline - weight;
2054 const U32 start = rankVal[weight];
2055 const U32 length = 1 << (targetLog-nbBits);
2057 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2059 int minWeight = nbBits + scaleLog;
2060 if (minWeight < 1) minWeight = 1;
2061 sortedRank = rankStart[minWeight];
2062 HUFv07_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2063 rankValOrigin[nbBits], minWeight,
2064 sortedList+sortedRank, sortedListSize-sortedRank,
2065 nbBitsBaseline, symbol);
2068 MEM_writeLE16(&(DElt.sequence), symbol);
2069 DElt.nbBits = (BYTE)(nbBits);
2072 const U32 end = start + length;
2073 for (u = start; u < end; u++) DTable[u] = DElt;
2075 rankVal[weight] += length;
2079 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
2081 BYTE weightList[HUFv07_SYMBOLVALUE_MAX + 1];
2082 sortedSymbol_t sortedSymbol[HUFv07_SYMBOLVALUE_MAX + 1];
2083 U32 rankStats[HUFv07_TABLELOG_ABSOLUTEMAX + 1] = { 0 };
2084 U32 rankStart0[HUFv07_TABLELOG_ABSOLUTEMAX + 2] = { 0 };
2085 U32* const rankStart = rankStart0+1;
2087 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2088 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2089 U32 const maxTableLog = dtd.maxTableLog;
2091 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */
2092 HUFv07_DEltX4* const dt = (HUFv07_DEltX4*)dtPtr;
2094 HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4) == sizeof(HUFv07_DTable)); /* if compilation fails here, assertion is false */
2095 if (maxTableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge);
2096 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */
2098 iSize = HUFv07_readStats(weightList, HUFv07_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2099 if (HUFv07_isError(iSize)) return iSize;
2102 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2104 /* find maxWeight */
2105 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2107 /* Get start index of each weight */
2108 { U32 w, nextRankStart = 0;
2109 for (w=1; w<maxW+1; w++) {
2110 U32 current = nextRankStart;
2111 nextRankStart += rankStats[w];
2112 rankStart[w] = current;
2114 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2115 sizeOfSort = nextRankStart;
2118 /* sort symbols by weight */
2120 for (s=0; s<nbSymbols; s++) {
2121 U32 const w = weightList[s];
2122 U32 const r = rankStart[w]++;
2123 sortedSymbol[r].symbol = (BYTE)s;
2124 sortedSymbol[r].weight = (BYTE)w;
2126 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2130 { U32* const rankVal0 = rankVal[0];
2131 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */
2132 U32 nextRankVal = 0;
2134 for (w=1; w<maxW+1; w++) {
2135 U32 current = nextRankVal;
2136 nextRankVal += rankStats[w] << (w+rescale);
2137 rankVal0[w] = current;
2139 { U32 const minBits = tableLog+1 - maxW;
2141 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
2142 U32* const rankValPtr = rankVal[consumed];
2144 for (w = 1; w < maxW+1; w++) {
2145 rankValPtr[w] = rankVal0[w] >> consumed;
2148 HUFv07_fillDTableX4(dt, maxTableLog,
2149 sortedSymbol, sizeOfSort,
2150 rankStart0, rankVal, maxW,
2153 dtd.tableLog = (BYTE)maxTableLog;
2155 memcpy(DTable, &dtd, sizeof(dtd));
2160 static U32 HUFv07_decodeSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2162 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2163 memcpy(op, dt+val, 2);
2164 BITv07_skipBits(DStream, dt[val].nbBits);
2165 return dt[val].length;
2168 static U32 HUFv07_decodeLastSymbolX4(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, 1);
2172 if (dt[val].length==1) BITv07_skipBits(DStream, dt[val].nbBits);
2174 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2175 BITv07_skipBits(DStream, dt[val].nbBits);
2176 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2177 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 */
2183 #define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2184 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2186 #define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2187 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
2188 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2190 #define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2192 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2194 static inline size_t HUFv07_decodeStreamX4(BYTE* p, BITv07_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv07_DEltX4* const dt, const U32 dtLog)
2196 BYTE* const pStart = p;
2198 /* up to 8 symbols at a time */
2199 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd-7)) {
2200 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2201 HUFv07_DECODE_SYMBOLX4_1(p, bitDPtr);
2202 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2203 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2206 /* closer to end : up to 2 symbols at a time */
2207 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-2))
2208 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2211 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2214 p += HUFv07_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2220 static size_t HUFv07_decompress1X4_usingDTable_internal(
2221 void* dst, size_t dstSize,
2222 const void* cSrc, size_t cSrcSize,
2223 const HUFv07_DTable* DTable)
2225 BITv07_DStream_t bitD;
2228 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
2229 if (HUFv07_isError(errorCode)) return errorCode;
2233 { BYTE* const ostart = (BYTE*) dst;
2234 BYTE* const oend = ostart + dstSize;
2235 const void* const dtPtr = DTable+1; /* force compiler to not use strict-aliasing */
2236 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2237 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2238 HUFv07_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog);
2242 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
2248 size_t HUFv07_decompress1X4_usingDTable(
2249 void* dst, size_t dstSize,
2250 const void* cSrc, size_t cSrcSize,
2251 const HUFv07_DTable* DTable)
2253 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2254 if (dtd.tableType != 1) return ERROR(GENERIC);
2255 return HUFv07_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2258 size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2260 const BYTE* ip = (const BYTE*) cSrc;
2262 size_t const hSize = HUFv07_readDTableX4 (DCtx, cSrc, cSrcSize);
2263 if (HUFv07_isError(hSize)) return hSize;
2264 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2265 ip += hSize; cSrcSize -= hSize;
2267 return HUFv07_decompress1X4_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
2270 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2272 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2273 return HUFv07_decompress1X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2276 static size_t HUFv07_decompress4X4_usingDTable_internal(
2277 void* dst, size_t dstSize,
2278 const void* cSrc, size_t cSrcSize,
2279 const HUFv07_DTable* DTable)
2281 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2283 { const BYTE* const istart = (const BYTE*) cSrc;
2284 BYTE* const ostart = (BYTE*) dst;
2285 BYTE* const oend = ostart + dstSize;
2286 const void* const dtPtr = DTable+1;
2287 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2290 BITv07_DStream_t bitD1;
2291 BITv07_DStream_t bitD2;
2292 BITv07_DStream_t bitD3;
2293 BITv07_DStream_t bitD4;
2294 size_t const length1 = MEM_readLE16(istart);
2295 size_t const length2 = MEM_readLE16(istart+2);
2296 size_t const length3 = MEM_readLE16(istart+4);
2297 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
2298 const BYTE* const istart1 = istart + 6; /* jumpTable */
2299 const BYTE* const istart2 = istart1 + length1;
2300 const BYTE* const istart3 = istart2 + length2;
2301 const BYTE* const istart4 = istart3 + length3;
2302 size_t const segmentSize = (dstSize+3) / 4;
2303 BYTE* const opStart2 = ostart + segmentSize;
2304 BYTE* const opStart3 = opStart2 + segmentSize;
2305 BYTE* const opStart4 = opStart3 + segmentSize;
2307 BYTE* op2 = opStart2;
2308 BYTE* op3 = opStart3;
2309 BYTE* op4 = opStart4;
2311 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2312 U32 const dtLog = dtd.tableLog;
2314 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2315 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
2316 if (HUFv07_isError(errorCode)) return errorCode; }
2317 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
2318 if (HUFv07_isError(errorCode)) return errorCode; }
2319 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
2320 if (HUFv07_isError(errorCode)) return errorCode; }
2321 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
2322 if (HUFv07_isError(errorCode)) return errorCode; }
2324 /* 16-32 symbols per loop (4-8 symbols per stream) */
2325 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2326 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
2327 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2328 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2329 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2330 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2331 HUFv07_DECODE_SYMBOLX4_1(op1, &bitD1);
2332 HUFv07_DECODE_SYMBOLX4_1(op2, &bitD2);
2333 HUFv07_DECODE_SYMBOLX4_1(op3, &bitD3);
2334 HUFv07_DECODE_SYMBOLX4_1(op4, &bitD4);
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_0(op1, &bitD1);
2340 HUFv07_DECODE_SYMBOLX4_0(op2, &bitD2);
2341 HUFv07_DECODE_SYMBOLX4_0(op3, &bitD3);
2342 HUFv07_DECODE_SYMBOLX4_0(op4, &bitD4);
2344 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2347 /* check corruption */
2348 if (op1 > opStart2) return ERROR(corruption_detected);
2349 if (op2 > opStart3) return ERROR(corruption_detected);
2350 if (op3 > opStart4) return ERROR(corruption_detected);
2351 /* note : op4 supposed already verified within main loop */
2353 /* finish bitStreams one by one */
2354 HUFv07_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2355 HUFv07_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2356 HUFv07_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2357 HUFv07_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2360 { U32 const endCheck = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2361 if (!endCheck) return ERROR(corruption_detected); }
2369 size_t HUFv07_decompress4X4_usingDTable(
2370 void* dst, size_t dstSize,
2371 const void* cSrc, size_t cSrcSize,
2372 const HUFv07_DTable* DTable)
2374 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2375 if (dtd.tableType != 1) return ERROR(GENERIC);
2376 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2380 size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2382 const BYTE* ip = (const BYTE*) cSrc;
2384 size_t hSize = HUFv07_readDTableX4 (dctx, cSrc, cSrcSize);
2385 if (HUFv07_isError(hSize)) return hSize;
2386 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2387 ip += hSize; cSrcSize -= hSize;
2389 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
2392 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2394 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2395 return HUFv07_decompress4X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2399 /* ********************************/
2400 /* Generic decompression selector */
2401 /* ********************************/
2403 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize,
2404 const void* cSrc, size_t cSrcSize,
2405 const HUFv07_DTable* DTable)
2407 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2408 return dtd.tableType ? HUFv07_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2409 HUFv07_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2412 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize,
2413 const void* cSrc, size_t cSrcSize,
2414 const HUFv07_DTable* DTable)
2416 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2417 return dtd.tableType ? HUFv07_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2418 HUFv07_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2422 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2423 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2425 /* single, double, quad */
2426 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2427 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2428 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2429 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2430 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2431 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2432 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2433 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2434 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2435 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2436 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2437 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2438 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2439 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2440 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2441 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2444 /** HUFv07_selectDecoder() :
2445 * Tells which decoder is likely to decode faster,
2446 * based on a set of pre-determined metrics.
2447 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
2448 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
2449 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize)
2451 /* decoder timing evaluation */
2452 U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2453 U32 const D256 = (U32)(dstSize >> 8);
2454 U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
2455 U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
2456 DTime1 += DTime1 >> 3; /* advantage to algorithm using less memory, for cache eviction */
2458 return DTime1 < DTime0;
2462 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2464 size_t HUFv07_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2466 static const decompressionAlgo decompress[2] = { HUFv07_decompress4X2, HUFv07_decompress4X4 };
2468 /* validation checks */
2469 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2470 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2471 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2472 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2474 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2475 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2478 /* return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams single-symbol decoding */
2479 /* return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams double-symbols decoding */
2482 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2484 /* validation checks */
2485 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2486 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2487 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2488 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2490 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2491 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2492 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2496 size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2498 /* validation checks */
2499 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2500 if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected); /* invalid */
2502 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2503 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2504 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2508 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2510 /* validation checks */
2511 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2512 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2513 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2514 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2516 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2517 return algoNb ? HUFv07_decompress1X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2518 HUFv07_decompress1X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2522 Common functions of Zstd compression library
2523 Copyright (C) 2015-2016, Yann Collet.
2525 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2527 Redistribution and use in source and binary forms, with or without
2528 modification, are permitted provided that the following conditions are
2530 * Redistributions of source code must retain the above copyright
2531 notice, this list of conditions and the following disclaimer.
2532 * Redistributions in binary form must reproduce the above
2533 copyright notice, this list of conditions and the following disclaimer
2534 in the documentation and/or other materials provided with the
2536 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2537 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2538 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2539 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2540 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2541 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2542 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2543 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2544 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2545 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2546 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2548 You can contact the author at :
2549 - zstd homepage : https://facebook.github.io/zstd/
2554 /*-****************************************
2555 * ZSTD Error Management
2556 ******************************************/
2557 /*! ZSTDv07_isError() :
2558 * tells if a return value is an error code */
2559 unsigned ZSTDv07_isError(size_t code) { return ERR_isError(code); }
2561 /*! ZSTDv07_getErrorName() :
2562 * provides error code string from function result (useful for debugging) */
2563 const char* ZSTDv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
2567 /* **************************************************************
2568 * ZBUFF Error Management
2569 ****************************************************************/
2570 unsigned ZBUFFv07_isError(size_t errorCode) { return ERR_isError(errorCode); }
2572 const char* ZBUFFv07_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2576 static void* ZSTDv07_defaultAllocFunction(void* opaque, size_t size)
2578 void* address = malloc(size);
2580 /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2584 static void ZSTDv07_defaultFreeFunction(void* opaque, void* address)
2587 /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2591 zstd_internal - common functions to include
2592 Header File for include
2593 Copyright (C) 2014-2016, Yann Collet.
2595 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2597 Redistribution and use in source and binary forms, with or without
2598 modification, are permitted provided that the following conditions are
2600 * Redistributions of source code must retain the above copyright
2601 notice, this list of conditions and the following disclaimer.
2602 * Redistributions in binary form must reproduce the above
2603 copyright notice, this list of conditions and the following disclaimer
2604 in the documentation and/or other materials provided with the
2606 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2607 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2608 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2609 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2610 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2611 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2612 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2613 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2614 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2615 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2616 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2618 You can contact the author at :
2619 - zstd homepage : https://www.zstd.net
2621 #ifndef ZSTDv07_CCOMMON_H_MODULE
2622 #define ZSTDv07_CCOMMON_H_MODULE
2625 /*-*************************************
2627 ***************************************/
2628 #define MIN(a,b) ((a)<(b) ? (a) : (b))
2629 #define MAX(a,b) ((a)>(b) ? (a) : (b))
2632 /*-*************************************
2634 ***************************************/
2635 #define ZSTDv07_OPT_NUM (1<<12)
2636 #define ZSTDv07_DICT_MAGIC 0xEC30A437 /* v0.7 */
2638 #define ZSTDv07_REP_NUM 3
2639 #define ZSTDv07_REP_INIT ZSTDv07_REP_NUM
2640 #define ZSTDv07_REP_MOVE (ZSTDv07_REP_NUM-1)
2641 static const U32 repStartValue[ZSTDv07_REP_NUM] = { 1, 4, 8 };
2643 #define KB *(1 <<10)
2644 #define MB *(1 <<20)
2645 #define GB *(1U<<30)
2654 #define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10
2655 static const size_t ZSTDv07_fcs_fieldSize[4] = { 0, 2, 4, 8 };
2656 static const size_t ZSTDv07_did_fieldSize[4] = { 0, 1, 2, 4 };
2658 #define ZSTDv07_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
2659 static const size_t ZSTDv07_blockHeaderSize = ZSTDv07_BLOCKHEADERSIZE;
2660 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2662 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2663 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
2665 #define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
2666 typedef enum { lbt_huffman, lbt_repeat, lbt_raw, lbt_rle } litBlockType_t;
2668 #define LONGNBSEQ 0x7F00
2671 #define EQUAL_READ32 4
2674 #define MaxLit ((1<<Litbits) - 1)
2678 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
2683 #define FSEv07_ENCODING_RAW 0
2684 #define FSEv07_ENCODING_RLE 1
2685 #define FSEv07_ENCODING_STATIC 2
2686 #define FSEv07_ENCODING_DYNAMIC 3
2688 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2690 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2691 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
2693 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2694 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
2696 static const U32 LL_defaultNormLog = 6;
2698 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2699 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2700 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
2702 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2703 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2704 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
2706 static const U32 ML_defaultNormLog = 6;
2708 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2709 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
2710 static const U32 OF_defaultNormLog = 5;
2713 /*-*******************************************
2714 * Shared functions to include for inlining
2715 *********************************************/
2716 static void ZSTDv07_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2717 #define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; }
2719 /*! ZSTDv07_wildcopy() :
2720 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
2721 #define WILDCOPY_OVERLENGTH 8
2722 MEM_STATIC void ZSTDv07_wildcopy(void* dst, const void* src, ptrdiff_t length)
2724 const BYTE* ip = (const BYTE*)src;
2725 BYTE* op = (BYTE*)dst;
2726 BYTE* const oend = op + length;
2733 /*-*******************************************
2734 * Private interfaces
2735 *********************************************/
2736 typedef struct ZSTDv07_stats_s ZSTDv07_stats_t;
2748 U32 rep[ZSTDv07_REP_INIT];
2749 } ZSTDv07_optimal_t;
2751 struct ZSTDv07_stats_s { U32 unused; };
2760 U16* litLengthStart;
2763 U16* matchLengthStart;
2766 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
2769 ZSTDv07_optimal_t* priceTable;
2770 ZSTDv07_match_t* matchTable;
2771 U32* matchLengthFreq;
2780 U32 log2matchLengthSum;
2782 U32 log2litLengthSum;
2787 U32 cachedLitLength;
2788 const BYTE* cachedLiterals;
2789 ZSTDv07_stats_t stats;
2792 void ZSTDv07_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
2794 /* custom memory allocation functions */
2795 static const ZSTDv07_customMem defaultCustomMem = { ZSTDv07_defaultAllocFunction, ZSTDv07_defaultFreeFunction, NULL };
2797 #endif /* ZSTDv07_CCOMMON_H_MODULE */
2799 zstd - standard compression library
2800 Copyright (C) 2014-2016, Yann Collet.
2802 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2804 Redistribution and use in source and binary forms, with or without
2805 modification, are permitted provided that the following conditions are
2807 * Redistributions of source code must retain the above copyright
2808 notice, this list of conditions and the following disclaimer.
2809 * Redistributions in binary form must reproduce the above
2810 copyright notice, this list of conditions and the following disclaimer
2811 in the documentation and/or other materials provided with the
2813 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2814 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2815 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2816 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2817 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2818 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2819 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2820 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2821 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2822 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2823 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2825 You can contact the author at :
2826 - zstd homepage : https://facebook.github.io/zstd
2829 /* ***************************************************************
2831 *****************************************************************/
2834 * Select how default decompression function ZSTDv07_decompress() will allocate memory,
2835 * in memory stack (0), or in memory heap (1, requires malloc())
2837 #ifndef ZSTDv07_HEAPMODE
2838 # define ZSTDv07_HEAPMODE 1
2842 /*-*******************************************************
2843 * Compiler specifics
2844 *********************************************************/
2845 #ifdef _MSC_VER /* Visual Studio */
2846 # include <intrin.h> /* For Visual 2005 */
2847 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2848 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2849 # pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */
2853 /*-*************************************
2855 ***************************************/
2856 #define ZSTDv07_isError ERR_isError /* for inlining */
2857 #define FSEv07_isError ERR_isError
2858 #define HUFv07_isError ERR_isError
2861 /*_*******************************************************
2863 **********************************************************/
2864 static void ZSTDv07_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2867 /*-*************************************************************
2868 * Context management
2869 ***************************************************************/
2870 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2871 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
2872 ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTDv07_dStage;
2874 struct ZSTDv07_DCtx_s
2876 FSEv07_DTable LLTable[FSEv07_DTABLE_SIZE_U32(LLFSELog)];
2877 FSEv07_DTable OffTable[FSEv07_DTABLE_SIZE_U32(OffFSELog)];
2878 FSEv07_DTable MLTable[FSEv07_DTABLE_SIZE_U32(MLFSELog)];
2879 HUFv07_DTable hufTable[HUFv07_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)]; /* can accommodate HUFv07_decompress4X */
2880 const void* previousDstEnd;
2883 const void* dictEnd;
2886 ZSTDv07_frameParams fParams;
2887 blockType_t bType; /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2888 ZSTDv07_dStage stage;
2891 XXH64_state_t xxhState;
2895 ZSTDv07_customMem customMem;
2897 BYTE litBuffer[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
2898 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
2899 }; /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */
2901 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx);
2903 size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx* dctx) { return sizeof(*dctx); }
2905 size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx); }
2907 size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx)
2909 dctx->expected = ZSTDv07_frameHeaderSize_min;
2910 dctx->stage = ZSTDds_getFrameHeaderSize;
2911 dctx->previousDstEnd = NULL;
2914 dctx->dictEnd = NULL;
2915 dctx->hufTable[0] = (HUFv07_DTable)((ZSTD_HUFFDTABLE_CAPACITY_LOG)*0x1000001);
2916 dctx->litEntropy = dctx->fseEntropy = 0;
2918 { int i; for (i=0; i<ZSTDv07_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; }
2922 ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem)
2926 if (!customMem.customAlloc && !customMem.customFree)
2927 customMem = defaultCustomMem;
2929 if (!customMem.customAlloc || !customMem.customFree)
2932 dctx = (ZSTDv07_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTDv07_DCtx));
2933 if (!dctx) return NULL;
2934 memcpy(&dctx->customMem, &customMem, sizeof(ZSTDv07_customMem));
2935 ZSTDv07_decompressBegin(dctx);
2939 ZSTDv07_DCtx* ZSTDv07_createDCtx(void)
2941 return ZSTDv07_createDCtx_advanced(defaultCustomMem);
2944 size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx* dctx)
2946 if (dctx==NULL) return 0; /* support free on NULL */
2947 dctx->customMem.customFree(dctx->customMem.opaque, dctx);
2948 return 0; /* reserved as a potential error code in the future */
2951 void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dstDCtx, const ZSTDv07_DCtx* srcDCtx)
2953 memcpy(dstDCtx, srcDCtx,
2954 sizeof(ZSTDv07_DCtx) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH + ZSTDv07_frameHeaderSize_max)); /* no need to copy workspace */
2958 /*-*************************************************************
2959 * Decompression section
2960 ***************************************************************/
2962 /* Frame format description
2963 Frame Header - [ Block Header - Block ] - Frame End
2965 - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h)
2966 - 1 byte - Frame Descriptor
2968 - 3 bytes, starting with a 2-bits descriptor
2969 Uncompressed, Compressed, Frame End, unused
2971 See Block Format Description
2973 - 3 bytes, compatible with Block Header
2979 1 byte - FrameHeaderDescription :
2980 bit 0-1 : dictID (0, 1, 2 or 4 bytes)
2981 bit 2 : checksumFlag
2982 bit 3 : reserved (must be zero)
2983 bit 4 : reserved (unused, can be any value)
2984 bit 5 : Single Segment (if 1, WindowLog byte is not present)
2985 bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
2986 if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
2988 Optional : WindowLog (0 or 1 byte)
2989 bit 0-2 : octal Fractional (1/8th)
2990 bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
2992 Optional : dictID (0, 1, 2 or 4 bytes)
2993 Automatic adaptation
2997 4 : all other values
2999 Optional : content size (0, 1, 2, 4 or 8 bytes)
3000 0 : unknown (fcfs==0 and swl==0)
3001 1 : 0-255 bytes (fcfs==0 and swl==1)
3002 2 : 256 - 65535+256 (fcfs==1)
3003 4 : 0 - 4GB-1 (fcfs==2)
3004 8 : 0 - 16EB-1 (fcfs==3)
3008 /* Compressed Block, format description
3010 Block = Literal Section - Sequences Section
3011 Prerequisite : size of (compressed) block, maximum size of regenerated data
3015 1.1) Header : 1-5 bytes
3017 00 compressed by Huff0
3019 10 is Raw (uncompressed)
3021 Note : using 01 => Huff0 with precomputed table ?
3022 Note : delta map ? => compressed ?
3024 1.1.1) Huff0-compressed literal block : 3-5 bytes
3025 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3026 srcSize < 1 KB => 3 bytes (2-2-10-10)
3027 srcSize < 16KB => 4 bytes (2-2-14-14)
3028 else => 5 bytes (2-2-18-18)
3029 big endian convention
3031 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
3032 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
3033 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
3035 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3039 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3040 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
3041 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3043 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3047 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3048 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3049 srcSize < 1 KB => 3 bytes (2-2-10-10)
3050 srcSize < 16KB => 4 bytes (2-2-14-14)
3051 else => 5 bytes (2-2-18-18)
3052 big endian convention
3054 1- CTable available (stored into workspace ?)
3055 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3058 1.2) Literal block content
3060 1.2.1) Huff0 block, using sizes from header
3063 1.2.2) Huff0 block, using prepared table
3070 2) Sequences section
3074 /** ZSTDv07_frameHeaderSize() :
3075 * srcSize must be >= ZSTDv07_frameHeaderSize_min.
3076 * @return : size of the Frame Header */
3077 static size_t ZSTDv07_frameHeaderSize(const void* src, size_t srcSize)
3079 if (srcSize < ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);
3080 { BYTE const fhd = ((const BYTE*)src)[4];
3081 U32 const dictID= fhd & 3;
3082 U32 const directMode = (fhd >> 5) & 1;
3083 U32 const fcsId = fhd >> 6;
3084 return ZSTDv07_frameHeaderSize_min + !directMode + ZSTDv07_did_fieldSize[dictID] + ZSTDv07_fcs_fieldSize[fcsId]
3085 + (directMode && !ZSTDv07_fcs_fieldSize[fcsId]);
3090 /** ZSTDv07_getFrameParams() :
3091 * decode Frame Header, or require larger `srcSize`.
3092 * @return : 0, `fparamsPtr` is correctly filled,
3093 * >0, `srcSize` is too small, result is expected `srcSize`,
3094 * or an error code, which can be tested using ZSTDv07_isError() */
3095 size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams* fparamsPtr, const void* src, size_t srcSize)
3097 const BYTE* ip = (const BYTE*)src;
3099 if (srcSize < ZSTDv07_frameHeaderSize_min) return ZSTDv07_frameHeaderSize_min;
3100 memset(fparamsPtr, 0, sizeof(*fparamsPtr));
3101 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3102 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3103 if (srcSize < ZSTDv07_skippableHeaderSize) return ZSTDv07_skippableHeaderSize; /* magic number + skippable frame length */
3104 fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);
3105 fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
3108 return ERROR(prefix_unknown);
3111 /* ensure there is enough `srcSize` to fully read/decode frame header */
3112 { size_t const fhsize = ZSTDv07_frameHeaderSize(src, srcSize);
3113 if (srcSize < fhsize) return fhsize; }
3115 { BYTE const fhdByte = ip[4];
3117 U32 const dictIDSizeCode = fhdByte&3;
3118 U32 const checksumFlag = (fhdByte>>2)&1;
3119 U32 const directMode = (fhdByte>>5)&1;
3120 U32 const fcsID = fhdByte>>6;
3121 U32 const windowSizeMax = 1U << ZSTDv07_WINDOWLOG_MAX;
3124 U64 frameContentSize = 0;
3125 if ((fhdByte & 0x08) != 0) /* reserved bits, which must be zero */
3126 return ERROR(frameParameter_unsupported);
3128 BYTE const wlByte = ip[pos++];
3129 U32 const windowLog = (wlByte >> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN;
3130 if (windowLog > ZSTDv07_WINDOWLOG_MAX)
3131 return ERROR(frameParameter_unsupported);
3132 windowSize = (1U << windowLog);
3133 windowSize += (windowSize >> 3) * (wlByte&7);
3136 switch(dictIDSizeCode)
3138 default: /* impossible */
3140 case 1 : dictID = ip[pos]; pos++; break;
3141 case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
3142 case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
3146 default: /* impossible */
3147 case 0 : if (directMode) frameContentSize = ip[pos]; break;
3148 case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
3149 case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
3150 case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
3152 if (!windowSize) windowSize = (U32)frameContentSize;
3153 if (windowSize > windowSizeMax)
3154 return ERROR(frameParameter_unsupported);
3155 fparamsPtr->frameContentSize = frameContentSize;
3156 fparamsPtr->windowSize = windowSize;
3157 fparamsPtr->dictID = dictID;
3158 fparamsPtr->checksumFlag = checksumFlag;
3164 /** ZSTDv07_getDecompressedSize() :
3165 * compatible with legacy mode
3166 * @return : decompressed size if known, 0 otherwise
3167 note : 0 can mean any of the following :
3168 - decompressed size is not provided within frame header
3169 - frame header unknown / not supported
3170 - frame header not completely provided (`srcSize` too small) */
3171 unsigned long long ZSTDv07_getDecompressedSize(const void* src, size_t srcSize)
3173 ZSTDv07_frameParams fparams;
3174 size_t const frResult = ZSTDv07_getFrameParams(&fparams, src, srcSize);
3175 if (frResult!=0) return 0;
3176 return fparams.frameContentSize;
3180 /** ZSTDv07_decodeFrameHeader() :
3181 * `srcSize` must be the size provided by ZSTDv07_frameHeaderSize().
3182 * @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */
3183 static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx* dctx, const void* src, size_t srcSize)
3185 size_t const result = ZSTDv07_getFrameParams(&(dctx->fParams), src, srcSize);
3186 if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
3187 if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
3194 blockType_t blockType;
3196 } blockProperties_t;
3198 /*! ZSTDv07_getcBlockSize() :
3199 * Provides the size of compressed block from block header `src` */
3200 static size_t ZSTDv07_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
3202 const BYTE* const in = (const BYTE*)src;
3205 if (srcSize < ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3207 bpPtr->blockType = (blockType_t)((*in) >> 6);
3208 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
3209 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
3211 if (bpPtr->blockType == bt_end) return 0;
3212 if (bpPtr->blockType == bt_rle) return 1;
3217 static size_t ZSTDv07_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3219 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
3221 memcpy(dst, src, srcSize);
3227 /*! ZSTDv07_decodeLiteralsBlock() :
3228 @return : nb of bytes read from src (< srcSize ) */
3229 static size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx* dctx,
3230 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
3232 const BYTE* const istart = (const BYTE*) src;
3234 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3236 switch((litBlockType_t)(istart[0]>> 6))
3239 { size_t litSize, litCSize, singleStream=0;
3240 U32 lhSize = (istart[0] >> 4) & 3;
3241 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3244 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3245 /* 2 - 2 - 10 - 10 */
3247 singleStream = istart[0] & 16;
3248 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3249 litCSize = ((istart[1] & 3) << 8) + istart[2];
3252 /* 2 - 2 - 14 - 14 */
3254 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3255 litCSize = ((istart[2] & 63) << 8) + istart[3];
3258 /* 2 - 2 - 18 - 18 */
3260 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3261 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
3264 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3265 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3267 if (HUFv07_isError(singleStream ?
3268 HUFv07_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3269 HUFv07_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3270 return ERROR(corruption_detected);
3272 dctx->litPtr = dctx->litBuffer;
3273 dctx->litSize = litSize;
3274 dctx->litEntropy = 1;
3275 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3276 return litCSize + lhSize;
3279 { size_t litSize, litCSize;
3280 U32 lhSize = ((istart[0]) >> 4) & 3;
3281 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
3282 return ERROR(corruption_detected);
3283 if (dctx->litEntropy==0)
3284 return ERROR(dictionary_corrupted);
3286 /* 2 - 2 - 10 - 10 */
3288 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3289 litCSize = ((istart[1] & 3) << 8) + istart[2];
3290 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3292 { size_t const errorCode = HUFv07_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTable);
3293 if (HUFv07_isError(errorCode)) return ERROR(corruption_detected);
3295 dctx->litPtr = dctx->litBuffer;
3296 dctx->litSize = litSize;
3297 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3298 return litCSize + lhSize;
3302 U32 lhSize = ((istart[0]) >> 4) & 3;
3305 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3307 litSize = istart[0] & 31;
3310 litSize = ((istart[0] & 15) << 8) + istart[1];
3313 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3317 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
3318 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3319 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3320 dctx->litPtr = dctx->litBuffer;
3321 dctx->litSize = litSize;
3322 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3323 return lhSize+litSize;
3325 /* direct reference into compressed stream */
3326 dctx->litPtr = istart+lhSize;
3327 dctx->litSize = litSize;
3328 return lhSize+litSize;
3332 U32 lhSize = ((istart[0]) >> 4) & 3;
3335 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3337 litSize = istart[0] & 31;
3340 litSize = ((istart[0] & 15) << 8) + istart[1];
3343 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3344 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3347 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3348 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3349 dctx->litPtr = dctx->litBuffer;
3350 dctx->litSize = litSize;
3354 return ERROR(corruption_detected); /* impossible */
3359 /*! ZSTDv07_buildSeqTable() :
3360 @return : nb bytes read from src,
3361 or an error code if it fails, testable with ZSTDv07_isError()
3363 static size_t ZSTDv07_buildSeqTable(FSEv07_DTable* DTable, U32 type, U32 max, U32 maxLog,
3364 const void* src, size_t srcSize,
3365 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3369 case FSEv07_ENCODING_RLE :
3370 if (!srcSize) return ERROR(srcSize_wrong);
3371 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3372 FSEv07_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */
3374 case FSEv07_ENCODING_RAW :
3375 FSEv07_buildDTable(DTable, defaultNorm, max, defaultLog);
3377 case FSEv07_ENCODING_STATIC:
3378 if (!flagRepeatTable) return ERROR(corruption_detected);
3380 default : /* impossible */
3381 case FSEv07_ENCODING_DYNAMIC :
3384 size_t const headerSize = FSEv07_readNCount(norm, &max, &tableLog, src, srcSize);
3385 if (FSEv07_isError(headerSize)) return ERROR(corruption_detected);
3386 if (tableLog > maxLog) return ERROR(corruption_detected);
3387 FSEv07_buildDTable(DTable, norm, max, tableLog);
3393 static size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr,
3394 FSEv07_DTable* DTableLL, FSEv07_DTable* DTableML, FSEv07_DTable* DTableOffb, U32 flagRepeatTable,
3395 const void* src, size_t srcSize)
3397 const BYTE* const istart = (const BYTE*)src;
3398 const BYTE* const iend = istart + srcSize;
3399 const BYTE* ip = istart;
3402 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3405 { int nbSeq = *ip++;
3406 if (!nbSeq) { *nbSeqPtr=0; return 1; }
3408 if (nbSeq == 0xFF) {
3409 if (ip+2 > iend) return ERROR(srcSize_wrong);
3410 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3412 if (ip >= iend) return ERROR(srcSize_wrong);
3413 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3419 /* FSE table descriptors */
3420 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 */
3421 { U32 const LLtype = *ip >> 6;
3422 U32 const OFtype = (*ip >> 4) & 3;
3423 U32 const MLtype = (*ip >> 2) & 3;
3427 { size_t const llhSize = ZSTDv07_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3428 if (ZSTDv07_isError(llhSize)) return ERROR(corruption_detected);
3431 { size_t const ofhSize = ZSTDv07_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3432 if (ZSTDv07_isError(ofhSize)) return ERROR(corruption_detected);
3435 { size_t const mlhSize = ZSTDv07_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3436 if (ZSTDv07_isError(mlhSize)) return ERROR(corruption_detected);
3451 BITv07_DStream_t DStream;
3452 FSEv07_DState_t stateLL;
3453 FSEv07_DState_t stateOffb;
3454 FSEv07_DState_t stateML;
3455 size_t prevOffset[ZSTDv07_REP_INIT];
3459 static seq_t ZSTDv07_decodeSequence(seqState_t* seqState)
3463 U32 const llCode = FSEv07_peekSymbol(&(seqState->stateLL));
3464 U32 const mlCode = FSEv07_peekSymbol(&(seqState->stateML));
3465 U32 const ofCode = FSEv07_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3467 U32 const llBits = LL_bits[llCode];
3468 U32 const mlBits = ML_bits[mlCode];
3469 U32 const ofBits = ofCode;
3470 U32 const totalBits = llBits+mlBits+ofBits;
3472 static const U32 LL_base[MaxLL+1] = {
3473 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3474 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3475 0x2000, 0x4000, 0x8000, 0x10000 };
3477 static const U32 ML_base[MaxML+1] = {
3478 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
3479 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
3480 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3481 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3483 static const U32 OF_base[MaxOff+1] = {
3484 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
3485 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
3486 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3487 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3494 offset = OF_base[ofCode] + BITv07_readBits(&(seqState->DStream), ofBits); /* <= (ZSTDv07_WINDOWLOG_MAX-1) bits */
3495 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));
3499 if ((llCode == 0) & (offset <= 1)) offset = 1-offset;
3501 size_t const temp = seqState->prevOffset[offset];
3502 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
3503 seqState->prevOffset[1] = seqState->prevOffset[0];
3504 seqState->prevOffset[0] = offset = temp;
3506 offset = seqState->prevOffset[0];
3509 seqState->prevOffset[2] = seqState->prevOffset[1];
3510 seqState->prevOffset[1] = seqState->prevOffset[0];
3511 seqState->prevOffset[0] = offset;
3513 seq.offset = offset;
3516 seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BITv07_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */
3517 if (MEM_32bits() && (mlBits+llBits>24)) BITv07_reloadDStream(&(seqState->DStream));
3519 seq.litLength = LL_base[llCode] + ((llCode>15) ? BITv07_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */
3521 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv07_reloadDStream(&(seqState->DStream));
3523 /* ANS state update */
3524 FSEv07_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */
3525 FSEv07_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */
3526 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream)); /* <= 18 bits */
3527 FSEv07_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */
3534 size_t ZSTDv07_execSequence(BYTE* op,
3535 BYTE* const oend, seq_t sequence,
3536 const BYTE** litPtr, const BYTE* const litLimit,
3537 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3539 BYTE* const oLitEnd = op + sequence.litLength;
3540 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3541 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3542 BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH;
3543 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3544 const BYTE* match = oLitEnd - sequence.offset;
3548 if (sequence.litLength + WILDCOPY_OVERLENGTH > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3549 if (sequenceLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3550 assert(litLimit >= *litPtr);
3551 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);;
3554 ZSTDv07_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3556 *litPtr = iLitEnd; /* update for next sequence */
3559 if (sequence.offset > (size_t)(oLitEnd - base)) {
3560 /* offset beyond prefix */
3561 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3562 match = dictEnd - (base-match);
3563 if (match + sequence.matchLength <= dictEnd) {
3564 memmove(oLitEnd, match, sequence.matchLength);
3565 return sequenceLength;
3567 /* span extDict & currentPrefixSegment */
3568 { size_t const length1 = (size_t)(dictEnd - match);
3569 memmove(oLitEnd, match, length1);
3570 op = oLitEnd + length1;
3571 sequence.matchLength -= length1;
3573 if (op > oend_w || sequence.matchLength < MINMATCH) {
3574 while (op < oMatchEnd) *op++ = *match++;
3575 return sequenceLength;
3578 /* Requirement: op <= oend_w */
3580 /* match within prefix */
3581 if (sequence.offset < 8) {
3582 /* close range match, overlap */
3583 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3584 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
3585 int const sub2 = dec64table[sequence.offset];
3590 match += dec32table[sequence.offset];
3591 ZSTDv07_copy4(op+4, match);
3594 ZSTDv07_copy8(op, match);
3596 op += 8; match += 8;
3598 if (oMatchEnd > oend-(16-MINMATCH)) {
3600 ZSTDv07_wildcopy(op, match, oend_w - op);
3601 match += oend_w - op;
3604 while (op < oMatchEnd) *op++ = *match++;
3606 ZSTDv07_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3608 return sequenceLength;
3612 static size_t ZSTDv07_decompressSequences(
3614 void* dst, size_t maxDstSize,
3615 const void* seqStart, size_t seqSize)
3617 const BYTE* ip = (const BYTE*)seqStart;
3618 const BYTE* const iend = ip + seqSize;
3619 BYTE* const ostart = (BYTE*)dst;
3620 BYTE* const oend = ostart + maxDstSize;
3622 const BYTE* litPtr = dctx->litPtr;
3623 const BYTE* const litEnd = litPtr + dctx->litSize;
3624 FSEv07_DTable* DTableLL = dctx->LLTable;
3625 FSEv07_DTable* DTableML = dctx->MLTable;
3626 FSEv07_DTable* DTableOffb = dctx->OffTable;
3627 const BYTE* const base = (const BYTE*) (dctx->base);
3628 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3629 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3632 /* Build Decoding Tables */
3633 { size_t const seqHSize = ZSTDv07_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize);
3634 if (ZSTDv07_isError(seqHSize)) return seqHSize;
3638 /* Regen sequences */
3640 seqState_t seqState;
3641 dctx->fseEntropy = 1;
3642 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; }
3643 { size_t const errorCode = BITv07_initDStream(&(seqState.DStream), ip, iend-ip);
3644 if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3645 FSEv07_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3646 FSEv07_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3647 FSEv07_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3649 for ( ; (BITv07_reloadDStream(&(seqState.DStream)) <= BITv07_DStream_completed) && nbSeq ; ) {
3651 { seq_t const sequence = ZSTDv07_decodeSequence(&seqState);
3652 size_t const oneSeqSize = ZSTDv07_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3653 if (ZSTDv07_isError(oneSeqSize)) return oneSeqSize;
3657 /* check if reached exact end */
3658 if (nbSeq) return ERROR(corruption_detected);
3659 /* save reps for next block */
3660 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
3663 /* last literal segment */
3664 { size_t const lastLLSize = litEnd - litPtr;
3665 /* if (litPtr > litEnd) return ERROR(corruption_detected); */ /* too many literals already used */
3666 if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
3667 if (lastLLSize > 0) {
3668 memcpy(op, litPtr, lastLLSize);
3677 static void ZSTDv07_checkContinuity(ZSTDv07_DCtx* dctx, const void* dst)
3679 if (dst != dctx->previousDstEnd) { /* not contiguous */
3680 dctx->dictEnd = dctx->previousDstEnd;
3681 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3683 dctx->previousDstEnd = dst;
3688 static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx* dctx,
3689 void* dst, size_t dstCapacity,
3690 const void* src, size_t srcSize)
3691 { /* blockType == blockCompressed */
3692 const BYTE* ip = (const BYTE*)src;
3694 if (srcSize >= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong);
3696 /* Decode literals sub-block */
3697 { size_t const litCSize = ZSTDv07_decodeLiteralsBlock(dctx, src, srcSize);
3698 if (ZSTDv07_isError(litCSize)) return litCSize;
3700 srcSize -= litCSize;
3702 return ZSTDv07_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3706 size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx,
3707 void* dst, size_t dstCapacity,
3708 const void* src, size_t srcSize)
3711 ZSTDv07_checkContinuity(dctx, dst);
3712 dSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3713 dctx->previousDstEnd = (char*)dst + dSize;
3718 /** ZSTDv07_insertBlock() :
3719 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
3720 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize)
3722 ZSTDv07_checkContinuity(dctx, blockStart);
3723 dctx->previousDstEnd = (const char*)blockStart + blockSize;
3728 static size_t ZSTDv07_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length)
3730 if (length > dstCapacity) return ERROR(dstSize_tooSmall);
3732 memset(dst, byte, length);
3738 /*! ZSTDv07_decompressFrame() :
3739 * `dctx` must be properly initialized */
3740 static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx* dctx,
3741 void* dst, size_t dstCapacity,
3742 const void* src, size_t srcSize)
3744 const BYTE* ip = (const BYTE*)src;
3745 const BYTE* const iend = ip + srcSize;
3746 BYTE* const ostart = (BYTE*)dst;
3747 BYTE* const oend = ostart + dstCapacity;
3749 size_t remainingSize = srcSize;
3752 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3755 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3756 if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3757 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3758 if (ZSTDv07_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3759 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3762 /* Loop on each block */
3765 blockProperties_t blockProperties;
3766 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, iend-ip, &blockProperties);
3767 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3769 ip += ZSTDv07_blockHeaderSize;
3770 remainingSize -= ZSTDv07_blockHeaderSize;
3771 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3773 switch(blockProperties.blockType)
3776 decodedSize = ZSTDv07_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3779 decodedSize = ZSTDv07_copyRawBlock(op, oend-op, ip, cBlockSize);
3782 decodedSize = ZSTDv07_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
3786 if (remainingSize) return ERROR(srcSize_wrong);
3790 return ERROR(GENERIC); /* impossible */
3792 if (blockProperties.blockType == bt_end) break; /* bt_end */
3794 if (ZSTDv07_isError(decodedSize)) return decodedSize;
3795 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
3798 remainingSize -= cBlockSize;
3805 /*! ZSTDv07_decompress_usingPreparedDCtx() :
3806 * Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
3807 * It avoids reloading the dictionary each time.
3808 * `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict().
3809 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
3810 static size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* refDCtx,
3811 void* dst, size_t dstCapacity,
3812 const void* src, size_t srcSize)
3814 ZSTDv07_copyDCtx(dctx, refDCtx);
3815 ZSTDv07_checkContinuity(dctx, dst);
3816 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3820 size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx* dctx,
3821 void* dst, size_t dstCapacity,
3822 const void* src, size_t srcSize,
3823 const void* dict, size_t dictSize)
3825 ZSTDv07_decompressBegin_usingDict(dctx, dict, dictSize);
3826 ZSTDv07_checkContinuity(dctx, dst);
3827 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3831 size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3833 return ZSTDv07_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3837 size_t ZSTDv07_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3839 #if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1)
3841 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx();
3842 if (dctx==NULL) return ERROR(memory_allocation);
3843 regenSize = ZSTDv07_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3844 ZSTDv07_freeDCtx(dctx);
3846 #else /* stack mode */
3848 return ZSTDv07_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3852 /* ZSTD_errorFrameSizeInfoLegacy() :
3853 assumes `cSize` and `dBound` are _not_ NULL */
3854 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3857 *dBound = ZSTD_CONTENTSIZE_ERROR;
3860 void ZSTDv07_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3862 const BYTE* ip = (const BYTE*)src;
3863 size_t remainingSize = srcSize;
3864 size_t nbBlocks = 0;
3867 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) {
3868 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3873 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, srcSize);
3874 if (ZSTDv07_isError(frameHeaderSize)) {
3875 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize);
3878 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3879 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3882 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) {
3883 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3886 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3889 /* Loop on each block */
3891 blockProperties_t blockProperties;
3892 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, remainingSize, &blockProperties);
3893 if (ZSTDv07_isError(cBlockSize)) {
3894 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3898 ip += ZSTDv07_blockHeaderSize;
3899 remainingSize -= ZSTDv07_blockHeaderSize;
3901 if (blockProperties.blockType == bt_end) break;
3903 if (cBlockSize > remainingSize) {
3904 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3909 remainingSize -= cBlockSize;
3913 *cSize = ip - (const BYTE*)src;
3914 *dBound = nbBlocks * ZSTDv07_BLOCKSIZE_ABSOLUTEMAX;
3917 /*_******************************
3918 * Streaming Decompression API
3919 ********************************/
3920 size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx)
3922 return dctx->expected;
3925 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx)
3927 return dctx->stage == ZSTDds_skipFrame;
3930 /** ZSTDv07_decompressContinue() :
3931 * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
3932 * or an error code, which can be tested using ZSTDv07_isError() */
3933 size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3936 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3937 if (dstCapacity) ZSTDv07_checkContinuity(dctx, dst);
3939 switch (dctx->stage)
3941 case ZSTDds_getFrameHeaderSize :
3942 if (srcSize != ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3943 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3944 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
3945 dctx->expected = ZSTDv07_skippableHeaderSize - ZSTDv07_frameHeaderSize_min; /* magic number + skippable frame length */
3946 dctx->stage = ZSTDds_decodeSkippableHeader;
3949 dctx->headerSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3950 if (ZSTDv07_isError(dctx->headerSize)) return dctx->headerSize;
3951 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
3952 if (dctx->headerSize > ZSTDv07_frameHeaderSize_min) {
3953 dctx->expected = dctx->headerSize - ZSTDv07_frameHeaderSize_min;
3954 dctx->stage = ZSTDds_decodeFrameHeader;
3957 dctx->expected = 0; /* not necessary to copy more */
3959 case ZSTDds_decodeFrameHeader:
3961 memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
3962 result = ZSTDv07_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
3963 if (ZSTDv07_isError(result)) return result;
3964 dctx->expected = ZSTDv07_blockHeaderSize;
3965 dctx->stage = ZSTDds_decodeBlockHeader;
3968 case ZSTDds_decodeBlockHeader:
3969 { blockProperties_t bp;
3970 size_t const cBlockSize = ZSTDv07_getcBlockSize(src, ZSTDv07_blockHeaderSize, &bp);
3971 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3972 if (bp.blockType == bt_end) {
3973 if (dctx->fParams.checksumFlag) {
3974 U64 const h64 = XXH64_digest(&dctx->xxhState);
3975 U32 const h32 = (U32)(h64>>11) & ((1<<22)-1);
3976 const BYTE* const ip = (const BYTE*)src;
3977 U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16);
3978 if (check32 != h32) return ERROR(checksum_wrong);
3981 dctx->stage = ZSTDds_getFrameHeaderSize;
3983 dctx->expected = cBlockSize;
3984 dctx->bType = bp.blockType;
3985 dctx->stage = ZSTDds_decompressBlock;
3989 case ZSTDds_decompressBlock:
3994 rSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3997 rSize = ZSTDv07_copyRawBlock(dst, dstCapacity, src, srcSize);
4000 return ERROR(GENERIC); /* not yet handled */
4002 case bt_end : /* should never happen (filtered at phase 1) */
4006 return ERROR(GENERIC); /* impossible */
4008 dctx->stage = ZSTDds_decodeBlockHeader;
4009 dctx->expected = ZSTDv07_blockHeaderSize;
4010 if (ZSTDv07_isError(rSize)) return rSize;
4011 dctx->previousDstEnd = (char*)dst + rSize;
4012 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
4015 case ZSTDds_decodeSkippableHeader:
4016 { memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
4017 dctx->expected = MEM_readLE32(dctx->headerBuffer + 4);
4018 dctx->stage = ZSTDds_skipFrame;
4021 case ZSTDds_skipFrame:
4022 { dctx->expected = 0;
4023 dctx->stage = ZSTDds_getFrameHeaderSize;
4027 return ERROR(GENERIC); /* impossible */
4032 static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4034 dctx->dictEnd = dctx->previousDstEnd;
4035 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
4037 dctx->previousDstEnd = (const char*)dict + dictSize;
4041 static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx* dctx, const void* const dict, size_t const dictSize)
4043 const BYTE* dictPtr = (const BYTE*)dict;
4044 const BYTE* const dictEnd = dictPtr + dictSize;
4046 { size_t const hSize = HUFv07_readDTableX4(dctx->hufTable, dict, dictSize);
4047 if (HUFv07_isError(hSize)) return ERROR(dictionary_corrupted);
4051 { short offcodeNCount[MaxOff+1];
4052 U32 offcodeMaxValue=MaxOff, offcodeLog;
4053 size_t const offcodeHeaderSize = FSEv07_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
4054 if (FSEv07_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
4055 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
4056 { size_t const errorCode = FSEv07_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
4057 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4058 dictPtr += offcodeHeaderSize;
4061 { short matchlengthNCount[MaxML+1];
4062 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
4063 size_t const matchlengthHeaderSize = FSEv07_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
4064 if (FSEv07_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
4065 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
4066 { size_t const errorCode = FSEv07_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
4067 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4068 dictPtr += matchlengthHeaderSize;
4071 { short litlengthNCount[MaxLL+1];
4072 unsigned litlengthMaxValue = MaxLL, litlengthLog;
4073 size_t const litlengthHeaderSize = FSEv07_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
4074 if (FSEv07_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
4075 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
4076 { size_t const errorCode = FSEv07_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
4077 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4078 dictPtr += litlengthHeaderSize;
4081 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
4082 dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] == 0 || dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
4083 dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] == 0 || dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
4084 dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] == 0 || dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
4087 dctx->litEntropy = dctx->fseEntropy = 1;
4088 return dictPtr - (const BYTE*)dict;
4091 static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4093 if (dictSize < 8) return ZSTDv07_refDictContent(dctx, dict, dictSize);
4094 { U32 const magic = MEM_readLE32(dict);
4095 if (magic != ZSTDv07_DICT_MAGIC) {
4096 return ZSTDv07_refDictContent(dctx, dict, dictSize); /* pure content mode */
4098 dctx->dictID = MEM_readLE32((const char*)dict + 4);
4100 /* load entropy tables */
4101 dict = (const char*)dict + 8;
4103 { size_t const eSize = ZSTDv07_loadEntropy(dctx, dict, dictSize);
4104 if (ZSTDv07_isError(eSize)) return ERROR(dictionary_corrupted);
4105 dict = (const char*)dict + eSize;
4109 /* reference dictionary content */
4110 return ZSTDv07_refDictContent(dctx, dict, dictSize);
4114 size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4116 { size_t const errorCode = ZSTDv07_decompressBegin(dctx);
4117 if (ZSTDv07_isError(errorCode)) return errorCode; }
4119 if (dict && dictSize) {
4120 size_t const errorCode = ZSTDv07_decompress_insertDictionary(dctx, dict, dictSize);
4121 if (ZSTDv07_isError(errorCode)) return ERROR(dictionary_corrupted);
4128 struct ZSTDv07_DDict_s {
4131 ZSTDv07_DCtx* refContext;
4132 }; /* typedef'd tp ZSTDv07_CDict within zstd.h */
4134 static ZSTDv07_DDict* ZSTDv07_createDDict_advanced(const void* dict, size_t dictSize, ZSTDv07_customMem customMem)
4136 if (!customMem.customAlloc && !customMem.customFree)
4137 customMem = defaultCustomMem;
4139 if (!customMem.customAlloc || !customMem.customFree)
4142 { ZSTDv07_DDict* const ddict = (ZSTDv07_DDict*) customMem.customAlloc(customMem.opaque, sizeof(*ddict));
4143 void* const dictContent = customMem.customAlloc(customMem.opaque, dictSize);
4144 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx_advanced(customMem);
4146 if (!dictContent || !ddict || !dctx) {
4147 customMem.customFree(customMem.opaque, dictContent);
4148 customMem.customFree(customMem.opaque, ddict);
4149 customMem.customFree(customMem.opaque, dctx);
4153 memcpy(dictContent, dict, dictSize);
4154 { size_t const errorCode = ZSTDv07_decompressBegin_usingDict(dctx, dictContent, dictSize);
4155 if (ZSTDv07_isError(errorCode)) {
4156 customMem.customFree(customMem.opaque, dictContent);
4157 customMem.customFree(customMem.opaque, ddict);
4158 customMem.customFree(customMem.opaque, dctx);
4162 ddict->dict = dictContent;
4163 ddict->dictSize = dictSize;
4164 ddict->refContext = dctx;
4169 /*! ZSTDv07_createDDict() :
4170 * Create a digested dictionary, ready to start decompression without startup delay.
4171 * `dict` can be released after `ZSTDv07_DDict` creation */
4172 ZSTDv07_DDict* ZSTDv07_createDDict(const void* dict, size_t dictSize)
4174 ZSTDv07_customMem const allocator = { NULL, NULL, NULL };
4175 return ZSTDv07_createDDict_advanced(dict, dictSize, allocator);
4178 size_t ZSTDv07_freeDDict(ZSTDv07_DDict* ddict)
4180 ZSTDv07_freeFunction const cFree = ddict->refContext->customMem.customFree;
4181 void* const opaque = ddict->refContext->customMem.opaque;
4182 ZSTDv07_freeDCtx(ddict->refContext);
4183 cFree(opaque, ddict->dict);
4184 cFree(opaque, ddict);
4188 /*! ZSTDv07_decompress_usingDDict() :
4189 * Decompression using a pre-digested Dictionary
4190 * Use dictionary without significant overhead. */
4191 ZSTDLIBv07_API size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx* dctx,
4192 void* dst, size_t dstCapacity,
4193 const void* src, size_t srcSize,
4194 const ZSTDv07_DDict* ddict)
4196 return ZSTDv07_decompress_usingPreparedDCtx(dctx, ddict->refContext,
4201 Buffered version of Zstd compression library
4202 Copyright (C) 2015-2016, Yann Collet.
4204 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
4206 Redistribution and use in source and binary forms, with or without
4207 modification, are permitted provided that the following conditions are
4209 * Redistributions of source code must retain the above copyright
4210 notice, this list of conditions and the following disclaimer.
4211 * Redistributions in binary form must reproduce the above
4212 copyright notice, this list of conditions and the following disclaimer
4213 in the documentation and/or other materials provided with the
4215 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4216 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
4217 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
4218 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
4219 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4220 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
4221 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
4222 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
4223 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
4224 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
4225 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4227 You can contact the author at :
4228 - zstd homepage : https://facebook.github.io/zstd/
4233 /*-***************************************************************************
4234 * Streaming decompression howto
4236 * A ZBUFFv07_DCtx object is required to track streaming operations.
4237 * Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources.
4238 * Use ZBUFFv07_decompressInit() to start a new decompression operation,
4239 * or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary.
4240 * Note that ZBUFFv07_DCtx objects can be re-init multiple times.
4242 * Use ZBUFFv07_decompressContinue() repetitively to consume your input.
4243 * *srcSizePtr and *dstCapacityPtr can be any size.
4244 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
4245 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
4246 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
4247 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
4248 * or 0 when a frame is completely decoded,
4249 * or an error code, which can be tested using ZBUFFv07_isError().
4251 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize()
4252 * output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
4253 * input : ZBUFFv07_recommendedDInSize == 128KB + 3;
4254 * just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
4255 * *******************************************************************************/
4257 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
4258 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv07_dStage;
4260 /* *** Resource management *** */
4261 struct ZBUFFv07_DCtx_s {
4263 ZSTDv07_frameParams fParams;
4264 ZBUFFv07_dStage stage;
4273 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
4275 ZSTDv07_customMem customMem;
4276 }; /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */
4278 ZSTDLIBv07_API ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem);
4280 ZBUFFv07_DCtx* ZBUFFv07_createDCtx(void)
4282 return ZBUFFv07_createDCtx_advanced(defaultCustomMem);
4285 ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem)
4289 if (!customMem.customAlloc && !customMem.customFree)
4290 customMem = defaultCustomMem;
4292 if (!customMem.customAlloc || !customMem.customFree)
4295 zbd = (ZBUFFv07_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFFv07_DCtx));
4296 if (zbd==NULL) return NULL;
4297 memset(zbd, 0, sizeof(ZBUFFv07_DCtx));
4298 memcpy(&zbd->customMem, &customMem, sizeof(ZSTDv07_customMem));
4299 zbd->zd = ZSTDv07_createDCtx_advanced(customMem);
4300 if (zbd->zd == NULL) { ZBUFFv07_freeDCtx(zbd); return NULL; }
4301 zbd->stage = ZBUFFds_init;
4305 size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx* zbd)
4307 if (zbd==NULL) return 0; /* support free on null */
4308 ZSTDv07_freeDCtx(zbd->zd);
4309 if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4310 if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4311 zbd->customMem.customFree(zbd->customMem.opaque, zbd);
4316 /* *** Initialization *** */
4318 size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx* zbd, const void* dict, size_t dictSize)
4320 zbd->stage = ZBUFFds_loadHeader;
4321 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
4322 return ZSTDv07_decompressBegin_usingDict(zbd->zd, dict, dictSize);
4325 size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx* zbd)
4327 return ZBUFFv07_decompressInitDictionary(zbd, NULL, 0);
4331 /* internal util function */
4332 MEM_STATIC size_t ZBUFFv07_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
4334 size_t const length = MIN(dstCapacity, srcSize);
4336 memcpy(dst, src, length);
4342 /* *** Decompression *** */
4344 size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx* zbd,
4345 void* dst, size_t* dstCapacityPtr,
4346 const void* src, size_t* srcSizePtr)
4348 const char* const istart = (const char*)src;
4349 const char* const iend = istart + *srcSizePtr;
4350 const char* ip = istart;
4351 char* const ostart = (char*)dst;
4352 char* const oend = ostart + *dstCapacityPtr;
4360 return ERROR(init_missing);
4362 case ZBUFFds_loadHeader :
4363 { size_t const hSize = ZSTDv07_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
4364 if (ZSTDv07_isError(hSize)) return hSize;
4366 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */
4367 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */
4369 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
4370 zbd->lhSize += iend-ip;
4371 *dstCapacityPtr = 0;
4372 return (hSize - zbd->lhSize) + ZSTDv07_blockHeaderSize; /* remaining header bytes + next block header */
4374 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
4378 /* Consume header */
4379 { size_t const h1Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv07_frameHeaderSize_min */
4380 size_t const h1Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4381 if (ZSTDv07_isError(h1Result)) return h1Result;
4382 if (h1Size < zbd->lhSize) { /* long header */
4383 size_t const h2Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4384 size_t const h2Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4385 if (ZSTDv07_isError(h2Result)) return h2Result;
4388 zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN);
4390 /* Frame header instruct buffer sizes */
4391 { size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX);
4392 zbd->blockSize = blockSize;
4393 if (zbd->inBuffSize < blockSize) {
4394 zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4395 zbd->inBuffSize = blockSize;
4396 zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize);
4397 if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4399 { size_t const neededOutSize = zbd->fParams.windowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
4400 if (zbd->outBuffSize < neededOutSize) {
4401 zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4402 zbd->outBuffSize = neededOutSize;
4403 zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize);
4404 if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4406 zbd->stage = ZBUFFds_read;
4410 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4411 if (neededInSize==0) { /* end of frame */
4412 zbd->stage = ZBUFFds_init;
4416 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
4417 const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4418 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4419 zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart),
4421 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4423 if (!decodedSize && !isSkipFrame) break; /* this was just a header */
4424 zbd->outEnd = zbd->outStart + decodedSize;
4425 zbd->stage = ZBUFFds_flush;
4428 if (ip==iend) { notDone = 0; break; } /* no more input */
4429 zbd->stage = ZBUFFds_load;
4433 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4434 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */
4436 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */
4437 loadedSize = ZBUFFv07_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4439 zbd->inPos += loadedSize;
4440 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
4442 /* decode loaded input */
4443 { const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4444 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4445 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4446 zbd->inBuff, neededInSize);
4447 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4448 zbd->inPos = 0; /* input is consumed */
4449 if (!decodedSize && !isSkipFrame) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */
4450 zbd->outEnd = zbd->outStart + decodedSize;
4451 zbd->stage = ZBUFFds_flush;
4458 { size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4459 size_t const flushedSize = ZBUFFv07_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4461 zbd->outStart += flushedSize;
4462 if (flushedSize == toFlushSize) {
4463 zbd->stage = ZBUFFds_read;
4464 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4465 zbd->outStart = zbd->outEnd = 0;
4468 /* cannot flush everything */
4472 default: return ERROR(GENERIC); /* impossible */
4476 *srcSizePtr = ip-istart;
4477 *dstCapacityPtr = op-ostart;
4478 { size_t nextSrcSizeHint = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4479 nextSrcSizeHint -= zbd->inPos; /* already loaded*/
4480 return nextSrcSizeHint;
4486 /* *************************************
4488 ***************************************/
4489 size_t ZBUFFv07_recommendedDInSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + ZSTDv07_blockHeaderSize /* block header size*/ ; }
4490 size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX; }