2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of this source tree. An additional grant
7 * of patent rights can be found in the PATENTS file in the same directory.
12 #include <stddef.h> /* size_t, ptrdiff_t */
13 #include <string.h> /* memcpy */
14 #include <stdlib.h> /* malloc, free, qsort */
16 #ifndef XXH_STATIC_LINKING_ONLY
17 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
19 #include "xxhash.h" /* XXH64_* */
22 #define FSEv07_STATIC_LINKING_ONLY /* FSEv07_MIN_TABLELOG */
23 #define HUFv07_STATIC_LINKING_ONLY /* HUFv07_TABLELOG_ABSOLUTEMAX */
24 #define ZSTDv07_STATIC_LINKING_ONLY
26 #include "error_private.h"
29 #ifdef ZSTDv07_STATIC_LINKING_ONLY
31 /* ====================================================================================
32 * The definitions in this section are considered experimental.
33 * They should never be used with a dynamic library, as they may change in the future.
34 * They are provided for advanced usages.
35 * Use them only in association with static linking.
36 * ==================================================================================== */
39 #define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U
41 #define ZSTDv07_WINDOWLOG_MAX_32 25
42 #define ZSTDv07_WINDOWLOG_MAX_64 27
43 #define ZSTDv07_WINDOWLOG_MAX ((U32)(MEM_32bits() ? ZSTDv07_WINDOWLOG_MAX_32 : ZSTDv07_WINDOWLOG_MAX_64))
44 #define ZSTDv07_WINDOWLOG_MIN 18
45 #define ZSTDv07_CHAINLOG_MAX (ZSTDv07_WINDOWLOG_MAX+1)
46 #define ZSTDv07_CHAINLOG_MIN 4
47 #define ZSTDv07_HASHLOG_MAX ZSTDv07_WINDOWLOG_MAX
48 #define ZSTDv07_HASHLOG_MIN 12
49 #define ZSTDv07_HASHLOG3_MAX 17
50 #define ZSTDv07_SEARCHLOG_MAX (ZSTDv07_WINDOWLOG_MAX-1)
51 #define ZSTDv07_SEARCHLOG_MIN 1
52 #define ZSTDv07_SEARCHLENGTH_MAX 7
53 #define ZSTDv07_SEARCHLENGTH_MIN 3
54 #define ZSTDv07_TARGETLENGTH_MIN 4
55 #define ZSTDv07_TARGETLENGTH_MAX 999
57 #define ZSTDv07_FRAMEHEADERSIZE_MAX 18 /* for static allocation */
58 static const size_t ZSTDv07_frameHeaderSize_min = 5;
59 static const size_t ZSTDv07_frameHeaderSize_max = ZSTDv07_FRAMEHEADERSIZE_MAX;
60 static const size_t ZSTDv07_skippableHeaderSize = 8; /* magic number + skippable frame length */
63 /* custom memory allocation functions */
64 typedef void* (*ZSTDv07_allocFunction) (void* opaque, size_t size);
65 typedef void (*ZSTDv07_freeFunction) (void* opaque, void* address);
66 typedef struct { ZSTDv07_allocFunction customAlloc; ZSTDv07_freeFunction customFree; void* opaque; } ZSTDv07_customMem;
69 /*--- Advanced Decompression functions ---*/
71 /*! ZSTDv07_estimateDCtxSize() :
72 * Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */
73 ZSTDLIBv07_API size_t ZSTDv07_estimateDCtxSize(void);
75 /*! ZSTDv07_createDCtx_advanced() :
76 * Create a ZSTD decompression context using external alloc and free functions */
77 ZSTDLIBv07_API ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem);
79 /*! ZSTDv07_sizeofDCtx() :
80 * Gives the amount of memory used by a given ZSTDv07_DCtx */
81 ZSTDLIBv07_API size_t ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx* dctx);
84 /* ******************************************************************
85 * Buffer-less streaming functions (synchronous mode)
86 ********************************************************************/
88 ZSTDLIBv07_API size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx);
89 ZSTDLIBv07_API size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize);
90 ZSTDLIBv07_API void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* preparedDCtx);
92 ZSTDLIBv07_API size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx);
93 ZSTDLIBv07_API size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
96 Buffer-less streaming decompression (synchronous mode)
98 A ZSTDv07_DCtx object is required to track streaming operations.
99 Use ZSTDv07_createDCtx() / ZSTDv07_freeDCtx() to manage it.
100 A ZSTDv07_DCtx object can be re-used multiple times.
102 First optional operation is to retrieve frame parameters, using ZSTDv07_getFrameParams(), which doesn't consume the input.
103 It can provide the minimum size of rolling buffer required to properly decompress data (`windowSize`),
104 and optionally the final size of uncompressed content.
105 (Note : content size is an optional info that may not be present. 0 means : content size unknown)
106 Frame parameters are extracted from the beginning of compressed frame.
107 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)
108 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
109 Result : 0 when successful, it means the ZSTDv07_frameParams structure has been filled.
110 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
111 errorCode, which can be tested using ZSTDv07_isError()
113 Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().
114 Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().
116 Then use ZSTDv07_nextSrcSizeToDecompress() and ZSTDv07_decompressContinue() alternatively.
117 ZSTDv07_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv07_decompressContinue().
118 ZSTDv07_decompressContinue() requires this exact amount of bytes, or it will fail.
120 @result of ZSTDv07_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity).
121 It can be zero, which is not an error; it just means ZSTDv07_decompressContinue() has decoded some header.
123 ZSTDv07_decompressContinue() needs previous data blocks during decompression, up to `windowSize`.
124 They should preferably be located contiguously, prior to current block.
125 Alternatively, a round buffer of sufficient size is also possible. Sufficient size is determined by frame parameters.
126 ZSTDv07_decompressContinue() is very sensitive to contiguity,
127 if 2 blocks don't follow each other, make sure that either the compressor breaks contiguity at the same place,
128 or that previous contiguous segment is large enough to properly handle maximum back-reference.
130 A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.
131 Context can then be reset to start a new decompression.
134 == Special case : skippable frames ==
136 Skippable frames allow the integration of user-defined data into a flow of concatenated frames.
137 Skippable frames will be ignored (skipped) by a decompressor. The format of skippable frame is following:
138 a) Skippable frame ID - 4 Bytes, Little endian format, any value from 0x184D2A50 to 0x184D2A5F
139 b) Frame Size - 4 Bytes, Little endian format, unsigned 32-bits
140 c) Frame Content - any content (User Data) of length equal to Frame Size
141 For skippable frames ZSTDv07_decompressContinue() always returns 0.
142 For skippable frames ZSTDv07_getFrameParams() returns fparamsPtr->windowLog==0 what means that a frame is skippable.
143 It also returns Frame Size as fparamsPtr->frameContentSize.
147 /* **************************************
149 ****************************************/
150 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
151 Frame metadata cost is typically ~18 bytes, which can be non-negligible for very small blocks (< 100 bytes).
152 User will have to take in charge required information to regenerate data, such as compressed and content sizes.
154 A few rules to respect :
155 - Compressing and decompressing require a context structure
156 + Use ZSTDv07_createCCtx() and ZSTDv07_createDCtx()
157 - It is necessary to init context before starting
158 + compression : ZSTDv07_compressBegin()
159 + decompression : ZSTDv07_decompressBegin()
160 + variants _usingDict() are also allowed
161 + copyCCtx() and copyDCtx() work too
162 - Block size is limited, it must be <= ZSTDv07_getBlockSizeMax()
163 + If you need to compress more, cut data into multiple blocks
164 + Consider using the regular ZSTDv07_compress() instead, as frame metadata costs become negligible when source size is large.
165 - When a block is considered not compressible enough, ZSTDv07_compressBlock() result will be zero.
166 In which case, nothing is produced into `dst`.
167 + User must test for such outcome and deal directly with uncompressed data
168 + ZSTDv07_decompressBlock() doesn't accept uncompressed data as input !!!
169 + In case of multiple successive blocks, decoder must be informed of uncompressed block existence to follow proper history.
170 Use ZSTDv07_insertBlock() in such a case.
173 #define ZSTDv07_BLOCKSIZE_ABSOLUTEMAX (128 * 1024) /* define, for static allocation */
174 ZSTDLIBv07_API size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
175 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize); /**< insert block into `dctx` history. Useful for uncompressed blocks */
178 #endif /* ZSTDv07_STATIC_LINKING_ONLY */
181 /* ******************************************************************
183 low-level memory access routines
184 Copyright (C) 2013-2015, Yann Collet.
186 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
188 Redistribution and use in source and binary forms, with or without
189 modification, are permitted provided that the following conditions are
192 * Redistributions of source code must retain the above copyright
193 notice, this list of conditions and the following disclaimer.
194 * Redistributions in binary form must reproduce the above
195 copyright notice, this list of conditions and the following disclaimer
196 in the documentation and/or other materials provided with the
199 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
200 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
201 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
202 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
203 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
204 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
205 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
206 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
207 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
208 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
209 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
211 You can contact the author at :
212 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
213 - Public forum : https://groups.google.com/forum/#!forum/lz4c
214 ****************************************************************** */
218 #if defined (__cplusplus)
222 /*-****************************************
224 ******************************************/
225 #if defined(_MSC_VER) /* Visual Studio */
226 # include <stdlib.h> /* _byteswap_ulong */
227 # include <intrin.h> /* _byteswap_* */
229 #if defined(__GNUC__)
230 # define MEM_STATIC static __attribute__((unused))
231 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
232 # define MEM_STATIC static inline
233 #elif defined(_MSC_VER)
234 # define MEM_STATIC static __inline
236 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
240 /*-**************************************************************
242 *****************************************************************/
243 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
245 typedef uint8_t BYTE;
246 typedef uint16_t U16;
248 typedef uint32_t U32;
250 typedef uint64_t U64;
253 typedef unsigned char BYTE;
254 typedef unsigned short U16;
255 typedef signed short S16;
256 typedef unsigned int U32;
257 typedef signed int S32;
258 typedef unsigned long long U64;
259 typedef signed long long S64;
263 /*-**************************************************************
265 *****************************************************************/
266 /* MEM_FORCE_MEMORY_ACCESS :
267 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
268 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
269 * The below switch allow to select different access method for improved performance.
270 * Method 0 (default) : use `memcpy()`. Safe and portable.
271 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
272 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
273 * Method 2 : direct access. This method is portable but violate C standard.
274 * It can generate buggy code on targets depending on alignment.
275 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
276 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
277 * Prefer these methods in priority order (0 > 1 > 2)
279 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
280 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
281 # define MEM_FORCE_MEMORY_ACCESS 2
282 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
283 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
284 # define MEM_FORCE_MEMORY_ACCESS 1
288 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
289 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
291 MEM_STATIC unsigned MEM_isLittleEndian(void)
293 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
297 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
299 /* violates C standard, by lying on structure alignment.
300 Only use if no other choice to achieve best performance on target platform */
301 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
302 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
303 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
305 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
307 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
309 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
310 /* currently only defined for gcc and icc */
311 typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign;
313 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
314 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
315 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
317 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
321 /* default method, safe and standard.
322 can sometimes prove slower */
324 MEM_STATIC U16 MEM_read16(const void* memPtr)
326 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
329 MEM_STATIC U32 MEM_read32(const void* memPtr)
331 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
334 MEM_STATIC U64 MEM_read64(const void* memPtr)
336 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
339 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
341 memcpy(memPtr, &value, sizeof(value));
344 #endif /* MEM_FORCE_MEMORY_ACCESS */
346 MEM_STATIC U32 MEM_swap32(U32 in)
348 #if defined(_MSC_VER) /* Visual Studio */
349 return _byteswap_ulong(in);
350 #elif defined (__GNUC__)
351 return __builtin_bswap32(in);
353 return ((in << 24) & 0xff000000 ) |
354 ((in << 8) & 0x00ff0000 ) |
355 ((in >> 8) & 0x0000ff00 ) |
356 ((in >> 24) & 0x000000ff );
360 MEM_STATIC U64 MEM_swap64(U64 in)
362 #if defined(_MSC_VER) /* Visual Studio */
363 return _byteswap_uint64(in);
364 #elif defined (__GNUC__)
365 return __builtin_bswap64(in);
367 return ((in << 56) & 0xff00000000000000ULL) |
368 ((in << 40) & 0x00ff000000000000ULL) |
369 ((in << 24) & 0x0000ff0000000000ULL) |
370 ((in << 8) & 0x000000ff00000000ULL) |
371 ((in >> 8) & 0x00000000ff000000ULL) |
372 ((in >> 24) & 0x0000000000ff0000ULL) |
373 ((in >> 40) & 0x000000000000ff00ULL) |
374 ((in >> 56) & 0x00000000000000ffULL);
379 /*=== Little endian r/w ===*/
381 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
383 if (MEM_isLittleEndian())
384 return MEM_read16(memPtr);
386 const BYTE* p = (const BYTE*)memPtr;
387 return (U16)(p[0] + (p[1]<<8));
391 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
393 if (MEM_isLittleEndian()) {
394 MEM_write16(memPtr, val);
396 BYTE* p = (BYTE*)memPtr;
398 p[1] = (BYTE)(val>>8);
402 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
404 if (MEM_isLittleEndian())
405 return MEM_read32(memPtr);
407 return MEM_swap32(MEM_read32(memPtr));
411 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
413 if (MEM_isLittleEndian())
414 return MEM_read64(memPtr);
416 return MEM_swap64(MEM_read64(memPtr));
419 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
422 return (size_t)MEM_readLE32(memPtr);
424 return (size_t)MEM_readLE64(memPtr);
429 #if defined (__cplusplus)
433 #endif /* MEM_H_MODULE */
434 /* ******************************************************************
437 header file (to include)
438 Copyright (C) 2013-2016, Yann Collet.
440 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
442 Redistribution and use in source and binary forms, with or without
443 modification, are permitted provided that the following conditions are
446 * Redistributions of source code must retain the above copyright
447 notice, this list of conditions and the following disclaimer.
448 * Redistributions in binary form must reproduce the above
449 copyright notice, this list of conditions and the following disclaimer
450 in the documentation and/or other materials provided with the
453 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
454 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
455 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
456 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
457 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
458 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
459 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
460 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
461 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
462 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
463 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
465 You can contact the author at :
466 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
467 ****************************************************************** */
468 #ifndef BITSTREAM_H_MODULE
469 #define BITSTREAM_H_MODULE
471 #if defined (__cplusplus)
477 * This API consists of small unitary functions, which must be inlined for best performance.
478 * Since link-time-optimization is not available for all compilers,
479 * these functions are defined into a .h to be included.
483 /*=========================================
485 =========================================*/
486 #if defined(__BMI__) && defined(__GNUC__)
487 # include <immintrin.h> /* support for bextr (experimental) */
490 /*-********************************************
491 * bitStream decoding API (read backward)
492 **********************************************/
496 unsigned bitsConsumed;
501 typedef enum { BITv07_DStream_unfinished = 0,
502 BITv07_DStream_endOfBuffer = 1,
503 BITv07_DStream_completed = 2,
504 BITv07_DStream_overflow = 3 } BITv07_DStream_status; /* result of BITv07_reloadDStream() */
505 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
507 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
508 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, unsigned nbBits);
509 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD);
510 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* bitD);
513 /* Start by invoking BITv07_initDStream().
514 * A chunk of the bitStream is then stored into a local register.
515 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
516 * You can then retrieve bitFields stored into the local register, **in reverse order**.
517 * Local register is explicitly reloaded from memory by the BITv07_reloadDStream() method.
518 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BITv07_DStream_unfinished.
519 * Otherwise, it can be less than that, so proceed accordingly.
520 * Checking if DStream has reached its end can be performed with BITv07_endOfDStream().
524 /*-****************************************
526 ******************************************/
527 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, unsigned nbBits);
528 /* faster, but works only if nbBits >= 1 */
532 /*-**************************************************************
534 ****************************************************************/
535 MEM_STATIC unsigned BITv07_highbit32 (register U32 val)
537 # if defined(_MSC_VER) /* Visual */
539 _BitScanReverse ( &r, val );
541 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
542 return 31 - __builtin_clz (val);
543 # else /* Software version */
544 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 };
551 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
557 /*-********************************************************
559 **********************************************************/
560 /*! BITv07_initDStream() :
561 * Initialize a BITv07_DStream_t.
562 * `bitD` : a pointer to an already allocated BITv07_DStream_t structure.
563 * `srcSize` must be the *exact* size of the bitStream, in bytes.
564 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
566 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
568 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
570 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
571 bitD->start = (const char*)srcBuffer;
572 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
573 bitD->bitContainer = MEM_readLEST(bitD->ptr);
574 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
575 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
576 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
578 bitD->start = (const char*)srcBuffer;
579 bitD->ptr = bitD->start;
580 bitD->bitContainer = *(const BYTE*)(bitD->start);
583 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);
584 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);
585 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);
586 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24;
587 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16;
588 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8;
591 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
592 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
593 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
594 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
601 /*! BITv07_lookBits() :
602 * Provides next n bits from local register.
603 * local register is not modified.
604 * On 32-bits, maxNbBits==24.
605 * On 64-bits, maxNbBits==56.
606 * @return : value extracted
608 MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits)
610 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
611 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
614 /*! BITv07_lookBitsFast() :
615 * unsafe version; only works only if nbBits >= 1 */
616 MEM_STATIC size_t BITv07_lookBitsFast(const BITv07_DStream_t* bitD, U32 nbBits)
618 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
619 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
622 MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits)
624 bitD->bitsConsumed += nbBits;
627 /*! BITv07_readBits() :
628 * Read (consume) next n bits from local register and update.
629 * Pay attention to not read more than nbBits contained into local register.
630 * @return : extracted value.
632 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits)
634 size_t const value = BITv07_lookBits(bitD, nbBits);
635 BITv07_skipBits(bitD, nbBits);
639 /*! BITv07_readBitsFast() :
640 * unsafe version; only works only if nbBits >= 1 */
641 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, U32 nbBits)
643 size_t const value = BITv07_lookBitsFast(bitD, nbBits);
644 BITv07_skipBits(bitD, nbBits);
648 /*! BITv07_reloadDStream() :
649 * Refill `BITv07_DStream_t` from src buffer previously defined (see BITv07_initDStream() ).
650 * This function is safe, it guarantees it will not read beyond src buffer.
651 * @return : status of `BITv07_DStream_t` internal register.
652 if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
653 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD)
655 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */
656 return BITv07_DStream_overflow;
658 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
659 bitD->ptr -= bitD->bitsConsumed >> 3;
660 bitD->bitsConsumed &= 7;
661 bitD->bitContainer = MEM_readLEST(bitD->ptr);
662 return BITv07_DStream_unfinished;
664 if (bitD->ptr == bitD->start) {
665 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv07_DStream_endOfBuffer;
666 return BITv07_DStream_completed;
668 { U32 nbBytes = bitD->bitsConsumed >> 3;
669 BITv07_DStream_status result = BITv07_DStream_unfinished;
670 if (bitD->ptr - nbBytes < bitD->start) {
671 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
672 result = BITv07_DStream_endOfBuffer;
674 bitD->ptr -= nbBytes;
675 bitD->bitsConsumed -= nbBytes*8;
676 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
681 /*! BITv07_endOfDStream() :
682 * @return Tells if DStream has exactly reached its end (all bits consumed).
684 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* DStream)
686 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
689 #if defined (__cplusplus)
693 #endif /* BITSTREAM_H_MODULE */
694 /* ******************************************************************
695 FSE : Finite State Entropy codec
696 Public Prototypes declaration
697 Copyright (C) 2013-2016, Yann Collet.
699 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
701 Redistribution and use in source and binary forms, with or without
702 modification, are permitted provided that the following conditions are
705 * Redistributions of source code must retain the above copyright
706 notice, this list of conditions and the following disclaimer.
707 * Redistributions in binary form must reproduce the above
708 copyright notice, this list of conditions and the following disclaimer
709 in the documentation and/or other materials provided with the
712 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
713 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
714 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
715 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
716 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
717 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
718 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
719 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
720 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
721 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
722 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
724 You can contact the author at :
725 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
726 ****************************************************************** */
730 #if defined (__cplusplus)
736 /*-****************************************
737 * FSE simple functions
738 ******************************************/
740 /*! FSEv07_decompress():
741 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
742 into already allocated destination buffer 'dst', of size 'dstCapacity'.
743 @return : size of regenerated data (<= maxDstSize),
744 or an error code, which can be tested using FSEv07_isError() .
746 ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!
747 Why ? : making this distinction requires a header.
748 Header management is intentionally delegated to the user layer, which can better manage special cases.
750 size_t FSEv07_decompress(void* dst, size_t dstCapacity,
751 const void* cSrc, size_t cSrcSize);
754 /* Error Management */
755 unsigned FSEv07_isError(size_t code); /* tells if a return value is an error code */
756 const char* FSEv07_getErrorName(size_t code); /* provides error code string (useful for debugging) */
759 /*-*****************************************
761 ******************************************/
763 FSEv07_decompress() does the following:
764 1. read normalized counters with readNCount()
765 2. build decoding table 'DTable' from normalized counters
766 3. decode the data stream using decoding table 'DTable'
768 The following API allows targeting specific sub-functions for advanced tasks.
769 For example, it's possible to compress several blocks using the same 'CTable',
770 or to save and provide normalized distribution using external method.
774 /* *** DECOMPRESSION *** */
776 /*! FSEv07_readNCount():
777 Read compactly saved 'normalizedCounter' from 'rBuffer'.
778 @return : size read from 'rBuffer',
779 or an errorCode, which can be tested using FSEv07_isError().
780 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
781 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
783 /*! Constructor and Destructor of FSEv07_DTable.
784 Note that its size depends on 'tableLog' */
785 typedef unsigned FSEv07_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
786 FSEv07_DTable* FSEv07_createDTable(unsigned tableLog);
787 void FSEv07_freeDTable(FSEv07_DTable* dt);
789 /*! FSEv07_buildDTable():
790 Builds 'dt', which must be already allocated, using FSEv07_createDTable().
791 return : 0, or an errorCode, which can be tested using FSEv07_isError() */
792 size_t FSEv07_buildDTable (FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
794 /*! FSEv07_decompress_usingDTable():
795 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
796 into `dst` which must be already allocated.
797 @return : size of regenerated data (necessarily <= `dstCapacity`),
798 or an errorCode, which can be tested using FSEv07_isError() */
799 size_t FSEv07_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv07_DTable* dt);
804 (Note : these functions only decompress FSE-compressed blocks.
805 If block is uncompressed, use memcpy() instead
806 If block is a single repeated byte, use memset() instead )
808 The first step is to obtain the normalized frequencies of symbols.
809 This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().
810 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
811 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
812 or size the table to handle worst case situations (typically 256).
813 FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
814 The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.
815 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
816 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
818 The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.
819 This is performed by the function FSEv07_buildDTable().
820 The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().
821 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
823 `FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().
824 `cSrcSize` must be strictly correct, otherwise decompression will fail.
825 FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
826 If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)
830 #ifdef FSEv07_STATIC_LINKING_ONLY
833 /* *****************************************
835 *******************************************/
836 /* FSE buffer bounds */
837 #define FSEv07_NCOUNTBOUND 512
838 #define FSEv07_BLOCKBOUND(size) (size + (size>>7))
840 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
841 #define FSEv07_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
844 /* *****************************************
846 *******************************************/
847 size_t FSEv07_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
848 /**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
850 unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus);
851 /**< same as FSEv07_optimalTableLog(), which used `minus==2` */
853 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits);
854 /**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
856 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, unsigned char symbolValue);
857 /**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */
861 /* *****************************************
862 * FSE symbol decompression API
863 *******************************************/
867 const void* table; /* precise table may vary, depending on U16 */
871 static void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt);
873 static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
877 Let's now decompose FSEv07_decompress_usingDTable() into its unitary components.
878 You will decode FSE-encoded symbols from the bitStream,
879 and also any other bitFields you put in, **in reverse order**.
881 You will need a few variables to track your bitStream. They are :
883 BITv07_DStream_t DStream; // Stream context
884 FSEv07_DState_t DState; // State context. Multiple ones are possible
885 FSEv07_DTable* DTablePtr; // Decoding table, provided by FSEv07_buildDTable()
887 The first thing to do is to init the bitStream.
888 errorCode = BITv07_initDStream(&DStream, srcBuffer, srcSize);
890 You should then retrieve your initial state(s)
891 (in reverse flushing order if you have several ones) :
892 errorCode = FSEv07_initDState(&DState, &DStream, DTablePtr);
894 You can then decode your data, symbol after symbol.
895 For information the maximum number of bits read by FSEv07_decodeSymbol() is 'tableLog'.
896 Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
897 unsigned char symbol = FSEv07_decodeSymbol(&DState, &DStream);
899 You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
900 Note : maximum allowed nbBits is 25, for 32-bits compatibility
901 size_t bitField = BITv07_readBits(&DStream, nbBits);
903 All above operations only read from local register (which size depends on size_t).
904 Refueling the register from memory is manually performed by the reload method.
905 endSignal = FSEv07_reloadDStream(&DStream);
907 BITv07_reloadDStream() result tells if there is still some more data to read from DStream.
908 BITv07_DStream_unfinished : there is still some data left into the DStream.
909 BITv07_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
910 BITv07_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
911 BITv07_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
913 When reaching end of buffer (BITv07_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
914 to properly detect the exact end of stream.
915 After each decoded symbol, check if DStream is fully consumed using this simple test :
916 BITv07_reloadDStream(&DStream) >= BITv07_DStream_completed
918 When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
919 Checking if DStream has reached its end is performed by :
920 BITv07_endOfDStream(&DStream);
921 Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
922 FSEv07_endOfDState(&DState);
926 /* *****************************************
928 *******************************************/
929 static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
930 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
933 /* ====== Decompression ====== */
938 } FSEv07_DTableHeader; /* sizeof U32 */
942 unsigned short newState;
943 unsigned char symbol;
944 unsigned char nbBits;
945 } FSEv07_decode_t; /* size == U32 */
947 MEM_STATIC void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt)
949 const void* ptr = dt;
950 const FSEv07_DTableHeader* const DTableH = (const FSEv07_DTableHeader*)ptr;
951 DStatePtr->state = BITv07_readBits(bitD, DTableH->tableLog);
952 BITv07_reloadDStream(bitD);
953 DStatePtr->table = dt + 1;
956 MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr)
958 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
962 MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
964 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
965 U32 const nbBits = DInfo.nbBits;
966 size_t const lowBits = BITv07_readBits(bitD, nbBits);
967 DStatePtr->state = DInfo.newState + lowBits;
970 MEM_STATIC BYTE FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
972 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
973 U32 const nbBits = DInfo.nbBits;
974 BYTE const symbol = DInfo.symbol;
975 size_t const lowBits = BITv07_readBits(bitD, nbBits);
977 DStatePtr->state = DInfo.newState + lowBits;
981 /*! FSEv07_decodeSymbolFast() :
982 unsafe, only works if no symbol has a probability > 50% */
983 MEM_STATIC BYTE FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
985 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
986 U32 const nbBits = DInfo.nbBits;
987 BYTE const symbol = DInfo.symbol;
988 size_t const lowBits = BITv07_readBitsFast(bitD, nbBits);
990 DStatePtr->state = DInfo.newState + lowBits;
996 #ifndef FSEv07_COMMONDEFS_ONLY
998 /* **************************************************************
1000 ****************************************************************/
1002 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1003 * Increasing memory usage improves compression ratio
1004 * Reduced memory usage can improve speed, due to cache effect
1005 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1006 #define FSEv07_MAX_MEMORY_USAGE 14
1007 #define FSEv07_DEFAULT_MEMORY_USAGE 13
1009 /*!FSEv07_MAX_SYMBOL_VALUE :
1010 * Maximum symbol value authorized.
1011 * Required for proper stack allocation */
1012 #define FSEv07_MAX_SYMBOL_VALUE 255
1015 /* **************************************************************
1016 * template functions type & suffix
1017 ****************************************************************/
1018 #define FSEv07_FUNCTION_TYPE BYTE
1019 #define FSEv07_FUNCTION_EXTENSION
1020 #define FSEv07_DECODE_TYPE FSEv07_decode_t
1023 #endif /* !FSEv07_COMMONDEFS_ONLY */
1026 /* ***************************************************************
1028 *****************************************************************/
1029 #define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2)
1030 #define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)
1031 #define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)
1032 #define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)
1033 #define FSEv07_MIN_TABLELOG 5
1035 #define FSEv07_TABLELOG_ABSOLUTE_MAX 15
1036 #if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX
1037 # error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"
1040 #define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
1043 #endif /* FSEv07_STATIC_LINKING_ONLY */
1046 #if defined (__cplusplus)
1050 #endif /* FSEv07_H */
1051 /* ******************************************************************
1052 Huffman coder, part of New Generation Entropy library
1054 Copyright (C) 2013-2016, Yann Collet.
1056 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1058 Redistribution and use in source and binary forms, with or without
1059 modification, are permitted provided that the following conditions are
1062 * Redistributions of source code must retain the above copyright
1063 notice, this list of conditions and the following disclaimer.
1064 * Redistributions in binary form must reproduce the above
1065 copyright notice, this list of conditions and the following disclaimer
1066 in the documentation and/or other materials provided with the
1069 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1070 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1071 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1072 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1073 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1074 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1075 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1076 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1077 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1078 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1079 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1081 You can contact the author at :
1082 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1083 ****************************************************************** */
1084 #ifndef HUFv07_H_298734234
1085 #define HUFv07_H_298734234
1087 #if defined (__cplusplus)
1093 /* *** simple functions *** */
1095 HUFv07_decompress() :
1096 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1097 into already allocated buffer 'dst', of minimum size 'dstSize'.
1098 `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
1099 Note : in contrast with FSE, HUFv07_decompress can regenerate
1100 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1101 because it knows size to regenerate.
1102 @return : size of regenerated data (== dstSize),
1103 or an error code, which can be tested using HUFv07_isError()
1105 size_t HUFv07_decompress(void* dst, size_t dstSize,
1106 const void* cSrc, size_t cSrcSize);
1109 /* ****************************************
1111 ******************************************/
1112 #define HUFv07_BLOCKSIZE_MAX (128 * 1024)
1114 /* Error Management */
1115 unsigned HUFv07_isError(size_t code); /**< tells if a return value is an error code */
1116 const char* HUFv07_getErrorName(size_t code); /**< provides error code string (useful for debugging) */
1119 /* *** Advanced function *** */
1122 #ifdef HUFv07_STATIC_LINKING_ONLY
1125 /* *** Constants *** */
1126 #define HUFv07_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */
1127 #define HUFv07_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */
1128 #define HUFv07_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */
1129 #define HUFv07_SYMBOLVALUE_MAX 255
1130 #if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX)
1131 # error "HUFv07_TABLELOG_MAX is too large !"
1135 /* ****************************************
1137 ******************************************/
1138 /* HUF buffer bounds */
1139 #define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1141 /* static allocation of HUF's DTable */
1142 typedef U32 HUFv07_DTable;
1143 #define HUFv07_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog)))
1144 #define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1145 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
1146 #define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1147 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
1150 /* ****************************************
1151 * Advanced decompression functions
1152 ******************************************/
1153 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1154 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1156 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< decodes RLE and uncompressed */
1157 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 */
1158 size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1159 size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1161 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
1162 size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1163 size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1166 /* ****************************************
1168 ******************************************/
1170 The following API allows targeting specific sub-functions for advanced tasks.
1171 For example, it's possible to compress several blocks using the same 'CTable',
1172 or to save and regenerate 'CTable' using external methods.
1174 /* FSEv07_count() : find it within "fse.h" */
1176 /*! HUFv07_readStats() :
1177 Read compact Huffman tree, saved by HUFv07_writeCTable().
1178 `huffWeight` is destination buffer.
1179 @return : size read from `src` , or an error Code .
1180 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */
1181 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1182 U32* nbSymbolsPtr, U32* tableLogPtr,
1183 const void* src, size_t srcSize);
1187 HUFv07_decompress() does the following:
1188 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1189 2. build Huffman table from save, using HUFv07_readDTableXn()
1190 3. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable
1193 /** HUFv07_selectDecoder() :
1194 * Tells which decoder is likely to decode faster,
1195 * based on a set of pre-determined metrics.
1196 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
1197 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
1198 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize);
1200 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1201 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1203 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1204 size_t HUFv07_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1205 size_t HUFv07_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1208 /* single stream variants */
1209 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1210 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1212 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1213 size_t HUFv07_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1214 size_t HUFv07_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1217 #endif /* HUFv07_STATIC_LINKING_ONLY */
1220 #if defined (__cplusplus)
1224 #endif /* HUFv07_H_298734234 */
1226 Common functions of New Generation Entropy library
1227 Copyright (C) 2016, Yann Collet.
1229 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1231 Redistribution and use in source and binary forms, with or without
1232 modification, are permitted provided that the following conditions are
1235 * Redistributions of source code must retain the above copyright
1236 notice, this list of conditions and the following disclaimer.
1237 * Redistributions in binary form must reproduce the above
1238 copyright notice, this list of conditions and the following disclaimer
1239 in the documentation and/or other materials provided with the
1242 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1243 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1244 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1245 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1246 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1247 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1248 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1249 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1250 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1251 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1252 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1254 You can contact the author at :
1255 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1256 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1257 *************************************************************************** */
1261 /*-****************************************
1262 * FSE Error Management
1263 ******************************************/
1264 unsigned FSEv07_isError(size_t code) { return ERR_isError(code); }
1266 const char* FSEv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1269 /* **************************************************************
1270 * HUF Error Management
1271 ****************************************************************/
1272 unsigned HUFv07_isError(size_t code) { return ERR_isError(code); }
1274 const char* HUFv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1277 /*-**************************************************************
1278 * FSE NCount encoding-decoding
1279 ****************************************************************/
1280 static short FSEv07_abs(short a) { return (short)(a<0 ? -a : a); }
1282 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1283 const void* headerBuffer, size_t hbSize)
1285 const BYTE* const istart = (const BYTE*) headerBuffer;
1286 const BYTE* const iend = istart + hbSize;
1287 const BYTE* ip = istart;
1293 unsigned charnum = 0;
1296 if (hbSize < 4) return ERROR(srcSize_wrong);
1297 bitStream = MEM_readLE32(ip);
1298 nbBits = (bitStream & 0xF) + FSEv07_MIN_TABLELOG; /* extract tableLog */
1299 if (nbBits > FSEv07_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1302 *tableLogPtr = nbBits;
1303 remaining = (1<<nbBits)+1;
1304 threshold = 1<<nbBits;
1307 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1309 unsigned n0 = charnum;
1310 while ((bitStream & 0xFFFF) == 0xFFFF) {
1314 bitStream = MEM_readLE32(ip) >> bitCount;
1319 while ((bitStream & 3) == 3) {
1324 n0 += bitStream & 3;
1326 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1327 while (charnum < n0) normalizedCounter[charnum++] = 0;
1328 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1331 bitStream = MEM_readLE32(ip) >> bitCount;
1336 { short const max = (short)((2*threshold-1)-remaining);
1339 if ((bitStream & (threshold-1)) < (U32)max) {
1340 count = (short)(bitStream & (threshold-1));
1341 bitCount += nbBits-1;
1343 count = (short)(bitStream & (2*threshold-1));
1344 if (count >= threshold) count -= max;
1348 count--; /* extra accuracy */
1349 remaining -= FSEv07_abs(count);
1350 normalizedCounter[charnum++] = count;
1352 while (remaining < threshold) {
1357 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1361 bitCount -= (int)(8 * (iend - 4 - ip));
1364 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1365 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1366 if (remaining != 1) return ERROR(GENERIC);
1367 *maxSVPtr = charnum-1;
1369 ip += (bitCount+7)>>3;
1370 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1375 /*! HUFv07_readStats() :
1376 Read compact Huffman tree, saved by HUFv07_writeCTable().
1377 `huffWeight` is destination buffer.
1378 @return : size read from `src` , or an error Code .
1379 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() .
1381 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1382 U32* nbSymbolsPtr, U32* tableLogPtr,
1383 const void* src, size_t srcSize)
1386 const BYTE* ip = (const BYTE*) src;
1390 if (!srcSize) return ERROR(srcSize_wrong);
1392 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1394 if (iSize >= 128) { /* special header */
1395 if (iSize >= (242)) { /* RLE */
1396 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1397 oSize = l[iSize-242];
1398 memset(huffWeight, 1, hwSize);
1401 else { /* Incompressible */
1402 oSize = iSize - 127;
1403 iSize = ((oSize+1)/2);
1404 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1405 if (oSize >= hwSize) return ERROR(corruption_detected);
1408 for (n=0; n<oSize; n+=2) {
1409 huffWeight[n] = ip[n/2] >> 4;
1410 huffWeight[n+1] = ip[n/2] & 15;
1412 else { /* header compressed with FSE (normal case) */
1413 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1414 oSize = FSEv07_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1415 if (FSEv07_isError(oSize)) return oSize;
1418 /* collect weight stats */
1419 memset(rankStats, 0, (HUFv07_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
1421 { U32 n; for (n=0; n<oSize; n++) {
1422 if (huffWeight[n] >= HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1423 rankStats[huffWeight[n]]++;
1424 weightTotal += (1 << huffWeight[n]) >> 1;
1426 if (weightTotal == 0) return ERROR(corruption_detected);
1428 /* get last non-null symbol weight (implied, total must be 2^n) */
1429 { U32 const tableLog = BITv07_highbit32(weightTotal) + 1;
1430 if (tableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1431 *tableLogPtr = tableLog;
1432 /* determine last weight */
1433 { U32 const total = 1 << tableLog;
1434 U32 const rest = total - weightTotal;
1435 U32 const verif = 1 << BITv07_highbit32(rest);
1436 U32 const lastWeight = BITv07_highbit32(rest) + 1;
1437 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1438 huffWeight[oSize] = (BYTE)lastWeight;
1439 rankStats[lastWeight]++;
1442 /* check tree construction validity */
1443 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1446 *nbSymbolsPtr = (U32)(oSize+1);
1449 /* ******************************************************************
1450 FSE : Finite State Entropy decoder
1451 Copyright (C) 2013-2015, Yann Collet.
1453 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1455 Redistribution and use in source and binary forms, with or without
1456 modification, are permitted provided that the following conditions are
1459 * Redistributions of source code must retain the above copyright
1460 notice, this list of conditions and the following disclaimer.
1461 * Redistributions in binary form must reproduce the above
1462 copyright notice, this list of conditions and the following disclaimer
1463 in the documentation and/or other materials provided with the
1466 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1467 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1468 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1469 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1470 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1471 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1472 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1473 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1474 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1475 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1476 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1478 You can contact the author at :
1479 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1480 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1481 ****************************************************************** */
1484 /* **************************************************************
1485 * Compiler specifics
1486 ****************************************************************/
1487 #ifdef _MSC_VER /* Visual Studio */
1488 # define FORCE_INLINE static __forceinline
1489 # include <intrin.h> /* For Visual 2005 */
1490 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1491 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1493 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1495 # define FORCE_INLINE static inline __attribute__((always_inline))
1497 # define FORCE_INLINE static inline
1500 # define FORCE_INLINE static
1501 # endif /* __STDC_VERSION__ */
1505 /* **************************************************************
1507 ****************************************************************/
1508 #define FSEv07_isError ERR_isError
1509 #define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1512 /* **************************************************************
1514 ****************************************************************/
1515 typedef U32 DTable_max_t[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG)];
1518 /* **************************************************************
1520 ****************************************************************/
1522 designed to be included
1523 for type-specific functions (template emulation in C)
1524 Objective is to write these functions only once, for improved maintenance
1528 #ifndef FSEv07_FUNCTION_EXTENSION
1529 # error "FSEv07_FUNCTION_EXTENSION must be defined"
1531 #ifndef FSEv07_FUNCTION_TYPE
1532 # error "FSEv07_FUNCTION_TYPE must be defined"
1535 /* Function names */
1536 #define FSEv07_CAT(X,Y) X##Y
1537 #define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y)
1538 #define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y)
1541 /* Function templates */
1542 FSEv07_DTable* FSEv07_createDTable (unsigned tableLog)
1544 if (tableLog > FSEv07_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv07_TABLELOG_ABSOLUTE_MAX;
1545 return (FSEv07_DTable*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1548 void FSEv07_freeDTable (FSEv07_DTable* dt)
1553 size_t FSEv07_buildDTable(FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1555 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1556 FSEv07_DECODE_TYPE* const tableDecode = (FSEv07_DECODE_TYPE*) (tdPtr);
1557 U16 symbolNext[FSEv07_MAX_SYMBOL_VALUE+1];
1559 U32 const maxSV1 = maxSymbolValue + 1;
1560 U32 const tableSize = 1 << tableLog;
1561 U32 highThreshold = tableSize-1;
1564 if (maxSymbolValue > FSEv07_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1565 if (tableLog > FSEv07_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1567 /* Init, lay down lowprob symbols */
1568 { FSEv07_DTableHeader DTableH;
1569 DTableH.tableLog = (U16)tableLog;
1570 DTableH.fastMode = 1;
1571 { S16 const largeLimit= (S16)(1 << (tableLog-1));
1573 for (s=0; s<maxSV1; s++) {
1574 if (normalizedCounter[s]==-1) {
1575 tableDecode[highThreshold--].symbol = (FSEv07_FUNCTION_TYPE)s;
1578 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1579 symbolNext[s] = normalizedCounter[s];
1581 memcpy(dt, &DTableH, sizeof(DTableH));
1584 /* Spread symbols */
1585 { U32 const tableMask = tableSize-1;
1586 U32 const step = FSEv07_TABLESTEP(tableSize);
1587 U32 s, position = 0;
1588 for (s=0; s<maxSV1; s++) {
1590 for (i=0; i<normalizedCounter[s]; i++) {
1591 tableDecode[position].symbol = (FSEv07_FUNCTION_TYPE)s;
1592 position = (position + step) & tableMask;
1593 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1596 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1599 /* Build Decoding table */
1601 for (u=0; u<tableSize; u++) {
1602 FSEv07_FUNCTION_TYPE const symbol = (FSEv07_FUNCTION_TYPE)(tableDecode[u].symbol);
1603 U16 nextState = symbolNext[symbol]++;
1604 tableDecode[u].nbBits = (BYTE) (tableLog - BITv07_highbit32 ((U32)nextState) );
1605 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1613 #ifndef FSEv07_COMMONDEFS_ONLY
1615 /*-*******************************************************
1616 * Decompression (Byte symbols)
1617 *********************************************************/
1618 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, BYTE symbolValue)
1621 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1622 void* dPtr = dt + 1;
1623 FSEv07_decode_t* const cell = (FSEv07_decode_t*)dPtr;
1625 DTableH->tableLog = 0;
1626 DTableH->fastMode = 0;
1629 cell->symbol = symbolValue;
1636 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits)
1639 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1640 void* dPtr = dt + 1;
1641 FSEv07_decode_t* const dinfo = (FSEv07_decode_t*)dPtr;
1642 const unsigned tableSize = 1 << nbBits;
1643 const unsigned tableMask = tableSize - 1;
1644 const unsigned maxSV1 = tableMask+1;
1648 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1650 /* Build Decoding Table */
1651 DTableH->tableLog = (U16)nbBits;
1652 DTableH->fastMode = 1;
1653 for (s=0; s<maxSV1; s++) {
1654 dinfo[s].newState = 0;
1655 dinfo[s].symbol = (BYTE)s;
1656 dinfo[s].nbBits = (BYTE)nbBits;
1662 FORCE_INLINE size_t FSEv07_decompress_usingDTable_generic(
1663 void* dst, size_t maxDstSize,
1664 const void* cSrc, size_t cSrcSize,
1665 const FSEv07_DTable* dt, const unsigned fast)
1667 BYTE* const ostart = (BYTE*) dst;
1669 BYTE* const omax = op + maxDstSize;
1670 BYTE* const olimit = omax-3;
1672 BITv07_DStream_t bitD;
1673 FSEv07_DState_t state1;
1674 FSEv07_DState_t state2;
1677 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1678 if (FSEv07_isError(errorCode)) return errorCode; }
1680 FSEv07_initDState(&state1, &bitD, dt);
1681 FSEv07_initDState(&state2, &bitD, dt);
1683 #define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1685 /* 4 symbols per loop */
1686 for ( ; (BITv07_reloadDStream(&bitD)==BITv07_DStream_unfinished) && (op<olimit) ; op+=4) {
1687 op[0] = FSEv07_GETSYMBOL(&state1);
1689 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1690 BITv07_reloadDStream(&bitD);
1692 op[1] = FSEv07_GETSYMBOL(&state2);
1694 if (FSEv07_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1695 { if (BITv07_reloadDStream(&bitD) > BITv07_DStream_unfinished) { op+=2; break; } }
1697 op[2] = FSEv07_GETSYMBOL(&state1);
1699 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1700 BITv07_reloadDStream(&bitD);
1702 op[3] = FSEv07_GETSYMBOL(&state2);
1706 /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1708 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1710 *op++ = FSEv07_GETSYMBOL(&state1);
1712 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1713 *op++ = FSEv07_GETSYMBOL(&state2);
1717 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1719 *op++ = FSEv07_GETSYMBOL(&state2);
1721 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1722 *op++ = FSEv07_GETSYMBOL(&state1);
1730 size_t FSEv07_decompress_usingDTable(void* dst, size_t originalSize,
1731 const void* cSrc, size_t cSrcSize,
1732 const FSEv07_DTable* dt)
1734 const void* ptr = dt;
1735 const FSEv07_DTableHeader* DTableH = (const FSEv07_DTableHeader*)ptr;
1736 const U32 fastMode = DTableH->fastMode;
1738 /* select fast mode (static) */
1739 if (fastMode) return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1740 return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1744 size_t FSEv07_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1746 const BYTE* const istart = (const BYTE*)cSrc;
1747 const BYTE* ip = istart;
1748 short counting[FSEv07_MAX_SYMBOL_VALUE+1];
1749 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1751 unsigned maxSymbolValue = FSEv07_MAX_SYMBOL_VALUE;
1753 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1755 /* normal FSE decoding mode */
1756 { size_t const NCountLength = FSEv07_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1757 if (FSEv07_isError(NCountLength)) return NCountLength;
1758 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1760 cSrcSize -= NCountLength;
1763 { size_t const errorCode = FSEv07_buildDTable (dt, counting, maxSymbolValue, tableLog);
1764 if (FSEv07_isError(errorCode)) return errorCode; }
1766 return FSEv07_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */
1771 #endif /* FSEv07_COMMONDEFS_ONLY */
1773 /* ******************************************************************
1774 Huffman decoder, part of New Generation Entropy library
1775 Copyright (C) 2013-2016, Yann Collet.
1777 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1779 Redistribution and use in source and binary forms, with or without
1780 modification, are permitted provided that the following conditions are
1783 * Redistributions of source code must retain the above copyright
1784 notice, this list of conditions and the following disclaimer.
1785 * Redistributions in binary form must reproduce the above
1786 copyright notice, this list of conditions and the following disclaimer
1787 in the documentation and/or other materials provided with the
1790 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1791 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1792 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1793 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1794 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1795 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1796 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1797 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1798 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1799 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1800 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1802 You can contact the author at :
1803 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1804 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1805 ****************************************************************** */
1807 /* **************************************************************
1808 * Compiler specifics
1809 ****************************************************************/
1810 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1811 /* inline is defined */
1812 #elif defined(_MSC_VER)
1813 # define inline __inline
1815 # define inline /* disable inline */
1819 #ifdef _MSC_VER /* Visual Studio */
1820 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1825 /* **************************************************************
1827 ****************************************************************/
1828 #define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1831 /*-***************************/
1832 /* generic DTableDesc */
1833 /*-***************************/
1835 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
1837 static DTableDesc HUFv07_getDTableDesc(const HUFv07_DTable* table)
1840 memcpy(&dtd, table, sizeof(dtd));
1845 /*-***************************/
1846 /* single-symbol decoding */
1847 /*-***************************/
1849 typedef struct { BYTE byte; BYTE nbBits; } HUFv07_DEltX2; /* single-symbol decoding */
1851 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
1853 BYTE huffWeight[HUFv07_SYMBOLVALUE_MAX + 1];
1854 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
1858 void* const dtPtr = DTable + 1;
1859 HUFv07_DEltX2* const dt = (HUFv07_DEltX2*)dtPtr;
1861 HUFv07_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUFv07_DTable));
1862 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1864 iSize = HUFv07_readStats(huffWeight, HUFv07_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1865 if (HUFv07_isError(iSize)) return iSize;
1868 { DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1869 if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge); /* DTable too small, huffman tree cannot fit in */
1871 dtd.tableLog = (BYTE)tableLog;
1872 memcpy(DTable, &dtd, sizeof(dtd));
1876 { U32 n, nextRankStart = 0;
1877 for (n=1; n<tableLog+1; n++) {
1878 U32 current = nextRankStart;
1879 nextRankStart += (rankVal[n] << (n-1));
1880 rankVal[n] = current;
1885 for (n=0; n<nbSymbols; n++) {
1886 U32 const w = huffWeight[n];
1887 U32 const length = (1 << w) >> 1;
1890 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1891 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1893 rankVal[w] += length;
1900 static BYTE HUFv07_decodeSymbolX2(BITv07_DStream_t* Dstream, const HUFv07_DEltX2* dt, const U32 dtLog)
1902 size_t const val = BITv07_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1903 BYTE const c = dt[val].byte;
1904 BITv07_skipBits(Dstream, dt[val].nbBits);
1908 #define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1909 *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1911 #define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1912 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1913 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1915 #define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1917 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1919 static inline size_t HUFv07_decodeStreamX2(BYTE* p, BITv07_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv07_DEltX2* const dt, const U32 dtLog)
1921 BYTE* const pStart = p;
1923 /* up to 4 symbols at a time */
1924 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-4)) {
1925 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1926 HUFv07_DECODE_SYMBOLX2_1(p, bitDPtr);
1927 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1928 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1931 /* closer to the end */
1932 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd))
1933 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1935 /* no more data to retrieve from bitstream, hence no need to reload */
1937 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1942 static size_t HUFv07_decompress1X2_usingDTable_internal(
1943 void* dst, size_t dstSize,
1944 const void* cSrc, size_t cSrcSize,
1945 const HUFv07_DTable* DTable)
1947 BYTE* op = (BYTE*)dst;
1948 BYTE* const oend = op + dstSize;
1949 const void* dtPtr = DTable + 1;
1950 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1951 BITv07_DStream_t bitD;
1952 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1953 U32 const dtLog = dtd.tableLog;
1955 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
1956 if (HUFv07_isError(errorCode)) return errorCode; }
1958 HUFv07_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1961 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
1966 size_t HUFv07_decompress1X2_usingDTable(
1967 void* dst, size_t dstSize,
1968 const void* cSrc, size_t cSrcSize,
1969 const HUFv07_DTable* DTable)
1971 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1972 if (dtd.tableType != 0) return ERROR(GENERIC);
1973 return HUFv07_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
1976 size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1978 const BYTE* ip = (const BYTE*) cSrc;
1980 size_t const hSize = HUFv07_readDTableX2 (DCtx, cSrc, cSrcSize);
1981 if (HUFv07_isError(hSize)) return hSize;
1982 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1983 ip += hSize; cSrcSize -= hSize;
1985 return HUFv07_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
1988 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1990 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
1991 return HUFv07_decompress1X2_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
1995 static size_t HUFv07_decompress4X2_usingDTable_internal(
1996 void* dst, size_t dstSize,
1997 const void* cSrc, size_t cSrcSize,
1998 const HUFv07_DTable* DTable)
2001 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2003 { const BYTE* const istart = (const BYTE*) cSrc;
2004 BYTE* const ostart = (BYTE*) dst;
2005 BYTE* const oend = ostart + dstSize;
2006 const void* const dtPtr = DTable + 1;
2007 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
2010 BITv07_DStream_t bitD1;
2011 BITv07_DStream_t bitD2;
2012 BITv07_DStream_t bitD3;
2013 BITv07_DStream_t bitD4;
2014 size_t const length1 = MEM_readLE16(istart);
2015 size_t const length2 = MEM_readLE16(istart+2);
2016 size_t const length3 = MEM_readLE16(istart+4);
2017 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
2018 const BYTE* const istart1 = istart + 6; /* jumpTable */
2019 const BYTE* const istart2 = istart1 + length1;
2020 const BYTE* const istart3 = istart2 + length2;
2021 const BYTE* const istart4 = istart3 + length3;
2022 const size_t segmentSize = (dstSize+3) / 4;
2023 BYTE* const opStart2 = ostart + segmentSize;
2024 BYTE* const opStart3 = opStart2 + segmentSize;
2025 BYTE* const opStart4 = opStart3 + segmentSize;
2027 BYTE* op2 = opStart2;
2028 BYTE* op3 = opStart3;
2029 BYTE* op4 = opStart4;
2031 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2032 U32 const dtLog = dtd.tableLog;
2034 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2035 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
2036 if (HUFv07_isError(errorCode)) return errorCode; }
2037 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
2038 if (HUFv07_isError(errorCode)) return errorCode; }
2039 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
2040 if (HUFv07_isError(errorCode)) return errorCode; }
2041 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
2042 if (HUFv07_isError(errorCode)) return errorCode; }
2044 /* 16-32 symbols per loop (4-8 symbols per stream) */
2045 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2046 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
2047 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
2048 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
2049 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
2050 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
2051 HUFv07_DECODE_SYMBOLX2_1(op1, &bitD1);
2052 HUFv07_DECODE_SYMBOLX2_1(op2, &bitD2);
2053 HUFv07_DECODE_SYMBOLX2_1(op3, &bitD3);
2054 HUFv07_DECODE_SYMBOLX2_1(op4, &bitD4);
2055 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
2056 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
2057 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
2058 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
2059 HUFv07_DECODE_SYMBOLX2_0(op1, &bitD1);
2060 HUFv07_DECODE_SYMBOLX2_0(op2, &bitD2);
2061 HUFv07_DECODE_SYMBOLX2_0(op3, &bitD3);
2062 HUFv07_DECODE_SYMBOLX2_0(op4, &bitD4);
2063 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2066 /* check corruption */
2067 if (op1 > opStart2) return ERROR(corruption_detected);
2068 if (op2 > opStart3) return ERROR(corruption_detected);
2069 if (op3 > opStart4) return ERROR(corruption_detected);
2070 /* note : op4 supposed already verified within main loop */
2072 /* finish bitStreams one by one */
2073 HUFv07_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2074 HUFv07_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2075 HUFv07_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2076 HUFv07_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2079 endSignal = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2080 if (!endSignal) return ERROR(corruption_detected);
2088 size_t HUFv07_decompress4X2_usingDTable(
2089 void* dst, size_t dstSize,
2090 const void* cSrc, size_t cSrcSize,
2091 const HUFv07_DTable* DTable)
2093 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2094 if (dtd.tableType != 0) return ERROR(GENERIC);
2095 return HUFv07_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2099 size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2101 const BYTE* ip = (const BYTE*) cSrc;
2103 size_t const hSize = HUFv07_readDTableX2 (dctx, cSrc, cSrcSize);
2104 if (HUFv07_isError(hSize)) return hSize;
2105 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2106 ip += hSize; cSrcSize -= hSize;
2108 return HUFv07_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx);
2111 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2113 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
2114 return HUFv07_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2118 /* *************************/
2119 /* double-symbols decoding */
2120 /* *************************/
2121 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv07_DEltX4; /* double-symbols decoding */
2123 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
2125 static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2126 const U32* rankValOrigin, const int minWeight,
2127 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2128 U32 nbBitsBaseline, U16 baseSeq)
2131 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2133 /* get pre-calculated rankVal */
2134 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2136 /* fill skipped values */
2138 U32 i, skipSize = rankVal[minWeight];
2139 MEM_writeLE16(&(DElt.sequence), baseSeq);
2140 DElt.nbBits = (BYTE)(consumed);
2142 for (i = 0; i < skipSize; i++)
2147 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2148 const U32 symbol = sortedSymbols[s].symbol;
2149 const U32 weight = sortedSymbols[s].weight;
2150 const U32 nbBits = nbBitsBaseline - weight;
2151 const U32 length = 1 << (sizeLog-nbBits);
2152 const U32 start = rankVal[weight];
2154 const U32 end = start + length;
2156 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2157 DElt.nbBits = (BYTE)(nbBits + consumed);
2159 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2161 rankVal[weight] += length;
2165 typedef U32 rankVal_t[HUFv07_TABLELOG_ABSOLUTEMAX][HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2167 static void HUFv07_fillDTableX4(HUFv07_DEltX4* DTable, const U32 targetLog,
2168 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2169 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2170 const U32 nbBitsBaseline)
2172 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2173 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2174 const U32 minBits = nbBitsBaseline - maxWeight;
2177 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2180 for (s=0; s<sortedListSize; s++) {
2181 const U16 symbol = sortedList[s].symbol;
2182 const U32 weight = sortedList[s].weight;
2183 const U32 nbBits = nbBitsBaseline - weight;
2184 const U32 start = rankVal[weight];
2185 const U32 length = 1 << (targetLog-nbBits);
2187 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2189 int minWeight = nbBits + scaleLog;
2190 if (minWeight < 1) minWeight = 1;
2191 sortedRank = rankStart[minWeight];
2192 HUFv07_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2193 rankValOrigin[nbBits], minWeight,
2194 sortedList+sortedRank, sortedListSize-sortedRank,
2195 nbBitsBaseline, symbol);
2198 MEM_writeLE16(&(DElt.sequence), symbol);
2199 DElt.nbBits = (BYTE)(nbBits);
2202 const U32 end = start + length;
2203 for (u = start; u < end; u++) DTable[u] = DElt;
2205 rankVal[weight] += length;
2209 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
2211 BYTE weightList[HUFv07_SYMBOLVALUE_MAX + 1];
2212 sortedSymbol_t sortedSymbol[HUFv07_SYMBOLVALUE_MAX + 1];
2213 U32 rankStats[HUFv07_TABLELOG_ABSOLUTEMAX + 1] = { 0 };
2214 U32 rankStart0[HUFv07_TABLELOG_ABSOLUTEMAX + 2] = { 0 };
2215 U32* const rankStart = rankStart0+1;
2217 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2218 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2219 U32 const maxTableLog = dtd.maxTableLog;
2221 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */
2222 HUFv07_DEltX4* const dt = (HUFv07_DEltX4*)dtPtr;
2224 HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4) == sizeof(HUFv07_DTable)); /* if compilation fails here, assertion is false */
2225 if (maxTableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge);
2226 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2228 iSize = HUFv07_readStats(weightList, HUFv07_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2229 if (HUFv07_isError(iSize)) return iSize;
2232 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2234 /* find maxWeight */
2235 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2237 /* Get start index of each weight */
2238 { U32 w, nextRankStart = 0;
2239 for (w=1; w<maxW+1; w++) {
2240 U32 current = nextRankStart;
2241 nextRankStart += rankStats[w];
2242 rankStart[w] = current;
2244 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2245 sizeOfSort = nextRankStart;
2248 /* sort symbols by weight */
2250 for (s=0; s<nbSymbols; s++) {
2251 U32 const w = weightList[s];
2252 U32 const r = rankStart[w]++;
2253 sortedSymbol[r].symbol = (BYTE)s;
2254 sortedSymbol[r].weight = (BYTE)w;
2256 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2260 { U32* const rankVal0 = rankVal[0];
2261 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */
2262 U32 nextRankVal = 0;
2264 for (w=1; w<maxW+1; w++) {
2265 U32 current = nextRankVal;
2266 nextRankVal += rankStats[w] << (w+rescale);
2267 rankVal0[w] = current;
2269 { U32 const minBits = tableLog+1 - maxW;
2271 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
2272 U32* const rankValPtr = rankVal[consumed];
2274 for (w = 1; w < maxW+1; w++) {
2275 rankValPtr[w] = rankVal0[w] >> consumed;
2278 HUFv07_fillDTableX4(dt, maxTableLog,
2279 sortedSymbol, sizeOfSort,
2280 rankStart0, rankVal, maxW,
2283 dtd.tableLog = (BYTE)maxTableLog;
2285 memcpy(DTable, &dtd, sizeof(dtd));
2290 static U32 HUFv07_decodeSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2292 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2293 memcpy(op, dt+val, 2);
2294 BITv07_skipBits(DStream, dt[val].nbBits);
2295 return dt[val].length;
2298 static U32 HUFv07_decodeLastSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2300 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2301 memcpy(op, dt+val, 1);
2302 if (dt[val].length==1) BITv07_skipBits(DStream, dt[val].nbBits);
2304 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2305 BITv07_skipBits(DStream, dt[val].nbBits);
2306 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2307 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 */
2313 #define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2314 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2316 #define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2317 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
2318 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2320 #define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2322 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2324 static inline size_t HUFv07_decodeStreamX4(BYTE* p, BITv07_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv07_DEltX4* const dt, const U32 dtLog)
2326 BYTE* const pStart = p;
2328 /* up to 8 symbols at a time */
2329 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd-7)) {
2330 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2331 HUFv07_DECODE_SYMBOLX4_1(p, bitDPtr);
2332 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2333 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2336 /* closer to end : up to 2 symbols at a time */
2337 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-2))
2338 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2341 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2344 p += HUFv07_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2350 static size_t HUFv07_decompress1X4_usingDTable_internal(
2351 void* dst, size_t dstSize,
2352 const void* cSrc, size_t cSrcSize,
2353 const HUFv07_DTable* DTable)
2355 BITv07_DStream_t bitD;
2358 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
2359 if (HUFv07_isError(errorCode)) return errorCode;
2363 { BYTE* const ostart = (BYTE*) dst;
2364 BYTE* const oend = ostart + dstSize;
2365 const void* const dtPtr = DTable+1; /* force compiler to not use strict-aliasing */
2366 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2367 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2368 HUFv07_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog);
2372 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
2378 size_t HUFv07_decompress1X4_usingDTable(
2379 void* dst, size_t dstSize,
2380 const void* cSrc, size_t cSrcSize,
2381 const HUFv07_DTable* DTable)
2383 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2384 if (dtd.tableType != 1) return ERROR(GENERIC);
2385 return HUFv07_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2388 size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2390 const BYTE* ip = (const BYTE*) cSrc;
2392 size_t const hSize = HUFv07_readDTableX4 (DCtx, cSrc, cSrcSize);
2393 if (HUFv07_isError(hSize)) return hSize;
2394 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2395 ip += hSize; cSrcSize -= hSize;
2397 return HUFv07_decompress1X4_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
2400 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2402 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2403 return HUFv07_decompress1X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2406 static size_t HUFv07_decompress4X4_usingDTable_internal(
2407 void* dst, size_t dstSize,
2408 const void* cSrc, size_t cSrcSize,
2409 const HUFv07_DTable* DTable)
2411 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2413 { const BYTE* const istart = (const BYTE*) cSrc;
2414 BYTE* const ostart = (BYTE*) dst;
2415 BYTE* const oend = ostart + dstSize;
2416 const void* const dtPtr = DTable+1;
2417 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2420 BITv07_DStream_t bitD1;
2421 BITv07_DStream_t bitD2;
2422 BITv07_DStream_t bitD3;
2423 BITv07_DStream_t bitD4;
2424 size_t const length1 = MEM_readLE16(istart);
2425 size_t const length2 = MEM_readLE16(istart+2);
2426 size_t const length3 = MEM_readLE16(istart+4);
2427 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
2428 const BYTE* const istart1 = istart + 6; /* jumpTable */
2429 const BYTE* const istart2 = istart1 + length1;
2430 const BYTE* const istart3 = istart2 + length2;
2431 const BYTE* const istart4 = istart3 + length3;
2432 size_t const segmentSize = (dstSize+3) / 4;
2433 BYTE* const opStart2 = ostart + segmentSize;
2434 BYTE* const opStart3 = opStart2 + segmentSize;
2435 BYTE* const opStart4 = opStart3 + segmentSize;
2437 BYTE* op2 = opStart2;
2438 BYTE* op3 = opStart3;
2439 BYTE* op4 = opStart4;
2441 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2442 U32 const dtLog = dtd.tableLog;
2444 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2445 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
2446 if (HUFv07_isError(errorCode)) return errorCode; }
2447 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
2448 if (HUFv07_isError(errorCode)) return errorCode; }
2449 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
2450 if (HUFv07_isError(errorCode)) return errorCode; }
2451 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
2452 if (HUFv07_isError(errorCode)) return errorCode; }
2454 /* 16-32 symbols per loop (4-8 symbols per stream) */
2455 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2456 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
2457 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2458 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2459 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2460 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2461 HUFv07_DECODE_SYMBOLX4_1(op1, &bitD1);
2462 HUFv07_DECODE_SYMBOLX4_1(op2, &bitD2);
2463 HUFv07_DECODE_SYMBOLX4_1(op3, &bitD3);
2464 HUFv07_DECODE_SYMBOLX4_1(op4, &bitD4);
2465 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2466 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2467 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2468 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2469 HUFv07_DECODE_SYMBOLX4_0(op1, &bitD1);
2470 HUFv07_DECODE_SYMBOLX4_0(op2, &bitD2);
2471 HUFv07_DECODE_SYMBOLX4_0(op3, &bitD3);
2472 HUFv07_DECODE_SYMBOLX4_0(op4, &bitD4);
2474 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2477 /* check corruption */
2478 if (op1 > opStart2) return ERROR(corruption_detected);
2479 if (op2 > opStart3) return ERROR(corruption_detected);
2480 if (op3 > opStart4) return ERROR(corruption_detected);
2481 /* note : op4 supposed already verified within main loop */
2483 /* finish bitStreams one by one */
2484 HUFv07_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2485 HUFv07_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2486 HUFv07_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2487 HUFv07_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2490 { U32 const endCheck = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2491 if (!endCheck) return ERROR(corruption_detected); }
2499 size_t HUFv07_decompress4X4_usingDTable(
2500 void* dst, size_t dstSize,
2501 const void* cSrc, size_t cSrcSize,
2502 const HUFv07_DTable* DTable)
2504 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2505 if (dtd.tableType != 1) return ERROR(GENERIC);
2506 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2510 size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2512 const BYTE* ip = (const BYTE*) cSrc;
2514 size_t hSize = HUFv07_readDTableX4 (dctx, cSrc, cSrcSize);
2515 if (HUFv07_isError(hSize)) return hSize;
2516 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2517 ip += hSize; cSrcSize -= hSize;
2519 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
2522 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2524 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2525 return HUFv07_decompress4X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2529 /* ********************************/
2530 /* Generic decompression selector */
2531 /* ********************************/
2533 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize,
2534 const void* cSrc, size_t cSrcSize,
2535 const HUFv07_DTable* DTable)
2537 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2538 return dtd.tableType ? HUFv07_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2539 HUFv07_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2542 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize,
2543 const void* cSrc, size_t cSrcSize,
2544 const HUFv07_DTable* DTable)
2546 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2547 return dtd.tableType ? HUFv07_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2548 HUFv07_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2552 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2553 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2555 /* single, double, quad */
2556 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2557 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2558 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2559 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2560 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2561 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2562 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2563 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2564 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2565 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2566 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2567 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2568 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2569 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2570 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2571 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2574 /** HUFv07_selectDecoder() :
2575 * Tells which decoder is likely to decode faster,
2576 * based on a set of pre-determined metrics.
2577 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
2578 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
2579 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize)
2581 /* decoder timing evaluation */
2582 U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2583 U32 const D256 = (U32)(dstSize >> 8);
2584 U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
2585 U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
2586 DTime1 += DTime1 >> 3; /* advantage to algorithm using less memory, for cache eviction */
2588 return DTime1 < DTime0;
2592 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2594 size_t HUFv07_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2596 static const decompressionAlgo decompress[2] = { HUFv07_decompress4X2, HUFv07_decompress4X4 };
2598 /* validation checks */
2599 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2600 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2601 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2602 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2604 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2605 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2608 //return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2609 //return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2612 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2614 /* validation checks */
2615 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2616 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2617 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2618 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2620 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2621 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2622 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2626 size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2628 /* validation checks */
2629 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2630 if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected); /* invalid */
2632 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2633 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2634 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2638 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2640 /* validation checks */
2641 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2642 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2643 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2644 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2646 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2647 return algoNb ? HUFv07_decompress1X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2648 HUFv07_decompress1X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2652 Common functions of Zstd compression library
2653 Copyright (C) 2015-2016, Yann Collet.
2655 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2657 Redistribution and use in source and binary forms, with or without
2658 modification, are permitted provided that the following conditions are
2660 * Redistributions of source code must retain the above copyright
2661 notice, this list of conditions and the following disclaimer.
2662 * Redistributions in binary form must reproduce the above
2663 copyright notice, this list of conditions and the following disclaimer
2664 in the documentation and/or other materials provided with the
2666 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2667 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2668 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2669 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2670 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2671 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2672 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2673 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2674 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2675 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2676 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2678 You can contact the author at :
2679 - zstd homepage : http://www.zstd.net/
2684 /*-****************************************
2685 * ZSTD Error Management
2686 ******************************************/
2687 /*! ZSTDv07_isError() :
2688 * tells if a return value is an error code */
2689 unsigned ZSTDv07_isError(size_t code) { return ERR_isError(code); }
2691 /*! ZSTDv07_getErrorName() :
2692 * provides error code string from function result (useful for debugging) */
2693 const char* ZSTDv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
2697 /* **************************************************************
2698 * ZBUFF Error Management
2699 ****************************************************************/
2700 unsigned ZBUFFv07_isError(size_t errorCode) { return ERR_isError(errorCode); }
2702 const char* ZBUFFv07_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2706 void* ZSTDv07_defaultAllocFunction(void* opaque, size_t size)
2708 void* address = malloc(size);
2710 /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2714 void ZSTDv07_defaultFreeFunction(void* opaque, void* address)
2717 /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2721 zstd_internal - common functions to include
2722 Header File for include
2723 Copyright (C) 2014-2016, Yann Collet.
2725 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2727 Redistribution and use in source and binary forms, with or without
2728 modification, are permitted provided that the following conditions are
2730 * Redistributions of source code must retain the above copyright
2731 notice, this list of conditions and the following disclaimer.
2732 * Redistributions in binary form must reproduce the above
2733 copyright notice, this list of conditions and the following disclaimer
2734 in the documentation and/or other materials provided with the
2736 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2737 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2738 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2739 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2740 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2741 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2742 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2743 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2744 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2745 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2746 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2748 You can contact the author at :
2749 - zstd homepage : https://www.zstd.net
2751 #ifndef ZSTDv07_CCOMMON_H_MODULE
2752 #define ZSTDv07_CCOMMON_H_MODULE
2755 /*-*************************************
2757 ***************************************/
2758 #define MIN(a,b) ((a)<(b) ? (a) : (b))
2759 #define MAX(a,b) ((a)>(b) ? (a) : (b))
2762 /*-*************************************
2764 ***************************************/
2765 #define ZSTDv07_OPT_NUM (1<<12)
2766 #define ZSTDv07_DICT_MAGIC 0xEC30A437 /* v0.7 */
2768 #define ZSTDv07_REP_NUM 3
2769 #define ZSTDv07_REP_INIT ZSTDv07_REP_NUM
2770 #define ZSTDv07_REP_MOVE (ZSTDv07_REP_NUM-1)
2771 static const U32 repStartValue[ZSTDv07_REP_NUM] = { 1, 4, 8 };
2773 #define KB *(1 <<10)
2774 #define MB *(1 <<20)
2775 #define GB *(1U<<30)
2784 #define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10
2785 static const size_t ZSTDv07_fcs_fieldSize[4] = { 0, 2, 4, 8 };
2786 static const size_t ZSTDv07_did_fieldSize[4] = { 0, 1, 2, 4 };
2788 #define ZSTDv07_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
2789 static const size_t ZSTDv07_blockHeaderSize = ZSTDv07_BLOCKHEADERSIZE;
2790 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2792 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2793 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
2796 typedef enum { lbt_huffman, lbt_repeat, lbt_raw, lbt_rle } litBlockType_t;
2798 #define LONGNBSEQ 0x7F00
2801 #define EQUAL_READ32 4
2804 #define MaxLit ((1<<Litbits) - 1)
2808 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
2813 #define FSEv07_ENCODING_RAW 0
2814 #define FSEv07_ENCODING_RLE 1
2815 #define FSEv07_ENCODING_STATIC 2
2816 #define FSEv07_ENCODING_DYNAMIC 3
2818 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2819 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
2821 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2822 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
2824 static const U32 LL_defaultNormLog = 6;
2826 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2827 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2828 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
2830 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2831 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2832 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
2834 static const U32 ML_defaultNormLog = 6;
2836 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2837 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
2838 static const U32 OF_defaultNormLog = 5;
2841 /*-*******************************************
2842 * Shared functions to include for inlining
2843 *********************************************/
2844 static void ZSTDv07_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2845 #define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; }
2847 /*! ZSTDv07_wildcopy() :
2848 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
2849 #define WILDCOPY_OVERLENGTH 8
2850 MEM_STATIC void ZSTDv07_wildcopy(void* dst, const void* src, ptrdiff_t length)
2852 const BYTE* ip = (const BYTE*)src;
2853 BYTE* op = (BYTE*)dst;
2854 BYTE* const oend = op + length;
2861 /*-*******************************************
2862 * Private interfaces
2863 *********************************************/
2864 typedef struct ZSTDv07_stats_s ZSTDv07_stats_t;
2876 U32 rep[ZSTDv07_REP_INIT];
2877 } ZSTDv07_optimal_t;
2879 struct ZSTDv07_stats_s { U32 unused; };
2888 U16* litLengthStart;
2891 U16* matchLengthStart;
2894 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
2897 ZSTDv07_optimal_t* priceTable;
2898 ZSTDv07_match_t* matchTable;
2899 U32* matchLengthFreq;
2908 U32 log2matchLengthSum;
2910 U32 log2litLengthSum;
2915 U32 cachedLitLength;
2916 const BYTE* cachedLiterals;
2917 ZSTDv07_stats_t stats;
2920 void ZSTDv07_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
2922 /* custom memory allocation functions */
2923 void* ZSTDv07_defaultAllocFunction(void* opaque, size_t size);
2924 void ZSTDv07_defaultFreeFunction(void* opaque, void* address);
2925 static const ZSTDv07_customMem defaultCustomMem = { ZSTDv07_defaultAllocFunction, ZSTDv07_defaultFreeFunction, NULL };
2927 #endif /* ZSTDv07_CCOMMON_H_MODULE */
2929 zstd - standard compression library
2930 Copyright (C) 2014-2016, Yann Collet.
2932 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2934 Redistribution and use in source and binary forms, with or without
2935 modification, are permitted provided that the following conditions are
2937 * Redistributions of source code must retain the above copyright
2938 notice, this list of conditions and the following disclaimer.
2939 * Redistributions in binary form must reproduce the above
2940 copyright notice, this list of conditions and the following disclaimer
2941 in the documentation and/or other materials provided with the
2943 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2944 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2945 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2946 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2947 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2948 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2949 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2950 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2951 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2952 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2953 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2955 You can contact the author at :
2956 - zstd homepage : http://www.zstd.net
2959 /* ***************************************************************
2961 *****************************************************************/
2964 * Select how default decompression function ZSTDv07_decompress() will allocate memory,
2965 * in memory stack (0), or in memory heap (1, requires malloc())
2967 #ifndef ZSTDv07_HEAPMODE
2968 # define ZSTDv07_HEAPMODE 1
2972 /*-*******************************************************
2973 * Compiler specifics
2974 *********************************************************/
2975 #ifdef _MSC_VER /* Visual Studio */
2976 # include <intrin.h> /* For Visual 2005 */
2977 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2978 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2979 # pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */
2983 /*-*************************************
2985 ***************************************/
2986 #define ZSTDv07_isError ERR_isError /* for inlining */
2987 #define FSEv07_isError ERR_isError
2988 #define HUFv07_isError ERR_isError
2991 /*_*******************************************************
2993 **********************************************************/
2994 static void ZSTDv07_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2997 /*-*************************************************************
2998 * Context management
2999 ***************************************************************/
3000 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
3001 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
3002 ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTDv07_dStage;
3004 struct ZSTDv07_DCtx_s
3006 FSEv07_DTable LLTable[FSEv07_DTABLE_SIZE_U32(LLFSELog)];
3007 FSEv07_DTable OffTable[FSEv07_DTABLE_SIZE_U32(OffFSELog)];
3008 FSEv07_DTable MLTable[FSEv07_DTABLE_SIZE_U32(MLFSELog)];
3009 HUFv07_DTable hufTable[HUFv07_DTABLE_SIZE(HufLog)]; /* can accommodate HUFv07_decompress4X */
3010 const void* previousDstEnd;
3013 const void* dictEnd;
3016 ZSTDv07_frameParams fParams;
3017 blockType_t bType; /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
3018 ZSTDv07_dStage stage;
3021 XXH64_state_t xxhState;
3025 ZSTDv07_customMem customMem;
3027 BYTE litBuffer[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
3028 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
3029 }; /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */
3031 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx);
3033 size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx* dctx) { return sizeof(*dctx); }
3035 size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx); }
3037 size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx)
3039 dctx->expected = ZSTDv07_frameHeaderSize_min;
3040 dctx->stage = ZSTDds_getFrameHeaderSize;
3041 dctx->previousDstEnd = NULL;
3044 dctx->dictEnd = NULL;
3045 dctx->hufTable[0] = (HUFv07_DTable)((HufLog)*0x1000001);
3046 dctx->litEntropy = dctx->fseEntropy = 0;
3048 { int i; for (i=0; i<ZSTDv07_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; }
3052 ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem)
3056 if (!customMem.customAlloc && !customMem.customFree)
3057 customMem = defaultCustomMem;
3059 if (!customMem.customAlloc || !customMem.customFree)
3062 dctx = (ZSTDv07_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTDv07_DCtx));
3063 if (!dctx) return NULL;
3064 memcpy(&dctx->customMem, &customMem, sizeof(ZSTDv07_customMem));
3065 ZSTDv07_decompressBegin(dctx);
3069 ZSTDv07_DCtx* ZSTDv07_createDCtx(void)
3071 return ZSTDv07_createDCtx_advanced(defaultCustomMem);
3074 size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx* dctx)
3076 if (dctx==NULL) return 0; /* support free on NULL */
3077 dctx->customMem.customFree(dctx->customMem.opaque, dctx);
3078 return 0; /* reserved as a potential error code in the future */
3081 void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dstDCtx, const ZSTDv07_DCtx* srcDCtx)
3083 memcpy(dstDCtx, srcDCtx,
3084 sizeof(ZSTDv07_DCtx) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH + ZSTDv07_frameHeaderSize_max)); /* no need to copy workspace */
3088 /*-*************************************************************
3089 * Decompression section
3090 ***************************************************************/
3092 /* Frame format description
3093 Frame Header - [ Block Header - Block ] - Frame End
3095 - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h)
3096 - 1 byte - Frame Descriptor
3098 - 3 bytes, starting with a 2-bits descriptor
3099 Uncompressed, Compressed, Frame End, unused
3101 See Block Format Description
3103 - 3 bytes, compatible with Block Header
3109 1 byte - FrameHeaderDescription :
3110 bit 0-1 : dictID (0, 1, 2 or 4 bytes)
3111 bit 2 : checksumFlag
3112 bit 3 : reserved (must be zero)
3113 bit 4 : reserved (unused, can be any value)
3114 bit 5 : Single Segment (if 1, WindowLog byte is not present)
3115 bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
3116 if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
3118 Optional : WindowLog (0 or 1 byte)
3119 bit 0-2 : octal Fractional (1/8th)
3120 bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
3122 Optional : dictID (0, 1, 2 or 4 bytes)
3123 Automatic adaptation
3127 4 : all other values
3129 Optional : content size (0, 1, 2, 4 or 8 bytes)
3130 0 : unknown (fcfs==0 and swl==0)
3131 1 : 0-255 bytes (fcfs==0 and swl==1)
3132 2 : 256 - 65535+256 (fcfs==1)
3133 4 : 0 - 4GB-1 (fcfs==2)
3134 8 : 0 - 16EB-1 (fcfs==3)
3138 /* Compressed Block, format description
3140 Block = Literal Section - Sequences Section
3141 Prerequisite : size of (compressed) block, maximum size of regenerated data
3145 1.1) Header : 1-5 bytes
3147 00 compressed by Huff0
3149 10 is Raw (uncompressed)
3151 Note : using 01 => Huff0 with precomputed table ?
3152 Note : delta map ? => compressed ?
3154 1.1.1) Huff0-compressed literal block : 3-5 bytes
3155 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3156 srcSize < 1 KB => 3 bytes (2-2-10-10)
3157 srcSize < 16KB => 4 bytes (2-2-14-14)
3158 else => 5 bytes (2-2-18-18)
3159 big endian convention
3161 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
3162 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
3163 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
3165 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3169 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3170 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
3171 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3173 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3177 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3178 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3179 srcSize < 1 KB => 3 bytes (2-2-10-10)
3180 srcSize < 16KB => 4 bytes (2-2-14-14)
3181 else => 5 bytes (2-2-18-18)
3182 big endian convention
3184 1- CTable available (stored into workspace ?)
3185 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3188 1.2) Literal block content
3190 1.2.1) Huff0 block, using sizes from header
3193 1.2.2) Huff0 block, using prepared table
3200 2) Sequences section
3204 /** ZSTDv07_frameHeaderSize() :
3205 * srcSize must be >= ZSTDv07_frameHeaderSize_min.
3206 * @return : size of the Frame Header */
3207 static size_t ZSTDv07_frameHeaderSize(const void* src, size_t srcSize)
3209 if (srcSize < ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);
3210 { BYTE const fhd = ((const BYTE*)src)[4];
3211 U32 const dictID= fhd & 3;
3212 U32 const directMode = (fhd >> 5) & 1;
3213 U32 const fcsId = fhd >> 6;
3214 return ZSTDv07_frameHeaderSize_min + !directMode + ZSTDv07_did_fieldSize[dictID] + ZSTDv07_fcs_fieldSize[fcsId]
3215 + (directMode && !ZSTDv07_fcs_fieldSize[fcsId]);
3220 /** ZSTDv07_getFrameParams() :
3221 * decode Frame Header, or require larger `srcSize`.
3222 * @return : 0, `fparamsPtr` is correctly filled,
3223 * >0, `srcSize` is too small, result is expected `srcSize`,
3224 * or an error code, which can be tested using ZSTDv07_isError() */
3225 size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams* fparamsPtr, const void* src, size_t srcSize)
3227 const BYTE* ip = (const BYTE*)src;
3229 if (srcSize < ZSTDv07_frameHeaderSize_min) return ZSTDv07_frameHeaderSize_min;
3230 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3231 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3232 if (srcSize < ZSTDv07_skippableHeaderSize) return ZSTDv07_skippableHeaderSize; /* magic number + skippable frame length */
3233 memset(fparamsPtr, 0, sizeof(*fparamsPtr));
3234 fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);
3235 fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
3238 return ERROR(prefix_unknown);
3241 /* ensure there is enough `srcSize` to fully read/decode frame header */
3242 { size_t const fhsize = ZSTDv07_frameHeaderSize(src, srcSize);
3243 if (srcSize < fhsize) return fhsize; }
3245 { BYTE const fhdByte = ip[4];
3247 U32 const dictIDSizeCode = fhdByte&3;
3248 U32 const checksumFlag = (fhdByte>>2)&1;
3249 U32 const directMode = (fhdByte>>5)&1;
3250 U32 const fcsID = fhdByte>>6;
3251 U32 const windowSizeMax = 1U << ZSTDv07_WINDOWLOG_MAX;
3254 U64 frameContentSize = 0;
3255 if ((fhdByte & 0x08) != 0) return ERROR(frameParameter_unsupported); /* reserved bits, which must be zero */
3257 BYTE const wlByte = ip[pos++];
3258 U32 const windowLog = (wlByte >> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN;
3259 if (windowLog > ZSTDv07_WINDOWLOG_MAX) return ERROR(frameParameter_unsupported);
3260 windowSize = (1U << windowLog);
3261 windowSize += (windowSize >> 3) * (wlByte&7);
3264 switch(dictIDSizeCode)
3266 default: /* impossible */
3268 case 1 : dictID = ip[pos]; pos++; break;
3269 case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
3270 case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
3274 default: /* impossible */
3275 case 0 : if (directMode) frameContentSize = ip[pos]; break;
3276 case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
3277 case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
3278 case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
3280 if (!windowSize) windowSize = (U32)frameContentSize;
3281 if (windowSize > windowSizeMax) return ERROR(frameParameter_unsupported);
3282 fparamsPtr->frameContentSize = frameContentSize;
3283 fparamsPtr->windowSize = windowSize;
3284 fparamsPtr->dictID = dictID;
3285 fparamsPtr->checksumFlag = checksumFlag;
3291 /** ZSTDv07_getDecompressedSize() :
3292 * compatible with legacy mode
3293 * @return : decompressed size if known, 0 otherwise
3294 note : 0 can mean any of the following :
3295 - decompressed size is not provided within frame header
3296 - frame header unknown / not supported
3297 - frame header not completely provided (`srcSize` too small) */
3298 unsigned long long ZSTDv07_getDecompressedSize(const void* src, size_t srcSize)
3300 { ZSTDv07_frameParams fparams;
3301 size_t const frResult = ZSTDv07_getFrameParams(&fparams, src, srcSize);
3302 if (frResult!=0) return 0;
3303 return fparams.frameContentSize;
3308 /** ZSTDv07_decodeFrameHeader() :
3309 * `srcSize` must be the size provided by ZSTDv07_frameHeaderSize().
3310 * @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */
3311 static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx* dctx, const void* src, size_t srcSize)
3313 size_t const result = ZSTDv07_getFrameParams(&(dctx->fParams), src, srcSize);
3314 if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
3315 if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
3322 blockType_t blockType;
3324 } blockProperties_t;
3326 /*! ZSTDv07_getcBlockSize() :
3327 * Provides the size of compressed block from block header `src` */
3328 size_t ZSTDv07_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
3330 const BYTE* const in = (const BYTE* const)src;
3333 if (srcSize < ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3335 bpPtr->blockType = (blockType_t)((*in) >> 6);
3336 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
3337 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
3339 if (bpPtr->blockType == bt_end) return 0;
3340 if (bpPtr->blockType == bt_rle) return 1;
3345 static size_t ZSTDv07_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3347 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
3348 memcpy(dst, src, srcSize);
3353 /*! ZSTDv07_decodeLiteralsBlock() :
3354 @return : nb of bytes read from src (< srcSize ) */
3355 size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx* dctx,
3356 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
3358 const BYTE* const istart = (const BYTE*) src;
3360 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3362 switch((litBlockType_t)(istart[0]>> 6))
3365 { size_t litSize, litCSize, singleStream=0;
3366 U32 lhSize = (istart[0] >> 4) & 3;
3367 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3370 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3371 /* 2 - 2 - 10 - 10 */
3373 singleStream = istart[0] & 16;
3374 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3375 litCSize = ((istart[1] & 3) << 8) + istart[2];
3378 /* 2 - 2 - 14 - 14 */
3380 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3381 litCSize = ((istart[2] & 63) << 8) + istart[3];
3384 /* 2 - 2 - 18 - 18 */
3386 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3387 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
3390 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3391 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3393 if (HUFv07_isError(singleStream ?
3394 HUFv07_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3395 HUFv07_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3396 return ERROR(corruption_detected);
3398 dctx->litPtr = dctx->litBuffer;
3399 dctx->litSize = litSize;
3400 dctx->litEntropy = 1;
3401 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3402 return litCSize + lhSize;
3405 { size_t litSize, litCSize;
3406 U32 lhSize = ((istart[0]) >> 4) & 3;
3407 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
3408 return ERROR(corruption_detected);
3409 if (dctx->litEntropy==0)
3410 return ERROR(dictionary_corrupted);
3412 /* 2 - 2 - 10 - 10 */
3414 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3415 litCSize = ((istart[1] & 3) << 8) + istart[2];
3416 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3418 { size_t const errorCode = HUFv07_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTable);
3419 if (HUFv07_isError(errorCode)) return ERROR(corruption_detected);
3421 dctx->litPtr = dctx->litBuffer;
3422 dctx->litSize = litSize;
3423 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3424 return litCSize + lhSize;
3428 U32 lhSize = ((istart[0]) >> 4) & 3;
3431 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3433 litSize = istart[0] & 31;
3436 litSize = ((istart[0] & 15) << 8) + istart[1];
3439 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3443 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
3444 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3445 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3446 dctx->litPtr = dctx->litBuffer;
3447 dctx->litSize = litSize;
3448 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3449 return lhSize+litSize;
3451 /* direct reference into compressed stream */
3452 dctx->litPtr = istart+lhSize;
3453 dctx->litSize = litSize;
3454 return lhSize+litSize;
3458 U32 lhSize = ((istart[0]) >> 4) & 3;
3461 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3463 litSize = istart[0] & 31;
3466 litSize = ((istart[0] & 15) << 8) + istart[1];
3469 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3470 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3473 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3474 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3475 dctx->litPtr = dctx->litBuffer;
3476 dctx->litSize = litSize;
3480 return ERROR(corruption_detected); /* impossible */
3485 /*! ZSTDv07_buildSeqTable() :
3486 @return : nb bytes read from src,
3487 or an error code if it fails, testable with ZSTDv07_isError()
3489 size_t ZSTDv07_buildSeqTable(FSEv07_DTable* DTable, U32 type, U32 max, U32 maxLog,
3490 const void* src, size_t srcSize,
3491 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3495 case FSEv07_ENCODING_RLE :
3496 if (!srcSize) return ERROR(srcSize_wrong);
3497 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3498 FSEv07_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */
3500 case FSEv07_ENCODING_RAW :
3501 FSEv07_buildDTable(DTable, defaultNorm, max, defaultLog);
3503 case FSEv07_ENCODING_STATIC:
3504 if (!flagRepeatTable) return ERROR(corruption_detected);
3506 default : /* impossible */
3507 case FSEv07_ENCODING_DYNAMIC :
3510 size_t const headerSize = FSEv07_readNCount(norm, &max, &tableLog, src, srcSize);
3511 if (FSEv07_isError(headerSize)) return ERROR(corruption_detected);
3512 if (tableLog > maxLog) return ERROR(corruption_detected);
3513 FSEv07_buildDTable(DTable, norm, max, tableLog);
3519 size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr,
3520 FSEv07_DTable* DTableLL, FSEv07_DTable* DTableML, FSEv07_DTable* DTableOffb, U32 flagRepeatTable,
3521 const void* src, size_t srcSize)
3523 const BYTE* const istart = (const BYTE* const)src;
3524 const BYTE* const iend = istart + srcSize;
3525 const BYTE* ip = istart;
3528 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3531 { int nbSeq = *ip++;
3532 if (!nbSeq) { *nbSeqPtr=0; return 1; }
3534 if (nbSeq == 0xFF) {
3535 if (ip+2 > iend) return ERROR(srcSize_wrong);
3536 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3538 if (ip >= iend) return ERROR(srcSize_wrong);
3539 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3545 /* FSE table descriptors */
3546 { U32 const LLtype = *ip >> 6;
3547 U32 const OFtype = (*ip >> 4) & 3;
3548 U32 const MLtype = (*ip >> 2) & 3;
3552 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3555 { size_t const llhSize = ZSTDv07_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3556 if (ZSTDv07_isError(llhSize)) return ERROR(corruption_detected);
3559 { size_t const ofhSize = ZSTDv07_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3560 if (ZSTDv07_isError(ofhSize)) return ERROR(corruption_detected);
3563 { size_t const mlhSize = ZSTDv07_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3564 if (ZSTDv07_isError(mlhSize)) return ERROR(corruption_detected);
3579 BITv07_DStream_t DStream;
3580 FSEv07_DState_t stateLL;
3581 FSEv07_DState_t stateOffb;
3582 FSEv07_DState_t stateML;
3583 size_t prevOffset[ZSTDv07_REP_INIT];
3587 static seq_t ZSTDv07_decodeSequence(seqState_t* seqState)
3591 U32 const llCode = FSEv07_peekSymbol(&(seqState->stateLL));
3592 U32 const mlCode = FSEv07_peekSymbol(&(seqState->stateML));
3593 U32 const ofCode = FSEv07_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3595 U32 const llBits = LL_bits[llCode];
3596 U32 const mlBits = ML_bits[mlCode];
3597 U32 const ofBits = ofCode;
3598 U32 const totalBits = llBits+mlBits+ofBits;
3600 static const U32 LL_base[MaxLL+1] = {
3601 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3602 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3603 0x2000, 0x4000, 0x8000, 0x10000 };
3605 static const U32 ML_base[MaxML+1] = {
3606 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
3607 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
3608 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3609 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3611 static const U32 OF_base[MaxOff+1] = {
3612 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
3613 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
3614 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3615 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3622 offset = OF_base[ofCode] + BITv07_readBits(&(seqState->DStream), ofBits); /* <= (ZSTDv07_WINDOWLOG_MAX-1) bits */
3623 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));
3627 if ((llCode == 0) & (offset <= 1)) offset = 1-offset;
3629 size_t const temp = seqState->prevOffset[offset];
3630 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
3631 seqState->prevOffset[1] = seqState->prevOffset[0];
3632 seqState->prevOffset[0] = offset = temp;
3634 offset = seqState->prevOffset[0];
3637 seqState->prevOffset[2] = seqState->prevOffset[1];
3638 seqState->prevOffset[1] = seqState->prevOffset[0];
3639 seqState->prevOffset[0] = offset;
3641 seq.offset = offset;
3644 seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BITv07_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */
3645 if (MEM_32bits() && (mlBits+llBits>24)) BITv07_reloadDStream(&(seqState->DStream));
3647 seq.litLength = LL_base[llCode] + ((llCode>15) ? BITv07_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */
3649 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv07_reloadDStream(&(seqState->DStream));
3651 /* ANS state update */
3652 FSEv07_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */
3653 FSEv07_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */
3654 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream)); /* <= 18 bits */
3655 FSEv07_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */
3662 size_t ZSTDv07_execSequence(BYTE* op,
3663 BYTE* const oend, seq_t sequence,
3664 const BYTE** litPtr, const BYTE* const litLimit,
3665 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3667 BYTE* const oLitEnd = op + sequence.litLength;
3668 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3669 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3670 BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH;
3671 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3672 const BYTE* match = oLitEnd - sequence.offset;
3675 if ((oLitEnd>oend_w) | (oMatchEnd>oend)) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
3676 if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */
3679 ZSTDv07_wildcopy(op, *litPtr, sequence.litLength); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3681 *litPtr = iLitEnd; /* update for next sequence */
3684 if (sequence.offset > (size_t)(oLitEnd - base)) {
3685 /* offset beyond prefix */
3686 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3687 match = dictEnd - (base-match);
3688 if (match + sequence.matchLength <= dictEnd) {
3689 memmove(oLitEnd, match, sequence.matchLength);
3690 return sequenceLength;
3692 /* span extDict & currentPrefixSegment */
3693 { size_t const length1 = dictEnd - match;
3694 memmove(oLitEnd, match, length1);
3695 op = oLitEnd + length1;
3696 sequence.matchLength -= length1;
3698 if (op > oend_w || sequence.matchLength < MINMATCH) {
3699 while (op < oMatchEnd) *op++ = *match++;
3700 return sequenceLength;
3703 /* Requirement: op <= oend_w */
3705 /* match within prefix */
3706 if (sequence.offset < 8) {
3707 /* close range match, overlap */
3708 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3709 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3710 int const sub2 = dec64table[sequence.offset];
3715 match += dec32table[sequence.offset];
3716 ZSTDv07_copy4(op+4, match);
3719 ZSTDv07_copy8(op, match);
3721 op += 8; match += 8;
3723 if (oMatchEnd > oend-(16-MINMATCH)) {
3725 ZSTDv07_wildcopy(op, match, oend_w - op);
3726 match += oend_w - op;
3729 while (op < oMatchEnd) *op++ = *match++;
3731 ZSTDv07_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3733 return sequenceLength;
3737 static size_t ZSTDv07_decompressSequences(
3739 void* dst, size_t maxDstSize,
3740 const void* seqStart, size_t seqSize)
3742 const BYTE* ip = (const BYTE*)seqStart;
3743 const BYTE* const iend = ip + seqSize;
3744 BYTE* const ostart = (BYTE* const)dst;
3745 BYTE* const oend = ostart + maxDstSize;
3747 const BYTE* litPtr = dctx->litPtr;
3748 const BYTE* const litEnd = litPtr + dctx->litSize;
3749 FSEv07_DTable* DTableLL = dctx->LLTable;
3750 FSEv07_DTable* DTableML = dctx->MLTable;
3751 FSEv07_DTable* DTableOffb = dctx->OffTable;
3752 const BYTE* const base = (const BYTE*) (dctx->base);
3753 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3754 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3757 /* Build Decoding Tables */
3758 { size_t const seqHSize = ZSTDv07_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize);
3759 if (ZSTDv07_isError(seqHSize)) return seqHSize;
3763 /* Regen sequences */
3765 seqState_t seqState;
3766 dctx->fseEntropy = 1;
3767 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; }
3768 { size_t const errorCode = BITv07_initDStream(&(seqState.DStream), ip, iend-ip);
3769 if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3770 FSEv07_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3771 FSEv07_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3772 FSEv07_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3774 for ( ; (BITv07_reloadDStream(&(seqState.DStream)) <= BITv07_DStream_completed) && nbSeq ; ) {
3776 { seq_t const sequence = ZSTDv07_decodeSequence(&seqState);
3777 size_t const oneSeqSize = ZSTDv07_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3778 if (ZSTDv07_isError(oneSeqSize)) return oneSeqSize;
3782 /* check if reached exact end */
3783 if (nbSeq) return ERROR(corruption_detected);
3784 /* save reps for next block */
3785 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
3788 /* last literal segment */
3789 { size_t const lastLLSize = litEnd - litPtr;
3790 //if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3791 if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
3792 memcpy(op, litPtr, lastLLSize);
3800 static void ZSTDv07_checkContinuity(ZSTDv07_DCtx* dctx, const void* dst)
3802 if (dst != dctx->previousDstEnd) { /* not contiguous */
3803 dctx->dictEnd = dctx->previousDstEnd;
3804 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3806 dctx->previousDstEnd = dst;
3811 static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx* dctx,
3812 void* dst, size_t dstCapacity,
3813 const void* src, size_t srcSize)
3814 { /* blockType == blockCompressed */
3815 const BYTE* ip = (const BYTE*)src;
3817 if (srcSize >= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong);
3819 /* Decode literals sub-block */
3820 { size_t const litCSize = ZSTDv07_decodeLiteralsBlock(dctx, src, srcSize);
3821 if (ZSTDv07_isError(litCSize)) return litCSize;
3823 srcSize -= litCSize;
3825 return ZSTDv07_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3829 size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx,
3830 void* dst, size_t dstCapacity,
3831 const void* src, size_t srcSize)
3834 ZSTDv07_checkContinuity(dctx, dst);
3835 dSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3836 dctx->previousDstEnd = (char*)dst + dSize;
3841 /** ZSTDv07_insertBlock() :
3842 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
3843 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize)
3845 ZSTDv07_checkContinuity(dctx, blockStart);
3846 dctx->previousDstEnd = (const char*)blockStart + blockSize;
3851 size_t ZSTDv07_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length)
3853 if (length > dstCapacity) return ERROR(dstSize_tooSmall);
3854 memset(dst, byte, length);
3859 /*! ZSTDv07_decompressFrame() :
3860 * `dctx` must be properly initialized */
3861 static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx* dctx,
3862 void* dst, size_t dstCapacity,
3863 const void* src, size_t srcSize)
3865 const BYTE* ip = (const BYTE*)src;
3866 const BYTE* const iend = ip + srcSize;
3867 BYTE* const ostart = (BYTE* const)dst;
3868 BYTE* const oend = ostart + dstCapacity;
3870 size_t remainingSize = srcSize;
3873 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3876 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3877 if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3878 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3879 if (ZSTDv07_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3880 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3883 /* Loop on each block */
3886 blockProperties_t blockProperties;
3887 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, iend-ip, &blockProperties);
3888 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3890 ip += ZSTDv07_blockHeaderSize;
3891 remainingSize -= ZSTDv07_blockHeaderSize;
3892 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3894 switch(blockProperties.blockType)
3897 decodedSize = ZSTDv07_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3900 decodedSize = ZSTDv07_copyRawBlock(op, oend-op, ip, cBlockSize);
3903 decodedSize = ZSTDv07_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
3907 if (remainingSize) return ERROR(srcSize_wrong);
3911 return ERROR(GENERIC); /* impossible */
3913 if (blockProperties.blockType == bt_end) break; /* bt_end */
3915 if (ZSTDv07_isError(decodedSize)) return decodedSize;
3916 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
3919 remainingSize -= cBlockSize;
3926 /*! ZSTDv07_decompress_usingPreparedDCtx() :
3927 * Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
3928 * It avoids reloading the dictionary each time.
3929 * `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict().
3930 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
3931 size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* refDCtx,
3932 void* dst, size_t dstCapacity,
3933 const void* src, size_t srcSize)
3935 ZSTDv07_copyDCtx(dctx, refDCtx);
3936 ZSTDv07_checkContinuity(dctx, dst);
3937 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3941 size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx* dctx,
3942 void* dst, size_t dstCapacity,
3943 const void* src, size_t srcSize,
3944 const void* dict, size_t dictSize)
3946 ZSTDv07_decompressBegin_usingDict(dctx, dict, dictSize);
3947 ZSTDv07_checkContinuity(dctx, dst);
3948 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3952 size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3954 return ZSTDv07_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3958 size_t ZSTDv07_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3960 #if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1)
3962 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx();
3963 if (dctx==NULL) return ERROR(memory_allocation);
3964 regenSize = ZSTDv07_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3965 ZSTDv07_freeDCtx(dctx);
3967 #else /* stack mode */
3969 return ZSTDv07_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3973 size_t ZSTDv07_findFrameCompressedSize(const void* src, size_t srcSize)
3975 const BYTE* ip = (const BYTE*)src;
3976 size_t remainingSize = srcSize;
3979 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3982 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3983 if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3984 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) return ERROR(prefix_unknown);
3985 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3986 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3989 /* Loop on each block */
3991 blockProperties_t blockProperties;
3992 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, remainingSize, &blockProperties);
3993 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3995 ip += ZSTDv07_blockHeaderSize;
3996 remainingSize -= ZSTDv07_blockHeaderSize;
3998 if (blockProperties.blockType == bt_end) break;
4000 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
4003 remainingSize -= cBlockSize;
4006 return ip - (const BYTE*)src;
4009 /*_******************************
4010 * Streaming Decompression API
4011 ********************************/
4012 size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx)
4014 return dctx->expected;
4017 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx)
4019 return dctx->stage == ZSTDds_skipFrame;
4022 /** ZSTDv07_decompressContinue() :
4023 * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
4024 * or an error code, which can be tested using ZSTDv07_isError() */
4025 size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
4028 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
4029 if (dstCapacity) ZSTDv07_checkContinuity(dctx, dst);
4031 switch (dctx->stage)
4033 case ZSTDds_getFrameHeaderSize :
4034 if (srcSize != ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
4035 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
4036 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
4037 dctx->expected = ZSTDv07_skippableHeaderSize - ZSTDv07_frameHeaderSize_min; /* magic number + skippable frame length */
4038 dctx->stage = ZSTDds_decodeSkippableHeader;
4041 dctx->headerSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
4042 if (ZSTDv07_isError(dctx->headerSize)) return dctx->headerSize;
4043 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
4044 if (dctx->headerSize > ZSTDv07_frameHeaderSize_min) {
4045 dctx->expected = dctx->headerSize - ZSTDv07_frameHeaderSize_min;
4046 dctx->stage = ZSTDds_decodeFrameHeader;
4049 dctx->expected = 0; /* not necessary to copy more */
4051 case ZSTDds_decodeFrameHeader:
4053 memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
4054 result = ZSTDv07_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
4055 if (ZSTDv07_isError(result)) return result;
4056 dctx->expected = ZSTDv07_blockHeaderSize;
4057 dctx->stage = ZSTDds_decodeBlockHeader;
4060 case ZSTDds_decodeBlockHeader:
4061 { blockProperties_t bp;
4062 size_t const cBlockSize = ZSTDv07_getcBlockSize(src, ZSTDv07_blockHeaderSize, &bp);
4063 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
4064 if (bp.blockType == bt_end) {
4065 if (dctx->fParams.checksumFlag) {
4066 U64 const h64 = XXH64_digest(&dctx->xxhState);
4067 U32 const h32 = (U32)(h64>>11) & ((1<<22)-1);
4068 const BYTE* const ip = (const BYTE*)src;
4069 U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16);
4070 if (check32 != h32) return ERROR(checksum_wrong);
4073 dctx->stage = ZSTDds_getFrameHeaderSize;
4075 dctx->expected = cBlockSize;
4076 dctx->bType = bp.blockType;
4077 dctx->stage = ZSTDds_decompressBlock;
4081 case ZSTDds_decompressBlock:
4086 rSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
4089 rSize = ZSTDv07_copyRawBlock(dst, dstCapacity, src, srcSize);
4092 return ERROR(GENERIC); /* not yet handled */
4094 case bt_end : /* should never happen (filtered at phase 1) */
4098 return ERROR(GENERIC); /* impossible */
4100 dctx->stage = ZSTDds_decodeBlockHeader;
4101 dctx->expected = ZSTDv07_blockHeaderSize;
4102 dctx->previousDstEnd = (char*)dst + rSize;
4103 if (ZSTDv07_isError(rSize)) return rSize;
4104 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
4107 case ZSTDds_decodeSkippableHeader:
4108 { memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
4109 dctx->expected = MEM_readLE32(dctx->headerBuffer + 4);
4110 dctx->stage = ZSTDds_skipFrame;
4113 case ZSTDds_skipFrame:
4114 { dctx->expected = 0;
4115 dctx->stage = ZSTDds_getFrameHeaderSize;
4119 return ERROR(GENERIC); /* impossible */
4124 static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4126 dctx->dictEnd = dctx->previousDstEnd;
4127 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
4129 dctx->previousDstEnd = (const char*)dict + dictSize;
4133 static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx* dctx, const void* const dict, size_t const dictSize)
4135 const BYTE* dictPtr = (const BYTE*)dict;
4136 const BYTE* const dictEnd = dictPtr + dictSize;
4138 { size_t const hSize = HUFv07_readDTableX4(dctx->hufTable, dict, dictSize);
4139 if (HUFv07_isError(hSize)) return ERROR(dictionary_corrupted);
4143 { short offcodeNCount[MaxOff+1];
4144 U32 offcodeMaxValue=MaxOff, offcodeLog;
4145 size_t const offcodeHeaderSize = FSEv07_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
4146 if (FSEv07_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
4147 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
4148 { size_t const errorCode = FSEv07_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
4149 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4150 dictPtr += offcodeHeaderSize;
4153 { short matchlengthNCount[MaxML+1];
4154 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
4155 size_t const matchlengthHeaderSize = FSEv07_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
4156 if (FSEv07_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
4157 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
4158 { size_t const errorCode = FSEv07_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
4159 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4160 dictPtr += matchlengthHeaderSize;
4163 { short litlengthNCount[MaxLL+1];
4164 unsigned litlengthMaxValue = MaxLL, litlengthLog;
4165 size_t const litlengthHeaderSize = FSEv07_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
4166 if (FSEv07_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
4167 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
4168 { size_t const errorCode = FSEv07_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
4169 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4170 dictPtr += litlengthHeaderSize;
4173 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
4174 dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] == 0 || dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
4175 dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] == 0 || dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
4176 dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] == 0 || dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
4179 dctx->litEntropy = dctx->fseEntropy = 1;
4180 return dictPtr - (const BYTE*)dict;
4183 static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4185 if (dictSize < 8) return ZSTDv07_refDictContent(dctx, dict, dictSize);
4186 { U32 const magic = MEM_readLE32(dict);
4187 if (magic != ZSTDv07_DICT_MAGIC) {
4188 return ZSTDv07_refDictContent(dctx, dict, dictSize); /* pure content mode */
4190 dctx->dictID = MEM_readLE32((const char*)dict + 4);
4192 /* load entropy tables */
4193 dict = (const char*)dict + 8;
4195 { size_t const eSize = ZSTDv07_loadEntropy(dctx, dict, dictSize);
4196 if (ZSTDv07_isError(eSize)) return ERROR(dictionary_corrupted);
4197 dict = (const char*)dict + eSize;
4201 /* reference dictionary content */
4202 return ZSTDv07_refDictContent(dctx, dict, dictSize);
4206 size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4208 { size_t const errorCode = ZSTDv07_decompressBegin(dctx);
4209 if (ZSTDv07_isError(errorCode)) return errorCode; }
4211 if (dict && dictSize) {
4212 size_t const errorCode = ZSTDv07_decompress_insertDictionary(dctx, dict, dictSize);
4213 if (ZSTDv07_isError(errorCode)) return ERROR(dictionary_corrupted);
4220 struct ZSTDv07_DDict_s {
4223 ZSTDv07_DCtx* refContext;
4224 }; /* typedef'd tp ZSTDv07_CDict within zstd.h */
4226 ZSTDv07_DDict* ZSTDv07_createDDict_advanced(const void* dict, size_t dictSize, ZSTDv07_customMem customMem)
4228 if (!customMem.customAlloc && !customMem.customFree)
4229 customMem = defaultCustomMem;
4231 if (!customMem.customAlloc || !customMem.customFree)
4234 { ZSTDv07_DDict* const ddict = (ZSTDv07_DDict*) customMem.customAlloc(customMem.opaque, sizeof(*ddict));
4235 void* const dictContent = customMem.customAlloc(customMem.opaque, dictSize);
4236 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx_advanced(customMem);
4238 if (!dictContent || !ddict || !dctx) {
4239 customMem.customFree(customMem.opaque, dictContent);
4240 customMem.customFree(customMem.opaque, ddict);
4241 customMem.customFree(customMem.opaque, dctx);
4245 memcpy(dictContent, dict, dictSize);
4246 { size_t const errorCode = ZSTDv07_decompressBegin_usingDict(dctx, dictContent, dictSize);
4247 if (ZSTDv07_isError(errorCode)) {
4248 customMem.customFree(customMem.opaque, dictContent);
4249 customMem.customFree(customMem.opaque, ddict);
4250 customMem.customFree(customMem.opaque, dctx);
4254 ddict->dict = dictContent;
4255 ddict->dictSize = dictSize;
4256 ddict->refContext = dctx;
4261 /*! ZSTDv07_createDDict() :
4262 * Create a digested dictionary, ready to start decompression without startup delay.
4263 * `dict` can be released after `ZSTDv07_DDict` creation */
4264 ZSTDv07_DDict* ZSTDv07_createDDict(const void* dict, size_t dictSize)
4266 ZSTDv07_customMem const allocator = { NULL, NULL, NULL };
4267 return ZSTDv07_createDDict_advanced(dict, dictSize, allocator);
4270 size_t ZSTDv07_freeDDict(ZSTDv07_DDict* ddict)
4272 ZSTDv07_freeFunction const cFree = ddict->refContext->customMem.customFree;
4273 void* const opaque = ddict->refContext->customMem.opaque;
4274 ZSTDv07_freeDCtx(ddict->refContext);
4275 cFree(opaque, ddict->dict);
4276 cFree(opaque, ddict);
4280 /*! ZSTDv07_decompress_usingDDict() :
4281 * Decompression using a pre-digested Dictionary
4282 * Use dictionary without significant overhead. */
4283 ZSTDLIBv07_API size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx* dctx,
4284 void* dst, size_t dstCapacity,
4285 const void* src, size_t srcSize,
4286 const ZSTDv07_DDict* ddict)
4288 return ZSTDv07_decompress_usingPreparedDCtx(dctx, ddict->refContext,
4293 Buffered version of Zstd compression library
4294 Copyright (C) 2015-2016, Yann Collet.
4296 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
4298 Redistribution and use in source and binary forms, with or without
4299 modification, are permitted provided that the following conditions are
4301 * Redistributions of source code must retain the above copyright
4302 notice, this list of conditions and the following disclaimer.
4303 * Redistributions in binary form must reproduce the above
4304 copyright notice, this list of conditions and the following disclaimer
4305 in the documentation and/or other materials provided with the
4307 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4308 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
4309 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
4310 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
4311 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4312 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
4313 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
4314 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
4315 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
4316 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
4317 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4319 You can contact the author at :
4320 - zstd homepage : http://www.zstd.net/
4325 /*-***************************************************************************
4326 * Streaming decompression howto
4328 * A ZBUFFv07_DCtx object is required to track streaming operations.
4329 * Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources.
4330 * Use ZBUFFv07_decompressInit() to start a new decompression operation,
4331 * or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary.
4332 * Note that ZBUFFv07_DCtx objects can be re-init multiple times.
4334 * Use ZBUFFv07_decompressContinue() repetitively to consume your input.
4335 * *srcSizePtr and *dstCapacityPtr can be any size.
4336 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
4337 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
4338 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
4339 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
4340 * or 0 when a frame is completely decoded,
4341 * or an error code, which can be tested using ZBUFFv07_isError().
4343 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize()
4344 * output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
4345 * input : ZBUFFv07_recommendedDInSize == 128KB + 3;
4346 * just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
4347 * *******************************************************************************/
4349 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
4350 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv07_dStage;
4352 /* *** Resource management *** */
4353 struct ZBUFFv07_DCtx_s {
4355 ZSTDv07_frameParams fParams;
4356 ZBUFFv07_dStage stage;
4365 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
4367 ZSTDv07_customMem customMem;
4368 }; /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */
4370 ZSTDLIBv07_API ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem);
4372 ZBUFFv07_DCtx* ZBUFFv07_createDCtx(void)
4374 return ZBUFFv07_createDCtx_advanced(defaultCustomMem);
4377 ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem)
4381 if (!customMem.customAlloc && !customMem.customFree)
4382 customMem = defaultCustomMem;
4384 if (!customMem.customAlloc || !customMem.customFree)
4387 zbd = (ZBUFFv07_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFFv07_DCtx));
4388 if (zbd==NULL) return NULL;
4389 memset(zbd, 0, sizeof(ZBUFFv07_DCtx));
4390 memcpy(&zbd->customMem, &customMem, sizeof(ZSTDv07_customMem));
4391 zbd->zd = ZSTDv07_createDCtx_advanced(customMem);
4392 if (zbd->zd == NULL) { ZBUFFv07_freeDCtx(zbd); return NULL; }
4393 zbd->stage = ZBUFFds_init;
4397 size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx* zbd)
4399 if (zbd==NULL) return 0; /* support free on null */
4400 ZSTDv07_freeDCtx(zbd->zd);
4401 if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4402 if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4403 zbd->customMem.customFree(zbd->customMem.opaque, zbd);
4408 /* *** Initialization *** */
4410 size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx* zbd, const void* dict, size_t dictSize)
4412 zbd->stage = ZBUFFds_loadHeader;
4413 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
4414 return ZSTDv07_decompressBegin_usingDict(zbd->zd, dict, dictSize);
4417 size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx* zbd)
4419 return ZBUFFv07_decompressInitDictionary(zbd, NULL, 0);
4423 /* internal util function */
4424 MEM_STATIC size_t ZBUFFv07_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
4426 size_t const length = MIN(dstCapacity, srcSize);
4427 memcpy(dst, src, length);
4432 /* *** Decompression *** */
4434 size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx* zbd,
4435 void* dst, size_t* dstCapacityPtr,
4436 const void* src, size_t* srcSizePtr)
4438 const char* const istart = (const char*)src;
4439 const char* const iend = istart + *srcSizePtr;
4440 const char* ip = istart;
4441 char* const ostart = (char*)dst;
4442 char* const oend = ostart + *dstCapacityPtr;
4450 return ERROR(init_missing);
4452 case ZBUFFds_loadHeader :
4453 { size_t const hSize = ZSTDv07_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
4454 if (ZSTDv07_isError(hSize)) return hSize;
4456 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */
4457 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */
4458 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
4459 zbd->lhSize += iend-ip;
4460 *dstCapacityPtr = 0;
4461 return (hSize - zbd->lhSize) + ZSTDv07_blockHeaderSize; /* remaining header bytes + next block header */
4463 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
4467 /* Consume header */
4468 { size_t const h1Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv07_frameHeaderSize_min */
4469 size_t const h1Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4470 if (ZSTDv07_isError(h1Result)) return h1Result;
4471 if (h1Size < zbd->lhSize) { /* long header */
4472 size_t const h2Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4473 size_t const h2Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4474 if (ZSTDv07_isError(h2Result)) return h2Result;
4477 zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN);
4479 /* Frame header instruct buffer sizes */
4480 { size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX);
4481 zbd->blockSize = blockSize;
4482 if (zbd->inBuffSize < blockSize) {
4483 zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4484 zbd->inBuffSize = blockSize;
4485 zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize);
4486 if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4488 { size_t const neededOutSize = zbd->fParams.windowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
4489 if (zbd->outBuffSize < neededOutSize) {
4490 zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4491 zbd->outBuffSize = neededOutSize;
4492 zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize);
4493 if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4495 zbd->stage = ZBUFFds_read;
4499 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4500 if (neededInSize==0) { /* end of frame */
4501 zbd->stage = ZBUFFds_init;
4505 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
4506 const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4507 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4508 zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart),
4510 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4512 if (!decodedSize && !isSkipFrame) break; /* this was just a header */
4513 zbd->outEnd = zbd->outStart + decodedSize;
4514 zbd->stage = ZBUFFds_flush;
4517 if (ip==iend) { notDone = 0; break; } /* no more input */
4518 zbd->stage = ZBUFFds_load;
4522 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4523 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */
4525 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */
4526 loadedSize = ZBUFFv07_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4528 zbd->inPos += loadedSize;
4529 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
4531 /* decode loaded input */
4532 { const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4533 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4534 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4535 zbd->inBuff, neededInSize);
4536 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4537 zbd->inPos = 0; /* input is consumed */
4538 if (!decodedSize && !isSkipFrame) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */
4539 zbd->outEnd = zbd->outStart + decodedSize;
4540 zbd->stage = ZBUFFds_flush;
4546 { size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4547 size_t const flushedSize = ZBUFFv07_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4549 zbd->outStart += flushedSize;
4550 if (flushedSize == toFlushSize) {
4551 zbd->stage = ZBUFFds_read;
4552 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4553 zbd->outStart = zbd->outEnd = 0;
4556 /* cannot flush everything */
4560 default: return ERROR(GENERIC); /* impossible */
4564 *srcSizePtr = ip-istart;
4565 *dstCapacityPtr = op-ostart;
4566 { size_t nextSrcSizeHint = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4567 nextSrcSizeHint -= zbd->inPos; /* already loaded*/
4568 return nextSrcSizeHint;
4574 /* *************************************
4576 ***************************************/
4577 size_t ZBUFFv07_recommendedDInSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + ZSTDv07_blockHeaderSize /* block header size*/ ; }
4578 size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX; }