2 * Copyright (c) Yann Collet, Meta Platforms, Inc. and affiliates.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
14 #include <stddef.h> /* size_t, ptrdiff_t */
15 #include <string.h> /* memcpy */
16 #include <stdlib.h> /* malloc, free, qsort */
17 #include "../common/compiler.h"
18 #include "../common/error_private.h"
22 /* ******************************************************************
24 low-level memory access routines
25 Copyright (C) 2013-2015, Yann Collet.
27 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
29 Redistribution and use in source and binary forms, with or without
30 modification, are permitted provided that the following conditions are
33 * Redistributions of source code must retain the above copyright
34 notice, this list of conditions and the following disclaimer.
35 * Redistributions in binary form must reproduce the above
36 copyright notice, this list of conditions and the following disclaimer
37 in the documentation and/or other materials provided with the
40 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
41 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
42 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
43 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
44 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
46 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
47 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
48 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
49 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
50 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
52 You can contact the author at :
53 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
54 - Public forum : https://groups.google.com/forum/#!forum/lz4c
55 ****************************************************************** */
59 #if defined (__cplusplus)
64 /*-****************************************
66 ******************************************/
67 #if defined(_MSC_VER) /* Visual Studio */
68 # include <stdlib.h> /* _byteswap_ulong */
69 # include <intrin.h> /* _byteswap_* */
73 /*-**************************************************************
75 *****************************************************************/
76 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
78 # include <inttypes.h>
80 # include <stdint.h> /* intptr_t */
90 typedef unsigned char BYTE;
91 typedef unsigned short U16;
92 typedef signed short S16;
93 typedef unsigned int U32;
94 typedef signed int S32;
95 typedef unsigned long long U64;
96 typedef signed long long S64;
100 /*-**************************************************************
102 *****************************************************************/
104 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
105 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
107 MEM_STATIC unsigned MEM_isLittleEndian(void)
109 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
113 MEM_STATIC U16 MEM_read16(const void* memPtr)
115 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
118 MEM_STATIC U32 MEM_read32(const void* memPtr)
120 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
123 MEM_STATIC U64 MEM_read64(const void* memPtr)
125 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
128 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
130 memcpy(memPtr, &value, sizeof(value));
133 MEM_STATIC U32 MEM_swap32(U32 in)
135 #if defined(_MSC_VER) /* Visual Studio */
136 return _byteswap_ulong(in);
137 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
138 return __builtin_bswap32(in);
140 return ((in << 24) & 0xff000000 ) |
141 ((in << 8) & 0x00ff0000 ) |
142 ((in >> 8) & 0x0000ff00 ) |
143 ((in >> 24) & 0x000000ff );
147 MEM_STATIC U64 MEM_swap64(U64 in)
149 #if defined(_MSC_VER) /* Visual Studio */
150 return _byteswap_uint64(in);
151 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
152 return __builtin_bswap64(in);
154 return ((in << 56) & 0xff00000000000000ULL) |
155 ((in << 40) & 0x00ff000000000000ULL) |
156 ((in << 24) & 0x0000ff0000000000ULL) |
157 ((in << 8) & 0x000000ff00000000ULL) |
158 ((in >> 8) & 0x00000000ff000000ULL) |
159 ((in >> 24) & 0x0000000000ff0000ULL) |
160 ((in >> 40) & 0x000000000000ff00ULL) |
161 ((in >> 56) & 0x00000000000000ffULL);
166 /*=== Little endian r/w ===*/
168 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
170 if (MEM_isLittleEndian())
171 return MEM_read16(memPtr);
173 const BYTE* p = (const BYTE*)memPtr;
174 return (U16)(p[0] + (p[1]<<8));
178 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
180 if (MEM_isLittleEndian()) {
181 MEM_write16(memPtr, val);
183 BYTE* p = (BYTE*)memPtr;
185 p[1] = (BYTE)(val>>8);
189 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
191 if (MEM_isLittleEndian())
192 return MEM_read32(memPtr);
194 return MEM_swap32(MEM_read32(memPtr));
198 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
200 if (MEM_isLittleEndian())
201 return MEM_read64(memPtr);
203 return MEM_swap64(MEM_read64(memPtr));
207 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
210 return (size_t)MEM_readLE32(memPtr);
212 return (size_t)MEM_readLE64(memPtr);
217 #if defined (__cplusplus)
221 #endif /* MEM_H_MODULE */
224 zstd - standard compression library
225 Header File for static linking only
226 Copyright (C) 2014-2016, Yann Collet.
228 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
230 Redistribution and use in source and binary forms, with or without
231 modification, are permitted provided that the following conditions are
233 * Redistributions of source code must retain the above copyright
234 notice, this list of conditions and the following disclaimer.
235 * Redistributions in binary form must reproduce the above
236 copyright notice, this list of conditions and the following disclaimer
237 in the documentation and/or other materials provided with the
239 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
240 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
241 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
242 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
243 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
244 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
245 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
246 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
247 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
248 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
249 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
251 You can contact the author at :
252 - zstd homepage : https://facebook.github.io/zstd
254 #ifndef ZSTDv06_STATIC_H
255 #define ZSTDv06_STATIC_H
257 /* The prototypes defined within this file are considered experimental.
258 * They should not be used in the context DLL as they may change in the future.
259 * Prefer static linking if you need them, to control breaking version changes issues.
262 #if defined (__cplusplus)
268 /*- Advanced Decompression functions -*/
270 /*! ZSTDv06_decompress_usingPreparedDCtx() :
271 * Same as ZSTDv06_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
272 * It avoids reloading the dictionary each time.
273 * `preparedDCtx` must have been properly initialized using ZSTDv06_decompressBegin_usingDict().
274 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
275 ZSTDLIBv06_API size_t ZSTDv06_decompress_usingPreparedDCtx(
276 ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* preparedDCtx,
277 void* dst, size_t dstCapacity,
278 const void* src, size_t srcSize);
282 #define ZSTDv06_FRAMEHEADERSIZE_MAX 13 /* for static allocation */
283 static const size_t ZSTDv06_frameHeaderSize_min = 5;
284 static const size_t ZSTDv06_frameHeaderSize_max = ZSTDv06_FRAMEHEADERSIZE_MAX;
286 ZSTDLIBv06_API size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx);
289 Streaming decompression, direct mode (bufferless)
291 A ZSTDv06_DCtx object is required to track streaming operations.
292 Use ZSTDv06_createDCtx() / ZSTDv06_freeDCtx() to manage it.
293 A ZSTDv06_DCtx object can be re-used multiple times.
295 First optional operation is to retrieve frame parameters, using ZSTDv06_getFrameParams(), which doesn't consume the input.
296 It can provide the minimum size of rolling buffer required to properly decompress data,
297 and optionally the final size of uncompressed content.
298 (Note : content size is an optional info that may not be present. 0 means : content size unknown)
299 Frame parameters are extracted from the beginning of compressed frame.
300 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)
301 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
302 Result : 0 when successful, it means the ZSTDv06_frameParams structure has been filled.
303 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
304 errorCode, which can be tested using ZSTDv06_isError()
306 Start decompression, with ZSTDv06_decompressBegin() or ZSTDv06_decompressBegin_usingDict().
307 Alternatively, you can copy a prepared context, using ZSTDv06_copyDCtx().
309 Then use ZSTDv06_nextSrcSizeToDecompress() and ZSTDv06_decompressContinue() alternatively.
310 ZSTDv06_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv06_decompressContinue().
311 ZSTDv06_decompressContinue() requires this exact amount of bytes, or it will fail.
312 ZSTDv06_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
313 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
315 @result of ZSTDv06_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity)
316 It can be zero, which is not an error; it just means ZSTDv06_decompressContinue() has decoded some header.
318 A frame is fully decoded when ZSTDv06_nextSrcSizeToDecompress() returns zero.
319 Context can then be reset to start a new decompression.
323 /* **************************************
325 ****************************************/
326 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
327 User will have to take in charge required information to regenerate data, such as compressed and content sizes.
329 A few rules to respect :
330 - Uncompressed block size must be <= ZSTDv06_BLOCKSIZE_MAX (128 KB)
331 - Compressing or decompressing requires a context structure
332 + Use ZSTDv06_createCCtx() and ZSTDv06_createDCtx()
333 - It is necessary to init context before starting
334 + compression : ZSTDv06_compressBegin()
335 + decompression : ZSTDv06_decompressBegin()
336 + variants _usingDict() are also allowed
337 + copyCCtx() and copyDCtx() work too
338 - When a block is considered not compressible enough, ZSTDv06_compressBlock() result will be zero.
339 In which case, nothing is produced into `dst`.
340 + User must test for such outcome and deal directly with uncompressed data
341 + ZSTDv06_decompressBlock() doesn't accept uncompressed data as input !!
344 #define ZSTDv06_BLOCKSIZE_MAX (128 * 1024) /* define, for static allocation */
345 ZSTDLIBv06_API size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
349 #if defined (__cplusplus)
353 #endif /* ZSTDv06_STATIC_H */
355 zstd_internal - common functions to include
356 Header File for include
357 Copyright (C) 2014-2016, Yann Collet.
359 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
361 Redistribution and use in source and binary forms, with or without
362 modification, are permitted provided that the following conditions are
364 * Redistributions of source code must retain the above copyright
365 notice, this list of conditions and the following disclaimer.
366 * Redistributions in binary form must reproduce the above
367 copyright notice, this list of conditions and the following disclaimer
368 in the documentation and/or other materials provided with the
370 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
371 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
372 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
373 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
374 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
375 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
376 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
377 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
378 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
379 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
380 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
382 You can contact the author at :
383 - zstd homepage : https://www.zstd.net
385 #ifndef ZSTDv06_CCOMMON_H_MODULE
386 #define ZSTDv06_CCOMMON_H_MODULE
389 /*-*************************************
391 ***************************************/
392 #define MIN(a,b) ((a)<(b) ? (a) : (b))
393 #define MAX(a,b) ((a)>(b) ? (a) : (b))
396 /*-*************************************
398 ***************************************/
399 #define ZSTDv06_DICT_MAGIC 0xEC30A436
401 #define ZSTDv06_REP_NUM 3
402 #define ZSTDv06_REP_INIT ZSTDv06_REP_NUM
403 #define ZSTDv06_REP_MOVE (ZSTDv06_REP_NUM-1)
416 #define ZSTDv06_WINDOWLOG_ABSOLUTEMIN 12
417 static const size_t ZSTDv06_fcs_fieldSize[4] = { 0, 1, 2, 8 };
419 #define ZSTDv06_BLOCKHEADERSIZE 3 /* because C standard does not allow a static const value to be defined using another static const value .... :( */
420 static const size_t ZSTDv06_blockHeaderSize = ZSTDv06_BLOCKHEADERSIZE;
421 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
423 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
424 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
426 #define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
433 #define LONGNBSEQ 0x7F00
436 #define EQUAL_READ32 4
437 #define REPCODE_STARTVALUE 1
440 #define MaxLit ((1<<Litbits) - 1)
444 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
449 #define FSEv06_ENCODING_RAW 0
450 #define FSEv06_ENCODING_RLE 1
451 #define FSEv06_ENCODING_STATIC 2
452 #define FSEv06_ENCODING_DYNAMIC 3
454 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
456 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
457 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
459 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
460 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
462 static const U32 LL_defaultNormLog = 6;
464 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
465 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
466 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
468 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
469 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
470 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
472 static const U32 ML_defaultNormLog = 6;
474 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
475 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
476 static const U32 OF_defaultNormLog = 5;
479 /*-*******************************************
480 * Shared functions to include for inlining
481 *********************************************/
482 static void ZSTDv06_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
483 #define COPY8(d,s) { ZSTDv06_copy8(d,s); d+=8; s+=8; }
485 /*! ZSTDv06_wildcopy() :
486 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
487 #define WILDCOPY_OVERLENGTH 8
488 MEM_STATIC void ZSTDv06_wildcopy(void* dst, const void* src, ptrdiff_t length)
490 const BYTE* ip = (const BYTE*)src;
491 BYTE* op = (BYTE*)dst;
492 BYTE* const oend = op + length;
500 /*-*******************************************
502 *********************************************/
513 U32 rep[ZSTDv06_REP_INIT];
516 typedef struct { U32 unused; } ZSTDv06_stats_t;
528 U16* matchLengthStart;
531 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
534 ZSTDv06_optimal_t* priceTable;
535 ZSTDv06_match_t* matchTable;
536 U32* matchLengthFreq;
545 U32 log2matchLengthSum;
547 U32 log2litLengthSum;
553 const BYTE* cachedLiterals;
554 ZSTDv06_stats_t stats;
557 void ZSTDv06_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
560 #endif /* ZSTDv06_CCOMMON_H_MODULE */
561 /* ******************************************************************
562 FSE : Finite State Entropy codec
563 Public Prototypes declaration
564 Copyright (C) 2013-2016, Yann Collet.
566 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
568 Redistribution and use in source and binary forms, with or without
569 modification, are permitted provided that the following conditions are
572 * Redistributions of source code must retain the above copyright
573 notice, this list of conditions and the following disclaimer.
574 * Redistributions in binary form must reproduce the above
575 copyright notice, this list of conditions and the following disclaimer
576 in the documentation and/or other materials provided with the
579 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
580 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
581 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
582 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
583 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
584 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
585 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
586 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
587 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
588 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
589 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
591 You can contact the author at :
592 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
593 ****************************************************************** */
597 #if defined (__cplusplus)
603 /*-****************************************
604 * FSE simple functions
605 ******************************************/
606 /*! FSEv06_decompress():
607 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
608 into already allocated destination buffer 'dst', of size 'dstCapacity'.
609 @return : size of regenerated data (<= maxDstSize),
610 or an error code, which can be tested using FSEv06_isError() .
612 ** Important ** : FSEv06_decompress() does not decompress non-compressible nor RLE data !!!
613 Why ? : making this distinction requires a header.
614 Header management is intentionally delegated to the user layer, which can better manage special cases.
616 size_t FSEv06_decompress(void* dst, size_t dstCapacity,
617 const void* cSrc, size_t cSrcSize);
620 /*-*****************************************
622 ******************************************/
623 size_t FSEv06_compressBound(size_t size); /* maximum compressed size */
625 /* Error Management */
626 unsigned FSEv06_isError(size_t code); /* tells if a return value is an error code */
627 const char* FSEv06_getErrorName(size_t code); /* provides error code string (useful for debugging) */
631 /*-*****************************************
633 ******************************************/
636 FSEv06_decompress() does the following:
637 1. read normalized counters with readNCount()
638 2. build decoding table 'DTable' from normalized counters
639 3. decode the data stream using decoding table 'DTable'
641 The following API allows targeting specific sub-functions for advanced tasks.
642 For example, it's possible to compress several blocks using the same 'CTable',
643 or to save and provide normalized distribution using external method.
647 /* *** DECOMPRESSION *** */
649 /*! FSEv06_readNCount():
650 Read compactly saved 'normalizedCounter' from 'rBuffer'.
651 @return : size read from 'rBuffer',
652 or an errorCode, which can be tested using FSEv06_isError().
653 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
654 size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
656 /*! Constructor and Destructor of FSEv06_DTable.
657 Note that its size depends on 'tableLog' */
658 typedef unsigned FSEv06_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
659 FSEv06_DTable* FSEv06_createDTable(unsigned tableLog);
660 void FSEv06_freeDTable(FSEv06_DTable* dt);
662 /*! FSEv06_buildDTable():
663 Builds 'dt', which must be already allocated, using FSEv06_createDTable().
664 return : 0, or an errorCode, which can be tested using FSEv06_isError() */
665 size_t FSEv06_buildDTable (FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
667 /*! FSEv06_decompress_usingDTable():
668 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
669 into `dst` which must be already allocated.
670 @return : size of regenerated data (necessarily <= `dstCapacity`),
671 or an errorCode, which can be tested using FSEv06_isError() */
672 size_t FSEv06_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv06_DTable* dt);
677 (Note : these functions only decompress FSE-compressed blocks.
678 If block is uncompressed, use memcpy() instead
679 If block is a single repeated byte, use memset() instead )
681 The first step is to obtain the normalized frequencies of symbols.
682 This can be performed by FSEv06_readNCount() if it was saved using FSEv06_writeNCount().
683 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
684 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
685 or size the table to handle worst case situations (typically 256).
686 FSEv06_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
687 The result of FSEv06_readNCount() is the number of bytes read from 'rBuffer'.
688 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
689 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
691 The next step is to build the decompression tables 'FSEv06_DTable' from 'normalizedCounter'.
692 This is performed by the function FSEv06_buildDTable().
693 The space required by 'FSEv06_DTable' must be already allocated using FSEv06_createDTable().
694 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
696 `FSEv06_DTable` can then be used to decompress `cSrc`, with FSEv06_decompress_usingDTable().
697 `cSrcSize` must be strictly correct, otherwise decompression will fail.
698 FSEv06_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
699 If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). (ex: dst buffer too small)
703 #if defined (__cplusplus)
707 #endif /* FSEv06_H */
708 /* ******************************************************************
711 header file (to include)
712 Copyright (C) 2013-2016, Yann Collet.
714 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
716 Redistribution and use in source and binary forms, with or without
717 modification, are permitted provided that the following conditions are
720 * Redistributions of source code must retain the above copyright
721 notice, this list of conditions and the following disclaimer.
722 * Redistributions in binary form must reproduce the above
723 copyright notice, this list of conditions and the following disclaimer
724 in the documentation and/or other materials provided with the
727 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
728 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
729 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
730 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
731 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
732 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
733 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
734 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
735 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
736 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
737 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
739 You can contact the author at :
740 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
741 ****************************************************************** */
742 #ifndef BITSTREAM_H_MODULE
743 #define BITSTREAM_H_MODULE
745 #if defined (__cplusplus)
751 * This API consists of small unitary functions, which must be inlined for best performance.
752 * Since link-time-optimization is not available for all compilers,
753 * these functions are defined into a .h to be included.
757 /*=========================================
759 =========================================*/
760 #if defined(__BMI__) && defined(__GNUC__)
761 # include <immintrin.h> /* support for bextr (experimental) */
766 /*-********************************************
767 * bitStream decoding API (read backward)
768 **********************************************/
772 unsigned bitsConsumed;
777 typedef enum { BITv06_DStream_unfinished = 0,
778 BITv06_DStream_endOfBuffer = 1,
779 BITv06_DStream_completed = 2,
780 BITv06_DStream_overflow = 3 } BITv06_DStream_status; /* result of BITv06_reloadDStream() */
781 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
783 MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
784 MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, unsigned nbBits);
785 MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD);
786 MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* bitD);
790 /*-****************************************
792 ******************************************/
793 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, unsigned nbBits);
794 /* faster, but works only if nbBits >= 1 */
798 /*-**************************************************************
800 ****************************************************************/
801 MEM_STATIC unsigned BITv06_highbit32 ( U32 val)
803 # if defined(_MSC_VER) /* Visual */
805 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
806 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
807 return __builtin_clz (val) ^ 31;
808 # else /* Software version */
809 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 };
817 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
824 /*-********************************************************
826 **********************************************************/
827 /*! BITv06_initDStream() :
828 * Initialize a BITv06_DStream_t.
829 * `bitD` : a pointer to an already allocated BITv06_DStream_t structure.
830 * `srcSize` must be the *exact* size of the bitStream, in bytes.
831 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
833 MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
835 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
837 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
838 bitD->start = (const char*)srcBuffer;
839 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
840 bitD->bitContainer = MEM_readLEST(bitD->ptr);
841 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
842 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */
843 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); }
845 bitD->start = (const char*)srcBuffer;
846 bitD->ptr = bitD->start;
847 bitD->bitContainer = *(const BYTE*)(bitD->start);
850 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
851 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
852 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
853 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
854 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
855 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */
858 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
859 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */
860 bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); }
861 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
868 MEM_STATIC size_t BITv06_lookBits(const BITv06_DStream_t* bitD, U32 nbBits)
870 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
871 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
874 /*! BITv06_lookBitsFast() :
875 * unsafe version; only works if nbBits >= 1 */
876 MEM_STATIC size_t BITv06_lookBitsFast(const BITv06_DStream_t* bitD, U32 nbBits)
878 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
879 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
882 MEM_STATIC void BITv06_skipBits(BITv06_DStream_t* bitD, U32 nbBits)
884 bitD->bitsConsumed += nbBits;
887 MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, U32 nbBits)
889 size_t const value = BITv06_lookBits(bitD, nbBits);
890 BITv06_skipBits(bitD, nbBits);
894 /*! BITv06_readBitsFast() :
895 * unsafe version; only works if nbBits >= 1 */
896 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, U32 nbBits)
898 size_t const value = BITv06_lookBitsFast(bitD, nbBits);
899 BITv06_skipBits(bitD, nbBits);
903 MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD)
905 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
906 return BITv06_DStream_overflow;
908 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
909 bitD->ptr -= bitD->bitsConsumed >> 3;
910 bitD->bitsConsumed &= 7;
911 bitD->bitContainer = MEM_readLEST(bitD->ptr);
912 return BITv06_DStream_unfinished;
914 if (bitD->ptr == bitD->start) {
915 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv06_DStream_endOfBuffer;
916 return BITv06_DStream_completed;
918 { U32 nbBytes = bitD->bitsConsumed >> 3;
919 BITv06_DStream_status result = BITv06_DStream_unfinished;
920 if (bitD->ptr - nbBytes < bitD->start) {
921 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
922 result = BITv06_DStream_endOfBuffer;
924 bitD->ptr -= nbBytes;
925 bitD->bitsConsumed -= nbBytes*8;
926 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
931 /*! BITv06_endOfDStream() :
932 * @return Tells if DStream has exactly reached its end (all bits consumed).
934 MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* DStream)
936 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
939 #if defined (__cplusplus)
943 #endif /* BITSTREAM_H_MODULE */
944 /* ******************************************************************
945 FSE : Finite State Entropy coder
946 header file for static linking (only)
947 Copyright (C) 2013-2015, Yann Collet
949 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
951 Redistribution and use in source and binary forms, with or without
952 modification, are permitted provided that the following conditions are
955 * Redistributions of source code must retain the above copyright
956 notice, this list of conditions and the following disclaimer.
957 * Redistributions in binary form must reproduce the above
958 copyright notice, this list of conditions and the following disclaimer
959 in the documentation and/or other materials provided with the
962 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
963 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
964 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
965 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
966 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
967 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
968 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
969 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
970 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
971 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
972 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
974 You can contact the author at :
975 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
976 - Public forum : https://groups.google.com/forum/#!forum/lz4c
977 ****************************************************************** */
978 #ifndef FSEv06_STATIC_H
979 #define FSEv06_STATIC_H
981 #if defined (__cplusplus)
986 /* *****************************************
988 *******************************************/
989 /* FSE buffer bounds */
990 #define FSEv06_NCOUNTBOUND 512
991 #define FSEv06_BLOCKBOUND(size) (size + (size>>7))
992 #define FSEv06_COMPRESSBOUND(size) (FSEv06_NCOUNTBOUND + FSEv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
994 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
995 #define FSEv06_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
998 /* *****************************************
1000 *******************************************/
1001 size_t FSEv06_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
1002 /* same as FSEv06_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
1004 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits);
1005 /* build a fake FSEv06_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
1007 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, unsigned char symbolValue);
1008 /* build a fake FSEv06_DTable, designed to always generate the same symbolValue */
1011 /* *****************************************
1012 * FSE symbol decompression API
1013 *******************************************/
1017 const void* table; /* precise table may vary, depending on U16 */
1021 static void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt);
1023 static unsigned char FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD);
1026 /* *****************************************
1028 *******************************************/
1029 static unsigned char FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD);
1030 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
1033 /* *****************************************
1034 * Implementation of inlined functions
1035 *******************************************/
1038 /* ====== Decompression ====== */
1043 } FSEv06_DTableHeader; /* sizeof U32 */
1047 unsigned short newState;
1048 unsigned char symbol;
1049 unsigned char nbBits;
1050 } FSEv06_decode_t; /* size == U32 */
1052 MEM_STATIC void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt)
1054 const void* ptr = dt;
1055 const FSEv06_DTableHeader* const DTableH = (const FSEv06_DTableHeader*)ptr;
1056 DStatePtr->state = BITv06_readBits(bitD, DTableH->tableLog);
1057 BITv06_reloadDStream(bitD);
1058 DStatePtr->table = dt + 1;
1061 MEM_STATIC BYTE FSEv06_peekSymbol(const FSEv06_DState_t* DStatePtr)
1063 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1064 return DInfo.symbol;
1067 MEM_STATIC void FSEv06_updateState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1069 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1070 U32 const nbBits = DInfo.nbBits;
1071 size_t const lowBits = BITv06_readBits(bitD, nbBits);
1072 DStatePtr->state = DInfo.newState + lowBits;
1075 MEM_STATIC BYTE FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1077 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1078 U32 const nbBits = DInfo.nbBits;
1079 BYTE const symbol = DInfo.symbol;
1080 size_t const lowBits = BITv06_readBits(bitD, nbBits);
1082 DStatePtr->state = DInfo.newState + lowBits;
1086 /*! FSEv06_decodeSymbolFast() :
1087 unsafe, only works if no symbol has a probability > 50% */
1088 MEM_STATIC BYTE FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1090 FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1091 U32 const nbBits = DInfo.nbBits;
1092 BYTE const symbol = DInfo.symbol;
1093 size_t const lowBits = BITv06_readBitsFast(bitD, nbBits);
1095 DStatePtr->state = DInfo.newState + lowBits;
1101 #ifndef FSEv06_COMMONDEFS_ONLY
1103 /* **************************************************************
1105 ****************************************************************/
1107 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1108 * Increasing memory usage improves compression ratio
1109 * Reduced memory usage can improve speed, due to cache effect
1110 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1111 #define FSEv06_MAX_MEMORY_USAGE 14
1112 #define FSEv06_DEFAULT_MEMORY_USAGE 13
1114 /*!FSEv06_MAX_SYMBOL_VALUE :
1115 * Maximum symbol value authorized.
1116 * Required for proper stack allocation */
1117 #define FSEv06_MAX_SYMBOL_VALUE 255
1120 /* **************************************************************
1121 * template functions type & suffix
1122 ****************************************************************/
1123 #define FSEv06_FUNCTION_TYPE BYTE
1124 #define FSEv06_FUNCTION_EXTENSION
1125 #define FSEv06_DECODE_TYPE FSEv06_decode_t
1128 #endif /* !FSEv06_COMMONDEFS_ONLY */
1131 /* ***************************************************************
1133 *****************************************************************/
1134 #define FSEv06_MAX_TABLELOG (FSEv06_MAX_MEMORY_USAGE-2)
1135 #define FSEv06_MAX_TABLESIZE (1U<<FSEv06_MAX_TABLELOG)
1136 #define FSEv06_MAXTABLESIZE_MASK (FSEv06_MAX_TABLESIZE-1)
1137 #define FSEv06_DEFAULT_TABLELOG (FSEv06_DEFAULT_MEMORY_USAGE-2)
1138 #define FSEv06_MIN_TABLELOG 5
1140 #define FSEv06_TABLELOG_ABSOLUTE_MAX 15
1141 #if FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX
1142 #error "FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX is not supported"
1145 #define FSEv06_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
1148 #if defined (__cplusplus)
1152 #endif /* FSEv06_STATIC_H */
1154 Common functions of New Generation Entropy library
1155 Copyright (C) 2016, Yann Collet.
1157 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1159 Redistribution and use in source and binary forms, with or without
1160 modification, are permitted provided that the following conditions are
1163 * Redistributions of source code must retain the above copyright
1164 notice, this list of conditions and the following disclaimer.
1165 * Redistributions in binary form must reproduce the above
1166 copyright notice, this list of conditions and the following disclaimer
1167 in the documentation and/or other materials provided with the
1170 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1171 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1172 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1173 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1174 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1175 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1176 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1177 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1178 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1179 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1180 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1182 You can contact the author at :
1183 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1184 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1185 *************************************************************************** */
1188 /*-****************************************
1189 * FSE Error Management
1190 ******************************************/
1191 unsigned FSEv06_isError(size_t code) { return ERR_isError(code); }
1193 const char* FSEv06_getErrorName(size_t code) { return ERR_getErrorName(code); }
1196 /* **************************************************************
1197 * HUF Error Management
1198 ****************************************************************/
1199 static unsigned HUFv06_isError(size_t code) { return ERR_isError(code); }
1202 /*-**************************************************************
1203 * FSE NCount encoding-decoding
1204 ****************************************************************/
1205 static short FSEv06_abs(short a) { return a<0 ? -a : a; }
1207 size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1208 const void* headerBuffer, size_t hbSize)
1210 const BYTE* const istart = (const BYTE*) headerBuffer;
1211 const BYTE* const iend = istart + hbSize;
1212 const BYTE* ip = istart;
1218 unsigned charnum = 0;
1221 if (hbSize < 4) return ERROR(srcSize_wrong);
1222 bitStream = MEM_readLE32(ip);
1223 nbBits = (bitStream & 0xF) + FSEv06_MIN_TABLELOG; /* extract tableLog */
1224 if (nbBits > FSEv06_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1227 *tableLogPtr = nbBits;
1228 remaining = (1<<nbBits)+1;
1229 threshold = 1<<nbBits;
1232 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1234 unsigned n0 = charnum;
1235 while ((bitStream & 0xFFFF) == 0xFFFF) {
1239 bitStream = MEM_readLE32(ip) >> bitCount;
1244 while ((bitStream & 3) == 3) {
1249 n0 += bitStream & 3;
1251 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1252 while (charnum < n0) normalizedCounter[charnum++] = 0;
1253 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1256 bitStream = MEM_readLE32(ip) >> bitCount;
1261 { short const max = (short)((2*threshold-1)-remaining);
1264 if ((bitStream & (threshold-1)) < (U32)max) {
1265 count = (short)(bitStream & (threshold-1));
1266 bitCount += nbBits-1;
1268 count = (short)(bitStream & (2*threshold-1));
1269 if (count >= threshold) count -= max;
1273 count--; /* extra accuracy */
1274 remaining -= FSEv06_abs(count);
1275 normalizedCounter[charnum++] = count;
1277 while (remaining < threshold) {
1282 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1286 bitCount -= (int)(8 * (iend - 4 - ip));
1289 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1290 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1291 if (remaining != 1) return ERROR(GENERIC);
1292 *maxSVPtr = charnum-1;
1294 ip += (bitCount+7)>>3;
1295 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1298 /* ******************************************************************
1299 FSE : Finite State Entropy decoder
1300 Copyright (C) 2013-2015, Yann Collet.
1302 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1304 Redistribution and use in source and binary forms, with or without
1305 modification, are permitted provided that the following conditions are
1308 * Redistributions of source code must retain the above copyright
1309 notice, this list of conditions and the following disclaimer.
1310 * Redistributions in binary form must reproduce the above
1311 copyright notice, this list of conditions and the following disclaimer
1312 in the documentation and/or other materials provided with the
1315 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1316 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1317 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1318 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1319 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1320 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1321 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1322 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1323 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1324 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1325 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1327 You can contact the author at :
1328 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1329 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1330 ****************************************************************** */
1333 /* **************************************************************
1334 * Compiler specifics
1335 ****************************************************************/
1336 #ifdef _MSC_VER /* Visual Studio */
1337 # define FORCE_INLINE static __forceinline
1338 # include <intrin.h> /* For Visual 2005 */
1339 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1340 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1342 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1344 # define FORCE_INLINE static inline __attribute__((always_inline))
1346 # define FORCE_INLINE static inline
1349 # define FORCE_INLINE static
1350 # endif /* __STDC_VERSION__ */
1354 /* **************************************************************
1356 ****************************************************************/
1357 #define FSEv06_isError ERR_isError
1358 #define FSEv06_STATIC_ASSERT(c) { enum { FSEv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1361 /* **************************************************************
1363 ****************************************************************/
1364 typedef U32 DTable_max_t[FSEv06_DTABLE_SIZE_U32(FSEv06_MAX_TABLELOG)];
1367 /* **************************************************************
1369 ****************************************************************/
1371 designed to be included
1372 for type-specific functions (template emulation in C)
1373 Objective is to write these functions only once, for improved maintenance
1377 #ifndef FSEv06_FUNCTION_EXTENSION
1378 # error "FSEv06_FUNCTION_EXTENSION must be defined"
1380 #ifndef FSEv06_FUNCTION_TYPE
1381 # error "FSEv06_FUNCTION_TYPE must be defined"
1384 /* Function names */
1385 #define FSEv06_CAT(X,Y) X##Y
1386 #define FSEv06_FUNCTION_NAME(X,Y) FSEv06_CAT(X,Y)
1387 #define FSEv06_TYPE_NAME(X,Y) FSEv06_CAT(X,Y)
1390 /* Function templates */
1391 FSEv06_DTable* FSEv06_createDTable (unsigned tableLog)
1393 if (tableLog > FSEv06_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv06_TABLELOG_ABSOLUTE_MAX;
1394 return (FSEv06_DTable*)malloc( FSEv06_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1397 void FSEv06_freeDTable (FSEv06_DTable* dt)
1402 size_t FSEv06_buildDTable(FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1404 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1405 FSEv06_DECODE_TYPE* const tableDecode = (FSEv06_DECODE_TYPE*) (tdPtr);
1406 U16 symbolNext[FSEv06_MAX_SYMBOL_VALUE+1];
1408 U32 const maxSV1 = maxSymbolValue + 1;
1409 U32 const tableSize = 1 << tableLog;
1410 U32 highThreshold = tableSize-1;
1413 if (maxSymbolValue > FSEv06_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1414 if (tableLog > FSEv06_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1416 /* Init, lay down lowprob symbols */
1417 { FSEv06_DTableHeader DTableH;
1418 DTableH.tableLog = (U16)tableLog;
1419 DTableH.fastMode = 1;
1420 { S16 const largeLimit= (S16)(1 << (tableLog-1));
1422 for (s=0; s<maxSV1; s++) {
1423 if (normalizedCounter[s]==-1) {
1424 tableDecode[highThreshold--].symbol = (FSEv06_FUNCTION_TYPE)s;
1427 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1428 symbolNext[s] = normalizedCounter[s];
1430 memcpy(dt, &DTableH, sizeof(DTableH));
1433 /* Spread symbols */
1434 { U32 const tableMask = tableSize-1;
1435 U32 const step = FSEv06_TABLESTEP(tableSize);
1436 U32 s, position = 0;
1437 for (s=0; s<maxSV1; s++) {
1439 for (i=0; i<normalizedCounter[s]; i++) {
1440 tableDecode[position].symbol = (FSEv06_FUNCTION_TYPE)s;
1441 position = (position + step) & tableMask;
1442 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1445 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1448 /* Build Decoding table */
1450 for (u=0; u<tableSize; u++) {
1451 FSEv06_FUNCTION_TYPE const symbol = (FSEv06_FUNCTION_TYPE)(tableDecode[u].symbol);
1452 U16 nextState = symbolNext[symbol]++;
1453 tableDecode[u].nbBits = (BYTE) (tableLog - BITv06_highbit32 ((U32)nextState) );
1454 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1462 #ifndef FSEv06_COMMONDEFS_ONLY
1464 /*-*******************************************************
1465 * Decompression (Byte symbols)
1466 *********************************************************/
1467 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, BYTE symbolValue)
1470 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr;
1471 void* dPtr = dt + 1;
1472 FSEv06_decode_t* const cell = (FSEv06_decode_t*)dPtr;
1474 DTableH->tableLog = 0;
1475 DTableH->fastMode = 0;
1478 cell->symbol = symbolValue;
1485 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits)
1488 FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr;
1489 void* dPtr = dt + 1;
1490 FSEv06_decode_t* const dinfo = (FSEv06_decode_t*)dPtr;
1491 const unsigned tableSize = 1 << nbBits;
1492 const unsigned tableMask = tableSize - 1;
1493 const unsigned maxSV1 = tableMask+1;
1497 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1499 /* Build Decoding Table */
1500 DTableH->tableLog = (U16)nbBits;
1501 DTableH->fastMode = 1;
1502 for (s=0; s<maxSV1; s++) {
1503 dinfo[s].newState = 0;
1504 dinfo[s].symbol = (BYTE)s;
1505 dinfo[s].nbBits = (BYTE)nbBits;
1511 FORCE_INLINE size_t FSEv06_decompress_usingDTable_generic(
1512 void* dst, size_t maxDstSize,
1513 const void* cSrc, size_t cSrcSize,
1514 const FSEv06_DTable* dt, const unsigned fast)
1516 BYTE* const ostart = (BYTE*) dst;
1518 BYTE* const omax = op + maxDstSize;
1519 BYTE* const olimit = omax-3;
1521 BITv06_DStream_t bitD;
1522 FSEv06_DState_t state1;
1523 FSEv06_DState_t state2;
1526 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1527 if (FSEv06_isError(errorCode)) return errorCode; }
1529 FSEv06_initDState(&state1, &bitD, dt);
1530 FSEv06_initDState(&state2, &bitD, dt);
1532 #define FSEv06_GETSYMBOL(statePtr) fast ? FSEv06_decodeSymbolFast(statePtr, &bitD) : FSEv06_decodeSymbol(statePtr, &bitD)
1534 /* 4 symbols per loop */
1535 for ( ; (BITv06_reloadDStream(&bitD)==BITv06_DStream_unfinished) && (op<olimit) ; op+=4) {
1536 op[0] = FSEv06_GETSYMBOL(&state1);
1538 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1539 BITv06_reloadDStream(&bitD);
1541 op[1] = FSEv06_GETSYMBOL(&state2);
1543 if (FSEv06_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1544 { if (BITv06_reloadDStream(&bitD) > BITv06_DStream_unfinished) { op+=2; break; } }
1546 op[2] = FSEv06_GETSYMBOL(&state1);
1548 if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1549 BITv06_reloadDStream(&bitD);
1551 op[3] = FSEv06_GETSYMBOL(&state2);
1555 /* note : BITv06_reloadDStream(&bitD) >= FSEv06_DStream_partiallyFilled; Ends at exactly BITv06_DStream_completed */
1557 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1559 *op++ = FSEv06_GETSYMBOL(&state1);
1561 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) {
1562 *op++ = FSEv06_GETSYMBOL(&state2);
1566 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1568 *op++ = FSEv06_GETSYMBOL(&state2);
1570 if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) {
1571 *op++ = FSEv06_GETSYMBOL(&state1);
1579 size_t FSEv06_decompress_usingDTable(void* dst, size_t originalSize,
1580 const void* cSrc, size_t cSrcSize,
1581 const FSEv06_DTable* dt)
1583 const void* ptr = dt;
1584 const FSEv06_DTableHeader* DTableH = (const FSEv06_DTableHeader*)ptr;
1585 const U32 fastMode = DTableH->fastMode;
1587 /* select fast mode (static) */
1588 if (fastMode) return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1589 return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1593 size_t FSEv06_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1595 const BYTE* const istart = (const BYTE*)cSrc;
1596 const BYTE* ip = istart;
1597 short counting[FSEv06_MAX_SYMBOL_VALUE+1];
1598 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1600 unsigned maxSymbolValue = FSEv06_MAX_SYMBOL_VALUE;
1602 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1604 /* normal FSE decoding mode */
1605 { size_t const NCountLength = FSEv06_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1606 if (FSEv06_isError(NCountLength)) return NCountLength;
1607 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1609 cSrcSize -= NCountLength;
1612 { size_t const errorCode = FSEv06_buildDTable (dt, counting, maxSymbolValue, tableLog);
1613 if (FSEv06_isError(errorCode)) return errorCode; }
1615 return FSEv06_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */
1620 #endif /* FSEv06_COMMONDEFS_ONLY */
1621 /* ******************************************************************
1622 Huffman coder, part of New Generation Entropy library
1624 Copyright (C) 2013-2016, Yann Collet.
1626 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1628 Redistribution and use in source and binary forms, with or without
1629 modification, are permitted provided that the following conditions are
1632 * Redistributions of source code must retain the above copyright
1633 notice, this list of conditions and the following disclaimer.
1634 * Redistributions in binary form must reproduce the above
1635 copyright notice, this list of conditions and the following disclaimer
1636 in the documentation and/or other materials provided with the
1639 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1640 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1641 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1642 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1643 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1644 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1645 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1646 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1647 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1648 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1649 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1651 You can contact the author at :
1652 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1653 ****************************************************************** */
1657 #if defined (__cplusplus)
1662 /* ****************************************
1663 * HUF simple functions
1664 ******************************************/
1665 size_t HUFv06_decompress(void* dst, size_t dstSize,
1666 const void* cSrc, size_t cSrcSize);
1668 HUFv06_decompress() :
1669 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1670 into already allocated destination buffer 'dst', of size 'dstSize'.
1671 `dstSize` : must be the **exact** size of original (uncompressed) data.
1672 Note : in contrast with FSE, HUFv06_decompress can regenerate
1673 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1674 because it knows size to regenerate.
1675 @return : size of regenerated data (== dstSize)
1676 or an error code, which can be tested using HUFv06_isError()
1680 /* ****************************************
1682 ******************************************/
1683 size_t HUFv06_compressBound(size_t size); /**< maximum compressed size */
1686 #if defined (__cplusplus)
1690 #endif /* HUFv06_H */
1691 /* ******************************************************************
1692 Huffman codec, part of New Generation Entropy library
1693 header file, for static linking only
1694 Copyright (C) 2013-2016, Yann Collet
1696 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1698 Redistribution and use in source and binary forms, with or without
1699 modification, are permitted provided that the following conditions are
1702 * Redistributions of source code must retain the above copyright
1703 notice, this list of conditions and the following disclaimer.
1704 * Redistributions in binary form must reproduce the above
1705 copyright notice, this list of conditions and the following disclaimer
1706 in the documentation and/or other materials provided with the
1709 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1710 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1711 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1712 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1713 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1714 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1715 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1716 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1717 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1718 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1719 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1721 You can contact the author at :
1722 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1723 ****************************************************************** */
1724 #ifndef HUFv06_STATIC_H
1725 #define HUFv06_STATIC_H
1727 #if defined (__cplusplus)
1732 /* ****************************************
1734 ******************************************/
1735 /* HUF buffer bounds */
1736 #define HUFv06_CTABLEBOUND 129
1737 #define HUFv06_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1738 #define HUFv06_COMPRESSBOUND(size) (HUFv06_CTABLEBOUND + HUFv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
1740 /* static allocation of HUF's DTable */
1741 #define HUFv06_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1742 #define HUFv06_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1743 unsigned short DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1744 #define HUFv06_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1745 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1746 #define HUFv06_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1747 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1750 /* ****************************************
1751 * Advanced decompression functions
1752 ******************************************/
1753 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1754 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1759 HUFv06_decompress() does the following:
1760 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1761 2. build Huffman table from save, using HUFv06_readDTableXn()
1762 3. decode 1 or 4 segments in parallel using HUFv06_decompressSXn_usingDTable
1764 size_t HUFv06_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1765 size_t HUFv06_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1767 size_t HUFv06_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1768 size_t HUFv06_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1771 /* single stream variants */
1772 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1773 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1775 size_t HUFv06_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1776 size_t HUFv06_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1780 /* **************************************************************
1782 ****************************************************************/
1783 #define HUFv06_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv06_MAX_TABLELOG. Beyond that value, code does not work */
1784 #define HUFv06_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv06_ABSOLUTEMAX_TABLELOG */
1785 #define HUFv06_DEFAULT_TABLELOG HUFv06_MAX_TABLELOG /* tableLog by default, when not specified */
1786 #define HUFv06_MAX_SYMBOL_VALUE 255
1787 #if (HUFv06_MAX_TABLELOG > HUFv06_ABSOLUTEMAX_TABLELOG)
1788 # error "HUFv06_MAX_TABLELOG is too large !"
1793 /*! HUFv06_readStats() :
1794 Read compact Huffman tree, saved by HUFv06_writeCTable().
1795 `huffWeight` is destination buffer.
1796 @return : size read from `src`
1798 MEM_STATIC size_t HUFv06_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1799 U32* nbSymbolsPtr, U32* tableLogPtr,
1800 const void* src, size_t srcSize)
1803 const BYTE* ip = (const BYTE*) src;
1807 if (!srcSize) return ERROR(srcSize_wrong);
1809 /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */
1811 if (iSize >= 128) { /* special header */
1812 if (iSize >= (242)) { /* RLE */
1813 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1814 oSize = l[iSize-242];
1815 memset(huffWeight, 1, hwSize);
1818 else { /* Incompressible */
1819 oSize = iSize - 127;
1820 iSize = ((oSize+1)/2);
1821 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1822 if (oSize >= hwSize) return ERROR(corruption_detected);
1825 for (n=0; n<oSize; n+=2) {
1826 huffWeight[n] = ip[n/2] >> 4;
1827 huffWeight[n+1] = ip[n/2] & 15;
1829 else { /* header compressed with FSE (normal case) */
1830 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1831 oSize = FSEv06_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1832 if (FSEv06_isError(oSize)) return oSize;
1835 /* collect weight stats */
1836 memset(rankStats, 0, (HUFv06_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1838 { U32 n; for (n=0; n<oSize; n++) {
1839 if (huffWeight[n] >= HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1840 rankStats[huffWeight[n]]++;
1841 weightTotal += (1 << huffWeight[n]) >> 1;
1843 if (weightTotal == 0) return ERROR(corruption_detected);
1845 /* get last non-null symbol weight (implied, total must be 2^n) */
1846 { U32 const tableLog = BITv06_highbit32(weightTotal) + 1;
1847 if (tableLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1848 *tableLogPtr = tableLog;
1849 /* determine last weight */
1850 { U32 const total = 1 << tableLog;
1851 U32 const rest = total - weightTotal;
1852 U32 const verif = 1 << BITv06_highbit32(rest);
1853 U32 const lastWeight = BITv06_highbit32(rest) + 1;
1854 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1855 huffWeight[oSize] = (BYTE)lastWeight;
1856 rankStats[lastWeight]++;
1859 /* check tree construction validity */
1860 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1863 *nbSymbolsPtr = (U32)(oSize+1);
1869 #if defined (__cplusplus)
1873 #endif /* HUFv06_STATIC_H */
1874 /* ******************************************************************
1875 Huffman decoder, part of New Generation Entropy library
1876 Copyright (C) 2013-2016, Yann Collet.
1878 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1880 Redistribution and use in source and binary forms, with or without
1881 modification, are permitted provided that the following conditions are
1884 * Redistributions of source code must retain the above copyright
1885 notice, this list of conditions and the following disclaimer.
1886 * Redistributions in binary form must reproduce the above
1887 copyright notice, this list of conditions and the following disclaimer
1888 in the documentation and/or other materials provided with the
1891 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1892 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1893 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1894 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1895 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1896 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1897 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1898 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1899 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1900 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1901 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1903 You can contact the author at :
1904 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1905 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1906 ****************************************************************** */
1908 /* **************************************************************
1909 * Compiler specifics
1910 ****************************************************************/
1911 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1912 /* inline is defined */
1913 #elif defined(_MSC_VER)
1914 # define inline __inline
1916 # define inline /* disable inline */
1920 #ifdef _MSC_VER /* Visual Studio */
1921 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1926 /* **************************************************************
1928 ****************************************************************/
1929 #define HUFv06_STATIC_ASSERT(c) { enum { HUFv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1933 /* *******************************************************
1934 * HUF : Huffman block decompression
1935 *********************************************************/
1936 typedef struct { BYTE byte; BYTE nbBits; } HUFv06_DEltX2; /* single-symbol decoding */
1938 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv06_DEltX4; /* double-symbols decoding */
1940 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1944 /*-***************************/
1945 /* single-symbol decoding */
1946 /*-***************************/
1948 size_t HUFv06_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1950 BYTE huffWeight[HUFv06_MAX_SYMBOL_VALUE + 1];
1951 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1957 void* const dtPtr = DTable + 1;
1958 HUFv06_DEltX2* const dt = (HUFv06_DEltX2*)dtPtr;
1960 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1961 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
1963 iSize = HUFv06_readStats(huffWeight, HUFv06_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1964 if (HUFv06_isError(iSize)) return iSize;
1967 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1968 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
1972 for (n=1; n<tableLog+1; n++) {
1973 U32 current = nextRankStart;
1974 nextRankStart += (rankVal[n] << (n-1));
1975 rankVal[n] = current;
1979 for (n=0; n<nbSymbols; n++) {
1980 const U32 w = huffWeight[n];
1981 const U32 length = (1 << w) >> 1;
1984 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1985 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1987 rankVal[w] += length;
1994 static BYTE HUFv06_decodeSymbolX2(BITv06_DStream_t* Dstream, const HUFv06_DEltX2* dt, const U32 dtLog)
1996 const size_t val = BITv06_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1997 const BYTE c = dt[val].byte;
1998 BITv06_skipBits(Dstream, dt[val].nbBits);
2002 #define HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
2003 *ptr++ = HUFv06_decodeSymbolX2(DStreamPtr, dt, dtLog)
2005 #define HUFv06_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
2006 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2007 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2009 #define HUFv06_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
2011 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2013 static inline size_t HUFv06_decodeStreamX2(BYTE* p, BITv06_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv06_DEltX2* const dt, const U32 dtLog)
2015 BYTE* const pStart = p;
2017 /* up to 4 symbols at a time */
2018 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-4)) {
2019 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr);
2020 HUFv06_DECODE_SYMBOLX2_1(p, bitDPtr);
2021 HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr);
2022 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2025 /* closer to the end */
2026 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd))
2027 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2029 /* no more data to retrieve from bitstream, hence no need to reload */
2031 HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2036 size_t HUFv06_decompress1X2_usingDTable(
2037 void* dst, size_t dstSize,
2038 const void* cSrc, size_t cSrcSize,
2041 BYTE* op = (BYTE*)dst;
2042 BYTE* const oend = op + dstSize;
2043 const U32 dtLog = DTable[0];
2044 const void* dtPtr = DTable;
2045 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr)+1;
2046 BITv06_DStream_t bitD;
2048 { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize);
2049 if (HUFv06_isError(errorCode)) return errorCode; }
2051 HUFv06_decodeStreamX2(op, &bitD, oend, dt, dtLog);
2054 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected);
2059 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2061 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG);
2062 const BYTE* ip = (const BYTE*) cSrc;
2064 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize);
2065 if (HUFv06_isError(errorCode)) return errorCode;
2066 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2068 cSrcSize -= errorCode;
2070 return HUFv06_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2074 size_t HUFv06_decompress4X2_usingDTable(
2075 void* dst, size_t dstSize,
2076 const void* cSrc, size_t cSrcSize,
2080 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2082 { const BYTE* const istart = (const BYTE*) cSrc;
2083 BYTE* const ostart = (BYTE*) dst;
2084 BYTE* const oend = ostart + dstSize;
2085 const void* const dtPtr = DTable;
2086 const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr) +1;
2087 const U32 dtLog = DTable[0];
2091 BITv06_DStream_t bitD1;
2092 BITv06_DStream_t bitD2;
2093 BITv06_DStream_t bitD3;
2094 BITv06_DStream_t bitD4;
2095 const size_t length1 = MEM_readLE16(istart);
2096 const size_t length2 = MEM_readLE16(istart+2);
2097 const size_t length3 = MEM_readLE16(istart+4);
2099 const BYTE* const istart1 = istart + 6; /* jumpTable */
2100 const BYTE* const istart2 = istart1 + length1;
2101 const BYTE* const istart3 = istart2 + length2;
2102 const BYTE* const istart4 = istart3 + length3;
2103 const size_t segmentSize = (dstSize+3) / 4;
2104 BYTE* const opStart2 = ostart + segmentSize;
2105 BYTE* const opStart3 = opStart2 + segmentSize;
2106 BYTE* const opStart4 = opStart3 + segmentSize;
2108 BYTE* op2 = opStart2;
2109 BYTE* op3 = opStart3;
2110 BYTE* op4 = opStart4;
2113 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2114 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2115 errorCode = BITv06_initDStream(&bitD1, istart1, length1);
2116 if (HUFv06_isError(errorCode)) return errorCode;
2117 errorCode = BITv06_initDStream(&bitD2, istart2, length2);
2118 if (HUFv06_isError(errorCode)) return errorCode;
2119 errorCode = BITv06_initDStream(&bitD3, istart3, length3);
2120 if (HUFv06_isError(errorCode)) return errorCode;
2121 errorCode = BITv06_initDStream(&bitD4, istart4, length4);
2122 if (HUFv06_isError(errorCode)) return errorCode;
2124 /* 16-32 symbols per loop (4-8 symbols per stream) */
2125 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2126 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) {
2127 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1);
2128 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2);
2129 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3);
2130 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4);
2131 HUFv06_DECODE_SYMBOLX2_1(op1, &bitD1);
2132 HUFv06_DECODE_SYMBOLX2_1(op2, &bitD2);
2133 HUFv06_DECODE_SYMBOLX2_1(op3, &bitD3);
2134 HUFv06_DECODE_SYMBOLX2_1(op4, &bitD4);
2135 HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1);
2136 HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2);
2137 HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3);
2138 HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4);
2139 HUFv06_DECODE_SYMBOLX2_0(op1, &bitD1);
2140 HUFv06_DECODE_SYMBOLX2_0(op2, &bitD2);
2141 HUFv06_DECODE_SYMBOLX2_0(op3, &bitD3);
2142 HUFv06_DECODE_SYMBOLX2_0(op4, &bitD4);
2143 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2146 /* check corruption */
2147 if (op1 > opStart2) return ERROR(corruption_detected);
2148 if (op2 > opStart3) return ERROR(corruption_detected);
2149 if (op3 > opStart4) return ERROR(corruption_detected);
2150 /* note : op4 supposed already verified within main loop */
2152 /* finish bitStreams one by one */
2153 HUFv06_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2154 HUFv06_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2155 HUFv06_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2156 HUFv06_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2159 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4);
2160 if (!endSignal) return ERROR(corruption_detected);
2168 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2170 HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG);
2171 const BYTE* ip = (const BYTE*) cSrc;
2173 size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize);
2174 if (HUFv06_isError(errorCode)) return errorCode;
2175 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2177 cSrcSize -= errorCode;
2179 return HUFv06_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2183 /* *************************/
2184 /* double-symbols decoding */
2185 /* *************************/
2187 static void HUFv06_fillDTableX4Level2(HUFv06_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2188 const U32* rankValOrigin, const int minWeight,
2189 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2190 U32 nbBitsBaseline, U16 baseSeq)
2193 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2195 /* get pre-calculated rankVal */
2196 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2198 /* fill skipped values */
2200 U32 i, skipSize = rankVal[minWeight];
2201 MEM_writeLE16(&(DElt.sequence), baseSeq);
2202 DElt.nbBits = (BYTE)(consumed);
2204 for (i = 0; i < skipSize; i++)
2209 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2210 const U32 symbol = sortedSymbols[s].symbol;
2211 const U32 weight = sortedSymbols[s].weight;
2212 const U32 nbBits = nbBitsBaseline - weight;
2213 const U32 length = 1 << (sizeLog-nbBits);
2214 const U32 start = rankVal[weight];
2216 const U32 end = start + length;
2218 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2219 DElt.nbBits = (BYTE)(nbBits + consumed);
2221 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2223 rankVal[weight] += length;
2227 typedef U32 rankVal_t[HUFv06_ABSOLUTEMAX_TABLELOG][HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2229 static void HUFv06_fillDTableX4(HUFv06_DEltX4* DTable, const U32 targetLog,
2230 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2231 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2232 const U32 nbBitsBaseline)
2234 U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2235 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2236 const U32 minBits = nbBitsBaseline - maxWeight;
2239 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2242 for (s=0; s<sortedListSize; s++) {
2243 const U16 symbol = sortedList[s].symbol;
2244 const U32 weight = sortedList[s].weight;
2245 const U32 nbBits = nbBitsBaseline - weight;
2246 const U32 start = rankVal[weight];
2247 const U32 length = 1 << (targetLog-nbBits);
2249 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2251 int minWeight = nbBits + scaleLog;
2252 if (minWeight < 1) minWeight = 1;
2253 sortedRank = rankStart[minWeight];
2254 HUFv06_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2255 rankValOrigin[nbBits], minWeight,
2256 sortedList+sortedRank, sortedListSize-sortedRank,
2257 nbBitsBaseline, symbol);
2260 MEM_writeLE16(&(DElt.sequence), symbol);
2261 DElt.nbBits = (BYTE)(nbBits);
2264 const U32 end = start + length;
2265 for (u = start; u < end; u++) DTable[u] = DElt;
2267 rankVal[weight] += length;
2271 size_t HUFv06_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2273 BYTE weightList[HUFv06_MAX_SYMBOL_VALUE + 1];
2274 sortedSymbol_t sortedSymbol[HUFv06_MAX_SYMBOL_VALUE + 1];
2275 U32 rankStats[HUFv06_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2276 U32 rankStart0[HUFv06_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2277 U32* const rankStart = rankStart0+1;
2279 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2280 const U32 memLog = DTable[0];
2282 void* dtPtr = DTable;
2283 HUFv06_DEltX4* const dt = ((HUFv06_DEltX4*)dtPtr) + 1;
2285 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
2286 if (memLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2287 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */
2289 iSize = HUFv06_readStats(weightList, HUFv06_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2290 if (HUFv06_isError(iSize)) return iSize;
2293 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2295 /* find maxWeight */
2296 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2298 /* Get start index of each weight */
2299 { U32 w, nextRankStart = 0;
2300 for (w=1; w<maxW+1; w++) {
2301 U32 current = nextRankStart;
2302 nextRankStart += rankStats[w];
2303 rankStart[w] = current;
2305 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2306 sizeOfSort = nextRankStart;
2309 /* sort symbols by weight */
2311 for (s=0; s<nbSymbols; s++) {
2312 U32 const w = weightList[s];
2313 U32 const r = rankStart[w]++;
2314 sortedSymbol[r].symbol = (BYTE)s;
2315 sortedSymbol[r].weight = (BYTE)w;
2317 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2321 { U32* const rankVal0 = rankVal[0];
2322 { int const rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2323 U32 nextRankVal = 0;
2325 for (w=1; w<maxW+1; w++) {
2326 U32 current = nextRankVal;
2327 nextRankVal += rankStats[w] << (w+rescale);
2328 rankVal0[w] = current;
2330 { U32 const minBits = tableLog+1 - maxW;
2332 for (consumed = minBits; consumed < memLog - minBits + 1; consumed++) {
2333 U32* const rankValPtr = rankVal[consumed];
2335 for (w = 1; w < maxW+1; w++) {
2336 rankValPtr[w] = rankVal0[w] >> consumed;
2339 HUFv06_fillDTableX4(dt, memLog,
2340 sortedSymbol, sizeOfSort,
2341 rankStart0, rankVal, maxW,
2348 static U32 HUFv06_decodeSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog)
2350 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2351 memcpy(op, dt+val, 2);
2352 BITv06_skipBits(DStream, dt[val].nbBits);
2353 return dt[val].length;
2356 static U32 HUFv06_decodeLastSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog)
2358 const size_t val = BITv06_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2359 memcpy(op, dt+val, 1);
2360 if (dt[val].length==1) BITv06_skipBits(DStream, dt[val].nbBits);
2362 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2363 BITv06_skipBits(DStream, dt[val].nbBits);
2364 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2365 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 */
2371 #define HUFv06_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2372 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2374 #define HUFv06_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2375 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2376 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2378 #define HUFv06_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2380 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2382 static inline size_t HUFv06_decodeStreamX4(BYTE* p, BITv06_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv06_DEltX4* const dt, const U32 dtLog)
2384 BYTE* const pStart = p;
2386 /* up to 8 symbols at a time */
2387 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd-7)) {
2388 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr);
2389 HUFv06_DECODE_SYMBOLX4_1(p, bitDPtr);
2390 HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr);
2391 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr);
2394 /* closer to the end */
2395 while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-2))
2396 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr);
2399 HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2402 p += HUFv06_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2408 size_t HUFv06_decompress1X4_usingDTable(
2409 void* dst, size_t dstSize,
2410 const void* cSrc, size_t cSrcSize,
2413 const BYTE* const istart = (const BYTE*) cSrc;
2414 BYTE* const ostart = (BYTE*) dst;
2415 BYTE* const oend = ostart + dstSize;
2417 const U32 dtLog = DTable[0];
2418 const void* const dtPtr = DTable;
2419 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1;
2422 BITv06_DStream_t bitD;
2423 { size_t const errorCode = BITv06_initDStream(&bitD, istart, cSrcSize);
2424 if (HUFv06_isError(errorCode)) return errorCode; }
2427 HUFv06_decodeStreamX4(ostart, &bitD, oend, dt, dtLog);
2430 if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected);
2436 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2438 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG);
2439 const BYTE* ip = (const BYTE*) cSrc;
2441 size_t const hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize);
2442 if (HUFv06_isError(hSize)) return hSize;
2443 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2447 return HUFv06_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2450 size_t HUFv06_decompress4X4_usingDTable(
2451 void* dst, size_t dstSize,
2452 const void* cSrc, size_t cSrcSize,
2455 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2457 { const BYTE* const istart = (const BYTE*) cSrc;
2458 BYTE* const ostart = (BYTE*) dst;
2459 BYTE* const oend = ostart + dstSize;
2460 const void* const dtPtr = DTable;
2461 const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1;
2462 const U32 dtLog = DTable[0];
2466 BITv06_DStream_t bitD1;
2467 BITv06_DStream_t bitD2;
2468 BITv06_DStream_t bitD3;
2469 BITv06_DStream_t bitD4;
2470 const size_t length1 = MEM_readLE16(istart);
2471 const size_t length2 = MEM_readLE16(istart+2);
2472 const size_t length3 = MEM_readLE16(istart+4);
2474 const BYTE* const istart1 = istart + 6; /* jumpTable */
2475 const BYTE* const istart2 = istart1 + length1;
2476 const BYTE* const istart3 = istart2 + length2;
2477 const BYTE* const istart4 = istart3 + length3;
2478 const size_t segmentSize = (dstSize+3) / 4;
2479 BYTE* const opStart2 = ostart + segmentSize;
2480 BYTE* const opStart3 = opStart2 + segmentSize;
2481 BYTE* const opStart4 = opStart3 + segmentSize;
2483 BYTE* op2 = opStart2;
2484 BYTE* op3 = opStart3;
2485 BYTE* op4 = opStart4;
2488 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2489 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2490 errorCode = BITv06_initDStream(&bitD1, istart1, length1);
2491 if (HUFv06_isError(errorCode)) return errorCode;
2492 errorCode = BITv06_initDStream(&bitD2, istart2, length2);
2493 if (HUFv06_isError(errorCode)) return errorCode;
2494 errorCode = BITv06_initDStream(&bitD3, istart3, length3);
2495 if (HUFv06_isError(errorCode)) return errorCode;
2496 errorCode = BITv06_initDStream(&bitD4, istart4, length4);
2497 if (HUFv06_isError(errorCode)) return errorCode;
2499 /* 16-32 symbols per loop (4-8 symbols per stream) */
2500 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2501 for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) {
2502 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1);
2503 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2);
2504 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3);
2505 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4);
2506 HUFv06_DECODE_SYMBOLX4_1(op1, &bitD1);
2507 HUFv06_DECODE_SYMBOLX4_1(op2, &bitD2);
2508 HUFv06_DECODE_SYMBOLX4_1(op3, &bitD3);
2509 HUFv06_DECODE_SYMBOLX4_1(op4, &bitD4);
2510 HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1);
2511 HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2);
2512 HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3);
2513 HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4);
2514 HUFv06_DECODE_SYMBOLX4_0(op1, &bitD1);
2515 HUFv06_DECODE_SYMBOLX4_0(op2, &bitD2);
2516 HUFv06_DECODE_SYMBOLX4_0(op3, &bitD3);
2517 HUFv06_DECODE_SYMBOLX4_0(op4, &bitD4);
2519 endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2522 /* check corruption */
2523 if (op1 > opStart2) return ERROR(corruption_detected);
2524 if (op2 > opStart3) return ERROR(corruption_detected);
2525 if (op3 > opStart4) return ERROR(corruption_detected);
2526 /* note : op4 supposed already verified within main loop */
2528 /* finish bitStreams one by one */
2529 HUFv06_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2530 HUFv06_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2531 HUFv06_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2532 HUFv06_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2535 endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4);
2536 if (!endSignal) return ERROR(corruption_detected);
2544 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2546 HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG);
2547 const BYTE* ip = (const BYTE*) cSrc;
2549 size_t hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize);
2550 if (HUFv06_isError(hSize)) return hSize;
2551 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2555 return HUFv06_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2561 /* ********************************/
2562 /* Generic decompression selector */
2563 /* ********************************/
2565 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2566 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2568 /* single, double, quad */
2569 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2570 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2571 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2572 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2573 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2574 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2575 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2576 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2577 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2578 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2579 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2580 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2581 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2582 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2583 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2584 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2587 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2589 size_t HUFv06_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2591 static const decompressionAlgo decompress[3] = { HUFv06_decompress4X2, HUFv06_decompress4X4, NULL };
2592 U32 Dtime[3]; /* decompression time estimation */
2594 /* validation checks */
2595 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2596 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2597 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2598 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2600 /* decoder timing evaluation */
2601 { U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2602 U32 const D256 = (U32)(dstSize >> 8);
2603 U32 n; for (n=0; n<3; n++)
2604 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2607 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2610 if (Dtime[1] < Dtime[0]) algoNb = 1;
2611 /* if (Dtime[2] < Dtime[algoNb]) algoNb = 2; */ /* current speed of HUFv06_decompress4X6 is not good */
2612 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2615 /* return HUFv06_decompress4X2(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams single-symbol decoding */
2616 /* return HUFv06_decompress4X4(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams double-symbols decoding */
2617 /* return HUFv06_decompress4X6(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams quad-symbols decoding */
2620 Common functions of Zstd compression library
2621 Copyright (C) 2015-2016, Yann Collet.
2623 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2625 Redistribution and use in source and binary forms, with or without
2626 modification, are permitted provided that the following conditions are
2628 * Redistributions of source code must retain the above copyright
2629 notice, this list of conditions and the following disclaimer.
2630 * Redistributions in binary form must reproduce the above
2631 copyright notice, this list of conditions and the following disclaimer
2632 in the documentation and/or other materials provided with the
2634 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2635 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2636 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2637 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2638 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2639 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2640 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2641 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2642 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2643 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2644 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2646 You can contact the author at :
2647 - zstd homepage : https://facebook.github.io/zstd/
2651 /*-****************************************
2653 ******************************************/
2655 /*-****************************************
2656 * ZSTD Error Management
2657 ******************************************/
2658 /*! ZSTDv06_isError() :
2659 * tells if a return value is an error code */
2660 unsigned ZSTDv06_isError(size_t code) { return ERR_isError(code); }
2662 /*! ZSTDv06_getErrorName() :
2663 * provides error code string from function result (useful for debugging) */
2664 const char* ZSTDv06_getErrorName(size_t code) { return ERR_getErrorName(code); }
2667 /* **************************************************************
2668 * ZBUFF Error Management
2669 ****************************************************************/
2670 unsigned ZBUFFv06_isError(size_t errorCode) { return ERR_isError(errorCode); }
2672 const char* ZBUFFv06_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2674 zstd - standard compression library
2675 Copyright (C) 2014-2016, Yann Collet.
2677 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2679 Redistribution and use in source and binary forms, with or without
2680 modification, are permitted provided that the following conditions are
2682 * Redistributions of source code must retain the above copyright
2683 notice, this list of conditions and the following disclaimer.
2684 * Redistributions in binary form must reproduce the above
2685 copyright notice, this list of conditions and the following disclaimer
2686 in the documentation and/or other materials provided with the
2688 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2689 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2690 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2691 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2692 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2693 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2694 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2695 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2696 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2697 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2698 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2700 You can contact the author at :
2701 - zstd homepage : https://facebook.github.io/zstd
2704 /* ***************************************************************
2706 *****************************************************************/
2709 * Select how default decompression function ZSTDv06_decompress() will allocate memory,
2710 * in memory stack (0), or in memory heap (1, requires malloc())
2712 #ifndef ZSTDv06_HEAPMODE
2713 # define ZSTDv06_HEAPMODE 1
2718 /*-*******************************************************
2719 * Compiler specifics
2720 *********************************************************/
2721 #ifdef _MSC_VER /* Visual Studio */
2722 # include <intrin.h> /* For Visual 2005 */
2723 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2724 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2728 /*-*************************************
2730 ***************************************/
2731 #define ZSTDv06_isError ERR_isError /* for inlining */
2732 #define FSEv06_isError ERR_isError
2733 #define HUFv06_isError ERR_isError
2736 /*_*******************************************************
2738 **********************************************************/
2739 static void ZSTDv06_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2742 /*-*************************************************************
2743 * Context management
2744 ***************************************************************/
2745 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2746 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTDv06_dStage;
2748 struct ZSTDv06_DCtx_s
2750 FSEv06_DTable LLTable[FSEv06_DTABLE_SIZE_U32(LLFSELog)];
2751 FSEv06_DTable OffTable[FSEv06_DTABLE_SIZE_U32(OffFSELog)];
2752 FSEv06_DTable MLTable[FSEv06_DTABLE_SIZE_U32(MLFSELog)];
2753 unsigned hufTableX4[HUFv06_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)];
2754 const void* previousDstEnd;
2757 const void* dictEnd;
2760 ZSTDv06_frameParams fParams;
2761 blockType_t bType; /* used in ZSTDv06_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2762 ZSTDv06_dStage stage;
2763 U32 flagRepeatTable;
2766 BYTE litBuffer[ZSTDv06_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];
2767 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX];
2768 }; /* typedef'd to ZSTDv06_DCtx within "zstd_static.h" */
2770 size_t ZSTDv06_sizeofDCtx (void); /* Hidden declaration */
2771 size_t ZSTDv06_sizeofDCtx (void) { return sizeof(ZSTDv06_DCtx); }
2773 size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx)
2775 dctx->expected = ZSTDv06_frameHeaderSize_min;
2776 dctx->stage = ZSTDds_getFrameHeaderSize;
2777 dctx->previousDstEnd = NULL;
2780 dctx->dictEnd = NULL;
2781 dctx->hufTableX4[0] = ZSTD_HUFFDTABLE_CAPACITY_LOG;
2782 dctx->flagRepeatTable = 0;
2786 ZSTDv06_DCtx* ZSTDv06_createDCtx(void)
2788 ZSTDv06_DCtx* dctx = (ZSTDv06_DCtx*)malloc(sizeof(ZSTDv06_DCtx));
2789 if (dctx==NULL) return NULL;
2790 ZSTDv06_decompressBegin(dctx);
2794 size_t ZSTDv06_freeDCtx(ZSTDv06_DCtx* dctx)
2797 return 0; /* reserved as a potential error code in the future */
2800 void ZSTDv06_copyDCtx(ZSTDv06_DCtx* dstDCtx, const ZSTDv06_DCtx* srcDCtx)
2802 memcpy(dstDCtx, srcDCtx,
2803 sizeof(ZSTDv06_DCtx) - (ZSTDv06_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH + ZSTDv06_frameHeaderSize_max)); /* no need to copy workspace */
2807 /*-*************************************************************
2808 * Decompression section
2809 ***************************************************************/
2811 /* Frame format description
2812 Frame Header - [ Block Header - Block ] - Frame End
2814 - 4 bytes - Magic Number : ZSTDv06_MAGICNUMBER (defined within zstd_static.h)
2815 - 1 byte - Frame Descriptor
2817 - 3 bytes, starting with a 2-bits descriptor
2818 Uncompressed, Compressed, Frame End, unused
2820 See Block Format Description
2822 - 3 bytes, compatible with Block Header
2829 bit 0-3 : windowLog - ZSTDv06_WINDOWLOG_ABSOLUTEMIN (see zstd_internal.h)
2830 bit 4 : minmatch 4(0) or 3(1)
2831 bit 5 : reserved (must be zero)
2832 bit 6-7 : Frame content size : unknown, 1 byte, 2 bytes, 8 bytes
2834 Optional : content size (0, 1, 2 or 8 bytes)
2842 /* Compressed Block, format description
2844 Block = Literal Section - Sequences Section
2845 Prerequisite : size of (compressed) block, maximum size of regenerated data
2849 1.1) Header : 1-5 bytes
2851 00 compressed by Huff0
2853 10 is Raw (uncompressed)
2855 Note : using 01 => Huff0 with precomputed table ?
2856 Note : delta map ? => compressed ?
2858 1.1.1) Huff0-compressed literal block : 3-5 bytes
2859 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2860 srcSize < 1 KB => 3 bytes (2-2-10-10)
2861 srcSize < 16KB => 4 bytes (2-2-14-14)
2862 else => 5 bytes (2-2-18-18)
2863 big endian convention
2865 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2866 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2867 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2869 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2873 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2874 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
2875 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2877 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2881 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2882 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2883 srcSize < 1 KB => 3 bytes (2-2-10-10)
2884 srcSize < 16KB => 4 bytes (2-2-14-14)
2885 else => 5 bytes (2-2-18-18)
2886 big endian convention
2888 1- CTable available (stored into workspace ?)
2889 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2892 1.2) Literal block content
2894 1.2.1) Huff0 block, using sizes from header
2897 1.2.2) Huff0 block, using prepared table
2904 2) Sequences section
2908 /** ZSTDv06_frameHeaderSize() :
2909 * srcSize must be >= ZSTDv06_frameHeaderSize_min.
2910 * @return : size of the Frame Header */
2911 static size_t ZSTDv06_frameHeaderSize(const void* src, size_t srcSize)
2913 if (srcSize < ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong);
2914 { U32 const fcsId = (((const BYTE*)src)[4]) >> 6;
2915 return ZSTDv06_frameHeaderSize_min + ZSTDv06_fcs_fieldSize[fcsId]; }
2919 /** ZSTDv06_getFrameParams() :
2920 * decode Frame Header, or provide expected `srcSize`.
2921 * @return : 0, `fparamsPtr` is correctly filled,
2922 * >0, `srcSize` is too small, result is expected `srcSize`,
2923 * or an error code, which can be tested using ZSTDv06_isError() */
2924 size_t ZSTDv06_getFrameParams(ZSTDv06_frameParams* fparamsPtr, const void* src, size_t srcSize)
2926 const BYTE* ip = (const BYTE*)src;
2928 if (srcSize < ZSTDv06_frameHeaderSize_min) return ZSTDv06_frameHeaderSize_min;
2929 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown);
2931 /* ensure there is enough `srcSize` to fully read/decode frame header */
2932 { size_t const fhsize = ZSTDv06_frameHeaderSize(src, srcSize);
2933 if (srcSize < fhsize) return fhsize; }
2935 memset(fparamsPtr, 0, sizeof(*fparamsPtr));
2936 { BYTE const frameDesc = ip[4];
2937 fparamsPtr->windowLog = (frameDesc & 0xF) + ZSTDv06_WINDOWLOG_ABSOLUTEMIN;
2938 if ((frameDesc & 0x20) != 0) return ERROR(frameParameter_unsupported); /* reserved 1 bit */
2939 switch(frameDesc >> 6) /* fcsId */
2941 default: /* impossible */
2942 case 0 : fparamsPtr->frameContentSize = 0; break;
2943 case 1 : fparamsPtr->frameContentSize = ip[5]; break;
2944 case 2 : fparamsPtr->frameContentSize = MEM_readLE16(ip+5)+256; break;
2945 case 3 : fparamsPtr->frameContentSize = MEM_readLE64(ip+5); break;
2951 /** ZSTDv06_decodeFrameHeader() :
2952 * `srcSize` must be the size provided by ZSTDv06_frameHeaderSize().
2953 * @return : 0 if success, or an error code, which can be tested using ZSTDv06_isError() */
2954 static size_t ZSTDv06_decodeFrameHeader(ZSTDv06_DCtx* zc, const void* src, size_t srcSize)
2956 size_t const result = ZSTDv06_getFrameParams(&(zc->fParams), src, srcSize);
2957 if ((MEM_32bits()) && (zc->fParams.windowLog > 25)) return ERROR(frameParameter_unsupported);
2964 blockType_t blockType;
2966 } blockProperties_t;
2968 /*! ZSTDv06_getcBlockSize() :
2969 * Provides the size of compressed block from block header `src` */
2970 static size_t ZSTDv06_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2972 const BYTE* const in = (const BYTE*)src;
2975 if (srcSize < ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
2977 bpPtr->blockType = (blockType_t)((*in) >> 6);
2978 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2979 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2981 if (bpPtr->blockType == bt_end) return 0;
2982 if (bpPtr->blockType == bt_rle) return 1;
2987 static size_t ZSTDv06_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2989 if (dst==NULL) return ERROR(dstSize_tooSmall);
2990 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
2991 memcpy(dst, src, srcSize);
2996 /*! ZSTDv06_decodeLiteralsBlock() :
2997 @return : nb of bytes read from src (< srcSize ) */
2998 static size_t ZSTDv06_decodeLiteralsBlock(ZSTDv06_DCtx* dctx,
2999 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
3001 const BYTE* const istart = (const BYTE*) src;
3003 /* any compressed block with literals segment must be at least this size */
3004 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3006 switch(istart[0]>> 6)
3009 { size_t litSize, litCSize, singleStream=0;
3010 U32 lhSize = ((istart[0]) >> 4) & 3;
3011 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3014 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3015 /* 2 - 2 - 10 - 10 */
3017 singleStream = istart[0] & 16;
3018 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3019 litCSize = ((istart[1] & 3) << 8) + istart[2];
3022 /* 2 - 2 - 14 - 14 */
3024 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3025 litCSize = ((istart[2] & 63) << 8) + istart[3];
3028 /* 2 - 2 - 18 - 18 */
3030 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3031 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
3034 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected);
3035 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3037 if (HUFv06_isError(singleStream ?
3038 HUFv06_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3039 HUFv06_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3040 return ERROR(corruption_detected);
3042 dctx->litPtr = dctx->litBuffer;
3043 dctx->litSize = litSize;
3044 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3045 return litCSize + lhSize;
3048 { size_t litSize, litCSize;
3049 U32 lhSize = ((istart[0]) >> 4) & 3;
3050 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
3051 return ERROR(corruption_detected);
3052 if (!dctx->flagRepeatTable)
3053 return ERROR(dictionary_corrupted);
3055 /* 2 - 2 - 10 - 10 */
3057 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3058 litCSize = ((istart[1] & 3) << 8) + istart[2];
3059 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3061 { size_t const errorCode = HUFv06_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4);
3062 if (HUFv06_isError(errorCode)) return ERROR(corruption_detected);
3064 dctx->litPtr = dctx->litBuffer;
3065 dctx->litSize = litSize;
3066 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3067 return litCSize + lhSize;
3071 U32 lhSize = ((istart[0]) >> 4) & 3;
3074 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3076 litSize = istart[0] & 31;
3079 litSize = ((istart[0] & 15) << 8) + istart[1];
3082 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3086 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
3087 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3088 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3089 dctx->litPtr = dctx->litBuffer;
3090 dctx->litSize = litSize;
3091 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3092 return lhSize+litSize;
3094 /* direct reference into compressed stream */
3095 dctx->litPtr = istart+lhSize;
3096 dctx->litSize = litSize;
3097 return lhSize+litSize;
3101 U32 lhSize = ((istart[0]) >> 4) & 3;
3104 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3106 litSize = istart[0] & 31;
3109 litSize = ((istart[0] & 15) << 8) + istart[1];
3112 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3113 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3116 if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected);
3117 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3118 dctx->litPtr = dctx->litBuffer;
3119 dctx->litSize = litSize;
3123 return ERROR(corruption_detected); /* impossible */
3128 /*! ZSTDv06_buildSeqTable() :
3129 @return : nb bytes read from src,
3130 or an error code if it fails, testable with ZSTDv06_isError()
3132 static size_t ZSTDv06_buildSeqTable(FSEv06_DTable* DTable, U32 type, U32 max, U32 maxLog,
3133 const void* src, size_t srcSize,
3134 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3138 case FSEv06_ENCODING_RLE :
3139 if (!srcSize) return ERROR(srcSize_wrong);
3140 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3141 FSEv06_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */
3143 case FSEv06_ENCODING_RAW :
3144 FSEv06_buildDTable(DTable, defaultNorm, max, defaultLog);
3146 case FSEv06_ENCODING_STATIC:
3147 if (!flagRepeatTable) return ERROR(corruption_detected);
3149 default : /* impossible */
3150 case FSEv06_ENCODING_DYNAMIC :
3153 size_t const headerSize = FSEv06_readNCount(norm, &max, &tableLog, src, srcSize);
3154 if (FSEv06_isError(headerSize)) return ERROR(corruption_detected);
3155 if (tableLog > maxLog) return ERROR(corruption_detected);
3156 FSEv06_buildDTable(DTable, norm, max, tableLog);
3162 static size_t ZSTDv06_decodeSeqHeaders(int* nbSeqPtr,
3163 FSEv06_DTable* DTableLL, FSEv06_DTable* DTableML, FSEv06_DTable* DTableOffb, U32 flagRepeatTable,
3164 const void* src, size_t srcSize)
3166 const BYTE* const istart = (const BYTE*)src;
3167 const BYTE* const iend = istart + srcSize;
3168 const BYTE* ip = istart;
3171 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3174 { int nbSeq = *ip++;
3175 if (!nbSeq) { *nbSeqPtr=0; return 1; }
3177 if (nbSeq == 0xFF) {
3178 if (ip+2 > iend) return ERROR(srcSize_wrong);
3179 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3181 if (ip >= iend) return ERROR(srcSize_wrong);
3182 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3188 /* FSE table descriptors */
3189 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 */
3190 { U32 const LLtype = *ip >> 6;
3191 U32 const Offtype = (*ip >> 4) & 3;
3192 U32 const MLtype = (*ip >> 2) & 3;
3196 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3197 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3200 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableOffb, Offtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3201 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3204 { size_t const bhSize = ZSTDv06_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3205 if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3220 BITv06_DStream_t DStream;
3221 FSEv06_DState_t stateLL;
3222 FSEv06_DState_t stateOffb;
3223 FSEv06_DState_t stateML;
3224 size_t prevOffset[ZSTDv06_REP_INIT];
3229 static void ZSTDv06_decodeSequence(seq_t* seq, seqState_t* seqState)
3231 /* Literal length */
3232 U32 const llCode = FSEv06_peekSymbol(&(seqState->stateLL));
3233 U32 const mlCode = FSEv06_peekSymbol(&(seqState->stateML));
3234 U32 const ofCode = FSEv06_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3236 U32 const llBits = LL_bits[llCode];
3237 U32 const mlBits = ML_bits[mlCode];
3238 U32 const ofBits = ofCode;
3239 U32 const totalBits = llBits+mlBits+ofBits;
3241 static const U32 LL_base[MaxLL+1] = {
3242 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3243 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3244 0x2000, 0x4000, 0x8000, 0x10000 };
3246 static const U32 ML_base[MaxML+1] = {
3247 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3248 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
3249 32, 34, 36, 38, 40, 44, 48, 56, 64, 80, 96, 0x80, 0x100, 0x200, 0x400, 0x800,
3250 0x1000, 0x2000, 0x4000, 0x8000, 0x10000 };
3252 static const U32 OF_base[MaxOff+1] = {
3253 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F,
3254 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF,
3255 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
3256 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1 };
3263 offset = OF_base[ofCode] + BITv06_readBits(&(seqState->DStream), ofBits); /* <= 26 bits */
3264 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream));
3267 if (offset < ZSTDv06_REP_NUM) {
3268 if (llCode == 0 && offset <= 1) offset = 1-offset;
3271 size_t temp = seqState->prevOffset[offset];
3273 seqState->prevOffset[2] = seqState->prevOffset[1];
3275 seqState->prevOffset[1] = seqState->prevOffset[0];
3276 seqState->prevOffset[0] = offset = temp;
3279 offset = seqState->prevOffset[0];
3282 offset -= ZSTDv06_REP_MOVE;
3283 seqState->prevOffset[2] = seqState->prevOffset[1];
3284 seqState->prevOffset[1] = seqState->prevOffset[0];
3285 seqState->prevOffset[0] = offset;
3287 seq->offset = offset;
3290 seq->matchLength = ML_base[mlCode] + MINMATCH + ((mlCode>31) ? BITv06_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */
3291 if (MEM_32bits() && (mlBits+llBits>24)) BITv06_reloadDStream(&(seqState->DStream));
3293 seq->litLength = LL_base[llCode] + ((llCode>15) ? BITv06_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */
3295 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv06_reloadDStream(&(seqState->DStream));
3297 /* ANS state update */
3298 FSEv06_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */
3299 FSEv06_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */
3300 if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream)); /* <= 18 bits */
3301 FSEv06_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */
3305 static size_t ZSTDv06_execSequence(BYTE* op,
3306 BYTE* const oend, seq_t sequence,
3307 const BYTE** litPtr, const BYTE* const litLimit,
3308 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3310 BYTE* const oLitEnd = op + sequence.litLength;
3311 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3312 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3313 BYTE* const oend_8 = oend-8;
3314 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3315 const BYTE* match = oLitEnd - sequence.offset;
3318 size_t const seqLength = sequence.litLength + sequence.matchLength;
3320 if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3321 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
3322 /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
3323 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
3325 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3326 if (iLitEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
3329 ZSTDv06_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3331 *litPtr = iLitEnd; /* update for next sequence */
3334 if (sequence.offset > (size_t)(oLitEnd - base)) {
3335 /* offset beyond prefix */
3336 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3337 match = dictEnd - (base-match);
3338 if (match + sequence.matchLength <= dictEnd) {
3339 memmove(oLitEnd, match, sequence.matchLength);
3340 return sequenceLength;
3342 /* span extDict & currentPrefixSegment */
3343 { size_t const length1 = dictEnd - match;
3344 memmove(oLitEnd, match, length1);
3345 op = oLitEnd + length1;
3346 sequence.matchLength -= length1;
3348 if (op > oend_8 || sequence.matchLength < MINMATCH) {
3349 while (op < oMatchEnd) *op++ = *match++;
3350 return sequenceLength;
3353 /* Requirement: op <= oend_8 */
3355 /* match within prefix */
3356 if (sequence.offset < 8) {
3357 /* close range match, overlap */
3358 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3359 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
3360 int const sub2 = dec64table[sequence.offset];
3365 match += dec32table[sequence.offset];
3366 ZSTDv06_copy4(op+4, match);
3369 ZSTDv06_copy8(op, match);
3371 op += 8; match += 8;
3373 if (oMatchEnd > oend-(16-MINMATCH)) {
3375 ZSTDv06_wildcopy(op, match, oend_8 - op);
3376 match += oend_8 - op;
3379 while (op < oMatchEnd) *op++ = *match++;
3381 ZSTDv06_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3383 return sequenceLength;
3387 static size_t ZSTDv06_decompressSequences(
3389 void* dst, size_t maxDstSize,
3390 const void* seqStart, size_t seqSize)
3392 const BYTE* ip = (const BYTE*)seqStart;
3393 const BYTE* const iend = ip + seqSize;
3394 BYTE* const ostart = (BYTE*)dst;
3395 BYTE* const oend = ostart + maxDstSize;
3397 const BYTE* litPtr = dctx->litPtr;
3398 const BYTE* const litEnd = litPtr + dctx->litSize;
3399 FSEv06_DTable* DTableLL = dctx->LLTable;
3400 FSEv06_DTable* DTableML = dctx->MLTable;
3401 FSEv06_DTable* DTableOffb = dctx->OffTable;
3402 const BYTE* const base = (const BYTE*) (dctx->base);
3403 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3404 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3407 /* Build Decoding Tables */
3408 { size_t const seqHSize = ZSTDv06_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->flagRepeatTable, ip, seqSize);
3409 if (ZSTDv06_isError(seqHSize)) return seqHSize;
3411 dctx->flagRepeatTable = 0;
3414 /* Regen sequences */
3417 seqState_t seqState;
3419 memset(&sequence, 0, sizeof(sequence));
3420 sequence.offset = REPCODE_STARTVALUE;
3421 { U32 i; for (i=0; i<ZSTDv06_REP_INIT; i++) seqState.prevOffset[i] = REPCODE_STARTVALUE; }
3422 { size_t const errorCode = BITv06_initDStream(&(seqState.DStream), ip, iend-ip);
3423 if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3424 FSEv06_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3425 FSEv06_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3426 FSEv06_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3428 for ( ; (BITv06_reloadDStream(&(seqState.DStream)) <= BITv06_DStream_completed) && nbSeq ; ) {
3430 ZSTDv06_decodeSequence(&sequence, &seqState);
3433 static BYTE* start = NULL;
3434 if (start==NULL) start = op;
3435 size_t pos = (size_t)(op-start);
3436 if ((pos >= 5810037) && (pos < 5810400))
3437 printf("Dpos %6u :%5u literals & match %3u bytes at distance %6u \n",
3438 pos, (U32)sequence.litLength, (U32)sequence.matchLength, (U32)sequence.offset);
3441 { size_t const oneSeqSize = ZSTDv06_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3442 if (ZSTDv06_isError(oneSeqSize)) return oneSeqSize;
3446 /* check if reached exact end */
3447 if (nbSeq) return ERROR(corruption_detected);
3450 /* last literal segment */
3451 { size_t const lastLLSize = litEnd - litPtr;
3452 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3453 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3454 if (lastLLSize > 0) {
3455 memcpy(op, litPtr, lastLLSize);
3464 static void ZSTDv06_checkContinuity(ZSTDv06_DCtx* dctx, const void* dst)
3466 if (dst != dctx->previousDstEnd) { /* not contiguous */
3467 dctx->dictEnd = dctx->previousDstEnd;
3468 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3470 dctx->previousDstEnd = dst;
3475 static size_t ZSTDv06_decompressBlock_internal(ZSTDv06_DCtx* dctx,
3476 void* dst, size_t dstCapacity,
3477 const void* src, size_t srcSize)
3478 { /* blockType == blockCompressed */
3479 const BYTE* ip = (const BYTE*)src;
3481 if (srcSize >= ZSTDv06_BLOCKSIZE_MAX) return ERROR(srcSize_wrong);
3483 /* Decode literals sub-block */
3484 { size_t const litCSize = ZSTDv06_decodeLiteralsBlock(dctx, src, srcSize);
3485 if (ZSTDv06_isError(litCSize)) return litCSize;
3487 srcSize -= litCSize;
3489 return ZSTDv06_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3493 size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx,
3494 void* dst, size_t dstCapacity,
3495 const void* src, size_t srcSize)
3497 ZSTDv06_checkContinuity(dctx, dst);
3498 return ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3502 /*! ZSTDv06_decompressFrame() :
3503 * `dctx` must be properly initialized */
3504 static size_t ZSTDv06_decompressFrame(ZSTDv06_DCtx* dctx,
3505 void* dst, size_t dstCapacity,
3506 const void* src, size_t srcSize)
3508 const BYTE* ip = (const BYTE*)src;
3509 const BYTE* const iend = ip + srcSize;
3510 BYTE* const ostart = (BYTE*)dst;
3512 BYTE* const oend = ostart + dstCapacity;
3513 size_t remainingSize = srcSize;
3514 blockProperties_t blockProperties = { bt_compressed, 0 };
3517 if (srcSize < ZSTDv06_frameHeaderSize_min+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
3520 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min);
3521 if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize;
3522 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
3523 if (ZSTDv06_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3524 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3527 /* Loop on each block */
3529 size_t decodedSize=0;
3530 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, iend-ip, &blockProperties);
3531 if (ZSTDv06_isError(cBlockSize)) return cBlockSize;
3533 ip += ZSTDv06_blockHeaderSize;
3534 remainingSize -= ZSTDv06_blockHeaderSize;
3535 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3537 switch(blockProperties.blockType)
3540 decodedSize = ZSTDv06_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3543 decodedSize = ZSTDv06_copyRawBlock(op, oend-op, ip, cBlockSize);
3546 return ERROR(GENERIC); /* not yet supported */
3550 if (remainingSize) return ERROR(srcSize_wrong);
3553 return ERROR(GENERIC); /* impossible */
3555 if (cBlockSize == 0) break; /* bt_end */
3557 if (ZSTDv06_isError(decodedSize)) return decodedSize;
3560 remainingSize -= cBlockSize;
3567 size_t ZSTDv06_decompress_usingPreparedDCtx(ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* refDCtx,
3568 void* dst, size_t dstCapacity,
3569 const void* src, size_t srcSize)
3571 ZSTDv06_copyDCtx(dctx, refDCtx);
3572 ZSTDv06_checkContinuity(dctx, dst);
3573 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3577 size_t ZSTDv06_decompress_usingDict(ZSTDv06_DCtx* dctx,
3578 void* dst, size_t dstCapacity,
3579 const void* src, size_t srcSize,
3580 const void* dict, size_t dictSize)
3582 ZSTDv06_decompressBegin_usingDict(dctx, dict, dictSize);
3583 ZSTDv06_checkContinuity(dctx, dst);
3584 return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3588 size_t ZSTDv06_decompressDCtx(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3590 return ZSTDv06_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3594 size_t ZSTDv06_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3596 #if defined(ZSTDv06_HEAPMODE) && (ZSTDv06_HEAPMODE==1)
3598 ZSTDv06_DCtx* dctx = ZSTDv06_createDCtx();
3599 if (dctx==NULL) return ERROR(memory_allocation);
3600 regenSize = ZSTDv06_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3601 ZSTDv06_freeDCtx(dctx);
3603 #else /* stack mode */
3605 return ZSTDv06_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3609 /* ZSTD_errorFrameSizeInfoLegacy() :
3610 assumes `cSize` and `dBound` are _not_ NULL */
3611 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3614 *dBound = ZSTD_CONTENTSIZE_ERROR;
3617 void ZSTDv06_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3619 const BYTE* ip = (const BYTE*)src;
3620 size_t remainingSize = srcSize;
3621 size_t nbBlocks = 0;
3622 blockProperties_t blockProperties = { bt_compressed, 0 };
3625 { size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, srcSize);
3626 if (ZSTDv06_isError(frameHeaderSize)) {
3627 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize);
3630 if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) {
3631 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3634 if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) {
3635 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3638 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3641 /* Loop on each block */
3643 size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, remainingSize, &blockProperties);
3644 if (ZSTDv06_isError(cBlockSize)) {
3645 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3649 ip += ZSTDv06_blockHeaderSize;
3650 remainingSize -= ZSTDv06_blockHeaderSize;
3651 if (cBlockSize > remainingSize) {
3652 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3656 if (cBlockSize == 0) break; /* bt_end */
3659 remainingSize -= cBlockSize;
3663 *cSize = ip - (const BYTE*)src;
3664 *dBound = nbBlocks * ZSTDv06_BLOCKSIZE_MAX;
3667 /*_******************************
3668 * Streaming Decompression API
3669 ********************************/
3670 size_t ZSTDv06_nextSrcSizeToDecompress(ZSTDv06_DCtx* dctx)
3672 return dctx->expected;
3675 size_t ZSTDv06_decompressContinue(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3678 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3679 if (dstCapacity) ZSTDv06_checkContinuity(dctx, dst);
3681 /* Decompress : frame header; part 1 */
3682 switch (dctx->stage)
3684 case ZSTDds_getFrameHeaderSize :
3685 if (srcSize != ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3686 dctx->headerSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min);
3687 if (ZSTDv06_isError(dctx->headerSize)) return dctx->headerSize;
3688 memcpy(dctx->headerBuffer, src, ZSTDv06_frameHeaderSize_min);
3689 if (dctx->headerSize > ZSTDv06_frameHeaderSize_min) {
3690 dctx->expected = dctx->headerSize - ZSTDv06_frameHeaderSize_min;
3691 dctx->stage = ZSTDds_decodeFrameHeader;
3694 dctx->expected = 0; /* not necessary to copy more */
3696 case ZSTDds_decodeFrameHeader:
3698 memcpy(dctx->headerBuffer + ZSTDv06_frameHeaderSize_min, src, dctx->expected);
3699 result = ZSTDv06_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
3700 if (ZSTDv06_isError(result)) return result;
3701 dctx->expected = ZSTDv06_blockHeaderSize;
3702 dctx->stage = ZSTDds_decodeBlockHeader;
3705 case ZSTDds_decodeBlockHeader:
3706 { blockProperties_t bp;
3707 size_t const cBlockSize = ZSTDv06_getcBlockSize(src, ZSTDv06_blockHeaderSize, &bp);
3708 if (ZSTDv06_isError(cBlockSize)) return cBlockSize;
3709 if (bp.blockType == bt_end) {
3711 dctx->stage = ZSTDds_getFrameHeaderSize;
3713 dctx->expected = cBlockSize;
3714 dctx->bType = bp.blockType;
3715 dctx->stage = ZSTDds_decompressBlock;
3719 case ZSTDds_decompressBlock:
3724 rSize = ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3727 rSize = ZSTDv06_copyRawBlock(dst, dstCapacity, src, srcSize);
3730 return ERROR(GENERIC); /* not yet handled */
3732 case bt_end : /* should never happen (filtered at phase 1) */
3736 return ERROR(GENERIC); /* impossible */
3738 dctx->stage = ZSTDds_decodeBlockHeader;
3739 dctx->expected = ZSTDv06_blockHeaderSize;
3740 if (ZSTDv06_isError(rSize)) return rSize;
3741 dctx->previousDstEnd = (char*)dst + rSize;
3745 return ERROR(GENERIC); /* impossible */
3750 static void ZSTDv06_refDictContent(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3752 dctx->dictEnd = dctx->previousDstEnd;
3753 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3755 dctx->previousDstEnd = (const char*)dict + dictSize;
3758 static size_t ZSTDv06_loadEntropy(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3760 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, litlengthHeaderSize;
3762 hSize = HUFv06_readDTableX4(dctx->hufTableX4, dict, dictSize);
3763 if (HUFv06_isError(hSize)) return ERROR(dictionary_corrupted);
3764 dict = (const char*)dict + hSize;
3767 { short offcodeNCount[MaxOff+1];
3768 U32 offcodeMaxValue=MaxOff, offcodeLog;
3769 offcodeHeaderSize = FSEv06_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize);
3770 if (FSEv06_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3771 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
3772 { size_t const errorCode = FSEv06_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
3773 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3774 dict = (const char*)dict + offcodeHeaderSize;
3775 dictSize -= offcodeHeaderSize;
3778 { short matchlengthNCount[MaxML+1];
3779 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3780 matchlengthHeaderSize = FSEv06_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize);
3781 if (FSEv06_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3782 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
3783 { size_t const errorCode = FSEv06_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
3784 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3785 dict = (const char*)dict + matchlengthHeaderSize;
3786 dictSize -= matchlengthHeaderSize;
3789 { short litlengthNCount[MaxLL+1];
3790 unsigned litlengthMaxValue = MaxLL, litlengthLog;
3791 litlengthHeaderSize = FSEv06_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize);
3792 if (FSEv06_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3793 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
3794 { size_t const errorCode = FSEv06_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
3795 if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3798 dctx->flagRepeatTable = 1;
3799 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize;
3802 static size_t ZSTDv06_decompress_insertDictionary(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3805 U32 const magic = MEM_readLE32(dict);
3806 if (magic != ZSTDv06_DICT_MAGIC) {
3807 /* pure content mode */
3808 ZSTDv06_refDictContent(dctx, dict, dictSize);
3811 /* load entropy tables */
3812 dict = (const char*)dict + 4;
3814 eSize = ZSTDv06_loadEntropy(dctx, dict, dictSize);
3815 if (ZSTDv06_isError(eSize)) return ERROR(dictionary_corrupted);
3817 /* reference dictionary content */
3818 dict = (const char*)dict + eSize;
3820 ZSTDv06_refDictContent(dctx, dict, dictSize);
3826 size_t ZSTDv06_decompressBegin_usingDict(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3828 { size_t const errorCode = ZSTDv06_decompressBegin(dctx);
3829 if (ZSTDv06_isError(errorCode)) return errorCode; }
3831 if (dict && dictSize) {
3832 size_t const errorCode = ZSTDv06_decompress_insertDictionary(dctx, dict, dictSize);
3833 if (ZSTDv06_isError(errorCode)) return ERROR(dictionary_corrupted);
3840 Buffered version of Zstd compression library
3841 Copyright (C) 2015-2016, Yann Collet.
3843 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
3845 Redistribution and use in source and binary forms, with or without
3846 modification, are permitted provided that the following conditions are
3848 * Redistributions of source code must retain the above copyright
3849 notice, this list of conditions and the following disclaimer.
3850 * Redistributions in binary form must reproduce the above
3851 copyright notice, this list of conditions and the following disclaimer
3852 in the documentation and/or other materials provided with the
3854 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3855 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3856 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3857 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3858 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3859 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3860 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3861 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3862 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3863 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3864 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3866 You can contact the author at :
3867 - zstd homepage : https://facebook.github.io/zstd/
3871 /*-***************************************************************************
3872 * Streaming decompression howto
3874 * A ZBUFFv06_DCtx object is required to track streaming operations.
3875 * Use ZBUFFv06_createDCtx() and ZBUFFv06_freeDCtx() to create/release resources.
3876 * Use ZBUFFv06_decompressInit() to start a new decompression operation,
3877 * or ZBUFFv06_decompressInitDictionary() if decompression requires a dictionary.
3878 * Note that ZBUFFv06_DCtx objects can be re-init multiple times.
3880 * Use ZBUFFv06_decompressContinue() repetitively to consume your input.
3881 * *srcSizePtr and *dstCapacityPtr can be any size.
3882 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
3883 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
3884 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
3885 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
3886 * or 0 when a frame is completely decoded,
3887 * or an error code, which can be tested using ZBUFFv06_isError().
3889 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv06_recommendedDInSize() and ZBUFFv06_recommendedDOutSize()
3890 * output : ZBUFFv06_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
3891 * input : ZBUFFv06_recommendedDInSize == 128KB + 3;
3892 * just follow indications from ZBUFFv06_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3893 * *******************************************************************************/
3895 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
3896 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv06_dStage;
3898 /* *** Resource management *** */
3899 struct ZBUFFv06_DCtx_s {
3901 ZSTDv06_frameParams fParams;
3902 ZBUFFv06_dStage stage;
3911 BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX];
3913 }; /* typedef'd to ZBUFFv06_DCtx within "zstd_buffered.h" */
3916 ZBUFFv06_DCtx* ZBUFFv06_createDCtx(void)
3918 ZBUFFv06_DCtx* zbd = (ZBUFFv06_DCtx*)malloc(sizeof(ZBUFFv06_DCtx));
3919 if (zbd==NULL) return NULL;
3920 memset(zbd, 0, sizeof(*zbd));
3921 zbd->zd = ZSTDv06_createDCtx();
3922 zbd->stage = ZBUFFds_init;
3926 size_t ZBUFFv06_freeDCtx(ZBUFFv06_DCtx* zbd)
3928 if (zbd==NULL) return 0; /* support free on null */
3929 ZSTDv06_freeDCtx(zbd->zd);
3937 /* *** Initialization *** */
3939 size_t ZBUFFv06_decompressInitDictionary(ZBUFFv06_DCtx* zbd, const void* dict, size_t dictSize)
3941 zbd->stage = ZBUFFds_loadHeader;
3942 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
3943 return ZSTDv06_decompressBegin_usingDict(zbd->zd, dict, dictSize);
3946 size_t ZBUFFv06_decompressInit(ZBUFFv06_DCtx* zbd)
3948 return ZBUFFv06_decompressInitDictionary(zbd, NULL, 0);
3953 MEM_STATIC size_t ZBUFFv06_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3955 size_t length = MIN(dstCapacity, srcSize);
3957 memcpy(dst, src, length);
3963 /* *** Decompression *** */
3965 size_t ZBUFFv06_decompressContinue(ZBUFFv06_DCtx* zbd,
3966 void* dst, size_t* dstCapacityPtr,
3967 const void* src, size_t* srcSizePtr)
3969 const char* const istart = (const char*)src;
3970 const char* const iend = istart + *srcSizePtr;
3971 const char* ip = istart;
3972 char* const ostart = (char*)dst;
3973 char* const oend = ostart + *dstCapacityPtr;
3981 return ERROR(init_missing);
3983 case ZBUFFds_loadHeader :
3984 { size_t const hSize = ZSTDv06_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
3986 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */
3987 if (ZSTDv06_isError(hSize)) return hSize;
3988 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */
3990 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
3991 zbd->lhSize += iend-ip;
3992 *dstCapacityPtr = 0;
3993 return (hSize - zbd->lhSize) + ZSTDv06_blockHeaderSize; /* remaining header bytes + next block header */
3995 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
3999 /* Consume header */
4000 { size_t const h1Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv06_frameHeaderSize_min */
4001 size_t const h1Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4002 if (ZSTDv06_isError(h1Result)) return h1Result;
4003 if (h1Size < zbd->lhSize) { /* long header */
4004 size_t const h2Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4005 size_t const h2Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4006 if (ZSTDv06_isError(h2Result)) return h2Result;
4009 /* Frame header instruct buffer sizes */
4010 { size_t const blockSize = MIN(1 << zbd->fParams.windowLog, ZSTDv06_BLOCKSIZE_MAX);
4011 zbd->blockSize = blockSize;
4012 if (zbd->inBuffSize < blockSize) {
4014 zbd->inBuffSize = blockSize;
4015 zbd->inBuff = (char*)malloc(blockSize);
4016 if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4018 { size_t const neededOutSize = ((size_t)1 << zbd->fParams.windowLog) + blockSize + WILDCOPY_OVERLENGTH * 2;
4019 if (zbd->outBuffSize < neededOutSize) {
4021 zbd->outBuffSize = neededOutSize;
4022 zbd->outBuff = (char*)malloc(neededOutSize);
4023 if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4025 zbd->stage = ZBUFFds_read;
4028 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4029 if (neededInSize==0) { /* end of frame */
4030 zbd->stage = ZBUFFds_init;
4034 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
4035 size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd,
4036 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4038 if (ZSTDv06_isError(decodedSize)) return decodedSize;
4040 if (!decodedSize) break; /* this was just a header */
4041 zbd->outEnd = zbd->outStart + decodedSize;
4042 zbd->stage = ZBUFFds_flush;
4045 if (ip==iend) { notDone = 0; break; } /* no more input */
4046 zbd->stage = ZBUFFds_load;
4050 { size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4051 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */
4053 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */
4054 loadedSize = ZBUFFv06_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4056 zbd->inPos += loadedSize;
4057 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
4059 /* decode loaded input */
4060 { size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd,
4061 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4062 zbd->inBuff, neededInSize);
4063 if (ZSTDv06_isError(decodedSize)) return decodedSize;
4064 zbd->inPos = 0; /* input is consumed */
4065 if (!decodedSize) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */
4066 zbd->outEnd = zbd->outStart + decodedSize;
4067 zbd->stage = ZBUFFds_flush;
4068 /* break; */ /* ZBUFFds_flush follows */
4073 { size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4074 size_t const flushedSize = ZBUFFv06_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4076 zbd->outStart += flushedSize;
4077 if (flushedSize == toFlushSize) {
4078 zbd->stage = ZBUFFds_read;
4079 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4080 zbd->outStart = zbd->outEnd = 0;
4083 /* cannot flush everything */
4087 default: return ERROR(GENERIC); /* impossible */
4091 *srcSizePtr = ip-istart;
4092 *dstCapacityPtr = op-ostart;
4093 { size_t nextSrcSizeHint = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4094 if (nextSrcSizeHint > ZSTDv06_blockHeaderSize) nextSrcSizeHint+= ZSTDv06_blockHeaderSize; /* get following block header too */
4095 nextSrcSizeHint -= zbd->inPos; /* already loaded*/
4096 return nextSrcSizeHint;
4102 /* *************************************
4104 ***************************************/
4105 size_t ZBUFFv06_recommendedDInSize(void) { return ZSTDv06_BLOCKSIZE_MAX + ZSTDv06_blockHeaderSize /* block header size*/ ; }
4106 size_t ZBUFFv06_recommendedDOutSize(void) { return ZSTDv06_BLOCKSIZE_MAX; }