2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
14 #include <stddef.h> /* size_t, ptrdiff_t */
15 #include <string.h> /* memcpy */
16 #include <stdlib.h> /* malloc, free, qsort */
17 #include "error_private.h"
21 /* ******************************************************************
23 low-level memory access routines
24 Copyright (C) 2013-2015, Yann Collet.
26 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
28 Redistribution and use in source and binary forms, with or without
29 modification, are permitted provided that the following conditions are
32 * Redistributions of source code must retain the above copyright
33 notice, this list of conditions and the following disclaimer.
34 * Redistributions in binary form must reproduce the above
35 copyright notice, this list of conditions and the following disclaimer
36 in the documentation and/or other materials provided with the
39 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
40 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
41 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
42 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
43 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
45 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
46 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
47 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
48 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
49 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
51 You can contact the author at :
52 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
53 - Public forum : https://groups.google.com/forum/#!forum/lz4c
54 ****************************************************************** */
58 #if defined (__cplusplus)
63 /*-****************************************
65 ******************************************/
66 #if defined(_MSC_VER) /* Visual Studio */
67 # include <stdlib.h> /* _byteswap_ulong */
68 # include <intrin.h> /* _byteswap_* */
71 # define MEM_STATIC static __attribute__((unused))
72 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
73 # define MEM_STATIC static inline
74 #elif defined(_MSC_VER)
75 # define MEM_STATIC static __inline
77 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
81 /*-**************************************************************
83 *****************************************************************/
84 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
94 typedef unsigned char BYTE;
95 typedef unsigned short U16;
96 typedef signed short S16;
97 typedef unsigned int U32;
98 typedef signed int S32;
99 typedef unsigned long long U64;
100 typedef signed long long S64;
104 /*-**************************************************************
106 *****************************************************************/
107 /* MEM_FORCE_MEMORY_ACCESS :
108 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
109 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
110 * The below switch allow to select different access method for improved performance.
111 * Method 0 (default) : use `memcpy()`. Safe and portable.
112 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
113 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
114 * Method 2 : direct access. This method is portable but violate C standard.
115 * It can generate buggy code on targets depending on alignment.
116 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
117 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
118 * Prefer these methods in priority order (0 > 1 > 2)
120 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
121 # 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__) )
122 # define MEM_FORCE_MEMORY_ACCESS 2
123 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
124 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
125 # define MEM_FORCE_MEMORY_ACCESS 1
129 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
130 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
132 MEM_STATIC unsigned MEM_isLittleEndian(void)
134 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
138 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
140 /* violates C standard, by lying on structure alignment.
141 Only use if no other choice to achieve best performance on target platform */
142 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
143 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
144 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
146 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
148 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
150 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
151 /* currently only defined for gcc and icc */
152 typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign;
154 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
155 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
156 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
158 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
162 /* default method, safe and standard.
163 can sometimes prove slower */
165 MEM_STATIC U16 MEM_read16(const void* memPtr)
167 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
170 MEM_STATIC U32 MEM_read32(const void* memPtr)
172 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
175 MEM_STATIC U64 MEM_read64(const void* memPtr)
177 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
180 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
182 memcpy(memPtr, &value, sizeof(value));
186 #endif /* MEM_FORCE_MEMORY_ACCESS */
188 MEM_STATIC U32 MEM_swap32(U32 in)
190 #if defined(_MSC_VER) /* Visual Studio */
191 return _byteswap_ulong(in);
192 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
193 return __builtin_bswap32(in);
195 return ((in << 24) & 0xff000000 ) |
196 ((in << 8) & 0x00ff0000 ) |
197 ((in >> 8) & 0x0000ff00 ) |
198 ((in >> 24) & 0x000000ff );
202 MEM_STATIC U64 MEM_swap64(U64 in)
204 #if defined(_MSC_VER) /* Visual Studio */
205 return _byteswap_uint64(in);
206 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
207 return __builtin_bswap64(in);
209 return ((in << 56) & 0xff00000000000000ULL) |
210 ((in << 40) & 0x00ff000000000000ULL) |
211 ((in << 24) & 0x0000ff0000000000ULL) |
212 ((in << 8) & 0x000000ff00000000ULL) |
213 ((in >> 8) & 0x00000000ff000000ULL) |
214 ((in >> 24) & 0x0000000000ff0000ULL) |
215 ((in >> 40) & 0x000000000000ff00ULL) |
216 ((in >> 56) & 0x00000000000000ffULL);
221 /*=== Little endian r/w ===*/
223 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
225 if (MEM_isLittleEndian())
226 return MEM_read16(memPtr);
228 const BYTE* p = (const BYTE*)memPtr;
229 return (U16)(p[0] + (p[1]<<8));
233 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
235 if (MEM_isLittleEndian()) {
236 MEM_write16(memPtr, val);
238 BYTE* p = (BYTE*)memPtr;
240 p[1] = (BYTE)(val>>8);
244 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
246 if (MEM_isLittleEndian())
247 return MEM_read32(memPtr);
249 return MEM_swap32(MEM_read32(memPtr));
253 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
255 if (MEM_isLittleEndian())
256 return MEM_read64(memPtr);
258 return MEM_swap64(MEM_read64(memPtr));
262 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
265 return (size_t)MEM_readLE32(memPtr);
267 return (size_t)MEM_readLE64(memPtr);
272 #if defined (__cplusplus)
276 #endif /* MEM_H_MODULE */
279 zstd - standard compression library
280 Header File for static linking only
281 Copyright (C) 2014-2016, Yann Collet.
283 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
285 Redistribution and use in source and binary forms, with or without
286 modification, are permitted provided that the following conditions are
288 * Redistributions of source code must retain the above copyright
289 notice, this list of conditions and the following disclaimer.
290 * Redistributions in binary form must reproduce the above
291 copyright notice, this list of conditions and the following disclaimer
292 in the documentation and/or other materials provided with the
294 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
295 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
296 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
297 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
298 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
299 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
300 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
301 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
302 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
303 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
304 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
306 You can contact the author at :
307 - zstd homepage : http://www.zstd.net
309 #ifndef ZSTDv06_STATIC_H
310 #define ZSTDv06_STATIC_H
312 /* The prototypes defined within this file are considered experimental.
313 * They should not be used in the context DLL as they may change in the future.
314 * Prefer static linking if you need them, to control breaking version changes issues.
317 #if defined (__cplusplus)
323 /*- Advanced Decompression functions -*/
325 /*! ZSTDv06_decompress_usingPreparedDCtx() :
326 * Same as ZSTDv06_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
327 * It avoids reloading the dictionary each time.
328 * `preparedDCtx` must have been properly initialized using ZSTDv06_decompressBegin_usingDict().
329 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
330 ZSTDLIBv06_API size_t ZSTDv06_decompress_usingPreparedDCtx(
331 ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* preparedDCtx,
332 void* dst, size_t dstCapacity,
333 const void* src, size_t srcSize);
337 #define ZSTDv06_FRAMEHEADERSIZE_MAX 13 /* for static allocation */
338 static const size_t ZSTDv06_frameHeaderSize_min = 5;
339 static const size_t ZSTDv06_frameHeaderSize_max = ZSTDv06_FRAMEHEADERSIZE_MAX;
341 ZSTDLIBv06_API size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx);
344 Streaming decompression, direct mode (bufferless)
346 A ZSTDv06_DCtx object is required to track streaming operations.
347 Use ZSTDv06_createDCtx() / ZSTDv06_freeDCtx() to manage it.
348 A ZSTDv06_DCtx object can be re-used multiple times.
350 First optional operation is to retrieve frame parameters, using ZSTDv06_getFrameParams(), which doesn't consume the input.
351 It can provide the minimum size of rolling buffer required to properly decompress data,
352 and optionally the final size of uncompressed content.
353 (Note : content size is an optional info that may not be present. 0 means : content size unknown)
354 Frame parameters are extracted from the beginning of compressed frame.
355 The amount of data to read is variable, from ZSTDv06_frameHeaderSize_min to ZSTDv06_frameHeaderSize_max (so if `srcSize` >= ZSTDv06_frameHeaderSize_max, it will always work)
356 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
357 Result : 0 when successful, it means the ZSTDv06_frameParams structure has been filled.
358 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
359 errorCode, which can be tested using ZSTDv06_isError()
361 Start decompression, with ZSTDv06_decompressBegin() or ZSTDv06_decompressBegin_usingDict().
362 Alternatively, you can copy a prepared context, using ZSTDv06_copyDCtx().
364 Then use ZSTDv06_nextSrcSizeToDecompress() and ZSTDv06_decompressContinue() alternatively.
365 ZSTDv06_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv06_decompressContinue().
366 ZSTDv06_decompressContinue() requires this exact amount of bytes, or it will fail.
367 ZSTDv06_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
368 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
370 @result of ZSTDv06_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity)
371 It can be zero, which is not an error; it just means ZSTDv06_decompressContinue() has decoded some header.
373 A frame is fully decoded when ZSTDv06_nextSrcSizeToDecompress() returns zero.
374 Context can then be reset to start a new decompression.
378 /* **************************************
380 ****************************************/
381 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
382 User will have to take in charge required information to regenerate data, such as compressed and content sizes.
384 A few rules to respect :
385 - Uncompressed block size must be <= ZSTDv06_BLOCKSIZE_MAX (128 KB)
386 - Compressing or decompressing requires a context structure
387 + Use ZSTDv06_createCCtx() and ZSTDv06_createDCtx()
388 - It is necessary to init context before starting
389 + compression : ZSTDv06_compressBegin()
390 + decompression : ZSTDv06_decompressBegin()
391 + variants _usingDict() are also allowed
392 + copyCCtx() and copyDCtx() work too
393 - When a block is considered not compressible enough, ZSTDv06_compressBlock() result will be zero.
394 In which case, nothing is produced into `dst`.
395 + User must test for such outcome and deal directly with uncompressed data
396 + ZSTDv06_decompressBlock() doesn't accept uncompressed data as input !!
399 #define ZSTDv06_BLOCKSIZE_MAX (128 * 1024) /* define, for static allocation */
400 ZSTDLIBv06_API size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
404 #if defined (__cplusplus)
408 #endif /* ZSTDv06_STATIC_H */
410 zstd_internal - common functions to include
411 Header File for include
412 Copyright (C) 2014-2016, Yann Collet.
414 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
416 Redistribution and use in source and binary forms, with or without
417 modification, are permitted provided that the following conditions are
419 * Redistributions of source code must retain the above copyright
420 notice, this list of conditions and the following disclaimer.
421 * Redistributions in binary form must reproduce the above
422 copyright notice, this list of conditions and the following disclaimer
423 in the documentation and/or other materials provided with the
425 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
426 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
427 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
428 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
429 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
430 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
431 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
432 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
433 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
434 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
435 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
437 You can contact the author at :
438 - zstd homepage : https://www.zstd.net
440 #ifndef ZSTDv06_CCOMMON_H_MODULE
441 #define ZSTDv06_CCOMMON_H_MODULE
444 /*-*************************************
446 ***************************************/
447 #define MIN(a,b) ((a)<(b) ? (a) : (b))
448 #define MAX(a,b) ((a)>(b) ? (a) : (b))
451 /*-*************************************
453 ***************************************/
454 #define ZSTDv06_DICT_MAGIC 0xEC30A436
456 #define ZSTDv06_REP_NUM 3
457 #define ZSTDv06_REP_INIT ZSTDv06_REP_NUM
458 #define ZSTDv06_REP_MOVE (ZSTDv06_REP_NUM-1)
471 #define ZSTDv06_WINDOWLOG_ABSOLUTEMIN 12
472 static const size_t ZSTDv06_fcs_fieldSize[4] = { 0, 1, 2, 8 };
474 #define ZSTDv06_BLOCKHEADERSIZE 3 /* because C standard does not allow a static const value to be defined using another static const value .... :( */
475 static const size_t ZSTDv06_blockHeaderSize = ZSTDv06_BLOCKHEADERSIZE;
476 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
478 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
479 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
488 #define LONGNBSEQ 0x7F00
491 #define EQUAL_READ32 4
492 #define REPCODE_STARTVALUE 1
495 #define MaxLit ((1<<Litbits) - 1)
499 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
504 #define FSEv06_ENCODING_RAW 0
505 #define FSEv06_ENCODING_RLE 1
506 #define FSEv06_ENCODING_STATIC 2
507 #define FSEv06_ENCODING_DYNAMIC 3
509 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
511 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
512 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
514 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
515 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
517 static const U32 LL_defaultNormLog = 6;
519 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
520 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
521 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
523 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
524 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
525 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
527 static const U32 ML_defaultNormLog = 6;
529 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
530 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
531 static const U32 OF_defaultNormLog = 5;
534 /*-*******************************************
535 * Shared functions to include for inlining
536 *********************************************/
537 static void ZSTDv06_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
538 #define COPY8(d,s) { ZSTDv06_copy8(d,s); d+=8; s+=8; }
540 /*! ZSTDv06_wildcopy() :
541 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
542 #define WILDCOPY_OVERLENGTH 8
543 MEM_STATIC void ZSTDv06_wildcopy(void* dst, const void* src, ptrdiff_t length)
545 const BYTE* ip = (const BYTE*)src;
546 BYTE* op = (BYTE*)dst;
547 BYTE* const oend = op + length;
555 /*-*******************************************
557 *********************************************/
568 U32 rep[ZSTDv06_REP_INIT];
571 typedef struct { U32 unused; } ZSTDv06_stats_t;
583 U16* matchLengthStart;
586 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
589 ZSTDv06_optimal_t* priceTable;
590 ZSTDv06_match_t* matchTable;
591 U32* matchLengthFreq;
600 U32 log2matchLengthSum;
602 U32 log2litLengthSum;
608 const BYTE* cachedLiterals;
609 ZSTDv06_stats_t stats;
612 void ZSTDv06_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
615 #endif /* ZSTDv06_CCOMMON_H_MODULE */
616 /* ******************************************************************
617 FSE : Finite State Entropy codec
618 Public Prototypes declaration
619 Copyright (C) 2013-2016, Yann Collet.
621 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
623 Redistribution and use in source and binary forms, with or without
624 modification, are permitted provided that the following conditions are
627 * Redistributions of source code must retain the above copyright
628 notice, this list of conditions and the following disclaimer.
629 * Redistributions in binary form must reproduce the above
630 copyright notice, this list of conditions and the following disclaimer
631 in the documentation and/or other materials provided with the
634 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
635 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
636 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
637 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
638 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
639 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
640 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
641 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
642 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
643 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
644 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
646 You can contact the author at :
647 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
648 ****************************************************************** */
652 #if defined (__cplusplus)
658 /*-****************************************
659 * FSE simple functions
660 ******************************************/
661 /*! FSEv06_decompress():
662 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
663 into already allocated destination buffer 'dst', of size 'dstCapacity'.
664 @return : size of regenerated data (<= maxDstSize),
665 or an error code, which can be tested using FSEv06_isError() .
667 ** Important ** : FSEv06_decompress() does not decompress non-compressible nor RLE data !!!
668 Why ? : making this distinction requires a header.
669 Header management is intentionally delegated to the user layer, which can better manage special cases.
671 size_t FSEv06_decompress(void* dst, size_t dstCapacity,
672 const void* cSrc, size_t cSrcSize);
675 /*-*****************************************
677 ******************************************/
678 size_t FSEv06_compressBound(size_t size); /* maximum compressed size */
680 /* Error Management */
681 unsigned FSEv06_isError(size_t code); /* tells if a return value is an error code */
682 const char* FSEv06_getErrorName(size_t code); /* provides error code string (useful for debugging) */
686 /*-*****************************************
688 ******************************************/
691 FSEv06_decompress() does the following:
692 1. read normalized counters with readNCount()
693 2. build decoding table 'DTable' from normalized counters
694 3. decode the data stream using decoding table 'DTable'
696 The following API allows targeting specific sub-functions for advanced tasks.
697 For example, it's possible to compress several blocks using the same 'CTable',
698 or to save and provide normalized distribution using external method.
702 /* *** DECOMPRESSION *** */
704 /*! FSEv06_readNCount():
705 Read compactly saved 'normalizedCounter' from 'rBuffer'.
706 @return : size read from 'rBuffer',
707 or an errorCode, which can be tested using FSEv06_isError().
708 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
709 size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
711 /*! Constructor and Destructor of FSEv06_DTable.
712 Note that its size depends on 'tableLog' */
713 typedef unsigned FSEv06_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
714 FSEv06_DTable* FSEv06_createDTable(unsigned tableLog);
715 void FSEv06_freeDTable(FSEv06_DTable* dt);
717 /*! FSEv06_buildDTable():
718 Builds 'dt', which must be already allocated, using FSEv06_createDTable().
719 return : 0, or an errorCode, which can be tested using FSEv06_isError() */
720 size_t FSEv06_buildDTable (FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
722 /*! FSEv06_decompress_usingDTable():
723 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
724 into `dst` which must be already allocated.
725 @return : size of regenerated data (necessarily <= `dstCapacity`),
726 or an errorCode, which can be tested using FSEv06_isError() */
727 size_t FSEv06_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv06_DTable* dt);
732 (Note : these functions only decompress FSE-compressed blocks.
733 If block is uncompressed, use memcpy() instead
734 If block is a single repeated byte, use memset() instead )
736 The first step is to obtain the normalized frequencies of symbols.
737 This can be performed by FSEv06_readNCount() if it was saved using FSEv06_writeNCount().
738 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
739 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
740 or size the table to handle worst case situations (typically 256).
741 FSEv06_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
742 The result of FSEv06_readNCount() is the number of bytes read from 'rBuffer'.
743 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
744 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
746 The next step is to build the decompression tables 'FSEv06_DTable' from 'normalizedCounter'.
747 This is performed by the function FSEv06_buildDTable().
748 The space required by 'FSEv06_DTable' must be already allocated using FSEv06_createDTable().
749 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
751 `FSEv06_DTable` can then be used to decompress `cSrc`, with FSEv06_decompress_usingDTable().
752 `cSrcSize` must be strictly correct, otherwise decompression will fail.
753 FSEv06_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
754 If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). (ex: dst buffer too small)
758 #if defined (__cplusplus)
762 #endif /* FSEv06_H */
763 /* ******************************************************************
766 header file (to include)
767 Copyright (C) 2013-2016, Yann Collet.
769 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
771 Redistribution and use in source and binary forms, with or without
772 modification, are permitted provided that the following conditions are
775 * Redistributions of source code must retain the above copyright
776 notice, this list of conditions and the following disclaimer.
777 * Redistributions in binary form must reproduce the above
778 copyright notice, this list of conditions and the following disclaimer
779 in the documentation and/or other materials provided with the
782 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
783 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
784 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
785 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
786 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
787 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
788 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
789 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
790 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
791 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
792 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
794 You can contact the author at :
795 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
796 ****************************************************************** */
797 #ifndef BITSTREAM_H_MODULE
798 #define BITSTREAM_H_MODULE
800 #if defined (__cplusplus)
806 * This API consists of small unitary functions, which must be inlined for best performance.
807 * Since link-time-optimization is not available for all compilers,
808 * these functions are defined into a .h to be included.
812 /*=========================================
814 =========================================*/
815 #if defined(__BMI__) && defined(__GNUC__)
816 # include <immintrin.h> /* support for bextr (experimental) */
821 /*-********************************************
822 * bitStream decoding API (read backward)
823 **********************************************/
827 unsigned bitsConsumed;
832 typedef enum { BITv06_DStream_unfinished = 0,
833 BITv06_DStream_endOfBuffer = 1,
834 BITv06_DStream_completed = 2,
835 BITv06_DStream_overflow = 3 } BITv06_DStream_status; /* result of BITv06_reloadDStream() */
836 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
838 MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
839 MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, unsigned nbBits);
840 MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD);
841 MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* bitD);
845 /*-****************************************
847 ******************************************/
848 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, unsigned nbBits);
849 /* faster, but works only if nbBits >= 1 */
853 /*-**************************************************************
855 ****************************************************************/
856 MEM_STATIC unsigned BITv06_highbit32 ( U32 val)
858 # if defined(_MSC_VER) /* Visual */
860 _BitScanReverse ( &r, val );
862 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
863 return 31 - __builtin_clz (val);
864 # else /* Software version */
865 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 };
873 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
880 /*-********************************************************
882 **********************************************************/
883 /*! BITv06_initDStream() :
884 * Initialize a BITv06_DStream_t.
885 * `bitD` : a pointer to an already allocated BITv06_DStream_t structure.
886 * `srcSize` must be the *exact* size of the bitStream, in bytes.
887 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
889 MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
891 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
893 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
894 bitD->start = (const char*)srcBuffer;
895 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
896 bitD->bitContainer = MEM_readLEST(bitD->ptr);
897 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
898 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */
899 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); }
901 bitD->start = (const char*)srcBuffer;
902 bitD->ptr = bitD->start;
903 bitD->bitContainer = *(const BYTE*)(bitD->start);
906 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
907 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
908 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
909 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
910 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
911 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */
914 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
915 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */
916 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); }
917 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
924 MEM_STATIC size_t BITv06_lookBits(const BITv06_DStream_t* bitD, U32 nbBits)
926 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
927 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
930 /*! BITv06_lookBitsFast() :
931 * unsafe version; only works only if nbBits >= 1 */
932 MEM_STATIC size_t BITv06_lookBitsFast(const BITv06_DStream_t* bitD, U32 nbBits)
934 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
935 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
938 MEM_STATIC void BITv06_skipBits(BITv06_DStream_t* bitD, U32 nbBits)
940 bitD->bitsConsumed += nbBits;
943 MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, U32 nbBits)
945 size_t const value = BITv06_lookBits(bitD, nbBits);
946 BITv06_skipBits(bitD, nbBits);
950 /*! BITv06_readBitsFast() :
951 * unsafe version; only works only if nbBits >= 1 */
952 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, U32 nbBits)
954 size_t const value = BITv06_lookBitsFast(bitD, nbBits);
955 BITv06_skipBits(bitD, nbBits);
959 MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD)
961 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
962 return BITv06_DStream_overflow;
964 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
965 bitD->ptr -= bitD->bitsConsumed >> 3;
966 bitD->bitsConsumed &= 7;
967 bitD->bitContainer = MEM_readLEST(bitD->ptr);
968 return BITv06_DStream_unfinished;
970 if (bitD->ptr == bitD->start) {
971 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv06_DStream_endOfBuffer;
972 return BITv06_DStream_completed;
974 { U32 nbBytes = bitD->bitsConsumed >> 3;
975 BITv06_DStream_status result = BITv06_DStream_unfinished;
976 if (bitD->ptr - nbBytes < bitD->start) {
977 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
978 result = BITv06_DStream_endOfBuffer;
980 bitD->ptr -= nbBytes;
981 bitD->bitsConsumed -= nbBytes*8;
982 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
987 /*! BITv06_endOfDStream() :
988 * @return Tells if DStream has exactly reached its end (all bits consumed).
990 MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* DStream)
992 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
995 #if defined (__cplusplus)
999 #endif /* BITSTREAM_H_MODULE */
1000 /* ******************************************************************
1001 FSE : Finite State Entropy coder
1002 header file for static linking (only)
1003 Copyright (C) 2013-2015, Yann Collet
1005 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1007 Redistribution and use in source and binary forms, with or without
1008 modification, are permitted provided that the following conditions are
1011 * Redistributions of source code must retain the above copyright
1012 notice, this list of conditions and the following disclaimer.
1013 * Redistributions in binary form must reproduce the above
1014 copyright notice, this list of conditions and the following disclaimer
1015 in the documentation and/or other materials provided with the
1018 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1019 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1020 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1021 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1022 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1023 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1024 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1025 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1026 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1027 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1028 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1030 You can contact the author at :
1031 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1032 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1033 ****************************************************************** */
1034 #ifndef FSEv06_STATIC_H
1035 #define FSEv06_STATIC_H
1037 #if defined (__cplusplus)
1042 /* *****************************************
1044 *******************************************/
1045 /* FSE buffer bounds */
1046 #define FSEv06_NCOUNTBOUND 512
1047 #define FSEv06_BLOCKBOUND(size) (size + (size>>7))
1048 #define FSEv06_COMPRESSBOUND(size) (FSEv06_NCOUNTBOUND + FSEv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
1050 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
1051 #define FSEv06_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
1054 /* *****************************************
1056 *******************************************/
1057 size_t FSEv06_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
1058 /* same as FSEv06_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
1060 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits);
1061 /* build a fake FSEv06_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
1063 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, unsigned char symbolValue);
1064 /* build a fake FSEv06_DTable, designed to always generate the same symbolValue */
1067 /* *****************************************
1068 * FSE symbol decompression API
1069 *******************************************/
1073 const void* table; /* precise table may vary, depending on U16 */
1077 static void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt);
1079 static unsigned char FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD);
1082 /* *****************************************
1084 *******************************************/
1085 static unsigned char FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD);
1086 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
1089 /* *****************************************
1090 * Implementation of inlined functions
1091 *******************************************/
1094 /* ====== Decompression ====== */
1099 } FSEv06_DTableHeader; /* sizeof U32 */
1103 unsigned short newState;
1104 unsigned char symbol;
1105 unsigned char nbBits;
1106 } FSEv06_decode_t; /* size == U32 */
1108 MEM_STATIC void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt)
1110 const void* ptr = dt;
1111 const FSEv06_DTableHeader* const DTableH = (const FSEv06_DTableHeader*)ptr;
1112 DStatePtr->state = BITv06_readBits(bitD, DTableH->tableLog);
1113 BITv06_reloadDStream(bitD);
1114 DStatePtr->table = dt + 1;
1117 MEM_STATIC BYTE FSEv06_peekSymbol(const FSEv06_DState_t* DStatePtr)
1119 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1120 return DInfo.symbol;
1123 MEM_STATIC void FSEv06_updateState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1125 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1126 U32 const nbBits = DInfo.nbBits;
1127 size_t const lowBits = BITv06_readBits(bitD, nbBits);
1128 DStatePtr->state = DInfo.newState + lowBits;
1131 MEM_STATIC BYTE FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1133 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1134 U32 const nbBits = DInfo.nbBits;
1135 BYTE const symbol = DInfo.symbol;
1136 size_t const lowBits = BITv06_readBits(bitD, nbBits);
1138 DStatePtr->state = DInfo.newState + lowBits;
1142 /*! FSEv06_decodeSymbolFast() :
1143 unsafe, only works if no symbol has a probability > 50% */
1144 MEM_STATIC BYTE FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1146 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1147 U32 const nbBits = DInfo.nbBits;
1148 BYTE const symbol = DInfo.symbol;
1149 size_t const lowBits = BITv06_readBitsFast(bitD, nbBits);
1151 DStatePtr->state = DInfo.newState + lowBits;
1157 #ifndef FSEv06_COMMONDEFS_ONLY
1159 /* **************************************************************
1161 ****************************************************************/
1163 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1164 * Increasing memory usage improves compression ratio
1165 * Reduced memory usage can improve speed, due to cache effect
1166 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1167 #define FSEv06_MAX_MEMORY_USAGE 14
1168 #define FSEv06_DEFAULT_MEMORY_USAGE 13
1170 /*!FSEv06_MAX_SYMBOL_VALUE :
1171 * Maximum symbol value authorized.
1172 * Required for proper stack allocation */
1173 #define FSEv06_MAX_SYMBOL_VALUE 255
1176 /* **************************************************************
1177 * template functions type & suffix
1178 ****************************************************************/
1179 #define FSEv06_FUNCTION_TYPE BYTE
1180 #define FSEv06_FUNCTION_EXTENSION
1181 #define FSEv06_DECODE_TYPE FSEv06_decode_t
1184 #endif /* !FSEv06_COMMONDEFS_ONLY */
1187 /* ***************************************************************
1189 *****************************************************************/
1190 #define FSEv06_MAX_TABLELOG (FSEv06_MAX_MEMORY_USAGE-2)
1191 #define FSEv06_MAX_TABLESIZE (1U<<FSEv06_MAX_TABLELOG)
1192 #define FSEv06_MAXTABLESIZE_MASK (FSEv06_MAX_TABLESIZE-1)
1193 #define FSEv06_DEFAULT_TABLELOG (FSEv06_DEFAULT_MEMORY_USAGE-2)
1194 #define FSEv06_MIN_TABLELOG 5
1196 #define FSEv06_TABLELOG_ABSOLUTE_MAX 15
1197 #if FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX
1198 #error "FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX is not supported"
1201 #define FSEv06_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
1204 #if defined (__cplusplus)
1208 #endif /* FSEv06_STATIC_H */
1210 Common functions of New Generation Entropy library
1211 Copyright (C) 2016, Yann Collet.
1213 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1215 Redistribution and use in source and binary forms, with or without
1216 modification, are permitted provided that the following conditions are
1219 * Redistributions of source code must retain the above copyright
1220 notice, this list of conditions and the following disclaimer.
1221 * Redistributions in binary form must reproduce the above
1222 copyright notice, this list of conditions and the following disclaimer
1223 in the documentation and/or other materials provided with the
1226 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1227 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1228 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1229 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1230 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1231 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1232 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1233 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1234 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1235 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1236 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1238 You can contact the author at :
1239 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1240 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1241 *************************************************************************** */
1244 /*-****************************************
1245 * FSE Error Management
1246 ******************************************/
1247 unsigned FSEv06_isError(size_t code) { return ERR_isError(code); }
1249 const char* FSEv06_getErrorName(size_t code) { return ERR_getErrorName(code); }
1252 /* **************************************************************
1253 * HUF Error Management
1254 ****************************************************************/
1255 static unsigned HUFv06_isError(size_t code) { return ERR_isError(code); }
1258 /*-**************************************************************
1259 * FSE NCount encoding-decoding
1260 ****************************************************************/
1261 static short FSEv06_abs(short a) { return a<0 ? -a : a; }
1263 size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1264 const void* headerBuffer, size_t hbSize)
1266 const BYTE* const istart = (const BYTE*) headerBuffer;
1267 const BYTE* const iend = istart + hbSize;
1268 const BYTE* ip = istart;
1274 unsigned charnum = 0;
1277 if (hbSize < 4) return ERROR(srcSize_wrong);
1278 bitStream = MEM_readLE32(ip);
1279 nbBits = (bitStream & 0xF) + FSEv06_MIN_TABLELOG; /* extract tableLog */
1280 if (nbBits > FSEv06_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1283 *tableLogPtr = nbBits;
1284 remaining = (1<<nbBits)+1;
1285 threshold = 1<<nbBits;
1288 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1290 unsigned n0 = charnum;
1291 while ((bitStream & 0xFFFF) == 0xFFFF) {
1295 bitStream = MEM_readLE32(ip) >> bitCount;
1300 while ((bitStream & 3) == 3) {
1305 n0 += bitStream & 3;
1307 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1308 while (charnum < n0) normalizedCounter[charnum++] = 0;
1309 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1312 bitStream = MEM_readLE32(ip) >> bitCount;
1317 { short const max = (short)((2*threshold-1)-remaining);
1320 if ((bitStream & (threshold-1)) < (U32)max) {
1321 count = (short)(bitStream & (threshold-1));
1322 bitCount += nbBits-1;
1324 count = (short)(bitStream & (2*threshold-1));
1325 if (count >= threshold) count -= max;
1329 count--; /* extra accuracy */
1330 remaining -= FSEv06_abs(count);
1331 normalizedCounter[charnum++] = count;
1333 while (remaining < threshold) {
1338 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1342 bitCount -= (int)(8 * (iend - 4 - ip));
1345 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1346 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1347 if (remaining != 1) return ERROR(GENERIC);
1348 *maxSVPtr = charnum-1;
1350 ip += (bitCount+7)>>3;
1351 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1354 /* ******************************************************************
1355 FSE : Finite State Entropy decoder
1356 Copyright (C) 2013-2015, Yann Collet.
1358 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1360 Redistribution and use in source and binary forms, with or without
1361 modification, are permitted provided that the following conditions are
1364 * Redistributions of source code must retain the above copyright
1365 notice, this list of conditions and the following disclaimer.
1366 * Redistributions in binary form must reproduce the above
1367 copyright notice, this list of conditions and the following disclaimer
1368 in the documentation and/or other materials provided with the
1371 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1372 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1373 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1374 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1375 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1376 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1377 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1378 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1379 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1380 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1381 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1383 You can contact the author at :
1384 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1385 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1386 ****************************************************************** */
1389 /* **************************************************************
1390 * Compiler specifics
1391 ****************************************************************/
1392 #ifdef _MSC_VER /* Visual Studio */
1393 # define FORCE_INLINE static __forceinline
1394 # include <intrin.h> /* For Visual 2005 */
1395 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1396 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1398 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1400 # define FORCE_INLINE static inline __attribute__((always_inline))
1402 # define FORCE_INLINE static inline
1405 # define FORCE_INLINE static
1406 # endif /* __STDC_VERSION__ */
1410 /* **************************************************************
1412 ****************************************************************/
1413 #define FSEv06_isError ERR_isError
1414 #define FSEv06_STATIC_ASSERT(c) { enum { FSEv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1417 /* **************************************************************
1419 ****************************************************************/
1420 typedef U32 DTable_max_t[FSEv06_DTABLE_SIZE_U32(FSEv06_MAX_TABLELOG)];
1423 /* **************************************************************
1425 ****************************************************************/
1427 designed to be included
1428 for type-specific functions (template emulation in C)
1429 Objective is to write these functions only once, for improved maintenance
1433 #ifndef FSEv06_FUNCTION_EXTENSION
1434 # error "FSEv06_FUNCTION_EXTENSION must be defined"
1436 #ifndef FSEv06_FUNCTION_TYPE
1437 # error "FSEv06_FUNCTION_TYPE must be defined"
1440 /* Function names */
1441 #define FSEv06_CAT(X,Y) X##Y
1442 #define FSEv06_FUNCTION_NAME(X,Y) FSEv06_CAT(X,Y)
1443 #define FSEv06_TYPE_NAME(X,Y) FSEv06_CAT(X,Y)
1446 /* Function templates */
1447 FSEv06_DTable* FSEv06_createDTable (unsigned tableLog)
1449 if (tableLog > FSEv06_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv06_TABLELOG_ABSOLUTE_MAX;
1450 return (FSEv06_DTable*)malloc( FSEv06_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1453 void FSEv06_freeDTable (FSEv06_DTable* dt)
1458 size_t FSEv06_buildDTable(FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1460 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1461 FSEv06_DECODE_TYPE* const tableDecode = (FSEv06_DECODE_TYPE*) (tdPtr);
1462 U16 symbolNext[FSEv06_MAX_SYMBOL_VALUE+1];
1464 U32 const maxSV1 = maxSymbolValue + 1;
1465 U32 const tableSize = 1 << tableLog;
1466 U32 highThreshold = tableSize-1;
1469 if (maxSymbolValue > FSEv06_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1470 if (tableLog > FSEv06_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1472 /* Init, lay down lowprob symbols */
1473 { FSEv06_DTableHeader DTableH;
1474 DTableH.tableLog = (U16)tableLog;
1475 DTableH.fastMode = 1;
1476 { S16 const largeLimit= (S16)(1 << (tableLog-1));
1478 for (s=0; s<maxSV1; s++) {
1479 if (normalizedCounter[s]==-1) {
1480 tableDecode[highThreshold--].symbol = (FSEv06_FUNCTION_TYPE)s;
1483 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1484 symbolNext[s] = normalizedCounter[s];
1486 memcpy(dt, &DTableH, sizeof(DTableH));
1489 /* Spread symbols */
1490 { U32 const tableMask = tableSize-1;
1491 U32 const step = FSEv06_TABLESTEP(tableSize);
1492 U32 s, position = 0;
1493 for (s=0; s<maxSV1; s++) {
1495 for (i=0; i<normalizedCounter[s]; i++) {
1496 tableDecode[position].symbol = (FSEv06_FUNCTION_TYPE)s;
1497 position = (position + step) & tableMask;
1498 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1501 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1504 /* Build Decoding table */
1506 for (u=0; u<tableSize; u++) {
1507 FSEv06_FUNCTION_TYPE const symbol = (FSEv06_FUNCTION_TYPE)(tableDecode[u].symbol);
1508 U16 nextState = symbolNext[symbol]++;
1509 tableDecode[u].nbBits = (BYTE) (tableLog - BITv06_highbit32 ((U32)nextState) );
1510 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1518 #ifndef FSEv06_COMMONDEFS_ONLY
1520 /*-*******************************************************
1521 * Decompression (Byte symbols)
1522 *********************************************************/
1523 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, BYTE symbolValue)
1526 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr;
1527 void* dPtr = dt + 1;
1528 FSEv06_decode_t* const cell = (FSEv06_decode_t*)dPtr;
1530 DTableH->tableLog = 0;
1531 DTableH->fastMode = 0;
1534 cell->symbol = symbolValue;
1541 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits)
1544 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr;
1545 void* dPtr = dt + 1;
1546 FSEv06_decode_t* const dinfo = (FSEv06_decode_t*)dPtr;
1547 const unsigned tableSize = 1 << nbBits;
1548 const unsigned tableMask = tableSize - 1;
1549 const unsigned maxSV1 = tableMask+1;
1553 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1555 /* Build Decoding Table */
1556 DTableH->tableLog = (U16)nbBits;
1557 DTableH->fastMode = 1;
1558 for (s=0; s<maxSV1; s++) {
1559 dinfo[s].newState = 0;
1560 dinfo[s].symbol = (BYTE)s;
1561 dinfo[s].nbBits = (BYTE)nbBits;
1567 FORCE_INLINE size_t FSEv06_decompress_usingDTable_generic(
1568 void* dst, size_t maxDstSize,
1569 const void* cSrc, size_t cSrcSize,
1570 const FSEv06_DTable* dt, const unsigned fast)
1572 BYTE* const ostart = (BYTE*) dst;
1574 BYTE* const omax = op + maxDstSize;
1575 BYTE* const olimit = omax-3;
1577 BITv06_DStream_t bitD;
1578 FSEv06_DState_t state1;
1579 FSEv06_DState_t state2;
1582 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1583 if (FSEv06_isError(errorCode)) return errorCode; }
1585 FSEv06_initDState(&state1, &bitD, dt);
1586 FSEv06_initDState(&state2, &bitD, dt);
1588 #define FSEv06_GETSYMBOL(statePtr) fast ? FSEv06_decodeSymbolFast(statePtr, &bitD) : FSEv06_decodeSymbol(statePtr, &bitD)
1590 /* 4 symbols per loop */
1591 for ( ; (BITv06_reloadDStream(&bitD)==BITv06_DStream_unfinished) && (op<olimit) ; op+=4) {
1592 op[0] = FSEv06_GETSYMBOL(&state1);
1594 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1595 BITv06_reloadDStream(&bitD);
1597 op[1] = FSEv06_GETSYMBOL(&state2);
1599 if (FSEv06_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1600 { if (BITv06_reloadDStream(&bitD) > BITv06_DStream_unfinished) { op+=2; break; } }
1602 op[2] = FSEv06_GETSYMBOL(&state1);
1604 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1605 BITv06_reloadDStream(&bitD);
1607 op[3] = FSEv06_GETSYMBOL(&state2);
1611 /* note : BITv06_reloadDStream(&bitD) >= FSEv06_DStream_partiallyFilled; Ends at exactly BITv06_DStream_completed */
1613 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1615 *op++ = FSEv06_GETSYMBOL(&state1);
1617 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) {
1618 *op++ = FSEv06_GETSYMBOL(&state2);
1622 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1624 *op++ = FSEv06_GETSYMBOL(&state2);
1626 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) {
1627 *op++ = FSEv06_GETSYMBOL(&state1);
1635 size_t FSEv06_decompress_usingDTable(void* dst, size_t originalSize,
1636 const void* cSrc, size_t cSrcSize,
1637 const FSEv06_DTable* dt)
1639 const void* ptr = dt;
1640 const FSEv06_DTableHeader* DTableH = (const FSEv06_DTableHeader*)ptr;
1641 const U32 fastMode = DTableH->fastMode;
1643 /* select fast mode (static) */
1644 if (fastMode) return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1645 return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1649 size_t FSEv06_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1651 const BYTE* const istart = (const BYTE*)cSrc;
1652 const BYTE* ip = istart;
1653 short counting[FSEv06_MAX_SYMBOL_VALUE+1];
1654 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1656 unsigned maxSymbolValue = FSEv06_MAX_SYMBOL_VALUE;
1658 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1660 /* normal FSE decoding mode */
1661 { size_t const NCountLength = FSEv06_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1662 if (FSEv06_isError(NCountLength)) return NCountLength;
1663 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1665 cSrcSize -= NCountLength;
1668 { size_t const errorCode = FSEv06_buildDTable (dt, counting, maxSymbolValue, tableLog);
1669 if (FSEv06_isError(errorCode)) return errorCode; }
1671 return FSEv06_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */
1676 #endif /* FSEv06_COMMONDEFS_ONLY */
1677 /* ******************************************************************
1678 Huffman coder, part of New Generation Entropy library
1680 Copyright (C) 2013-2016, Yann Collet.
1682 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1684 Redistribution and use in source and binary forms, with or without
1685 modification, are permitted provided that the following conditions are
1688 * Redistributions of source code must retain the above copyright
1689 notice, this list of conditions and the following disclaimer.
1690 * Redistributions in binary form must reproduce the above
1691 copyright notice, this list of conditions and the following disclaimer
1692 in the documentation and/or other materials provided with the
1695 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1696 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1697 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1698 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1699 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1700 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1701 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1702 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1703 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1704 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1705 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1707 You can contact the author at :
1708 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1709 ****************************************************************** */
1713 #if defined (__cplusplus)
1718 /* ****************************************
1719 * HUF simple functions
1720 ******************************************/
1721 size_t HUFv06_decompress(void* dst, size_t dstSize,
1722 const void* cSrc, size_t cSrcSize);
1724 HUFv06_decompress() :
1725 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1726 into already allocated destination buffer 'dst', of size 'dstSize'.
1727 `dstSize` : must be the **exact** size of original (uncompressed) data.
1728 Note : in contrast with FSE, HUFv06_decompress can regenerate
1729 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1730 because it knows size to regenerate.
1731 @return : size of regenerated data (== dstSize)
1732 or an error code, which can be tested using HUFv06_isError()
1736 /* ****************************************
1738 ******************************************/
1739 size_t HUFv06_compressBound(size_t size); /**< maximum compressed size */
1742 #if defined (__cplusplus)
1746 #endif /* HUFv06_H */
1747 /* ******************************************************************
1748 Huffman codec, part of New Generation Entropy library
1749 header file, for static linking only
1750 Copyright (C) 2013-2016, Yann Collet
1752 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1754 Redistribution and use in source and binary forms, with or without
1755 modification, are permitted provided that the following conditions are
1758 * Redistributions of source code must retain the above copyright
1759 notice, this list of conditions and the following disclaimer.
1760 * Redistributions in binary form must reproduce the above
1761 copyright notice, this list of conditions and the following disclaimer
1762 in the documentation and/or other materials provided with the
1765 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1766 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1767 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1768 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1769 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1770 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1771 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1772 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1773 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1774 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1775 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1777 You can contact the author at :
1778 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1779 ****************************************************************** */
1780 #ifndef HUFv06_STATIC_H
1781 #define HUFv06_STATIC_H
1783 #if defined (__cplusplus)
1788 /* ****************************************
1790 ******************************************/
1791 /* HUF buffer bounds */
1792 #define HUFv06_CTABLEBOUND 129
1793 #define HUFv06_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1794 #define HUFv06_COMPRESSBOUND(size) (HUFv06_CTABLEBOUND + HUFv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
1796 /* static allocation of HUF's DTable */
1797 #define HUFv06_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1798 #define HUFv06_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1799 unsigned short DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1800 #define HUFv06_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1801 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1802 #define HUFv06_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1803 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1806 /* ****************************************
1807 * Advanced decompression functions
1808 ******************************************/
1809 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1810 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1815 HUFv06_decompress() does the following:
1816 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1817 2. build Huffman table from save, using HUFv06_readDTableXn()
1818 3. decode 1 or 4 segments in parallel using HUFv06_decompressSXn_usingDTable
1820 size_t HUFv06_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1821 size_t HUFv06_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1823 size_t HUFv06_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1824 size_t HUFv06_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1827 /* single stream variants */
1828 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1829 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1831 size_t HUFv06_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1832 size_t HUFv06_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1836 /* **************************************************************
1838 ****************************************************************/
1839 #define HUFv06_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv06_MAX_TABLELOG. Beyond that value, code does not work */
1840 #define HUFv06_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv06_ABSOLUTEMAX_TABLELOG */
1841 #define HUFv06_DEFAULT_TABLELOG HUFv06_MAX_TABLELOG /* tableLog by default, when not specified */
1842 #define HUFv06_MAX_SYMBOL_VALUE 255
1843 #if (HUFv06_MAX_TABLELOG > HUFv06_ABSOLUTEMAX_TABLELOG)
1844 # error "HUFv06_MAX_TABLELOG is too large !"
1849 /*! HUFv06_readStats() :
1850 Read compact Huffman tree, saved by HUFv06_writeCTable().
1851 `huffWeight` is destination buffer.
1852 @return : size read from `src`
1854 MEM_STATIC size_t HUFv06_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1855 U32* nbSymbolsPtr, U32* tableLogPtr,
1856 const void* src, size_t srcSize)
1859 const BYTE* ip = (const BYTE*) src;
1863 if (!srcSize) return ERROR(srcSize_wrong);
1865 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1867 if (iSize >= 128) { /* special header */
1868 if (iSize >= (242)) { /* RLE */
1869 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1870 oSize = l[iSize-242];
1871 memset(huffWeight, 1, hwSize);
1874 else { /* Incompressible */
1875 oSize = iSize - 127;
1876 iSize = ((oSize+1)/2);
1877 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1878 if (oSize >= hwSize) return ERROR(corruption_detected);
1881 for (n=0; n<oSize; n+=2) {
1882 huffWeight[n] = ip[n/2] >> 4;
1883 huffWeight[n+1] = ip[n/2] & 15;
1885 else { /* header compressed with FSE (normal case) */
1886 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1887 oSize = FSEv06_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1888 if (FSEv06_isError(oSize)) return oSize;
1891 /* collect weight stats */
1892 memset(rankStats, 0, (HUFv06_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1894 { U32 n; for (n=0; n<oSize; n++) {
1895 if (huffWeight[n] >= HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1896 rankStats[huffWeight[n]]++;
1897 weightTotal += (1 << huffWeight[n]) >> 1;
1899 if (weightTotal == 0) return ERROR(corruption_detected);
1901 /* get last non-null symbol weight (implied, total must be 2^n) */
1902 { U32 const tableLog = BITv06_highbit32(weightTotal) + 1;
1903 if (tableLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1904 *tableLogPtr = tableLog;
1905 /* determine last weight */
1906 { U32 const total = 1 << tableLog;
1907 U32 const rest = total - weightTotal;
1908 U32 const verif = 1 << BITv06_highbit32(rest);
1909 U32 const lastWeight = BITv06_highbit32(rest) + 1;
1910 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1911 huffWeight[oSize] = (BYTE)lastWeight;
1912 rankStats[lastWeight]++;
1915 /* check tree construction validity */
1916 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1919 *nbSymbolsPtr = (U32)(oSize+1);
1925 #if defined (__cplusplus)
1929 #endif /* HUFv06_STATIC_H */
1930 /* ******************************************************************
1931 Huffman decoder, part of New Generation Entropy library
1932 Copyright (C) 2013-2016, Yann Collet.
1934 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1936 Redistribution and use in source and binary forms, with or without
1937 modification, are permitted provided that the following conditions are
1940 * Redistributions of source code must retain the above copyright
1941 notice, this list of conditions and the following disclaimer.
1942 * Redistributions in binary form must reproduce the above
1943 copyright notice, this list of conditions and the following disclaimer
1944 in the documentation and/or other materials provided with the
1947 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1948 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1949 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1950 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1951 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1952 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1953 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1954 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1955 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1956 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1957 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1959 You can contact the author at :
1960 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1961 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1962 ****************************************************************** */
1964 /* **************************************************************
1965 * Compiler specifics
1966 ****************************************************************/
1967 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1968 /* inline is defined */
1969 #elif defined(_MSC_VER)
1970 # define inline __inline
1972 # define inline /* disable inline */
1976 #ifdef _MSC_VER /* Visual Studio */
1977 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1982 /* **************************************************************
1984 ****************************************************************/
1985 #define HUFv06_STATIC_ASSERT(c) { enum { HUFv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1989 /* *******************************************************
1990 * HUF : Huffman block decompression
1991 *********************************************************/
1992 typedef struct { BYTE byte; BYTE nbBits; } HUFv06_DEltX2; /* single-symbol decoding */
1994 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv06_DEltX4; /* double-symbols decoding */
1996 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
2000 /*-***************************/
2001 /* single-symbol decoding */
2002 /*-***************************/
2004 size_t HUFv06_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
2006 BYTE huffWeight[HUFv06_MAX_SYMBOL_VALUE + 1];
2007 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
2013 void* const dtPtr = DTable + 1;
2014 HUFv06_DEltX2* const dt = (HUFv06_DEltX2*)dtPtr;
2016 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
2017 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
2019 iSize = HUFv06_readStats(huffWeight, HUFv06_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
2020 if (HUFv06_isError(iSize)) return iSize;
2023 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
2024 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
2028 for (n=1; n<tableLog+1; n++) {
2029 U32 current = nextRankStart;
2030 nextRankStart += (rankVal[n] << (n-1));
2031 rankVal[n] = current;
2035 for (n=0; n<nbSymbols; n++) {
2036 const U32 w = huffWeight[n];
2037 const U32 length = (1 << w) >> 1;
2040 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
2041 for (i = rankVal[w]; i < rankVal[w] + length; i++)
2043 rankVal[w] += length;
2050 static BYTE HUFv06_decodeSymbolX2(BITv06_DStream_t* Dstream, const HUFv06_DEltX2* dt, const U32 dtLog)
2052 const size_t val = BITv06_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
2053 const BYTE c = dt[val].byte;
2054 BITv06_skipBits(Dstream, dt[val].nbBits);
2058 #define HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
2059 *ptr++ = HUFv06_decodeSymbolX2(DStreamPtr, dt, dtLog)
2061 #define HUFv06_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
2062 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2063 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2065 #define HUFv06_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
2067 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2069 static inline size_t HUFv06_decodeStreamX2(BYTE* p, BITv06_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv06_DEltX2* const dt, const U32 dtLog)
2071 BYTE* const pStart = p;
2073 /* up to 4 symbols at a time */
2074 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-4)) {
2075 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr);
2076 HUFv06_DECODE_SYMBOLX2_1(p, bitDPtr);
2077 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr);
2078 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2081 /* closer to the end */
2082 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd))
2083 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2085 /* no more data to retrieve from bitstream, hence no need to reload */
2087 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2092 size_t HUFv06_decompress1X2_usingDTable(
2093 void* dst, size_t dstSize,
2094 const void* cSrc, size_t cSrcSize,
2097 BYTE* op = (BYTE*)dst;
2098 BYTE* const oend = op + dstSize;
2099 const U32 dtLog = DTable[0];
2100 const void* dtPtr = DTable;
2101 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr)+1;
2102 BITv06_DStream_t bitD;
2104 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize);
2105 if (HUFv06_isError(errorCode)) return errorCode; }
2107 HUFv06_decodeStreamX2(op, &bitD, oend, dt, dtLog);
2110 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected);
2115 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2117 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG);
2118 const BYTE* ip = (const BYTE*) cSrc;
2120 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize);
2121 if (HUFv06_isError(errorCode)) return errorCode;
2122 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2124 cSrcSize -= errorCode;
2126 return HUFv06_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2130 size_t HUFv06_decompress4X2_usingDTable(
2131 void* dst, size_t dstSize,
2132 const void* cSrc, size_t cSrcSize,
2136 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2138 { const BYTE* const istart = (const BYTE*) cSrc;
2139 BYTE* const ostart = (BYTE*) dst;
2140 BYTE* const oend = ostart + dstSize;
2141 const void* const dtPtr = DTable;
2142 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr) +1;
2143 const U32 dtLog = DTable[0];
2147 BITv06_DStream_t bitD1;
2148 BITv06_DStream_t bitD2;
2149 BITv06_DStream_t bitD3;
2150 BITv06_DStream_t bitD4;
2151 const size_t length1 = MEM_readLE16(istart);
2152 const size_t length2 = MEM_readLE16(istart+2);
2153 const size_t length3 = MEM_readLE16(istart+4);
2155 const BYTE* const istart1 = istart + 6; /* jumpTable */
2156 const BYTE* const istart2 = istart1 + length1;
2157 const BYTE* const istart3 = istart2 + length2;
2158 const BYTE* const istart4 = istart3 + length3;
2159 const size_t segmentSize = (dstSize+3) / 4;
2160 BYTE* const opStart2 = ostart + segmentSize;
2161 BYTE* const opStart3 = opStart2 + segmentSize;
2162 BYTE* const opStart4 = opStart3 + segmentSize;
2164 BYTE* op2 = opStart2;
2165 BYTE* op3 = opStart3;
2166 BYTE* op4 = opStart4;
2169 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2170 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2171 errorCode = BITv06_initDStream(&bitD1, istart1, length1);
2172 if (HUFv06_isError(errorCode)) return errorCode;
2173 errorCode = BITv06_initDStream(&bitD2, istart2, length2);
2174 if (HUFv06_isError(errorCode)) return errorCode;
2175 errorCode = BITv06_initDStream(&bitD3, istart3, length3);
2176 if (HUFv06_isError(errorCode)) return errorCode;
2177 errorCode = BITv06_initDStream(&bitD4, istart4, length4);
2178 if (HUFv06_isError(errorCode)) return errorCode;
2180 /* 16-32 symbols per loop (4-8 symbols per stream) */
2181 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2182 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) {
2183 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1);
2184 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2);
2185 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3);
2186 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4);
2187 HUFv06_DECODE_SYMBOLX2_1(op1, &bitD1);
2188 HUFv06_DECODE_SYMBOLX2_1(op2, &bitD2);
2189 HUFv06_DECODE_SYMBOLX2_1(op3, &bitD3);
2190 HUFv06_DECODE_SYMBOLX2_1(op4, &bitD4);
2191 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1);
2192 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2);
2193 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3);
2194 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4);
2195 HUFv06_DECODE_SYMBOLX2_0(op1, &bitD1);
2196 HUFv06_DECODE_SYMBOLX2_0(op2, &bitD2);
2197 HUFv06_DECODE_SYMBOLX2_0(op3, &bitD3);
2198 HUFv06_DECODE_SYMBOLX2_0(op4, &bitD4);
2199 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2202 /* check corruption */
2203 if (op1 > opStart2) return ERROR(corruption_detected);
2204 if (op2 > opStart3) return ERROR(corruption_detected);
2205 if (op3 > opStart4) return ERROR(corruption_detected);
2206 /* note : op4 supposed already verified within main loop */
2208 /* finish bitStreams one by one */
2209 HUFv06_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2210 HUFv06_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2211 HUFv06_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2212 HUFv06_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2215 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4);
2216 if (!endSignal) return ERROR(corruption_detected);
2224 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2226 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG);
2227 const BYTE* ip = (const BYTE*) cSrc;
2229 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize);
2230 if (HUFv06_isError(errorCode)) return errorCode;
2231 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2233 cSrcSize -= errorCode;
2235 return HUFv06_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2239 /* *************************/
2240 /* double-symbols decoding */
2241 /* *************************/
2243 static void HUFv06_fillDTableX4Level2(HUFv06_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2244 const U32* rankValOrigin, const int minWeight,
2245 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2246 U32 nbBitsBaseline, U16 baseSeq)
2249 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2251 /* get pre-calculated rankVal */
2252 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2254 /* fill skipped values */
2256 U32 i, skipSize = rankVal[minWeight];
2257 MEM_writeLE16(&(DElt.sequence), baseSeq);
2258 DElt.nbBits = (BYTE)(consumed);
2260 for (i = 0; i < skipSize; i++)
2265 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2266 const U32 symbol = sortedSymbols[s].symbol;
2267 const U32 weight = sortedSymbols[s].weight;
2268 const U32 nbBits = nbBitsBaseline - weight;
2269 const U32 length = 1 << (sizeLog-nbBits);
2270 const U32 start = rankVal[weight];
2272 const U32 end = start + length;
2274 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2275 DElt.nbBits = (BYTE)(nbBits + consumed);
2277 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2279 rankVal[weight] += length;
2283 typedef U32 rankVal_t[HUFv06_ABSOLUTEMAX_TABLELOG][HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2285 static void HUFv06_fillDTableX4(HUFv06_DEltX4* DTable, const U32 targetLog,
2286 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2287 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2288 const U32 nbBitsBaseline)
2290 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2291 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2292 const U32 minBits = nbBitsBaseline - maxWeight;
2295 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2298 for (s=0; s<sortedListSize; s++) {
2299 const U16 symbol = sortedList[s].symbol;
2300 const U32 weight = sortedList[s].weight;
2301 const U32 nbBits = nbBitsBaseline - weight;
2302 const U32 start = rankVal[weight];
2303 const U32 length = 1 << (targetLog-nbBits);
2305 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2307 int minWeight = nbBits + scaleLog;
2308 if (minWeight < 1) minWeight = 1;
2309 sortedRank = rankStart[minWeight];
2310 HUFv06_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2311 rankValOrigin[nbBits], minWeight,
2312 sortedList+sortedRank, sortedListSize-sortedRank,
2313 nbBitsBaseline, symbol);
2316 MEM_writeLE16(&(DElt.sequence), symbol);
2317 DElt.nbBits = (BYTE)(nbBits);
2320 const U32 end = start + length;
2321 for (u = start; u < end; u++) DTable[u] = DElt;
2323 rankVal[weight] += length;
2327 size_t HUFv06_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2329 BYTE weightList[HUFv06_MAX_SYMBOL_VALUE + 1];
2330 sortedSymbol_t sortedSymbol[HUFv06_MAX_SYMBOL_VALUE + 1];
2331 U32 rankStats[HUFv06_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2332 U32 rankStart0[HUFv06_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2333 U32* const rankStart = rankStart0+1;
2335 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2336 const U32 memLog = DTable[0];
2338 void* dtPtr = DTable;
2339 HUFv06_DEltX4* const dt = ((HUFv06_DEltX4*)dtPtr) + 1;
2341 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
2342 if (memLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2343 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2345 iSize = HUFv06_readStats(weightList, HUFv06_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2346 if (HUFv06_isError(iSize)) return iSize;
2349 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2351 /* find maxWeight */
2352 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2354 /* Get start index of each weight */
2355 { U32 w, nextRankStart = 0;
2356 for (w=1; w<maxW+1; w++) {
2357 U32 current = nextRankStart;
2358 nextRankStart += rankStats[w];
2359 rankStart[w] = current;
2361 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2362 sizeOfSort = nextRankStart;
2365 /* sort symbols by weight */
2367 for (s=0; s<nbSymbols; s++) {
2368 U32 const w = weightList[s];
2369 U32 const r = rankStart[w]++;
2370 sortedSymbol[r].symbol = (BYTE)s;
2371 sortedSymbol[r].weight = (BYTE)w;
2373 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2377 { U32* const rankVal0 = rankVal[0];
2378 { int const rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2379 U32 nextRankVal = 0;
2381 for (w=1; w<maxW+1; w++) {
2382 U32 current = nextRankVal;
2383 nextRankVal += rankStats[w] << (w+rescale);
2384 rankVal0[w] = current;
2386 { U32 const minBits = tableLog+1 - maxW;
2388 for (consumed = minBits; consumed < memLog - minBits + 1; consumed++) {
2389 U32* const rankValPtr = rankVal[consumed];
2391 for (w = 1; w < maxW+1; w++) {
2392 rankValPtr[w] = rankVal0[w] >> consumed;
2395 HUFv06_fillDTableX4(dt, memLog,
2396 sortedSymbol, sizeOfSort,
2397 rankStart0, rankVal, maxW,
2404 static U32 HUFv06_decodeSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog)
2406 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2407 memcpy(op, dt+val, 2);
2408 BITv06_skipBits(DStream, dt[val].nbBits);
2409 return dt[val].length;
2412 static U32 HUFv06_decodeLastSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog)
2414 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2415 memcpy(op, dt+val, 1);
2416 if (dt[val].length==1) BITv06_skipBits(DStream, dt[val].nbBits);
2418 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2419 BITv06_skipBits(DStream, dt[val].nbBits);
2420 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2421 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 */
2427 #define HUFv06_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2428 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2430 #define HUFv06_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2431 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2432 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2434 #define HUFv06_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2436 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2438 static inline size_t HUFv06_decodeStreamX4(BYTE* p, BITv06_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv06_DEltX4* const dt, const U32 dtLog)
2440 BYTE* const pStart = p;
2442 /* up to 8 symbols at a time */
2443 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd-7)) {
2444 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr);
2445 HUFv06_DECODE_SYMBOLX4_1(p, bitDPtr);
2446 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr);
2447 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr);
2450 /* closer to the end */
2451 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-2))
2452 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr);
2455 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2458 p += HUFv06_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2464 size_t HUFv06_decompress1X4_usingDTable(
2465 void* dst, size_t dstSize,
2466 const void* cSrc, size_t cSrcSize,
2469 const BYTE* const istart = (const BYTE*) cSrc;
2470 BYTE* const ostart = (BYTE*) dst;
2471 BYTE* const oend = ostart + dstSize;
2473 const U32 dtLog = DTable[0];
2474 const void* const dtPtr = DTable;
2475 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1;
2478 BITv06_DStream_t bitD;
2479 { size_t const errorCode = BITv06_initDStream(&bitD, istart, cSrcSize);
2480 if (HUFv06_isError(errorCode)) return errorCode; }
2483 HUFv06_decodeStreamX4(ostart, &bitD, oend, dt, dtLog);
2486 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected);
2492 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2494 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG);
2495 const BYTE* ip = (const BYTE*) cSrc;
2497 size_t const hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize);
2498 if (HUFv06_isError(hSize)) return hSize;
2499 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2503 return HUFv06_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2506 size_t HUFv06_decompress4X4_usingDTable(
2507 void* dst, size_t dstSize,
2508 const void* cSrc, size_t cSrcSize,
2511 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2513 { const BYTE* const istart = (const BYTE*) cSrc;
2514 BYTE* const ostart = (BYTE*) dst;
2515 BYTE* const oend = ostart + dstSize;
2516 const void* const dtPtr = DTable;
2517 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1;
2518 const U32 dtLog = DTable[0];
2522 BITv06_DStream_t bitD1;
2523 BITv06_DStream_t bitD2;
2524 BITv06_DStream_t bitD3;
2525 BITv06_DStream_t bitD4;
2526 const size_t length1 = MEM_readLE16(istart);
2527 const size_t length2 = MEM_readLE16(istart+2);
2528 const size_t length3 = MEM_readLE16(istart+4);
2530 const BYTE* const istart1 = istart + 6; /* jumpTable */
2531 const BYTE* const istart2 = istart1 + length1;
2532 const BYTE* const istart3 = istart2 + length2;
2533 const BYTE* const istart4 = istart3 + length3;
2534 const size_t segmentSize = (dstSize+3) / 4;
2535 BYTE* const opStart2 = ostart + segmentSize;
2536 BYTE* const opStart3 = opStart2 + segmentSize;
2537 BYTE* const opStart4 = opStart3 + segmentSize;
2539 BYTE* op2 = opStart2;
2540 BYTE* op3 = opStart3;
2541 BYTE* op4 = opStart4;
2544 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2545 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2546 errorCode = BITv06_initDStream(&bitD1, istart1, length1);
2547 if (HUFv06_isError(errorCode)) return errorCode;
2548 errorCode = BITv06_initDStream(&bitD2, istart2, length2);
2549 if (HUFv06_isError(errorCode)) return errorCode;
2550 errorCode = BITv06_initDStream(&bitD3, istart3, length3);
2551 if (HUFv06_isError(errorCode)) return errorCode;
2552 errorCode = BITv06_initDStream(&bitD4, istart4, length4);
2553 if (HUFv06_isError(errorCode)) return errorCode;
2555 /* 16-32 symbols per loop (4-8 symbols per stream) */
2556 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2557 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) {
2558 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1);
2559 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2);
2560 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3);
2561 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4);
2562 HUFv06_DECODE_SYMBOLX4_1(op1, &bitD1);
2563 HUFv06_DECODE_SYMBOLX4_1(op2, &bitD2);
2564 HUFv06_DECODE_SYMBOLX4_1(op3, &bitD3);
2565 HUFv06_DECODE_SYMBOLX4_1(op4, &bitD4);
2566 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1);
2567 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2);
2568 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3);
2569 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4);
2570 HUFv06_DECODE_SYMBOLX4_0(op1, &bitD1);
2571 HUFv06_DECODE_SYMBOLX4_0(op2, &bitD2);
2572 HUFv06_DECODE_SYMBOLX4_0(op3, &bitD3);
2573 HUFv06_DECODE_SYMBOLX4_0(op4, &bitD4);
2575 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2578 /* check corruption */
2579 if (op1 > opStart2) return ERROR(corruption_detected);
2580 if (op2 > opStart3) return ERROR(corruption_detected);
2581 if (op3 > opStart4) return ERROR(corruption_detected);
2582 /* note : op4 supposed already verified within main loop */
2584 /* finish bitStreams one by one */
2585 HUFv06_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2586 HUFv06_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2587 HUFv06_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2588 HUFv06_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2591 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4);
2592 if (!endSignal) return ERROR(corruption_detected);
2600 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2602 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG);
2603 const BYTE* ip = (const BYTE*) cSrc;
2605 size_t hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize);
2606 if (HUFv06_isError(hSize)) return hSize;
2607 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2611 return HUFv06_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2617 /* ********************************/
2618 /* Generic decompression selector */
2619 /* ********************************/
2621 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2622 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2624 /* single, double, quad */
2625 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2626 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2627 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2628 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2629 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2630 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2631 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2632 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2633 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2634 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2635 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2636 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2637 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2638 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2639 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2640 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2643 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2645 size_t HUFv06_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2647 static const decompressionAlgo decompress[3] = { HUFv06_decompress4X2, HUFv06_decompress4X4, NULL };
2648 U32 Dtime[3]; /* decompression time estimation */
2650 /* validation checks */
2651 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2652 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2653 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2654 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2656 /* decoder timing evaluation */
2657 { U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2658 U32 const D256 = (U32)(dstSize >> 8);
2659 U32 n; for (n=0; n<3; n++)
2660 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2663 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2666 if (Dtime[1] < Dtime[0]) algoNb = 1;
2667 // if (Dtime[2] < Dtime[algoNb]) algoNb = 2; /* current speed of HUFv06_decompress4X6 is not good */
2668 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2671 //return HUFv06_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2672 //return HUFv06_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2673 //return HUFv06_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2676 Common functions of Zstd compression library
2677 Copyright (C) 2015-2016, Yann Collet.
2679 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2681 Redistribution and use in source and binary forms, with or without
2682 modification, are permitted provided that the following conditions are
2684 * Redistributions of source code must retain the above copyright
2685 notice, this list of conditions and the following disclaimer.
2686 * Redistributions in binary form must reproduce the above
2687 copyright notice, this list of conditions and the following disclaimer
2688 in the documentation and/or other materials provided with the
2690 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2691 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2692 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2693 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2694 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2695 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2696 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2697 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2698 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2699 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2700 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2702 You can contact the author at :
2703 - zstd homepage : http://www.zstd.net/
2707 /*-****************************************
2709 ******************************************/
2711 /*-****************************************
2712 * ZSTD Error Management
2713 ******************************************/
2714 /*! ZSTDv06_isError() :
2715 * tells if a return value is an error code */
2716 unsigned ZSTDv06_isError(size_t code) { return ERR_isError(code); }
2718 /*! ZSTDv06_getErrorName() :
2719 * provides error code string from function result (useful for debugging) */
2720 const char* ZSTDv06_getErrorName(size_t code) { return ERR_getErrorName(code); }
2723 /* **************************************************************
2724 * ZBUFF Error Management
2725 ****************************************************************/
2726 unsigned ZBUFFv06_isError(size_t errorCode) { return ERR_isError(errorCode); }
2728 const char* ZBUFFv06_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2730 zstd - standard compression library
2731 Copyright (C) 2014-2016, Yann Collet.
2733 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2735 Redistribution and use in source and binary forms, with or without
2736 modification, are permitted provided that the following conditions are
2738 * Redistributions of source code must retain the above copyright
2739 notice, this list of conditions and the following disclaimer.
2740 * Redistributions in binary form must reproduce the above
2741 copyright notice, this list of conditions and the following disclaimer
2742 in the documentation and/or other materials provided with the
2744 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2745 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2746 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2747 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2748 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2749 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2750 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2751 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2752 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2753 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2754 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2756 You can contact the author at :
2757 - zstd homepage : http://www.zstd.net
2760 /* ***************************************************************
2762 *****************************************************************/
2765 * Select how default decompression function ZSTDv06_decompress() will allocate memory,
2766 * in memory stack (0), or in memory heap (1, requires malloc())
2768 #ifndef ZSTDv06_HEAPMODE
2769 # define ZSTDv06_HEAPMODE 1
2774 /*-*******************************************************
2775 * Compiler specifics
2776 *********************************************************/
2777 #ifdef _MSC_VER /* Visual Studio */
2778 # include <intrin.h> /* For Visual 2005 */
2779 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2780 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2784 /*-*************************************
2786 ***************************************/
2787 #define ZSTDv06_isError ERR_isError /* for inlining */
2788 #define FSEv06_isError ERR_isError
2789 #define HUFv06_isError ERR_isError
2792 /*_*******************************************************
2794 **********************************************************/
2795 static void ZSTDv06_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2798 /*-*************************************************************
2799 * Context management
2800 ***************************************************************/
2801 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2802 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTDv06_dStage;
2804 struct ZSTDv06_DCtx_s
2806 FSEv06_DTable LLTable[FSEv06_DTABLE_SIZE_U32(LLFSELog)];
2807 FSEv06_DTable OffTable[FSEv06_DTABLE_SIZE_U32(OffFSELog)];
2808 FSEv06_DTable MLTable[FSEv06_DTABLE_SIZE_U32(MLFSELog)];
2809 unsigned hufTableX4[HUFv06_DTABLE_SIZE(HufLog)];
2810 const void* previousDstEnd;
2813 const void* dictEnd;
2816 ZSTDv06_frameParams fParams;
2817 blockType_t bType; /* used in ZSTDv06_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2818 ZSTDv06_dStage stage;
2819 U32 flagRepeatTable;
2822 BYTE litBuffer[ZSTDv06_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];
2823 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX];
2824 }; /* typedef'd to ZSTDv06_DCtx within "zstd_static.h" */
2826 size_t ZSTDv06_sizeofDCtx (void); /* Hidden declaration */
2827 size_t ZSTDv06_sizeofDCtx (void) { return sizeof(ZSTDv06_DCtx); }
2829 size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx)
2831 dctx->expected = ZSTDv06_frameHeaderSize_min;
2832 dctx->stage = ZSTDds_getFrameHeaderSize;
2833 dctx->previousDstEnd = NULL;
2836 dctx->dictEnd = NULL;
2837 dctx->hufTableX4[0] = HufLog;
2838 dctx->flagRepeatTable = 0;
2842 ZSTDv06_DCtx* ZSTDv06_createDCtx(void)
2844 ZSTDv06_DCtx* dctx = (ZSTDv06_DCtx*)malloc(sizeof(ZSTDv06_DCtx));
2845 if (dctx==NULL) return NULL;
2846 ZSTDv06_decompressBegin(dctx);
2850 size_t ZSTDv06_freeDCtx(ZSTDv06_DCtx* dctx)
2853 return 0; /* reserved as a potential error code in the future */
2856 void ZSTDv06_copyDCtx(ZSTDv06_DCtx* dstDCtx, const ZSTDv06_DCtx* srcDCtx)
2858 memcpy(dstDCtx, srcDCtx,
2859 sizeof(ZSTDv06_DCtx) - (ZSTDv06_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH + ZSTDv06_frameHeaderSize_max)); /* no need to copy workspace */
2863 /*-*************************************************************
2864 * Decompression section
2865 ***************************************************************/
2867 /* Frame format description
2868 Frame Header - [ Block Header - Block ] - Frame End
2870 - 4 bytes - Magic Number : ZSTDv06_MAGICNUMBER (defined within zstd_static.h)
2871 - 1 byte - Frame Descriptor
2873 - 3 bytes, starting with a 2-bits descriptor
2874 Uncompressed, Compressed, Frame End, unused
2876 See Block Format Description
2878 - 3 bytes, compatible with Block Header
2885 bit 0-3 : windowLog - ZSTDv06_WINDOWLOG_ABSOLUTEMIN (see zstd_internal.h)
2886 bit 4 : minmatch 4(0) or 3(1)
2887 bit 5 : reserved (must be zero)
2888 bit 6-7 : Frame content size : unknown, 1 byte, 2 bytes, 8 bytes
2890 Optional : content size (0, 1, 2 or 8 bytes)
2898 /* Compressed Block, format description
2900 Block = Literal Section - Sequences Section
2901 Prerequisite : size of (compressed) block, maximum size of regenerated data
2905 1.1) Header : 1-5 bytes
2907 00 compressed by Huff0
2909 10 is Raw (uncompressed)
2911 Note : using 01 => Huff0 with precomputed table ?
2912 Note : delta map ? => compressed ?
2914 1.1.1) Huff0-compressed literal block : 3-5 bytes
2915 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2916 srcSize < 1 KB => 3 bytes (2-2-10-10)
2917 srcSize < 16KB => 4 bytes (2-2-14-14)
2918 else => 5 bytes (2-2-18-18)
2919 big endian convention
2921 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2922 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2923 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2925 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2929 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2930 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
2931 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2933 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2937 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2938 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2939 srcSize < 1 KB => 3 bytes (2-2-10-10)
2940 srcSize < 16KB => 4 bytes (2-2-14-14)
2941 else => 5 bytes (2-2-18-18)
2942 big endian convention
2944 1- CTable available (stored into workspace ?)
2945 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2948 1.2) Literal block content
2950 1.2.1) Huff0 block, using sizes from header
2953 1.2.2) Huff0 block, using prepared table
2960 2) Sequences section
2964 /** ZSTDv06_frameHeaderSize() :
2965 * srcSize must be >= ZSTDv06_frameHeaderSize_min.
2966 * @return : size of the Frame Header */
2967 static size_t ZSTDv06_frameHeaderSize(const void* src, size_t srcSize)
2969 if (srcSize < ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong);
2970 { U32 const fcsId = (((const BYTE*)src)[4]) >> 6;
2971 return ZSTDv06_frameHeaderSize_min + ZSTDv06_fcs_fieldSize[fcsId]; }
2975 /** ZSTDv06_getFrameParams() :
2976 * decode Frame Header, or provide expected `srcSize`.
2977 * @return : 0, `fparamsPtr` is correctly filled,
2978 * >0, `srcSize` is too small, result is expected `srcSize`,
2979 * or an error code, which can be tested using ZSTDv06_isError() */
2980 size_t ZSTDv06_getFrameParams(ZSTDv06_frameParams* fparamsPtr, const void* src, size_t srcSize)
2982 const BYTE* ip = (const BYTE*)src;
2984 if (srcSize < ZSTDv06_frameHeaderSize_min) return ZSTDv06_frameHeaderSize_min;
2985 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown);
2987 /* ensure there is enough `srcSize` to fully read/decode frame header */
2988 { size_t const fhsize = ZSTDv06_frameHeaderSize(src, srcSize);
2989 if (srcSize < fhsize) return fhsize; }
2991 memset(fparamsPtr, 0, sizeof(*fparamsPtr));
2992 { BYTE const frameDesc = ip[4];
2993 fparamsPtr->windowLog = (frameDesc & 0xF) + ZSTDv06_WINDOWLOG_ABSOLUTEMIN;
2994 if ((frameDesc & 0x20) != 0) return ERROR(frameParameter_unsupported); /* reserved 1 bit */
2995 switch(frameDesc >> 6) /* fcsId */
2997 default: /* impossible */
2998 case 0 : fparamsPtr->frameContentSize = 0; break;
2999 case 1 : fparamsPtr->frameContentSize = ip[5]; break;
3000 case 2 : fparamsPtr->frameContentSize = MEM_readLE16(ip+5)+256; break;
3001 case 3 : fparamsPtr->frameContentSize = MEM_readLE64(ip+5); break;
3007 /** ZSTDv06_decodeFrameHeader() :
3008 * `srcSize` must be the size provided by ZSTDv06_frameHeaderSize().
3009 * @return : 0 if success, or an error code, which can be tested using ZSTDv06_isError() */
3010 static size_t ZSTDv06_decodeFrameHeader(ZSTDv06_DCtx* zc, const void* src, size_t srcSize)
3012 size_t const result = ZSTDv06_getFrameParams(&(zc->fParams), src, srcSize);
3013 if ((MEM_32bits()) && (zc->fParams.windowLog > 25)) return ERROR(frameParameter_unsupported);
3020 blockType_t blockType;
3022 } blockProperties_t;
3024 /*! ZSTDv06_getcBlockSize() :
3025 * Provides the size of compressed block from block header `src` */
3026 static size_t ZSTDv06_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
3028 const BYTE* const in = (const BYTE* const)src;
3031 if (srcSize < ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
3033 bpPtr->blockType = (blockType_t)((*in) >> 6);
3034 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
3035 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
3037 if (bpPtr->blockType == bt_end) return 0;
3038 if (bpPtr->blockType == bt_rle) return 1;
3043 static size_t ZSTDv06_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3045 if (dst==NULL) return ERROR(dstSize_tooSmall);
3046 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
3047 memcpy(dst, src, srcSize);
3052 /*! ZSTDv06_decodeLiteralsBlock() :
3053 @return : nb of bytes read from src (< srcSize ) */
3054 static size_t ZSTDv06_decodeLiteralsBlock(ZSTDv06_DCtx* dctx,
3055 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
3057 const BYTE* const istart = (const BYTE*) src;
3059 /* any compressed block with literals segment must be at least this size */
3060 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3062 switch(istart[0]>> 6)
3065 { size_t litSize, litCSize, singleStream=0;
3066 U32 lhSize = ((istart[0]) >> 4) & 3;
3067 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3070 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3071 /* 2 - 2 - 10 - 10 */
3073 singleStream = istart[0] & 16;
3074 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3075 litCSize = ((istart[1] & 3) << 8) + istart[2];
3078 /* 2 - 2 - 14 - 14 */
3080 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3081 litCSize = ((istart[2] & 63) << 8) + istart[3];
3084 /* 2 - 2 - 18 - 18 */
3086 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3087 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
3090 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected);
3091 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3093 if (HUFv06_isError(singleStream ?
3094 HUFv06_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3095 HUFv06_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3096 return ERROR(corruption_detected);
3098 dctx->litPtr = dctx->litBuffer;
3099 dctx->litSize = litSize;
3100 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3101 return litCSize + lhSize;
3104 { size_t litSize, litCSize;
3105 U32 lhSize = ((istart[0]) >> 4) & 3;
3106 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
3107 return ERROR(corruption_detected);
3108 if (!dctx->flagRepeatTable)
3109 return ERROR(dictionary_corrupted);
3111 /* 2 - 2 - 10 - 10 */
3113 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3114 litCSize = ((istart[1] & 3) << 8) + istart[2];
3115 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3117 { size_t const errorCode = HUFv06_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4);
3118 if (HUFv06_isError(errorCode)) return ERROR(corruption_detected);
3120 dctx->litPtr = dctx->litBuffer;
3121 dctx->litSize = litSize;
3122 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3123 return litCSize + lhSize;
3127 U32 lhSize = ((istart[0]) >> 4) & 3;
3130 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3132 litSize = istart[0] & 31;
3135 litSize = ((istart[0] & 15) << 8) + istart[1];
3138 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3142 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
3143 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3144 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3145 dctx->litPtr = dctx->litBuffer;
3146 dctx->litSize = litSize;
3147 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3148 return lhSize+litSize;
3150 /* direct reference into compressed stream */
3151 dctx->litPtr = istart+lhSize;
3152 dctx->litSize = litSize;
3153 return lhSize+litSize;
3157 U32 lhSize = ((istart[0]) >> 4) & 3;
3160 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3162 litSize = istart[0] & 31;
3165 litSize = ((istart[0] & 15) << 8) + istart[1];
3168 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3169 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3172 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected);
3173 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3174 dctx->litPtr = dctx->litBuffer;
3175 dctx->litSize = litSize;
3179 return ERROR(corruption_detected); /* impossible */
3184 /*! ZSTDv06_buildSeqTable() :
3185 @return : nb bytes read from src,
3186 or an error code if it fails, testable with ZSTDv06_isError()
3188 static size_t ZSTDv06_buildSeqTable(FSEv06_DTable* DTable, U32 type, U32 max, U32 maxLog,
3189 const void* src, size_t srcSize,
3190 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3194 case FSEv06_ENCODING_RLE :
3195 if (!srcSize) return ERROR(srcSize_wrong);
3196 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3197 FSEv06_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */
3199 case FSEv06_ENCODING_RAW :
3200 FSEv06_buildDTable(DTable, defaultNorm, max, defaultLog);
3202 case FSEv06_ENCODING_STATIC:
3203 if (!flagRepeatTable) return ERROR(corruption_detected);
3205 default : /* impossible */
3206 case FSEv06_ENCODING_DYNAMIC :
3209 size_t const headerSize = FSEv06_readNCount(norm, &max, &tableLog, src, srcSize);
3210 if (FSEv06_isError(headerSize)) return ERROR(corruption_detected);
3211 if (tableLog > maxLog) return ERROR(corruption_detected);
3212 FSEv06_buildDTable(DTable, norm, max, tableLog);
3218 static size_t ZSTDv06_decodeSeqHeaders(int* nbSeqPtr,
3219 FSEv06_DTable* DTableLL, FSEv06_DTable* DTableML, FSEv06_DTable* DTableOffb, U32 flagRepeatTable,
3220 const void* src, size_t srcSize)
3222 const BYTE* const istart = (const BYTE* const)src;
3223 const BYTE* const iend = istart + srcSize;
3224 const BYTE* ip = istart;
3227 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3230 { int nbSeq = *ip++;
3231 if (!nbSeq) { *nbSeqPtr=0; return 1; }
3233 if (nbSeq == 0xFF) {
3234 if (ip+2 > iend) return ERROR(srcSize_wrong);
3235 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3237 if (ip >= iend) return ERROR(srcSize_wrong);
3238 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3244 /* FSE table descriptors */
3245 if (ip + 4 > iend) return ERROR(srcSize_wrong); /* min : header byte + all 3 are "raw", hence no header, but at least xxLog bits per type */
3246 { U32 const LLtype = *ip >> 6;
3247 U32 const Offtype = (*ip >> 4) & 3;
3248 U32 const MLtype = (*ip >> 2) & 3;
3252 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3253 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3256 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableOffb, Offtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3257 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3260 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3261 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3276 BITv06_DStream_t DStream;
3277 FSEv06_DState_t stateLL;
3278 FSEv06_DState_t stateOffb;
3279 FSEv06_DState_t stateML;
3280 size_t prevOffset[ZSTDv06_REP_INIT];
3285 static void ZSTDv06_decodeSequence(seq_t* seq, seqState_t* seqState)
3287 /* Literal length */
3288 U32 const llCode = FSEv06_peekSymbol(&(seqState->stateLL));
3289 U32 const mlCode = FSEv06_peekSymbol(&(seqState->stateML));
3290 U32 const ofCode = FSEv06_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3292 U32 const llBits = LL_bits[llCode];
3293 U32 const mlBits = ML_bits[mlCode];
3294 U32 const ofBits = ofCode;
3295 U32 const totalBits = llBits+mlBits+ofBits;
3297 static const U32 LL_base[MaxLL+1] = {
3298 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3299 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3300 0x2000, 0x4000, 0x8000, 0x10000 };
3302 static const U32 ML_base[MaxML+1] = {
3303 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3304 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
3305 32, 34, 36, 38, 40, 44, 48, 56, 64, 80, 96, 0x80, 0x100, 0x200, 0x400, 0x800,
3306 0x1000, 0x2000, 0x4000, 0x8000, 0x10000 };
3308 static const U32 OF_base[MaxOff+1] = {
3309 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F,
3310 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF,
3311 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
3312 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1 };
3319 offset = OF_base[ofCode] + BITv06_readBits(&(seqState->DStream), ofBits); /* <= 26 bits */
3320 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream));
3323 if (offset < ZSTDv06_REP_NUM) {
3324 if (llCode == 0 && offset <= 1) offset = 1-offset;
3327 size_t temp = seqState->prevOffset[offset];
3329 seqState->prevOffset[2] = seqState->prevOffset[1];
3331 seqState->prevOffset[1] = seqState->prevOffset[0];
3332 seqState->prevOffset[0] = offset = temp;
3335 offset = seqState->prevOffset[0];
3338 offset -= ZSTDv06_REP_MOVE;
3339 seqState->prevOffset[2] = seqState->prevOffset[1];
3340 seqState->prevOffset[1] = seqState->prevOffset[0];
3341 seqState->prevOffset[0] = offset;
3343 seq->offset = offset;
3346 seq->matchLength = ML_base[mlCode] + MINMATCH + ((mlCode>31) ? BITv06_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */
3347 if (MEM_32bits() && (mlBits+llBits>24)) BITv06_reloadDStream(&(seqState->DStream));
3349 seq->litLength = LL_base[llCode] + ((llCode>15) ? BITv06_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */
3351 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv06_reloadDStream(&(seqState->DStream));
3353 /* ANS state update */
3354 FSEv06_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */
3355 FSEv06_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */
3356 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); /* <= 18 bits */
3357 FSEv06_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */
3361 static size_t ZSTDv06_execSequence(BYTE* op,
3362 BYTE* const oend, seq_t sequence,
3363 const BYTE** litPtr, const BYTE* const litLimit,
3364 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3366 BYTE* const oLitEnd = op + sequence.litLength;
3367 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3368 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3369 BYTE* const oend_8 = oend-8;
3370 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3371 const BYTE* match = oLitEnd - sequence.offset;
3374 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
3375 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3376 if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */
3379 ZSTDv06_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3381 *litPtr = iLitEnd; /* update for next sequence */
3384 if (sequence.offset > (size_t)(oLitEnd - base)) {
3385 /* offset beyond prefix */
3386 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3387 match = dictEnd - (base-match);
3388 if (match + sequence.matchLength <= dictEnd) {
3389 memmove(oLitEnd, match, sequence.matchLength);
3390 return sequenceLength;
3392 /* span extDict & currentPrefixSegment */
3393 { size_t const length1 = dictEnd - match;
3394 memmove(oLitEnd, match, length1);
3395 op = oLitEnd + length1;
3396 sequence.matchLength -= length1;
3398 if (op > oend_8 || sequence.matchLength < MINMATCH) {
3399 while (op < oMatchEnd) *op++ = *match++;
3400 return sequenceLength;
3403 /* Requirement: op <= oend_8 */
3405 /* match within prefix */
3406 if (sequence.offset < 8) {
3407 /* close range match, overlap */
3408 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3409 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
3410 int const sub2 = dec64table[sequence.offset];
3415 match += dec32table[sequence.offset];
3416 ZSTDv06_copy4(op+4, match);
3419 ZSTDv06_copy8(op, match);
3421 op += 8; match += 8;
3423 if (oMatchEnd > oend-(16-MINMATCH)) {
3425 ZSTDv06_wildcopy(op, match, oend_8 - op);
3426 match += oend_8 - op;
3429 while (op < oMatchEnd) *op++ = *match++;
3431 ZSTDv06_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3433 return sequenceLength;
3437 static size_t ZSTDv06_decompressSequences(
3439 void* dst, size_t maxDstSize,
3440 const void* seqStart, size_t seqSize)
3442 const BYTE* ip = (const BYTE*)seqStart;
3443 const BYTE* const iend = ip + seqSize;
3444 BYTE* const ostart = (BYTE* const)dst;
3445 BYTE* const oend = ostart + maxDstSize;
3447 const BYTE* litPtr = dctx->litPtr;
3448 const BYTE* const litEnd = litPtr + dctx->litSize;
3449 FSEv06_DTable* DTableLL = dctx->LLTable;
3450 FSEv06_DTable* DTableML = dctx->MLTable;
3451 FSEv06_DTable* DTableOffb = dctx->OffTable;
3452 const BYTE* const base = (const BYTE*) (dctx->base);
3453 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3454 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3457 /* Build Decoding Tables */
3458 { size_t const seqHSize = ZSTDv06_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->flagRepeatTable, ip, seqSize);
3459 if (ZSTDv06_isError(seqHSize)) return seqHSize;
3461 dctx->flagRepeatTable = 0;
3464 /* Regen sequences */
3467 seqState_t seqState;
3469 memset(&sequence, 0, sizeof(sequence));
3470 sequence.offset = REPCODE_STARTVALUE;
3471 { U32 i; for (i=0; i<ZSTDv06_REP_INIT; i++) seqState.prevOffset[i] = REPCODE_STARTVALUE; }
3472 { size_t const errorCode = BITv06_initDStream(&(seqState.DStream), ip, iend-ip);
3473 if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3474 FSEv06_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3475 FSEv06_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3476 FSEv06_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3478 for ( ; (BITv06_reloadDStream(&(seqState.DStream)) <= BITv06_DStream_completed) && nbSeq ; ) {
3480 ZSTDv06_decodeSequence(&sequence, &seqState);
3483 static BYTE* start = NULL;
3484 if (start==NULL) start = op;
3485 size_t pos = (size_t)(op-start);
3486 if ((pos >= 5810037) && (pos < 5810400))
3487 printf("Dpos %6u :%5u literals & match %3u bytes at distance %6u \n",
3488 pos, (U32)sequence.litLength, (U32)sequence.matchLength, (U32)sequence.offset);
3491 { size_t const oneSeqSize = ZSTDv06_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3492 if (ZSTDv06_isError(oneSeqSize)) return oneSeqSize;
3496 /* check if reached exact end */
3497 if (nbSeq) return ERROR(corruption_detected);
3500 /* last literal segment */
3501 { size_t const lastLLSize = litEnd - litPtr;
3502 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3503 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3504 memcpy(op, litPtr, lastLLSize);
3512 static void ZSTDv06_checkContinuity(ZSTDv06_DCtx* dctx, const void* dst)
3514 if (dst != dctx->previousDstEnd) { /* not contiguous */
3515 dctx->dictEnd = dctx->previousDstEnd;
3516 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3518 dctx->previousDstEnd = dst;
3523 static size_t ZSTDv06_decompressBlock_internal(ZSTDv06_DCtx* dctx,
3524 void* dst, size_t dstCapacity,
3525 const void* src, size_t srcSize)
3526 { /* blockType == blockCompressed */
3527 const BYTE* ip = (const BYTE*)src;
3529 if (srcSize >= ZSTDv06_BLOCKSIZE_MAX) return ERROR(srcSize_wrong);
3531 /* Decode literals sub-block */
3532 { size_t const litCSize = ZSTDv06_decodeLiteralsBlock(dctx, src, srcSize);
3533 if (ZSTDv06_isError(litCSize)) return litCSize;
3535 srcSize -= litCSize;
3537 return ZSTDv06_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3541 size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx,
3542 void* dst, size_t dstCapacity,
3543 const void* src, size_t srcSize)
3545 ZSTDv06_checkContinuity(dctx, dst);
3546 return ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3550 /*! ZSTDv06_decompressFrame() :
3551 * `dctx` must be properly initialized */
3552 static size_t ZSTDv06_decompressFrame(ZSTDv06_DCtx* dctx,
3553 void* dst, size_t dstCapacity,
3554 const void* src, size_t srcSize)
3556 const BYTE* ip = (const BYTE*)src;
3557 const BYTE* const iend = ip + srcSize;
3558 BYTE* const ostart = (BYTE* const)dst;
3560 BYTE* const oend = ostart + dstCapacity;
3561 size_t remainingSize = srcSize;
3562 blockProperties_t blockProperties = { bt_compressed, 0 };
3565 if (srcSize < ZSTDv06_frameHeaderSize_min+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
3568 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min);
3569 if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize;
3570 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
3571 if (ZSTDv06_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3572 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3575 /* Loop on each block */
3577 size_t decodedSize=0;
3578 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, iend-ip, &blockProperties);
3579 if (ZSTDv06_isError(cBlockSize)) return cBlockSize;
3581 ip += ZSTDv06_blockHeaderSize;
3582 remainingSize -= ZSTDv06_blockHeaderSize;
3583 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3585 switch(blockProperties.blockType)
3588 decodedSize = ZSTDv06_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3591 decodedSize = ZSTDv06_copyRawBlock(op, oend-op, ip, cBlockSize);
3594 return ERROR(GENERIC); /* not yet supported */
3598 if (remainingSize) return ERROR(srcSize_wrong);
3601 return ERROR(GENERIC); /* impossible */
3603 if (cBlockSize == 0) break; /* bt_end */
3605 if (ZSTDv06_isError(decodedSize)) return decodedSize;
3608 remainingSize -= cBlockSize;
3615 size_t ZSTDv06_decompress_usingPreparedDCtx(ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* refDCtx,
3616 void* dst, size_t dstCapacity,
3617 const void* src, size_t srcSize)
3619 ZSTDv06_copyDCtx(dctx, refDCtx);
3620 ZSTDv06_checkContinuity(dctx, dst);
3621 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3625 size_t ZSTDv06_decompress_usingDict(ZSTDv06_DCtx* dctx,
3626 void* dst, size_t dstCapacity,
3627 const void* src, size_t srcSize,
3628 const void* dict, size_t dictSize)
3630 ZSTDv06_decompressBegin_usingDict(dctx, dict, dictSize);
3631 ZSTDv06_checkContinuity(dctx, dst);
3632 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3636 size_t ZSTDv06_decompressDCtx(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3638 return ZSTDv06_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3642 size_t ZSTDv06_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3644 #if defined(ZSTDv06_HEAPMODE) && (ZSTDv06_HEAPMODE==1)
3646 ZSTDv06_DCtx* dctx = ZSTDv06_createDCtx();
3647 if (dctx==NULL) return ERROR(memory_allocation);
3648 regenSize = ZSTDv06_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3649 ZSTDv06_freeDCtx(dctx);
3651 #else /* stack mode */
3653 return ZSTDv06_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3657 /* ZSTD_errorFrameSizeInfoLegacy() :
3658 assumes `cSize` and `dBound` are _not_ NULL */
3659 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3662 *dBound = ZSTD_CONTENTSIZE_ERROR;
3665 void ZSTDv06_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3667 const BYTE* ip = (const BYTE*)src;
3668 size_t remainingSize = srcSize;
3669 size_t nbBlocks = 0;
3670 blockProperties_t blockProperties = { bt_compressed, 0 };
3673 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, srcSize);
3674 if (ZSTDv06_isError(frameHeaderSize)) {
3675 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize);
3678 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) {
3679 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3682 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) {
3683 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3686 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3689 /* Loop on each block */
3691 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, remainingSize, &blockProperties);
3692 if (ZSTDv06_isError(cBlockSize)) {
3693 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3697 ip += ZSTDv06_blockHeaderSize;
3698 remainingSize -= ZSTDv06_blockHeaderSize;
3699 if (cBlockSize > remainingSize) {
3700 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3704 if (cBlockSize == 0) break; /* bt_end */
3707 remainingSize -= cBlockSize;
3711 *cSize = ip - (const BYTE*)src;
3712 *dBound = nbBlocks * ZSTDv06_BLOCKSIZE_MAX;
3715 /*_******************************
3716 * Streaming Decompression API
3717 ********************************/
3718 size_t ZSTDv06_nextSrcSizeToDecompress(ZSTDv06_DCtx* dctx)
3720 return dctx->expected;
3723 size_t ZSTDv06_decompressContinue(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3726 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3727 if (dstCapacity) ZSTDv06_checkContinuity(dctx, dst);
3729 /* Decompress : frame header; part 1 */
3730 switch (dctx->stage)
3732 case ZSTDds_getFrameHeaderSize :
3733 if (srcSize != ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3734 dctx->headerSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min);
3735 if (ZSTDv06_isError(dctx->headerSize)) return dctx->headerSize;
3736 memcpy(dctx->headerBuffer, src, ZSTDv06_frameHeaderSize_min);
3737 if (dctx->headerSize > ZSTDv06_frameHeaderSize_min) {
3738 dctx->expected = dctx->headerSize - ZSTDv06_frameHeaderSize_min;
3739 dctx->stage = ZSTDds_decodeFrameHeader;
3742 dctx->expected = 0; /* not necessary to copy more */
3744 case ZSTDds_decodeFrameHeader:
3746 memcpy(dctx->headerBuffer + ZSTDv06_frameHeaderSize_min, src, dctx->expected);
3747 result = ZSTDv06_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
3748 if (ZSTDv06_isError(result)) return result;
3749 dctx->expected = ZSTDv06_blockHeaderSize;
3750 dctx->stage = ZSTDds_decodeBlockHeader;
3753 case ZSTDds_decodeBlockHeader:
3754 { blockProperties_t bp;
3755 size_t const cBlockSize = ZSTDv06_getcBlockSize(src, ZSTDv06_blockHeaderSize, &bp);
3756 if (ZSTDv06_isError(cBlockSize)) return cBlockSize;
3757 if (bp.blockType == bt_end) {
3759 dctx->stage = ZSTDds_getFrameHeaderSize;
3761 dctx->expected = cBlockSize;
3762 dctx->bType = bp.blockType;
3763 dctx->stage = ZSTDds_decompressBlock;
3767 case ZSTDds_decompressBlock:
3772 rSize = ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3775 rSize = ZSTDv06_copyRawBlock(dst, dstCapacity, src, srcSize);
3778 return ERROR(GENERIC); /* not yet handled */
3780 case bt_end : /* should never happen (filtered at phase 1) */
3784 return ERROR(GENERIC); /* impossible */
3786 dctx->stage = ZSTDds_decodeBlockHeader;
3787 dctx->expected = ZSTDv06_blockHeaderSize;
3788 dctx->previousDstEnd = (char*)dst + rSize;
3792 return ERROR(GENERIC); /* impossible */
3797 static void ZSTDv06_refDictContent(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3799 dctx->dictEnd = dctx->previousDstEnd;
3800 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3802 dctx->previousDstEnd = (const char*)dict + dictSize;
3805 static size_t ZSTDv06_loadEntropy(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3807 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, litlengthHeaderSize;
3809 hSize = HUFv06_readDTableX4(dctx->hufTableX4, dict, dictSize);
3810 if (HUFv06_isError(hSize)) return ERROR(dictionary_corrupted);
3811 dict = (const char*)dict + hSize;
3814 { short offcodeNCount[MaxOff+1];
3815 U32 offcodeMaxValue=MaxOff, offcodeLog;
3816 offcodeHeaderSize = FSEv06_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize);
3817 if (FSEv06_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3818 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
3819 { size_t const errorCode = FSEv06_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
3820 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3821 dict = (const char*)dict + offcodeHeaderSize;
3822 dictSize -= offcodeHeaderSize;
3825 { short matchlengthNCount[MaxML+1];
3826 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3827 matchlengthHeaderSize = FSEv06_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize);
3828 if (FSEv06_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3829 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
3830 { size_t const errorCode = FSEv06_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
3831 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3832 dict = (const char*)dict + matchlengthHeaderSize;
3833 dictSize -= matchlengthHeaderSize;
3836 { short litlengthNCount[MaxLL+1];
3837 unsigned litlengthMaxValue = MaxLL, litlengthLog;
3838 litlengthHeaderSize = FSEv06_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize);
3839 if (FSEv06_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3840 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
3841 { size_t const errorCode = FSEv06_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
3842 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3845 dctx->flagRepeatTable = 1;
3846 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize;
3849 static size_t ZSTDv06_decompress_insertDictionary(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3852 U32 const magic = MEM_readLE32(dict);
3853 if (magic != ZSTDv06_DICT_MAGIC) {
3854 /* pure content mode */
3855 ZSTDv06_refDictContent(dctx, dict, dictSize);
3858 /* load entropy tables */
3859 dict = (const char*)dict + 4;
3861 eSize = ZSTDv06_loadEntropy(dctx, dict, dictSize);
3862 if (ZSTDv06_isError(eSize)) return ERROR(dictionary_corrupted);
3864 /* reference dictionary content */
3865 dict = (const char*)dict + eSize;
3867 ZSTDv06_refDictContent(dctx, dict, dictSize);
3873 size_t ZSTDv06_decompressBegin_usingDict(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3875 { size_t const errorCode = ZSTDv06_decompressBegin(dctx);
3876 if (ZSTDv06_isError(errorCode)) return errorCode; }
3878 if (dict && dictSize) {
3879 size_t const errorCode = ZSTDv06_decompress_insertDictionary(dctx, dict, dictSize);
3880 if (ZSTDv06_isError(errorCode)) return ERROR(dictionary_corrupted);
3887 Buffered version of Zstd compression library
3888 Copyright (C) 2015-2016, Yann Collet.
3890 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
3892 Redistribution and use in source and binary forms, with or without
3893 modification, are permitted provided that the following conditions are
3895 * Redistributions of source code must retain the above copyright
3896 notice, this list of conditions and the following disclaimer.
3897 * Redistributions in binary form must reproduce the above
3898 copyright notice, this list of conditions and the following disclaimer
3899 in the documentation and/or other materials provided with the
3901 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3902 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3903 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3904 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3905 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3906 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3907 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3908 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3909 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3910 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3911 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3913 You can contact the author at :
3914 - zstd homepage : http://www.zstd.net/
3918 /*-***************************************************************************
3919 * Streaming decompression howto
3921 * A ZBUFFv06_DCtx object is required to track streaming operations.
3922 * Use ZBUFFv06_createDCtx() and ZBUFFv06_freeDCtx() to create/release resources.
3923 * Use ZBUFFv06_decompressInit() to start a new decompression operation,
3924 * or ZBUFFv06_decompressInitDictionary() if decompression requires a dictionary.
3925 * Note that ZBUFFv06_DCtx objects can be re-init multiple times.
3927 * Use ZBUFFv06_decompressContinue() repetitively to consume your input.
3928 * *srcSizePtr and *dstCapacityPtr can be any size.
3929 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
3930 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
3931 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
3932 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
3933 * or 0 when a frame is completely decoded,
3934 * or an error code, which can be tested using ZBUFFv06_isError().
3936 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv06_recommendedDInSize() and ZBUFFv06_recommendedDOutSize()
3937 * output : ZBUFFv06_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
3938 * input : ZBUFFv06_recommendedDInSize == 128KB + 3;
3939 * just follow indications from ZBUFFv06_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3940 * *******************************************************************************/
3942 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
3943 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv06_dStage;
3945 /* *** Resource management *** */
3946 struct ZBUFFv06_DCtx_s {
3948 ZSTDv06_frameParams fParams;
3949 ZBUFFv06_dStage stage;
3958 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX];
3960 }; /* typedef'd to ZBUFFv06_DCtx within "zstd_buffered.h" */
3963 ZBUFFv06_DCtx* ZBUFFv06_createDCtx(void)
3965 ZBUFFv06_DCtx* zbd = (ZBUFFv06_DCtx*)malloc(sizeof(ZBUFFv06_DCtx));
3966 if (zbd==NULL) return NULL;
3967 memset(zbd, 0, sizeof(*zbd));
3968 zbd->zd = ZSTDv06_createDCtx();
3969 zbd->stage = ZBUFFds_init;
3973 size_t ZBUFFv06_freeDCtx(ZBUFFv06_DCtx* zbd)
3975 if (zbd==NULL) return 0; /* support free on null */
3976 ZSTDv06_freeDCtx(zbd->zd);
3984 /* *** Initialization *** */
3986 size_t ZBUFFv06_decompressInitDictionary(ZBUFFv06_DCtx* zbd, const void* dict, size_t dictSize)
3988 zbd->stage = ZBUFFds_loadHeader;
3989 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
3990 return ZSTDv06_decompressBegin_usingDict(zbd->zd, dict, dictSize);
3993 size_t ZBUFFv06_decompressInit(ZBUFFv06_DCtx* zbd)
3995 return ZBUFFv06_decompressInitDictionary(zbd, NULL, 0);
4000 MEM_STATIC size_t ZBUFFv06_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
4002 size_t length = MIN(dstCapacity, srcSize);
4003 memcpy(dst, src, length);
4008 /* *** Decompression *** */
4010 size_t ZBUFFv06_decompressContinue(ZBUFFv06_DCtx* zbd,
4011 void* dst, size_t* dstCapacityPtr,
4012 const void* src, size_t* srcSizePtr)
4014 const char* const istart = (const char*)src;
4015 const char* const iend = istart + *srcSizePtr;
4016 const char* ip = istart;
4017 char* const ostart = (char*)dst;
4018 char* const oend = ostart + *dstCapacityPtr;
4026 return ERROR(init_missing);
4028 case ZBUFFds_loadHeader :
4029 { size_t const hSize = ZSTDv06_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
4031 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */
4032 if (ZSTDv06_isError(hSize)) return hSize;
4033 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */
4034 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
4035 zbd->lhSize += iend-ip;
4036 *dstCapacityPtr = 0;
4037 return (hSize - zbd->lhSize) + ZSTDv06_blockHeaderSize; /* remaining header bytes + next block header */
4039 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
4043 /* Consume header */
4044 { size_t const h1Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv06_frameHeaderSize_min */
4045 size_t const h1Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4046 if (ZSTDv06_isError(h1Result)) return h1Result;
4047 if (h1Size < zbd->lhSize) { /* long header */
4048 size_t const h2Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4049 size_t const h2Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4050 if (ZSTDv06_isError(h2Result)) return h2Result;
4053 /* Frame header instruct buffer sizes */
4054 { size_t const blockSize = MIN(1 << zbd->fParams.windowLog, ZSTDv06_BLOCKSIZE_MAX);
4055 zbd->blockSize = blockSize;
4056 if (zbd->inBuffSize < blockSize) {
4058 zbd->inBuffSize = blockSize;
4059 zbd->inBuff = (char*)malloc(blockSize);
4060 if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4062 { size_t const neededOutSize = ((size_t)1 << zbd->fParams.windowLog) + blockSize + WILDCOPY_OVERLENGTH * 2;
4063 if (zbd->outBuffSize < neededOutSize) {
4065 zbd->outBuffSize = neededOutSize;
4066 zbd->outBuff = (char*)malloc(neededOutSize);
4067 if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4069 zbd->stage = ZBUFFds_read;
4072 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4073 if (neededInSize==0) { /* end of frame */
4074 zbd->stage = ZBUFFds_init;
4078 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
4079 size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd,
4080 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4082 if (ZSTDv06_isError(decodedSize)) return decodedSize;
4084 if (!decodedSize) break; /* this was just a header */
4085 zbd->outEnd = zbd->outStart + decodedSize;
4086 zbd->stage = ZBUFFds_flush;
4089 if (ip==iend) { notDone = 0; break; } /* no more input */
4090 zbd->stage = ZBUFFds_load;
4094 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4095 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */
4097 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */
4098 loadedSize = ZBUFFv06_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4100 zbd->inPos += loadedSize;
4101 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
4103 /* decode loaded input */
4104 { size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd,
4105 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4106 zbd->inBuff, neededInSize);
4107 if (ZSTDv06_isError(decodedSize)) return decodedSize;
4108 zbd->inPos = 0; /* input is consumed */
4109 if (!decodedSize) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */
4110 zbd->outEnd = zbd->outStart + decodedSize;
4111 zbd->stage = ZBUFFds_flush;
4112 // break; /* ZBUFFds_flush follows */
4117 { size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4118 size_t const flushedSize = ZBUFFv06_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4120 zbd->outStart += flushedSize;
4121 if (flushedSize == toFlushSize) {
4122 zbd->stage = ZBUFFds_read;
4123 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4124 zbd->outStart = zbd->outEnd = 0;
4127 /* cannot flush everything */
4131 default: return ERROR(GENERIC); /* impossible */
4135 *srcSizePtr = ip-istart;
4136 *dstCapacityPtr = op-ostart;
4137 { size_t nextSrcSizeHint = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4138 if (nextSrcSizeHint > ZSTDv06_blockHeaderSize) nextSrcSizeHint+= ZSTDv06_blockHeaderSize; /* get following block header too */
4139 nextSrcSizeHint -= zbd->inPos; /* already loaded*/
4140 return nextSrcSizeHint;
4146 /* *************************************
4148 ***************************************/
4149 size_t ZBUFFv06_recommendedDInSize(void) { return ZSTDv06_BLOCKSIZE_MAX + ZSTDv06_blockHeaderSize /* block header size*/ ; }
4150 size_t ZBUFFv06_recommendedDOutSize(void) { return ZSTDv06_BLOCKSIZE_MAX; }