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 "../common/error_private.h"
17 /* ******************************************************************
19 low-level memory access routines
20 Copyright (C) 2013-2015, Yann Collet.
22 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
24 Redistribution and use in source and binary forms, with or without
25 modification, are permitted provided that the following conditions are
28 * Redistributions of source code must retain the above copyright
29 notice, this list of conditions and the following disclaimer.
30 * Redistributions in binary form must reproduce the above
31 copyright notice, this list of conditions and the following disclaimer
32 in the documentation and/or other materials provided with the
35 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
38 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
39 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
42 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
43 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
44 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
45 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47 You can contact the author at :
48 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
49 - Public forum : https://groups.google.com/forum/#!forum/lz4c
50 ****************************************************************** */
54 #if defined (__cplusplus)
58 /*-****************************************
60 ******************************************/
61 #include <stddef.h> /* size_t, ptrdiff_t */
62 #include <string.h> /* memcpy */
65 /*-****************************************
67 ******************************************/
69 # define MEM_STATIC static __attribute__((unused))
70 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
71 # define MEM_STATIC static inline
72 #elif defined(_MSC_VER)
73 # define MEM_STATIC static __inline
75 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
79 /*-**************************************************************
81 *****************************************************************/
82 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
84 # include <inttypes.h>
86 # include <stdint.h> /* intptr_t */
96 typedef unsigned char BYTE;
97 typedef unsigned short U16;
98 typedef signed short S16;
99 typedef unsigned int U32;
100 typedef signed int S32;
101 typedef unsigned long long U64;
102 typedef signed long long S64;
106 /*-**************************************************************
108 *****************************************************************/
110 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
111 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
113 MEM_STATIC unsigned MEM_isLittleEndian(void)
115 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
119 MEM_STATIC U16 MEM_read16(const void* memPtr)
121 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
124 MEM_STATIC U32 MEM_read32(const void* memPtr)
126 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
129 MEM_STATIC U64 MEM_read64(const void* memPtr)
131 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
134 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
136 memcpy(memPtr, &value, sizeof(value));
139 MEM_STATIC void MEM_write32(void* memPtr, U32 value)
141 memcpy(memPtr, &value, sizeof(value));
144 MEM_STATIC void MEM_write64(void* memPtr, U64 value)
146 memcpy(memPtr, &value, sizeof(value));
149 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
151 if (MEM_isLittleEndian())
152 return MEM_read16(memPtr);
154 const BYTE* p = (const BYTE*)memPtr;
155 return (U16)(p[0] + (p[1]<<8));
159 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
161 if (MEM_isLittleEndian()) {
162 MEM_write16(memPtr, val);
164 BYTE* p = (BYTE*)memPtr;
166 p[1] = (BYTE)(val>>8);
170 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
172 if (MEM_isLittleEndian())
173 return MEM_read32(memPtr);
175 const BYTE* p = (const BYTE*)memPtr;
176 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
181 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
183 if (MEM_isLittleEndian())
184 return MEM_read64(memPtr);
186 const BYTE* p = (const BYTE*)memPtr;
187 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
188 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
193 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
196 return (size_t)MEM_readLE32(memPtr);
198 return (size_t)MEM_readLE64(memPtr);
202 #if defined (__cplusplus)
206 #endif /* MEM_H_MODULE */
209 zstd - standard compression library
210 Header File for static linking only
211 Copyright (C) 2014-2016, Yann Collet.
213 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
215 Redistribution and use in source and binary forms, with or without
216 modification, are permitted provided that the following conditions are
218 * Redistributions of source code must retain the above copyright
219 notice, this list of conditions and the following disclaimer.
220 * Redistributions in binary form must reproduce the above
221 copyright notice, this list of conditions and the following disclaimer
222 in the documentation and/or other materials provided with the
224 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
225 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
226 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
227 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
228 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
229 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
230 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
231 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
232 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
233 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
234 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
236 You can contact the author at :
237 - zstd homepage : https://facebook.github.io/zstd
239 #ifndef ZSTD_STATIC_H
240 #define ZSTD_STATIC_H
242 /* The prototypes defined within this file are considered experimental.
243 * They should not be used in the context DLL as they may change in the future.
244 * Prefer static linking if you need them, to control breaking version changes issues.
247 #if defined (__cplusplus)
253 /*-*************************************
255 ***************************************/
256 #define ZSTDv05_WINDOWLOG_ABSOLUTEMIN 11
259 /*-*************************************
261 ***************************************/
262 /*- Advanced Decompression functions -*/
264 /*! ZSTDv05_decompress_usingPreparedDCtx() :
265 * Same as ZSTDv05_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
266 * It avoids reloading the dictionary each time.
267 * `preparedDCtx` must have been properly initialized using ZSTDv05_decompressBegin_usingDict().
268 * Requires 2 contexts : 1 for reference, which will not be modified, and 1 to run the decompression operation */
269 size_t ZSTDv05_decompress_usingPreparedDCtx(
270 ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* preparedDCtx,
271 void* dst, size_t dstCapacity,
272 const void* src, size_t srcSize);
275 /* **************************************
276 * Streaming functions (direct mode)
277 ****************************************/
278 size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx);
281 Streaming decompression, direct mode (bufferless)
283 A ZSTDv05_DCtx object is required to track streaming operations.
284 Use ZSTDv05_createDCtx() / ZSTDv05_freeDCtx() to manage it.
285 A ZSTDv05_DCtx object can be re-used multiple times.
287 First typical operation is to retrieve frame parameters, using ZSTDv05_getFrameParams().
288 This operation is independent, and just needs enough input data to properly decode the frame header.
289 Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.
290 Result : 0 when successful, it means the ZSTDv05_parameters structure has been filled.
291 >0 : means there is not enough data into src. Provides the expected size to successfully decode header.
292 errorCode, which can be tested using ZSTDv05_isError()
294 Start decompression, with ZSTDv05_decompressBegin() or ZSTDv05_decompressBegin_usingDict()
295 Alternatively, you can copy a prepared context, using ZSTDv05_copyDCtx()
297 Then use ZSTDv05_nextSrcSizeToDecompress() and ZSTDv05_decompressContinue() alternatively.
298 ZSTDv05_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv05_decompressContinue().
299 ZSTDv05_decompressContinue() requires this exact amount of bytes, or it will fail.
300 ZSTDv05_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
301 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
303 @result of ZSTDv05_decompressContinue() is the number of bytes regenerated within 'dst'.
304 It can be zero, which is not an error; it just means ZSTDv05_decompressContinue() has decoded some header.
306 A frame is fully decoded when ZSTDv05_nextSrcSizeToDecompress() returns zero.
307 Context can then be reset to start a new decompression.
311 /* **************************************
313 ****************************************/
314 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
315 User will have to take in charge required information to regenerate data, such as block sizes.
317 A few rules to respect :
318 - Uncompressed block size must be <= 128 KB
319 - Compressing or decompressing requires a context structure
320 + Use ZSTDv05_createCCtx() and ZSTDv05_createDCtx()
321 - It is necessary to init context before starting
322 + compression : ZSTDv05_compressBegin()
323 + decompression : ZSTDv05_decompressBegin()
324 + variants _usingDict() are also allowed
325 + copyCCtx() and copyDCtx() work too
326 - When a block is considered not compressible enough, ZSTDv05_compressBlock() result will be zero.
327 In which case, nothing is produced into `dst`.
328 + User must test for such outcome and deal directly with uncompressed data
329 + ZSTDv05_decompressBlock() doesn't accept uncompressed data as input !!
332 size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
337 #if defined (__cplusplus)
341 #endif /* ZSTDv05_STATIC_H */
345 zstd_internal - common functions to include
346 Header File for include
347 Copyright (C) 2014-2016, Yann Collet.
349 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
351 Redistribution and use in source and binary forms, with or without
352 modification, are permitted provided that the following conditions are
354 * Redistributions of source code must retain the above copyright
355 notice, this list of conditions and the following disclaimer.
356 * Redistributions in binary form must reproduce the above
357 copyright notice, this list of conditions and the following disclaimer
358 in the documentation and/or other materials provided with the
360 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
361 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
362 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
363 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
364 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
365 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
366 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
367 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
368 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
369 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
370 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
372 You can contact the author at :
373 - zstd source repository : https://github.com/Cyan4973/zstd
375 #ifndef ZSTD_CCOMMON_H_MODULE
376 #define ZSTD_CCOMMON_H_MODULE
380 /*-*************************************
382 ***************************************/
383 #define MIN(a,b) ((a)<(b) ? (a) : (b))
384 #define MAX(a,b) ((a)>(b) ? (a) : (b))
387 /*-*************************************
389 ***************************************/
390 #define ZSTDv05_DICT_MAGIC 0xEC30A435
396 #define BLOCKSIZE (128 KB) /* define, for static allocation */
398 static const size_t ZSTDv05_blockHeaderSize = 3;
399 static const size_t ZSTDv05_frameHeaderSize_min = 5;
400 #define ZSTDv05_frameHeaderSize_max 5 /* define, for static allocation */
415 #define REPCODE_STARTVALUE 1
421 #define MaxLit ((1<<Litbits) - 1)
422 #define MaxML ((1<<MLbits) - 1)
423 #define MaxLL ((1<<LLbits) - 1)
424 #define MaxOff ((1<<Offbits)- 1)
425 #define MLFSEv05Log 10
426 #define LLFSEv05Log 10
427 #define OffFSEv05Log 9
428 #define MaxSeq MAX(MaxLL, MaxML)
430 #define FSEv05_ENCODING_RAW 0
431 #define FSEv05_ENCODING_RLE 1
432 #define FSEv05_ENCODING_STATIC 2
433 #define FSEv05_ENCODING_DYNAMIC 3
436 #define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
438 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
439 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
441 #define WILDCOPY_OVERLENGTH 8
443 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
445 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
448 /*-*******************************************
449 * Shared functions to include for inlining
450 *********************************************/
451 static void ZSTDv05_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
453 #define COPY8(d,s) { ZSTDv05_copy8(d,s); d+=8; s+=8; }
455 /*! ZSTDv05_wildcopy() :
456 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
457 MEM_STATIC void ZSTDv05_wildcopy(void* dst, const void* src, ptrdiff_t length)
459 const BYTE* ip = (const BYTE*)src;
460 BYTE* op = (BYTE*)dst;
461 BYTE* const oend = op + length;
468 /*-*******************************************
470 *********************************************/
479 BYTE* litLengthStart;
481 BYTE* matchLengthStart;
486 U32* matchLengthFreq;
498 #endif /* ZSTDv05_CCOMMON_H_MODULE */
499 /* ******************************************************************
500 FSEv05 : Finite State Entropy coder
502 Copyright (C) 2013-2015, Yann Collet.
504 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
506 Redistribution and use in source and binary forms, with or without
507 modification, are permitted provided that the following conditions are
510 * Redistributions of source code must retain the above copyright
511 notice, this list of conditions and the following disclaimer.
512 * Redistributions in binary form must reproduce the above
513 copyright notice, this list of conditions and the following disclaimer
514 in the documentation and/or other materials provided with the
517 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
518 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
519 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
520 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
521 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
522 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
523 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
524 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
525 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
526 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
527 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
529 You can contact the author at :
530 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
531 - Public forum : https://groups.google.com/forum/#!forum/lz4c
532 ****************************************************************** */
536 #if defined (__cplusplus)
541 /* *****************************************
543 ******************************************/
544 #include <stddef.h> /* size_t, ptrdiff_t */
547 /*-****************************************
548 * FSEv05 simple functions
549 ******************************************/
550 size_t FSEv05_decompress(void* dst, size_t maxDstSize,
551 const void* cSrc, size_t cSrcSize);
554 Decompress FSEv05 data from buffer 'cSrc', of size 'cSrcSize',
555 into already allocated destination buffer 'dst', of size 'maxDstSize'.
556 return : size of regenerated data (<= maxDstSize)
557 or an error code, which can be tested using FSEv05_isError()
559 ** Important ** : FSEv05_decompress() doesn't decompress non-compressible nor RLE data !!!
560 Why ? : making this distinction requires a header.
561 Header management is intentionally delegated to the user layer, which can better manage special cases.
565 /* *****************************************
567 ******************************************/
568 /* Error Management */
569 unsigned FSEv05_isError(size_t code); /* tells if a return value is an error code */
570 const char* FSEv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
575 /* *****************************************
576 * FSEv05 detailed API
577 ******************************************/
578 /* *** DECOMPRESSION *** */
582 Read compactly saved 'normalizedCounter' from 'rBuffer'.
583 return : size read from 'rBuffer'
584 or an errorCode, which can be tested using FSEv05_isError()
585 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
586 size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
589 Constructor and Destructor of type FSEv05_DTable
590 Note that its size depends on 'tableLog' */
591 typedef unsigned FSEv05_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
592 FSEv05_DTable* FSEv05_createDTable(unsigned tableLog);
593 void FSEv05_freeDTable(FSEv05_DTable* dt);
596 FSEv05_buildDTable():
597 Builds 'dt', which must be already allocated, using FSEv05_createDTable()
599 or an errorCode, which can be tested using FSEv05_isError() */
600 size_t FSEv05_buildDTable (FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
603 FSEv05_decompress_usingDTable():
604 Decompress compressed source @cSrc of size @cSrcSize using `dt`
605 into `dst` which must be already allocated.
606 @return : size of regenerated data (necessarily <= @dstCapacity)
607 or an errorCode, which can be tested using FSEv05_isError() */
608 size_t FSEv05_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv05_DTable* dt);
612 #if defined (__cplusplus)
616 #endif /* FSEv05_H */
617 /* ******************************************************************
619 Part of FSEv05 library
620 header file (to include)
621 Copyright (C) 2013-2016, Yann Collet.
623 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
625 Redistribution and use in source and binary forms, with or without
626 modification, are permitted provided that the following conditions are
629 * Redistributions of source code must retain the above copyright
630 notice, this list of conditions and the following disclaimer.
631 * Redistributions in binary form must reproduce the above
632 copyright notice, this list of conditions and the following disclaimer
633 in the documentation and/or other materials provided with the
636 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
637 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
638 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
639 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
640 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
641 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
642 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
643 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
644 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
645 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
646 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
648 You can contact the author at :
649 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
650 ****************************************************************** */
651 #ifndef BITv05STREAM_H_MODULE
652 #define BITv05STREAM_H_MODULE
654 #if defined (__cplusplus)
660 * This API consists of small unitary functions, which highly benefit from being inlined.
661 * Since link-time-optimization is not available for all compilers,
662 * these functions are defined into a .h to be included.
667 /*-********************************************
668 * bitStream decoding API (read backward)
669 **********************************************/
673 unsigned bitsConsumed;
678 typedef enum { BITv05_DStream_unfinished = 0,
679 BITv05_DStream_endOfBuffer = 1,
680 BITv05_DStream_completed = 2,
681 BITv05_DStream_overflow = 3 } BITv05_DStream_status; /* result of BITv05_reloadDStream() */
682 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
684 MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
685 MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits);
686 MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD);
687 MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* bitD);
690 /*-****************************************
692 ******************************************/
693 MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, unsigned nbBits);
694 /* faster, but works only if nbBits >= 1 */
698 /*-**************************************************************
700 ****************************************************************/
701 MEM_STATIC unsigned BITv05_highbit32 (U32 val)
703 # if defined(_MSC_VER) /* Visual */
705 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
706 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
707 return __builtin_clz (val) ^ 31;
708 # else /* Software version */
709 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 };
717 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
724 /*-********************************************************
726 **********************************************************/
727 /*!BITv05_initDStream
728 * Initialize a BITv05_DStream_t.
729 * @bitD : a pointer to an already allocated BITv05_DStream_t structure
730 * @srcBuffer must point at the beginning of a bitStream
731 * @srcSize must be the exact size of the bitStream
732 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
734 MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
736 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
738 if (srcSize >= sizeof(size_t)) { /* normal case */
740 bitD->start = (const char*)srcBuffer;
741 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
742 bitD->bitContainer = MEM_readLEST(bitD->ptr);
743 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
744 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
745 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
748 bitD->start = (const char*)srcBuffer;
749 bitD->ptr = bitD->start;
750 bitD->bitContainer = *(const BYTE*)(bitD->start);
753 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
754 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
755 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
756 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
757 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
758 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */
761 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
762 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
763 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
764 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
770 MEM_STATIC size_t BITv05_lookBits(BITv05_DStream_t* bitD, U32 nbBits)
772 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
773 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
776 /*! BITv05_lookBitsFast :
777 * unsafe version; only works if nbBits >= 1 */
778 MEM_STATIC size_t BITv05_lookBitsFast(BITv05_DStream_t* bitD, U32 nbBits)
780 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
781 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
784 MEM_STATIC void BITv05_skipBits(BITv05_DStream_t* bitD, U32 nbBits)
786 bitD->bitsConsumed += nbBits;
789 MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits)
791 size_t value = BITv05_lookBits(bitD, nbBits);
792 BITv05_skipBits(bitD, nbBits);
796 /*!BITv05_readBitsFast :
797 * unsafe version; only works if nbBits >= 1 */
798 MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, unsigned nbBits)
800 size_t value = BITv05_lookBitsFast(bitD, nbBits);
801 BITv05_skipBits(bitD, nbBits);
805 MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD)
807 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
808 return BITv05_DStream_overflow;
810 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
811 bitD->ptr -= bitD->bitsConsumed >> 3;
812 bitD->bitsConsumed &= 7;
813 bitD->bitContainer = MEM_readLEST(bitD->ptr);
814 return BITv05_DStream_unfinished;
816 if (bitD->ptr == bitD->start) {
817 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv05_DStream_endOfBuffer;
818 return BITv05_DStream_completed;
821 U32 nbBytes = bitD->bitsConsumed >> 3;
822 BITv05_DStream_status result = BITv05_DStream_unfinished;
823 if (bitD->ptr - nbBytes < bitD->start) {
824 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
825 result = BITv05_DStream_endOfBuffer;
827 bitD->ptr -= nbBytes;
828 bitD->bitsConsumed -= nbBytes*8;
829 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
834 /*! BITv05_endOfDStream
835 * @return Tells if DStream has reached its exact end
837 MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* DStream)
839 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
842 #if defined (__cplusplus)
846 #endif /* BITv05STREAM_H_MODULE */
847 /* ******************************************************************
848 FSEv05 : Finite State Entropy coder
849 header file for static linking (only)
850 Copyright (C) 2013-2015, Yann Collet
852 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
854 Redistribution and use in source and binary forms, with or without
855 modification, are permitted provided that the following conditions are
858 * Redistributions of source code must retain the above copyright
859 notice, this list of conditions and the following disclaimer.
860 * Redistributions in binary form must reproduce the above
861 copyright notice, this list of conditions and the following disclaimer
862 in the documentation and/or other materials provided with the
865 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
866 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
867 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
868 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
869 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
870 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
871 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
872 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
873 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
874 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
875 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
877 You can contact the author at :
878 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
879 - Public forum : https://groups.google.com/forum/#!forum/lz4c
880 ****************************************************************** */
881 #ifndef FSEv05_STATIC_H
882 #define FSEv05_STATIC_H
884 #if defined (__cplusplus)
890 /* *****************************************
892 *******************************************/
893 /* It is possible to statically allocate FSEv05 CTable/DTable as a table of unsigned using below macros */
894 #define FSEv05_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
897 /* *****************************************
898 * FSEv05 advanced API
899 *******************************************/
900 size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits);
901 /* build a fake FSEv05_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
903 size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, unsigned char symbolValue);
904 /* build a fake FSEv05_DTable, designed to always generate the same symbolValue */
908 /* *****************************************
909 * FSEv05 symbol decompression API
910 *******************************************/
914 const void* table; /* precise table may vary, depending on U16 */
918 static void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt);
920 static unsigned char FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
922 static unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr);
926 /* *****************************************
928 *******************************************/
929 static unsigned char FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
930 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
933 /* *****************************************
934 * Implementation of inlined functions
935 *******************************************/
941 } FSEv05_DTableHeader; /* sizeof U32 */
945 unsigned short newState;
946 unsigned char symbol;
947 unsigned char nbBits;
948 } FSEv05_decode_t; /* size == U32 */
950 MEM_STATIC void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt)
952 const void* ptr = dt;
953 const FSEv05_DTableHeader* const DTableH = (const FSEv05_DTableHeader*)ptr;
954 DStatePtr->state = BITv05_readBits(bitD, DTableH->tableLog);
955 BITv05_reloadDStream(bitD);
956 DStatePtr->table = dt + 1;
959 MEM_STATIC BYTE FSEv05_peakSymbol(FSEv05_DState_t* DStatePtr)
961 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
965 MEM_STATIC BYTE FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
967 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
968 const U32 nbBits = DInfo.nbBits;
969 BYTE symbol = DInfo.symbol;
970 size_t lowBits = BITv05_readBits(bitD, nbBits);
972 DStatePtr->state = DInfo.newState + lowBits;
976 MEM_STATIC BYTE FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
978 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
979 const U32 nbBits = DInfo.nbBits;
980 BYTE symbol = DInfo.symbol;
981 size_t lowBits = BITv05_readBitsFast(bitD, nbBits);
983 DStatePtr->state = DInfo.newState + lowBits;
987 MEM_STATIC unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr)
989 return DStatePtr->state == 0;
993 #if defined (__cplusplus)
997 #endif /* FSEv05_STATIC_H */
998 /* ******************************************************************
999 FSEv05 : Finite State Entropy coder
1000 Copyright (C) 2013-2015, Yann Collet.
1002 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1004 Redistribution and use in source and binary forms, with or without
1005 modification, are permitted provided that the following conditions are
1008 * Redistributions of source code must retain the above copyright
1009 notice, this list of conditions and the following disclaimer.
1010 * Redistributions in binary form must reproduce the above
1011 copyright notice, this list of conditions and the following disclaimer
1012 in the documentation and/or other materials provided with the
1015 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1016 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1017 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1018 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1019 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1020 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1021 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1022 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1023 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1024 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1025 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1027 You can contact the author at :
1028 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1029 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1030 ****************************************************************** */
1032 #ifndef FSEv05_COMMONDEFS_ONLY
1034 /* **************************************************************
1036 ****************************************************************/
1038 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1039 * Increasing memory usage improves compression ratio
1040 * Reduced memory usage can improve speed, due to cache effect
1041 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1042 #define FSEv05_MAX_MEMORY_USAGE 14
1043 #define FSEv05_DEFAULT_MEMORY_USAGE 13
1045 /*!FSEv05_MAX_SYMBOL_VALUE :
1046 * Maximum symbol value authorized.
1047 * Required for proper stack allocation */
1048 #define FSEv05_MAX_SYMBOL_VALUE 255
1051 /* **************************************************************
1052 * template functions type & suffix
1053 ****************************************************************/
1054 #define FSEv05_FUNCTION_TYPE BYTE
1055 #define FSEv05_FUNCTION_EXTENSION
1056 #define FSEv05_DECODE_TYPE FSEv05_decode_t
1059 #endif /* !FSEv05_COMMONDEFS_ONLY */
1061 /* **************************************************************
1062 * Compiler specifics
1063 ****************************************************************/
1064 #ifdef _MSC_VER /* Visual Studio */
1065 # define FORCE_INLINE static __forceinline
1066 # include <intrin.h> /* For Visual 2005 */
1067 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1068 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1070 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1072 # define FORCE_INLINE static inline __attribute__((always_inline))
1074 # define FORCE_INLINE static inline
1077 # define FORCE_INLINE static
1078 # endif /* __STDC_VERSION__ */
1082 /* **************************************************************
1084 ****************************************************************/
1085 #include <stdlib.h> /* malloc, free, qsort */
1086 #include <string.h> /* memcpy, memset */
1087 #include <stdio.h> /* printf (debug) */
1091 /* ***************************************************************
1093 *****************************************************************/
1094 #define FSEv05_MAX_TABLELOG (FSEv05_MAX_MEMORY_USAGE-2)
1095 #define FSEv05_MAX_TABLESIZE (1U<<FSEv05_MAX_TABLELOG)
1096 #define FSEv05_MAXTABLESIZE_MASK (FSEv05_MAX_TABLESIZE-1)
1097 #define FSEv05_DEFAULT_TABLELOG (FSEv05_DEFAULT_MEMORY_USAGE-2)
1098 #define FSEv05_MIN_TABLELOG 5
1100 #define FSEv05_TABLELOG_ABSOLUTE_MAX 15
1101 #if FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX
1102 #error "FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX is not supported"
1106 /* **************************************************************
1108 ****************************************************************/
1109 #define FSEv05_STATIC_ASSERT(c) { enum { FSEv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1112 /* **************************************************************
1114 ****************************************************************/
1115 typedef unsigned DTable_max_t[FSEv05_DTABLE_SIZE_U32(FSEv05_MAX_TABLELOG)];
1118 /* **************************************************************
1120 ****************************************************************/
1122 designed to be included
1123 for type-specific functions (template emulation in C)
1124 Objective is to write these functions only once, for improved maintenance
1128 #ifndef FSEv05_FUNCTION_EXTENSION
1129 # error "FSEv05_FUNCTION_EXTENSION must be defined"
1131 #ifndef FSEv05_FUNCTION_TYPE
1132 # error "FSEv05_FUNCTION_TYPE must be defined"
1135 /* Function names */
1136 #define FSEv05_CAT(X,Y) X##Y
1137 #define FSEv05_FUNCTION_NAME(X,Y) FSEv05_CAT(X,Y)
1138 #define FSEv05_TYPE_NAME(X,Y) FSEv05_CAT(X,Y)
1141 /* Function templates */
1142 static U32 FSEv05_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1146 FSEv05_DTable* FSEv05_createDTable (unsigned tableLog)
1148 if (tableLog > FSEv05_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv05_TABLELOG_ABSOLUTE_MAX;
1149 return (FSEv05_DTable*)malloc( FSEv05_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1152 void FSEv05_freeDTable (FSEv05_DTable* dt)
1157 size_t FSEv05_buildDTable(FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1159 FSEv05_DTableHeader DTableH;
1160 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */
1161 FSEv05_DECODE_TYPE* const tableDecode = (FSEv05_DECODE_TYPE*) (tdPtr);
1162 const U32 tableSize = 1 << tableLog;
1163 const U32 tableMask = tableSize-1;
1164 const U32 step = FSEv05_tableStep(tableSize);
1165 U16 symbolNext[FSEv05_MAX_SYMBOL_VALUE+1];
1167 U32 highThreshold = tableSize-1;
1168 const S16 largeLimit= (S16)(1 << (tableLog-1));
1173 if (maxSymbolValue > FSEv05_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1174 if (tableLog > FSEv05_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1176 /* Init, lay down lowprob symbols */
1177 memset(tableDecode, 0, sizeof(FSEv05_FUNCTION_TYPE) * (maxSymbolValue+1) ); /* useless init, but keep static analyzer happy, and we don't need to performance optimize legacy decoders */
1178 DTableH.tableLog = (U16)tableLog;
1179 for (s=0; s<=maxSymbolValue; s++) {
1180 if (normalizedCounter[s]==-1) {
1181 tableDecode[highThreshold--].symbol = (FSEv05_FUNCTION_TYPE)s;
1184 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1185 symbolNext[s] = normalizedCounter[s];
1188 /* Spread symbols */
1189 for (s=0; s<=maxSymbolValue; s++) {
1191 for (i=0; i<normalizedCounter[s]; i++) {
1192 tableDecode[position].symbol = (FSEv05_FUNCTION_TYPE)s;
1193 position = (position + step) & tableMask;
1194 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1197 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1199 /* Build Decoding table */
1202 for (i=0; i<tableSize; i++) {
1203 FSEv05_FUNCTION_TYPE symbol = (FSEv05_FUNCTION_TYPE)(tableDecode[i].symbol);
1204 U16 nextState = symbolNext[symbol]++;
1205 tableDecode[i].nbBits = (BYTE) (tableLog - BITv05_highbit32 ((U32)nextState) );
1206 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1209 DTableH.fastMode = (U16)noLarge;
1210 memcpy(dt, &DTableH, sizeof(DTableH));
1215 #ifndef FSEv05_COMMONDEFS_ONLY
1216 /*-****************************************
1217 * FSEv05 helper functions
1218 ******************************************/
1219 unsigned FSEv05_isError(size_t code) { return ERR_isError(code); }
1221 const char* FSEv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1224 /*-**************************************************************
1225 * FSEv05 NCount encoding-decoding
1226 ****************************************************************/
1227 static short FSEv05_abs(short a) { return a<0 ? -a : a; }
1230 size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1231 const void* headerBuffer, size_t hbSize)
1233 const BYTE* const istart = (const BYTE*) headerBuffer;
1234 const BYTE* const iend = istart + hbSize;
1235 const BYTE* ip = istart;
1241 unsigned charnum = 0;
1244 if (hbSize < 4) return ERROR(srcSize_wrong);
1245 bitStream = MEM_readLE32(ip);
1246 nbBits = (bitStream & 0xF) + FSEv05_MIN_TABLELOG; /* extract tableLog */
1247 if (nbBits > FSEv05_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1250 *tableLogPtr = nbBits;
1251 remaining = (1<<nbBits)+1;
1252 threshold = 1<<nbBits;
1255 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1257 unsigned n0 = charnum;
1258 while ((bitStream & 0xFFFF) == 0xFFFF) {
1262 bitStream = MEM_readLE32(ip) >> bitCount;
1267 while ((bitStream & 3) == 3) {
1272 n0 += bitStream & 3;
1274 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1275 while (charnum < n0) normalizedCounter[charnum++] = 0;
1276 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1279 bitStream = MEM_readLE32(ip) >> bitCount;
1285 const short max = (short)((2*threshold-1)-remaining);
1288 if ((bitStream & (threshold-1)) < (U32)max) {
1289 count = (short)(bitStream & (threshold-1));
1290 bitCount += nbBits-1;
1292 count = (short)(bitStream & (2*threshold-1));
1293 if (count >= threshold) count -= max;
1297 count--; /* extra accuracy */
1298 remaining -= FSEv05_abs(count);
1299 normalizedCounter[charnum++] = count;
1301 while (remaining < threshold) {
1306 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1310 bitCount -= (int)(8 * (iend - 4 - ip));
1313 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1315 if (remaining != 1) return ERROR(GENERIC);
1316 *maxSVPtr = charnum-1;
1318 ip += (bitCount+7)>>3;
1319 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1325 /*-*******************************************************
1326 * Decompression (Byte symbols)
1327 *********************************************************/
1328 size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, BYTE symbolValue)
1331 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1332 void* dPtr = dt + 1;
1333 FSEv05_decode_t* const cell = (FSEv05_decode_t*)dPtr;
1335 DTableH->tableLog = 0;
1336 DTableH->fastMode = 0;
1339 cell->symbol = symbolValue;
1346 size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits)
1349 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1350 void* dPtr = dt + 1;
1351 FSEv05_decode_t* const dinfo = (FSEv05_decode_t*)dPtr;
1352 const unsigned tableSize = 1 << nbBits;
1353 const unsigned tableMask = tableSize - 1;
1354 const unsigned maxSymbolValue = tableMask;
1358 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1360 /* Build Decoding Table */
1361 DTableH->tableLog = (U16)nbBits;
1362 DTableH->fastMode = 1;
1363 for (s=0; s<=maxSymbolValue; s++) {
1364 dinfo[s].newState = 0;
1365 dinfo[s].symbol = (BYTE)s;
1366 dinfo[s].nbBits = (BYTE)nbBits;
1372 FORCE_INLINE size_t FSEv05_decompress_usingDTable_generic(
1373 void* dst, size_t maxDstSize,
1374 const void* cSrc, size_t cSrcSize,
1375 const FSEv05_DTable* dt, const unsigned fast)
1377 BYTE* const ostart = (BYTE*) dst;
1379 BYTE* const omax = op + maxDstSize;
1380 BYTE* const olimit = omax-3;
1382 BITv05_DStream_t bitD;
1383 FSEv05_DState_t state1;
1384 FSEv05_DState_t state2;
1388 errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1389 if (FSEv05_isError(errorCode)) return errorCode;
1391 FSEv05_initDState(&state1, &bitD, dt);
1392 FSEv05_initDState(&state2, &bitD, dt);
1394 #define FSEv05_GETSYMBOL(statePtr) fast ? FSEv05_decodeSymbolFast(statePtr, &bitD) : FSEv05_decodeSymbol(statePtr, &bitD)
1396 /* 4 symbols per loop */
1397 for ( ; (BITv05_reloadDStream(&bitD)==BITv05_DStream_unfinished) && (op<olimit) ; op+=4) {
1398 op[0] = FSEv05_GETSYMBOL(&state1);
1400 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1401 BITv05_reloadDStream(&bitD);
1403 op[1] = FSEv05_GETSYMBOL(&state2);
1405 if (FSEv05_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1406 { if (BITv05_reloadDStream(&bitD) > BITv05_DStream_unfinished) { op+=2; break; } }
1408 op[2] = FSEv05_GETSYMBOL(&state1);
1410 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1411 BITv05_reloadDStream(&bitD);
1413 op[3] = FSEv05_GETSYMBOL(&state2);
1417 /* note : BITv05_reloadDStream(&bitD) >= FSEv05_DStream_partiallyFilled; Ends at exactly BITv05_DStream_completed */
1419 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state1))) )
1422 *op++ = FSEv05_GETSYMBOL(&state1);
1424 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state2))) )
1427 *op++ = FSEv05_GETSYMBOL(&state2);
1431 if (BITv05_endOfDStream(&bitD) && FSEv05_endOfDState(&state1) && FSEv05_endOfDState(&state2))
1434 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1436 return ERROR(corruption_detected);
1440 size_t FSEv05_decompress_usingDTable(void* dst, size_t originalSize,
1441 const void* cSrc, size_t cSrcSize,
1442 const FSEv05_DTable* dt)
1444 const void* ptr = dt;
1445 const FSEv05_DTableHeader* DTableH = (const FSEv05_DTableHeader*)ptr;
1446 const U32 fastMode = DTableH->fastMode;
1448 /* select fast mode (static) */
1449 if (fastMode) return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1450 return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1454 size_t FSEv05_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1456 const BYTE* const istart = (const BYTE*)cSrc;
1457 const BYTE* ip = istart;
1458 short counting[FSEv05_MAX_SYMBOL_VALUE+1];
1459 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1461 unsigned maxSymbolValue = FSEv05_MAX_SYMBOL_VALUE;
1464 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1466 /* normal FSEv05 decoding mode */
1467 errorCode = FSEv05_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1468 if (FSEv05_isError(errorCode)) return errorCode;
1469 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1471 cSrcSize -= errorCode;
1473 errorCode = FSEv05_buildDTable (dt, counting, maxSymbolValue, tableLog);
1474 if (FSEv05_isError(errorCode)) return errorCode;
1476 /* always return, even if it is an error code */
1477 return FSEv05_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1482 #endif /* FSEv05_COMMONDEFS_ONLY */
1483 /* ******************************************************************
1484 Huff0 : Huffman coder, part of New Generation Entropy library
1486 Copyright (C) 2013-2016, Yann Collet.
1488 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1490 Redistribution and use in source and binary forms, with or without
1491 modification, are permitted provided that the following conditions are
1494 * Redistributions of source code must retain the above copyright
1495 notice, this list of conditions and the following disclaimer.
1496 * Redistributions in binary form must reproduce the above
1497 copyright notice, this list of conditions and the following disclaimer
1498 in the documentation and/or other materials provided with the
1501 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1502 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1503 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1504 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1505 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1506 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1507 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1508 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1509 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1510 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1511 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1513 You can contact the author at :
1514 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1515 ****************************************************************** */
1519 #if defined (__cplusplus)
1525 /* ****************************************
1526 * Huff0 simple functions
1527 ******************************************/
1528 size_t HUFv05_decompress(void* dst, size_t dstSize,
1529 const void* cSrc, size_t cSrcSize);
1531 HUFv05_decompress():
1532 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1533 into already allocated destination buffer 'dst', of size 'dstSize'.
1534 @dstSize : must be the **exact** size of original (uncompressed) data.
1535 Note : in contrast with FSEv05, HUFv05_decompress can regenerate
1536 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1537 because it knows size to regenerate.
1538 @return : size of regenerated data (== dstSize)
1539 or an error code, which can be tested using HUFv05_isError()
1543 /* ****************************************
1545 ******************************************/
1546 /* Error Management */
1547 unsigned HUFv05_isError(size_t code); /* tells if a return value is an error code */
1548 const char* HUFv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
1551 #if defined (__cplusplus)
1556 /* ******************************************************************
1557 Huff0 : Huffman codec, part of New Generation Entropy library
1558 header file, for static linking only
1559 Copyright (C) 2013-2016, Yann Collet
1561 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1563 Redistribution and use in source and binary forms, with or without
1564 modification, are permitted provided that the following conditions are
1567 * Redistributions of source code must retain the above copyright
1568 notice, this list of conditions and the following disclaimer.
1569 * Redistributions in binary form must reproduce the above
1570 copyright notice, this list of conditions and the following disclaimer
1571 in the documentation and/or other materials provided with the
1574 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1575 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1576 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1577 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1578 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1579 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1580 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1581 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1582 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1583 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1584 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1586 You can contact the author at :
1587 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1588 ****************************************************************** */
1589 #ifndef HUF0_STATIC_H
1590 #define HUF0_STATIC_H
1592 #if defined (__cplusplus)
1598 /* ****************************************
1600 ******************************************/
1601 /* static allocation of Huff0's DTable */
1602 #define HUFv05_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1603 #define HUFv05_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1604 unsigned short DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1605 #define HUFv05_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1606 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1607 #define HUFv05_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1608 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1611 /* ****************************************
1612 * Advanced decompression functions
1613 ******************************************/
1614 size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1615 size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1618 /* ****************************************
1619 * Huff0 detailed API
1620 ******************************************/
1622 HUFv05_decompress() does the following:
1623 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1624 2. build Huffman table from save, using HUFv05_readDTableXn()
1625 3. decode 1 or 4 segments in parallel using HUFv05_decompressSXn_usingDTable
1627 size_t HUFv05_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1628 size_t HUFv05_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1630 size_t HUFv05_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1631 size_t HUFv05_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1634 /* single stream variants */
1636 size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1637 size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1639 size_t HUFv05_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1640 size_t HUFv05_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1644 #if defined (__cplusplus)
1648 #endif /* HUF0_STATIC_H */
1649 /* ******************************************************************
1650 Huff0 : Huffman coder, part of New Generation Entropy library
1651 Copyright (C) 2013-2015, Yann Collet.
1653 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1655 Redistribution and use in source and binary forms, with or without
1656 modification, are permitted provided that the following conditions are
1659 * Redistributions of source code must retain the above copyright
1660 notice, this list of conditions and the following disclaimer.
1661 * Redistributions in binary form must reproduce the above
1662 copyright notice, this list of conditions and the following disclaimer
1663 in the documentation and/or other materials provided with the
1666 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1667 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1668 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1669 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1670 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1671 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1672 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1673 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1674 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1675 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1676 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1678 You can contact the author at :
1679 - FSEv05+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1680 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1681 ****************************************************************** */
1683 /* **************************************************************
1684 * Compiler specifics
1685 ****************************************************************/
1686 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1687 /* inline is defined */
1688 #elif defined(_MSC_VER)
1689 # define inline __inline
1691 # define inline /* disable inline */
1695 #ifdef _MSC_VER /* Visual Studio */
1696 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1700 /* **************************************************************
1702 ****************************************************************/
1703 #include <stdlib.h> /* malloc, free, qsort */
1704 #include <string.h> /* memcpy, memset */
1705 #include <stdio.h> /* printf (debug) */
1708 /* **************************************************************
1710 ****************************************************************/
1711 #define HUFv05_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv05_MAX_TABLELOG. Beyond that value, code does not work */
1712 #define HUFv05_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv05_ABSOLUTEMAX_TABLELOG */
1713 #define HUFv05_DEFAULT_TABLELOG HUFv05_MAX_TABLELOG /* tableLog by default, when not specified */
1714 #define HUFv05_MAX_SYMBOL_VALUE 255
1715 #if (HUFv05_MAX_TABLELOG > HUFv05_ABSOLUTEMAX_TABLELOG)
1716 # error "HUFv05_MAX_TABLELOG is too large !"
1720 /* **************************************************************
1722 ****************************************************************/
1723 unsigned HUFv05_isError(size_t code) { return ERR_isError(code); }
1724 const char* HUFv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1725 #define HUFv05_STATIC_ASSERT(c) { enum { HUFv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1728 /* *******************************************************
1729 * Huff0 : Huffman block decompression
1730 *********************************************************/
1731 typedef struct { BYTE byte; BYTE nbBits; } HUFv05_DEltX2; /* single-symbol decoding */
1733 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv05_DEltX4; /* double-symbols decoding */
1735 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1737 /*! HUFv05_readStats
1738 Read compact Huffman tree, saved by HUFv05_writeCTable
1739 @huffWeight : destination buffer
1740 @return : size read from `src`
1742 static size_t HUFv05_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1743 U32* nbSymbolsPtr, U32* tableLogPtr,
1744 const void* src, size_t srcSize)
1748 const BYTE* ip = (const BYTE*) src;
1753 if (!srcSize) return ERROR(srcSize_wrong);
1755 /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */
1757 if (iSize >= 128) { /* special header */
1758 if (iSize >= (242)) { /* RLE */
1759 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1760 oSize = l[iSize-242];
1761 memset(huffWeight, 1, hwSize);
1764 else { /* Incompressible */
1765 oSize = iSize - 127;
1766 iSize = ((oSize+1)/2);
1767 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1768 if (oSize >= hwSize) return ERROR(corruption_detected);
1770 for (n=0; n<oSize; n+=2) {
1771 huffWeight[n] = ip[n/2] >> 4;
1772 huffWeight[n+1] = ip[n/2] & 15;
1774 else { /* header compressed with FSEv05 (normal case) */
1775 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1776 oSize = FSEv05_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1777 if (FSEv05_isError(oSize)) return oSize;
1780 /* collect weight stats */
1781 memset(rankStats, 0, (HUFv05_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1783 for (n=0; n<oSize; n++) {
1784 if (huffWeight[n] >= HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1785 rankStats[huffWeight[n]]++;
1786 weightTotal += (1 << huffWeight[n]) >> 1;
1788 if (weightTotal == 0) return ERROR(corruption_detected);
1790 /* get last non-null symbol weight (implied, total must be 2^n) */
1791 tableLog = BITv05_highbit32(weightTotal) + 1;
1792 if (tableLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1793 { /* determine last weight */
1794 U32 total = 1 << tableLog;
1795 U32 rest = total - weightTotal;
1796 U32 verif = 1 << BITv05_highbit32(rest);
1797 U32 lastWeight = BITv05_highbit32(rest) + 1;
1798 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1799 huffWeight[oSize] = (BYTE)lastWeight;
1800 rankStats[lastWeight]++;
1803 /* check tree construction validity */
1804 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1807 *nbSymbolsPtr = (U32)(oSize+1);
1808 *tableLogPtr = tableLog;
1813 /*-***************************/
1814 /* single-symbol decoding */
1815 /*-***************************/
1817 size_t HUFv05_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1819 BYTE huffWeight[HUFv05_MAX_SYMBOL_VALUE + 1];
1820 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1826 void* const dtPtr = DTable + 1;
1827 HUFv05_DEltX2* const dt = (HUFv05_DEltX2*)dtPtr;
1829 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1830 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
1832 iSize = HUFv05_readStats(huffWeight, HUFv05_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1833 if (HUFv05_isError(iSize)) return iSize;
1836 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1837 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
1841 for (n=1; n<=tableLog; n++) {
1842 U32 current = nextRankStart;
1843 nextRankStart += (rankVal[n] << (n-1));
1844 rankVal[n] = current;
1848 for (n=0; n<nbSymbols; n++) {
1849 const U32 w = huffWeight[n];
1850 const U32 length = (1 << w) >> 1;
1853 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1854 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1856 rankVal[w] += length;
1862 static BYTE HUFv05_decodeSymbolX2(BITv05_DStream_t* Dstream, const HUFv05_DEltX2* dt, const U32 dtLog)
1864 const size_t val = BITv05_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1865 const BYTE c = dt[val].byte;
1866 BITv05_skipBits(Dstream, dt[val].nbBits);
1870 #define HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1871 *ptr++ = HUFv05_decodeSymbolX2(DStreamPtr, dt, dtLog)
1873 #define HUFv05_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1874 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
1875 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1877 #define HUFv05_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1879 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1881 static inline size_t HUFv05_decodeStreamX2(BYTE* p, BITv05_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv05_DEltX2* const dt, const U32 dtLog)
1883 BYTE* const pStart = p;
1885 /* up to 4 symbols at a time */
1886 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-4)) {
1887 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1888 HUFv05_DECODE_SYMBOLX2_1(p, bitDPtr);
1889 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1890 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1893 /* closer to the end */
1894 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd))
1895 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1897 /* no more data to retrieve from bitstream, hence no need to reload */
1899 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1904 size_t HUFv05_decompress1X2_usingDTable(
1905 void* dst, size_t dstSize,
1906 const void* cSrc, size_t cSrcSize,
1909 BYTE* op = (BYTE*)dst;
1910 BYTE* const oend = op + dstSize;
1911 const U32 dtLog = DTable[0];
1912 const void* dtPtr = DTable;
1913 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr)+1;
1914 BITv05_DStream_t bitD;
1916 if (dstSize <= cSrcSize) return ERROR(dstSize_tooSmall);
1917 { size_t const errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize);
1918 if (HUFv05_isError(errorCode)) return errorCode; }
1920 HUFv05_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1923 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
1928 size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1930 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
1931 const BYTE* ip = (const BYTE*) cSrc;
1934 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
1935 if (HUFv05_isError(errorCode)) return errorCode;
1936 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1938 cSrcSize -= errorCode;
1940 return HUFv05_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1944 size_t HUFv05_decompress4X2_usingDTable(
1945 void* dst, size_t dstSize,
1946 const void* cSrc, size_t cSrcSize,
1950 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1952 const BYTE* const istart = (const BYTE*) cSrc;
1953 BYTE* const ostart = (BYTE*) dst;
1954 BYTE* const oend = ostart + dstSize;
1955 const void* const dtPtr = DTable;
1956 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr) +1;
1957 const U32 dtLog = DTable[0];
1961 BITv05_DStream_t bitD1;
1962 BITv05_DStream_t bitD2;
1963 BITv05_DStream_t bitD3;
1964 BITv05_DStream_t bitD4;
1965 const size_t length1 = MEM_readLE16(istart);
1966 const size_t length2 = MEM_readLE16(istart+2);
1967 const size_t length3 = MEM_readLE16(istart+4);
1969 const BYTE* const istart1 = istart + 6; /* jumpTable */
1970 const BYTE* const istart2 = istart1 + length1;
1971 const BYTE* const istart3 = istart2 + length2;
1972 const BYTE* const istart4 = istart3 + length3;
1973 const size_t segmentSize = (dstSize+3) / 4;
1974 BYTE* const opStart2 = ostart + segmentSize;
1975 BYTE* const opStart3 = opStart2 + segmentSize;
1976 BYTE* const opStart4 = opStart3 + segmentSize;
1978 BYTE* op2 = opStart2;
1979 BYTE* op3 = opStart3;
1980 BYTE* op4 = opStart4;
1983 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1984 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1985 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
1986 if (HUFv05_isError(errorCode)) return errorCode;
1987 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
1988 if (HUFv05_isError(errorCode)) return errorCode;
1989 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
1990 if (HUFv05_isError(errorCode)) return errorCode;
1991 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
1992 if (HUFv05_isError(errorCode)) return errorCode;
1994 /* 16-32 symbols per loop (4-8 symbols per stream) */
1995 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
1996 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
1997 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
1998 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
1999 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2000 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2001 HUFv05_DECODE_SYMBOLX2_1(op1, &bitD1);
2002 HUFv05_DECODE_SYMBOLX2_1(op2, &bitD2);
2003 HUFv05_DECODE_SYMBOLX2_1(op3, &bitD3);
2004 HUFv05_DECODE_SYMBOLX2_1(op4, &bitD4);
2005 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
2006 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
2007 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2008 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2009 HUFv05_DECODE_SYMBOLX2_0(op1, &bitD1);
2010 HUFv05_DECODE_SYMBOLX2_0(op2, &bitD2);
2011 HUFv05_DECODE_SYMBOLX2_0(op3, &bitD3);
2012 HUFv05_DECODE_SYMBOLX2_0(op4, &bitD4);
2013 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2016 /* check corruption */
2017 if (op1 > opStart2) return ERROR(corruption_detected);
2018 if (op2 > opStart3) return ERROR(corruption_detected);
2019 if (op3 > opStart4) return ERROR(corruption_detected);
2020 /* note : op4 supposed already verified within main loop */
2022 /* finish bitStreams one by one */
2023 HUFv05_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2024 HUFv05_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2025 HUFv05_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2026 HUFv05_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2029 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2030 if (!endSignal) return ERROR(corruption_detected);
2038 size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2040 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
2041 const BYTE* ip = (const BYTE*) cSrc;
2044 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
2045 if (HUFv05_isError(errorCode)) return errorCode;
2046 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2048 cSrcSize -= errorCode;
2050 return HUFv05_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2054 /* *************************/
2055 /* double-symbols decoding */
2056 /* *************************/
2058 static void HUFv05_fillDTableX4Level2(HUFv05_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2059 const U32* rankValOrigin, const int minWeight,
2060 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2061 U32 nbBitsBaseline, U16 baseSeq)
2064 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2067 /* get pre-calculated rankVal */
2068 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2070 /* fill skipped values */
2072 U32 i, skipSize = rankVal[minWeight];
2073 MEM_writeLE16(&(DElt.sequence), baseSeq);
2074 DElt.nbBits = (BYTE)(consumed);
2076 for (i = 0; i < skipSize; i++)
2081 for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2082 const U32 symbol = sortedSymbols[s].symbol;
2083 const U32 weight = sortedSymbols[s].weight;
2084 const U32 nbBits = nbBitsBaseline - weight;
2085 const U32 length = 1 << (sizeLog-nbBits);
2086 const U32 start = rankVal[weight];
2088 const U32 end = start + length;
2090 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2091 DElt.nbBits = (BYTE)(nbBits + consumed);
2093 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2095 rankVal[weight] += length;
2099 typedef U32 rankVal_t[HUFv05_ABSOLUTEMAX_TABLELOG][HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2101 static void HUFv05_fillDTableX4(HUFv05_DEltX4* DTable, const U32 targetLog,
2102 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2103 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2104 const U32 nbBitsBaseline)
2106 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2107 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2108 const U32 minBits = nbBitsBaseline - maxWeight;
2111 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2114 for (s=0; s<sortedListSize; s++) {
2115 const U16 symbol = sortedList[s].symbol;
2116 const U32 weight = sortedList[s].weight;
2117 const U32 nbBits = nbBitsBaseline - weight;
2118 const U32 start = rankVal[weight];
2119 const U32 length = 1 << (targetLog-nbBits);
2121 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2123 int minWeight = nbBits + scaleLog;
2124 if (minWeight < 1) minWeight = 1;
2125 sortedRank = rankStart[minWeight];
2126 HUFv05_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2127 rankValOrigin[nbBits], minWeight,
2128 sortedList+sortedRank, sortedListSize-sortedRank,
2129 nbBitsBaseline, symbol);
2132 const U32 end = start + length;
2135 MEM_writeLE16(&(DElt.sequence), symbol);
2136 DElt.nbBits = (BYTE)(nbBits);
2138 for (i = start; i < end; i++)
2141 rankVal[weight] += length;
2145 size_t HUFv05_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize)
2147 BYTE weightList[HUFv05_MAX_SYMBOL_VALUE + 1];
2148 sortedSymbol_t sortedSymbol[HUFv05_MAX_SYMBOL_VALUE + 1];
2149 U32 rankStats[HUFv05_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2150 U32 rankStart0[HUFv05_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2151 U32* const rankStart = rankStart0+1;
2153 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2154 const U32 memLog = DTable[0];
2156 void* dtPtr = DTable;
2157 HUFv05_DEltX4* const dt = ((HUFv05_DEltX4*)dtPtr) + 1;
2159 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX4) == sizeof(unsigned)); /* if compilation fails here, assertion is false */
2160 if (memLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2161 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */
2163 iSize = HUFv05_readStats(weightList, HUFv05_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2164 if (HUFv05_isError(iSize)) return iSize;
2167 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2169 /* find maxWeight */
2170 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2172 /* Get start index of each weight */
2174 U32 w, nextRankStart = 0;
2175 for (w=1; w<=maxW; w++) {
2176 U32 current = nextRankStart;
2177 nextRankStart += rankStats[w];
2178 rankStart[w] = current;
2180 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2181 sizeOfSort = nextRankStart;
2184 /* sort symbols by weight */
2187 for (s=0; s<nbSymbols; s++) {
2188 U32 w = weightList[s];
2189 U32 r = rankStart[w]++;
2190 sortedSymbol[r].symbol = (BYTE)s;
2191 sortedSymbol[r].weight = (BYTE)w;
2193 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2198 const U32 minBits = tableLog+1 - maxW;
2199 U32 nextRankVal = 0;
2201 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2202 U32* rankVal0 = rankVal[0];
2203 for (w=1; w<=maxW; w++) {
2204 U32 current = nextRankVal;
2205 nextRankVal += rankStats[w] << (w+rescale);
2206 rankVal0[w] = current;
2208 for (consumed = minBits; consumed <= memLog - minBits; consumed++) {
2209 U32* rankValPtr = rankVal[consumed];
2210 for (w = 1; w <= maxW; w++) {
2211 rankValPtr[w] = rankVal0[w] >> consumed;
2214 HUFv05_fillDTableX4(dt, memLog,
2215 sortedSymbol, sizeOfSort,
2216 rankStart0, rankVal, maxW,
2223 static U32 HUFv05_decodeSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2225 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2226 memcpy(op, dt+val, 2);
2227 BITv05_skipBits(DStream, dt[val].nbBits);
2228 return dt[val].length;
2231 static U32 HUFv05_decodeLastSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2233 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2234 memcpy(op, dt+val, 1);
2235 if (dt[val].length==1) BITv05_skipBits(DStream, dt[val].nbBits);
2237 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2238 BITv05_skipBits(DStream, dt[val].nbBits);
2239 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2240 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 */
2246 #define HUFv05_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2247 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2249 #define HUFv05_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2250 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
2251 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2253 #define HUFv05_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2255 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2257 static inline size_t HUFv05_decodeStreamX4(BYTE* p, BITv05_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv05_DEltX4* const dt, const U32 dtLog)
2259 BYTE* const pStart = p;
2261 /* up to 8 symbols at a time */
2262 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd-7)) {
2263 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2264 HUFv05_DECODE_SYMBOLX4_1(p, bitDPtr);
2265 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2266 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2269 /* closer to the end */
2270 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-2))
2271 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2274 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2277 p += HUFv05_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2283 size_t HUFv05_decompress1X4_usingDTable(
2284 void* dst, size_t dstSize,
2285 const void* cSrc, size_t cSrcSize,
2286 const unsigned* DTable)
2288 const BYTE* const istart = (const BYTE*) cSrc;
2289 BYTE* const ostart = (BYTE*) dst;
2290 BYTE* const oend = ostart + dstSize;
2292 const U32 dtLog = DTable[0];
2293 const void* const dtPtr = DTable;
2294 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2298 BITv05_DStream_t bitD;
2299 errorCode = BITv05_initDStream(&bitD, istart, cSrcSize);
2300 if (HUFv05_isError(errorCode)) return errorCode;
2302 /* finish bitStreams one by one */
2303 HUFv05_decodeStreamX4(ostart, &bitD, oend, dt, dtLog);
2306 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
2312 size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2314 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2315 const BYTE* ip = (const BYTE*) cSrc;
2317 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2318 if (HUFv05_isError(hSize)) return hSize;
2319 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2323 return HUFv05_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2326 size_t HUFv05_decompress4X4_usingDTable(
2327 void* dst, size_t dstSize,
2328 const void* cSrc, size_t cSrcSize,
2329 const unsigned* DTable)
2331 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2334 const BYTE* const istart = (const BYTE*) cSrc;
2335 BYTE* const ostart = (BYTE*) dst;
2336 BYTE* const oend = ostart + dstSize;
2337 const void* const dtPtr = DTable;
2338 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2339 const U32 dtLog = DTable[0];
2343 BITv05_DStream_t bitD1;
2344 BITv05_DStream_t bitD2;
2345 BITv05_DStream_t bitD3;
2346 BITv05_DStream_t bitD4;
2347 const size_t length1 = MEM_readLE16(istart);
2348 const size_t length2 = MEM_readLE16(istart+2);
2349 const size_t length3 = MEM_readLE16(istart+4);
2351 const BYTE* const istart1 = istart + 6; /* jumpTable */
2352 const BYTE* const istart2 = istart1 + length1;
2353 const BYTE* const istart3 = istart2 + length2;
2354 const BYTE* const istart4 = istart3 + length3;
2355 const size_t segmentSize = (dstSize+3) / 4;
2356 BYTE* const opStart2 = ostart + segmentSize;
2357 BYTE* const opStart3 = opStart2 + segmentSize;
2358 BYTE* const opStart4 = opStart3 + segmentSize;
2360 BYTE* op2 = opStart2;
2361 BYTE* op3 = opStart3;
2362 BYTE* op4 = opStart4;
2365 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2366 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2367 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
2368 if (HUFv05_isError(errorCode)) return errorCode;
2369 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
2370 if (HUFv05_isError(errorCode)) return errorCode;
2371 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
2372 if (HUFv05_isError(errorCode)) return errorCode;
2373 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
2374 if (HUFv05_isError(errorCode)) return errorCode;
2376 /* 16-32 symbols per loop (4-8 symbols per stream) */
2377 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2378 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
2379 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2380 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2381 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2382 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2383 HUFv05_DECODE_SYMBOLX4_1(op1, &bitD1);
2384 HUFv05_DECODE_SYMBOLX4_1(op2, &bitD2);
2385 HUFv05_DECODE_SYMBOLX4_1(op3, &bitD3);
2386 HUFv05_DECODE_SYMBOLX4_1(op4, &bitD4);
2387 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2388 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2389 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2390 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2391 HUFv05_DECODE_SYMBOLX4_0(op1, &bitD1);
2392 HUFv05_DECODE_SYMBOLX4_0(op2, &bitD2);
2393 HUFv05_DECODE_SYMBOLX4_0(op3, &bitD3);
2394 HUFv05_DECODE_SYMBOLX4_0(op4, &bitD4);
2396 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2399 /* check corruption */
2400 if (op1 > opStart2) return ERROR(corruption_detected);
2401 if (op2 > opStart3) return ERROR(corruption_detected);
2402 if (op3 > opStart4) return ERROR(corruption_detected);
2403 /* note : op4 supposed already verified within main loop */
2405 /* finish bitStreams one by one */
2406 HUFv05_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2407 HUFv05_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2408 HUFv05_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2409 HUFv05_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2412 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2413 if (!endSignal) return ERROR(corruption_detected);
2421 size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2423 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2424 const BYTE* ip = (const BYTE*) cSrc;
2426 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2427 if (HUFv05_isError(hSize)) return hSize;
2428 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2432 return HUFv05_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2436 /* ********************************/
2437 /* Generic decompression selector */
2438 /* ********************************/
2440 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2441 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2443 /* single, double, quad */
2444 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2445 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2446 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2447 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2448 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2449 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2450 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2451 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2452 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2453 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2454 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2455 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2456 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2457 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2458 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2459 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2462 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2464 size_t HUFv05_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2466 static const decompressionAlgo decompress[3] = { HUFv05_decompress4X2, HUFv05_decompress4X4, NULL };
2467 /* estimate decompression time */
2469 const U32 D256 = (U32)(dstSize >> 8);
2474 /* validation checks */
2475 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2476 if (cSrcSize >= dstSize) return ERROR(corruption_detected); /* invalid, or not compressed, but not compressed already dealt with */
2477 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2479 /* decoder timing evaluation */
2480 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2482 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2484 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2486 if (Dtime[1] < Dtime[0]) algoNb = 1;
2488 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2490 /* return HUFv05_decompress4X2(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams single-symbol decoding */
2491 /* return HUFv05_decompress4X4(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams double-symbols decoding */
2492 /* return HUFv05_decompress4X6(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams quad-symbols decoding */
2495 zstd - standard compression library
2496 Copyright (C) 2014-2016, Yann Collet.
2498 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2500 Redistribution and use in source and binary forms, with or without
2501 modification, are permitted provided that the following conditions are
2503 * Redistributions of source code must retain the above copyright
2504 notice, this list of conditions and the following disclaimer.
2505 * Redistributions in binary form must reproduce the above
2506 copyright notice, this list of conditions and the following disclaimer
2507 in the documentation and/or other materials provided with the
2509 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2510 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2511 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2512 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2513 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2514 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2515 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2516 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2517 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2518 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2519 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2521 You can contact the author at :
2522 - zstd source repository : https://github.com/Cyan4973/zstd
2525 /* ***************************************************************
2527 *****************************************************************/
2530 * Select how default decompression function ZSTDv05_decompress() will allocate memory,
2531 * in memory stack (0), or in memory heap (1, requires malloc())
2533 #ifndef ZSTDv05_HEAPMODE
2534 # define ZSTDv05_HEAPMODE 1
2538 /*-*******************************************************
2540 *********************************************************/
2541 #include <stdlib.h> /* calloc */
2542 #include <string.h> /* memcpy, memmove */
2543 #include <stdio.h> /* debug only : printf */
2546 /*-*******************************************************
2547 * Compiler specifics
2548 *********************************************************/
2549 #ifdef _MSC_VER /* Visual Studio */
2550 # include <intrin.h> /* For Visual 2005 */
2551 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2552 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2556 /*-*************************************
2558 ***************************************/
2561 blockType_t blockType;
2563 } blockProperties_t;
2566 /* *******************************************************
2568 **********************************************************/
2569 static void ZSTDv05_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2572 /* *************************************
2574 ***************************************/
2575 /*! ZSTDv05_isError() :
2576 * tells if a return value is an error code */
2577 unsigned ZSTDv05_isError(size_t code) { return ERR_isError(code); }
2580 /*! ZSTDv05_getErrorName() :
2581 * provides error code string (useful for debugging) */
2582 const char* ZSTDv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
2585 /* *************************************************************
2586 * Context management
2587 ***************************************************************/
2588 typedef enum { ZSTDv05ds_getFrameHeaderSize, ZSTDv05ds_decodeFrameHeader,
2589 ZSTDv05ds_decodeBlockHeader, ZSTDv05ds_decompressBlock } ZSTDv05_dStage;
2591 struct ZSTDv05_DCtx_s
2593 FSEv05_DTable LLTable[FSEv05_DTABLE_SIZE_U32(LLFSEv05Log)];
2594 FSEv05_DTable OffTable[FSEv05_DTABLE_SIZE_U32(OffFSEv05Log)];
2595 FSEv05_DTable MLTable[FSEv05_DTABLE_SIZE_U32(MLFSEv05Log)];
2596 unsigned hufTableX4[HUFv05_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)];
2597 const void* previousDstEnd;
2600 const void* dictEnd;
2603 ZSTDv05_parameters params;
2604 blockType_t bType; /* used in ZSTDv05_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2605 ZSTDv05_dStage stage;
2606 U32 flagStaticTables;
2609 BYTE litBuffer[BLOCKSIZE + WILDCOPY_OVERLENGTH];
2610 BYTE headerBuffer[ZSTDv05_frameHeaderSize_max];
2611 }; /* typedef'd to ZSTDv05_DCtx within "zstd_static.h" */
2613 size_t ZSTDv05_sizeofDCtx (void); /* Hidden declaration */
2614 size_t ZSTDv05_sizeofDCtx (void) { return sizeof(ZSTDv05_DCtx); }
2616 size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx)
2618 dctx->expected = ZSTDv05_frameHeaderSize_min;
2619 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
2620 dctx->previousDstEnd = NULL;
2623 dctx->dictEnd = NULL;
2624 dctx->hufTableX4[0] = ZSTD_HUFFDTABLE_CAPACITY_LOG;
2625 dctx->flagStaticTables = 0;
2629 ZSTDv05_DCtx* ZSTDv05_createDCtx(void)
2631 ZSTDv05_DCtx* dctx = (ZSTDv05_DCtx*)malloc(sizeof(ZSTDv05_DCtx));
2632 if (dctx==NULL) return NULL;
2633 ZSTDv05_decompressBegin(dctx);
2637 size_t ZSTDv05_freeDCtx(ZSTDv05_DCtx* dctx)
2640 return 0; /* reserved as a potential error code in the future */
2643 void ZSTDv05_copyDCtx(ZSTDv05_DCtx* dstDCtx, const ZSTDv05_DCtx* srcDCtx)
2645 memcpy(dstDCtx, srcDCtx,
2646 sizeof(ZSTDv05_DCtx) - (BLOCKSIZE+WILDCOPY_OVERLENGTH + ZSTDv05_frameHeaderSize_max)); /* no need to copy workspace */
2650 /* *************************************************************
2651 * Decompression section
2652 ***************************************************************/
2654 /* Frame format description
2655 Frame Header - [ Block Header - Block ] - Frame End
2657 - 4 bytes - Magic Number : ZSTDv05_MAGICNUMBER (defined within zstd_internal.h)
2658 - 1 byte - Window Descriptor
2660 - 3 bytes, starting with a 2-bits descriptor
2661 Uncompressed, Compressed, Frame End, unused
2663 See Block Format Description
2665 - 3 bytes, compatible with Block Header
2668 /* Block format description
2670 Block = Literal Section - Sequences Section
2671 Prerequisite : size of (compressed) block, maximum size of regenerated data
2675 1.1) Header : 1-5 bytes
2677 00 compressed by Huff0
2679 10 is Raw (uncompressed)
2681 Note : using 01 => Huff0 with precomputed table ?
2682 Note : delta map ? => compressed ?
2684 1.1.1) Huff0-compressed literal block : 3-5 bytes
2685 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2686 srcSize < 1 KB => 3 bytes (2-2-10-10)
2687 srcSize < 16KB => 4 bytes (2-2-14-14)
2688 else => 5 bytes (2-2-18-18)
2689 big endian convention
2691 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2692 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2693 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2695 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2699 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2700 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
2701 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2703 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2707 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2708 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2709 srcSize < 1 KB => 3 bytes (2-2-10-10)
2710 srcSize < 16KB => 4 bytes (2-2-14-14)
2711 else => 5 bytes (2-2-18-18)
2712 big endian convention
2714 1- CTable available (stored into workspace ?)
2715 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2718 1.2) Literal block content
2720 1.2.1) Huff0 block, using sizes from header
2723 1.2.2) Huff0 block, using prepared table
2730 2) Sequences section
2735 /** ZSTDv05_decodeFrameHeader_Part1() :
2736 * decode the 1st part of the Frame Header, which tells Frame Header size.
2737 * srcSize must be == ZSTDv05_frameHeaderSize_min.
2738 * @return : the full size of the Frame Header */
2739 static size_t ZSTDv05_decodeFrameHeader_Part1(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2742 if (srcSize != ZSTDv05_frameHeaderSize_min)
2743 return ERROR(srcSize_wrong);
2744 magicNumber = MEM_readLE32(src);
2745 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2746 zc->headerSize = ZSTDv05_frameHeaderSize_min;
2747 return zc->headerSize;
2751 size_t ZSTDv05_getFrameParams(ZSTDv05_parameters* params, const void* src, size_t srcSize)
2754 if (srcSize < ZSTDv05_frameHeaderSize_min) return ZSTDv05_frameHeaderSize_max;
2755 magicNumber = MEM_readLE32(src);
2756 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2757 memset(params, 0, sizeof(*params));
2758 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTDv05_WINDOWLOG_ABSOLUTEMIN;
2759 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */
2763 /** ZSTDv05_decodeFrameHeader_Part2() :
2764 * decode the full Frame Header.
2765 * srcSize must be the size provided by ZSTDv05_decodeFrameHeader_Part1().
2766 * @return : 0, or an error code, which can be tested using ZSTDv05_isError() */
2767 static size_t ZSTDv05_decodeFrameHeader_Part2(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2770 if (srcSize != zc->headerSize)
2771 return ERROR(srcSize_wrong);
2772 result = ZSTDv05_getFrameParams(&(zc->params), src, srcSize);
2773 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported);
2778 static size_t ZSTDv05_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2780 const BYTE* const in = (const BYTE*)src;
2785 return ERROR(srcSize_wrong);
2788 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2790 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2791 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2793 if (bpPtr->blockType == bt_end) return 0;
2794 if (bpPtr->blockType == bt_rle) return 1;
2799 static size_t ZSTDv05_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2801 if (dst==NULL) return ERROR(dstSize_tooSmall);
2802 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2803 memcpy(dst, src, srcSize);
2808 /*! ZSTDv05_decodeLiteralsBlock() :
2809 @return : nb of bytes read from src (< srcSize ) */
2810 static size_t ZSTDv05_decodeLiteralsBlock(ZSTDv05_DCtx* dctx,
2811 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
2813 const BYTE* const istart = (const BYTE*) src;
2815 /* any compressed block with literals segment must be at least this size */
2816 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2818 switch(istart[0]>> 6)
2822 size_t litSize, litCSize, singleStream=0;
2823 U32 lhSize = ((istart[0]) >> 4) & 3;
2824 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
2827 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2828 /* 2 - 2 - 10 - 10 */
2830 singleStream = istart[0] & 16;
2831 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2832 litCSize = ((istart[1] & 3) << 8) + istart[2];
2835 /* 2 - 2 - 14 - 14 */
2837 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
2838 litCSize = ((istart[2] & 63) << 8) + istart[3];
2841 /* 2 - 2 - 18 - 18 */
2843 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
2844 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
2847 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2848 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2850 if (HUFv05_isError(singleStream ?
2851 HUFv05_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) :
2852 HUFv05_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
2853 return ERROR(corruption_detected);
2855 dctx->litPtr = dctx->litBuffer;
2856 dctx->litSize = litSize;
2857 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2858 return litCSize + lhSize;
2863 size_t litSize, litCSize;
2864 U32 lhSize = ((istart[0]) >> 4) & 3;
2865 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
2866 return ERROR(corruption_detected);
2867 if (!dctx->flagStaticTables)
2868 return ERROR(dictionary_corrupted);
2870 /* 2 - 2 - 10 - 10 */
2872 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2873 litCSize = ((istart[1] & 3) << 8) + istart[2];
2874 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2876 errorCode = HUFv05_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4);
2877 if (HUFv05_isError(errorCode)) return ERROR(corruption_detected);
2879 dctx->litPtr = dctx->litBuffer;
2880 dctx->litSize = litSize;
2881 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2882 return litCSize + lhSize;
2887 U32 lhSize = ((istart[0]) >> 4) & 3;
2890 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2892 litSize = istart[0] & 31;
2895 litSize = ((istart[0] & 15) << 8) + istart[1];
2898 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2902 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
2903 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
2904 memcpy(dctx->litBuffer, istart+lhSize, litSize);
2905 dctx->litPtr = dctx->litBuffer;
2906 dctx->litSize = litSize;
2907 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2908 return lhSize+litSize;
2910 /* direct reference into compressed stream */
2911 dctx->litPtr = istart+lhSize;
2912 dctx->litSize = litSize;
2913 return lhSize+litSize;
2918 U32 lhSize = ((istart[0]) >> 4) & 3;
2921 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2923 litSize = istart[0] & 31;
2926 litSize = ((istart[0] & 15) << 8) + istart[1];
2929 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2930 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
2933 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2934 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
2935 dctx->litPtr = dctx->litBuffer;
2936 dctx->litSize = litSize;
2940 return ERROR(corruption_detected); /* impossible */
2945 static size_t ZSTDv05_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2946 FSEv05_DTable* DTableLL, FSEv05_DTable* DTableML, FSEv05_DTable* DTableOffb,
2947 const void* src, size_t srcSize, U32 flagStaticTable)
2949 const BYTE* const istart = (const BYTE*)src;
2950 const BYTE* ip = istart;
2951 const BYTE* const iend = istart + srcSize;
2952 U32 LLtype, Offtype, MLtype;
2953 unsigned LLlog, Offlog, MLlog;
2957 if (srcSize < MIN_SEQUENCES_SIZE)
2958 return ERROR(srcSize_wrong);
2962 if (*nbSeq==0) return 1;
2963 if (*nbSeq >= 128) {
2964 if (ip >= iend) return ERROR(srcSize_wrong);
2965 *nbSeq = ((nbSeq[0]-128)<<8) + *ip++;
2968 if (ip >= iend) return ERROR(srcSize_wrong);
2970 Offtype = (*ip >> 4) & 3;
2971 MLtype = (*ip >> 2) & 3;
2973 if (ip+3 > iend) return ERROR(srcSize_wrong);
2974 dumpsLength = ip[2];
2975 dumpsLength += ip[1] << 8;
2978 if (ip+2 > iend) return ERROR(srcSize_wrong);
2979 dumpsLength = ip[1];
2980 dumpsLength += (ip[0] & 1) << 8;
2985 *dumpsLengthPtr = dumpsLength;
2988 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2992 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */
2998 case FSEv05_ENCODING_RLE :
3000 FSEv05_buildDTable_rle(DTableLL, *ip++);
3002 case FSEv05_ENCODING_RAW :
3004 FSEv05_buildDTable_raw(DTableLL, LLbits);
3006 case FSEv05_ENCODING_STATIC:
3007 if (!flagStaticTable) return ERROR(corruption_detected);
3009 case FSEv05_ENCODING_DYNAMIC :
3010 default : /* impossible */
3011 { unsigned max = MaxLL;
3012 headerSize = FSEv05_readNCount(norm, &max, &LLlog, ip, iend-ip);
3013 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3014 if (LLlog > LLFSEv05Log) return ERROR(corruption_detected);
3016 FSEv05_buildDTable(DTableLL, norm, max, LLlog);
3021 case FSEv05_ENCODING_RLE :
3023 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3024 FSEv05_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
3026 case FSEv05_ENCODING_RAW :
3028 FSEv05_buildDTable_raw(DTableOffb, Offbits);
3030 case FSEv05_ENCODING_STATIC:
3031 if (!flagStaticTable) return ERROR(corruption_detected);
3033 case FSEv05_ENCODING_DYNAMIC :
3034 default : /* impossible */
3035 { unsigned max = MaxOff;
3036 headerSize = FSEv05_readNCount(norm, &max, &Offlog, ip, iend-ip);
3037 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3038 if (Offlog > OffFSEv05Log) return ERROR(corruption_detected);
3040 FSEv05_buildDTable(DTableOffb, norm, max, Offlog);
3045 case FSEv05_ENCODING_RLE :
3047 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3048 FSEv05_buildDTable_rle(DTableML, *ip++);
3050 case FSEv05_ENCODING_RAW :
3052 FSEv05_buildDTable_raw(DTableML, MLbits);
3054 case FSEv05_ENCODING_STATIC:
3055 if (!flagStaticTable) return ERROR(corruption_detected);
3057 case FSEv05_ENCODING_DYNAMIC :
3058 default : /* impossible */
3059 { unsigned max = MaxML;
3060 headerSize = FSEv05_readNCount(norm, &max, &MLlog, ip, iend-ip);
3061 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3062 if (MLlog > MLFSEv05Log) return ERROR(corruption_detected);
3064 FSEv05_buildDTable(DTableML, norm, max, MLlog);
3078 BITv05_DStream_t DStream;
3079 FSEv05_DState_t stateLL;
3080 FSEv05_DState_t stateOffb;
3081 FSEv05_DState_t stateML;
3084 const BYTE* dumpsEnd;
3089 static void ZSTDv05_decodeSequence(seq_t* seq, seqState_t* seqState)
3095 const BYTE* dumps = seqState->dumps;
3096 const BYTE* const de = seqState->dumpsEnd;
3098 /* Literal length */
3099 litLength = FSEv05_peakSymbol(&(seqState->stateLL));
3100 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3101 if (litLength == MaxLL) {
3102 const U32 add = *dumps++;
3103 if (add < 255) litLength += add;
3104 else if (dumps + 2 <= de) {
3105 litLength = MEM_readLE16(dumps);
3107 if ((litLength & 1) && dumps < de) {
3108 litLength += *dumps << 16;
3113 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3118 static const U32 offsetPrefix[MaxOff+1] = {
3119 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3120 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3121 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3122 U32 offsetCode = FSEv05_peakSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3123 U32 nbBits = offsetCode - 1;
3124 if (offsetCode==0) nbBits = 0; /* cmove */
3125 offset = offsetPrefix[offsetCode] + BITv05_readBits(&(seqState->DStream), nbBits);
3126 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3127 if (offsetCode==0) offset = prevOffset; /* repcode, cmove */
3128 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */
3129 FSEv05_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* update */
3132 /* Literal length update */
3133 FSEv05_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); /* update */
3134 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3137 matchLength = FSEv05_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3138 if (matchLength == MaxML) {
3139 const U32 add = dumps<de ? *dumps++ : 0;
3140 if (add < 255) matchLength += add;
3141 else if (dumps + 2 <= de) {
3142 matchLength = MEM_readLE16(dumps);
3144 if ((matchLength & 1) && dumps < de) {
3145 matchLength += *dumps << 16;
3150 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3152 matchLength += MINMATCH;
3155 seq->litLength = litLength;
3156 seq->offset = offset;
3157 seq->matchLength = matchLength;
3158 seqState->dumps = dumps;
3162 static U64 totalDecoded = 0;
3163 printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n",
3164 (U32)(totalDecoded), (U32)litLength, (U32)matchLength, (U32)offset);
3165 totalDecoded += litLength + matchLength;
3171 static size_t ZSTDv05_execSequence(BYTE* op,
3172 BYTE* const oend, seq_t sequence,
3173 const BYTE** litPtr, const BYTE* const litLimit,
3174 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3176 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3177 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
3178 BYTE* const oLitEnd = op + sequence.litLength;
3179 const size_t sequenceLength = sequence.litLength + sequence.matchLength;
3180 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3181 BYTE* const oend_8 = oend-8;
3182 const BYTE* const litEnd = *litPtr + sequence.litLength;
3183 const BYTE* match = oLitEnd - sequence.offset;
3186 size_t const seqLength = sequence.litLength + sequence.matchLength;
3188 if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3189 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
3190 /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
3191 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
3193 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3194 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
3197 ZSTDv05_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3199 *litPtr = litEnd; /* update for next sequence */
3202 if (sequence.offset > (size_t)(oLitEnd - base)) {
3203 /* offset beyond prefix */
3204 if (sequence.offset > (size_t)(oLitEnd - vBase))
3205 return ERROR(corruption_detected);
3206 match = dictEnd - (base-match);
3207 if (match + sequence.matchLength <= dictEnd) {
3208 memmove(oLitEnd, match, sequence.matchLength);
3209 return sequenceLength;
3211 /* span extDict & currentPrefixSegment */
3213 size_t length1 = dictEnd - match;
3214 memmove(oLitEnd, match, length1);
3215 op = oLitEnd + length1;
3216 sequence.matchLength -= length1;
3218 if (op > oend_8 || sequence.matchLength < MINMATCH) {
3219 while (op < oMatchEnd) *op++ = *match++;
3220 return sequenceLength;
3223 /* Requirement: op <= oend_8 */
3225 /* match within prefix */
3226 if (sequence.offset < 8) {
3227 /* close range match, overlap */
3228 const int sub2 = dec64table[sequence.offset];
3233 match += dec32table[sequence.offset];
3234 ZSTDv05_copy4(op+4, match);
3237 ZSTDv05_copy8(op, match);
3239 op += 8; match += 8;
3241 if (oMatchEnd > oend-(16-MINMATCH)) {
3243 ZSTDv05_wildcopy(op, match, oend_8 - op);
3244 match += oend_8 - op;
3247 while (op < oMatchEnd)
3250 ZSTDv05_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3252 return sequenceLength;
3256 static size_t ZSTDv05_decompressSequences(
3258 void* dst, size_t maxDstSize,
3259 const void* seqStart, size_t seqSize)
3261 const BYTE* ip = (const BYTE*)seqStart;
3262 const BYTE* const iend = ip + seqSize;
3263 BYTE* const ostart = (BYTE*)dst;
3265 BYTE* const oend = ostart + maxDstSize;
3266 size_t errorCode, dumpsLength=0;
3267 const BYTE* litPtr = dctx->litPtr;
3268 const BYTE* const litEnd = litPtr + dctx->litSize;
3270 const BYTE* dumps = NULL;
3271 unsigned* DTableLL = dctx->LLTable;
3272 unsigned* DTableML = dctx->MLTable;
3273 unsigned* DTableOffb = dctx->OffTable;
3274 const BYTE* const base = (const BYTE*) (dctx->base);
3275 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3276 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3278 /* Build Decoding Tables */
3279 errorCode = ZSTDv05_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3280 DTableLL, DTableML, DTableOffb,
3281 ip, seqSize, dctx->flagStaticTables);
3282 if (ZSTDv05_isError(errorCode)) return errorCode;
3285 /* Regen sequences */
3288 seqState_t seqState;
3290 memset(&sequence, 0, sizeof(sequence));
3291 sequence.offset = REPCODE_STARTVALUE;
3292 seqState.dumps = dumps;
3293 seqState.dumpsEnd = dumps + dumpsLength;
3294 seqState.prevOffset = REPCODE_STARTVALUE;
3295 errorCode = BITv05_initDStream(&(seqState.DStream), ip, iend-ip);
3296 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3297 FSEv05_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3298 FSEv05_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3299 FSEv05_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3301 for ( ; (BITv05_reloadDStream(&(seqState.DStream)) <= BITv05_DStream_completed) && nbSeq ; ) {
3304 ZSTDv05_decodeSequence(&sequence, &seqState);
3305 oneSeqSize = ZSTDv05_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3306 if (ZSTDv05_isError(oneSeqSize)) return oneSeqSize;
3310 /* check if reached exact end */
3311 if (nbSeq) return ERROR(corruption_detected);
3314 /* last literal segment */
3316 size_t lastLLSize = litEnd - litPtr;
3317 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3318 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3319 if (lastLLSize > 0) {
3320 memcpy(op, litPtr, lastLLSize);
3329 static void ZSTDv05_checkContinuity(ZSTDv05_DCtx* dctx, const void* dst)
3331 if (dst != dctx->previousDstEnd) { /* not contiguous */
3332 dctx->dictEnd = dctx->previousDstEnd;
3333 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3335 dctx->previousDstEnd = dst;
3340 static size_t ZSTDv05_decompressBlock_internal(ZSTDv05_DCtx* dctx,
3341 void* dst, size_t dstCapacity,
3342 const void* src, size_t srcSize)
3343 { /* blockType == blockCompressed */
3344 const BYTE* ip = (const BYTE*)src;
3347 if (srcSize >= BLOCKSIZE) return ERROR(srcSize_wrong);
3349 /* Decode literals sub-block */
3350 litCSize = ZSTDv05_decodeLiteralsBlock(dctx, src, srcSize);
3351 if (ZSTDv05_isError(litCSize)) return litCSize;
3353 srcSize -= litCSize;
3355 return ZSTDv05_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3359 size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx,
3360 void* dst, size_t dstCapacity,
3361 const void* src, size_t srcSize)
3363 ZSTDv05_checkContinuity(dctx, dst);
3364 return ZSTDv05_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3368 /*! ZSTDv05_decompress_continueDCtx
3369 * dctx must have been properly initialized */
3370 static size_t ZSTDv05_decompress_continueDCtx(ZSTDv05_DCtx* dctx,
3371 void* dst, size_t maxDstSize,
3372 const void* src, size_t srcSize)
3374 const BYTE* ip = (const BYTE*)src;
3375 const BYTE* iend = ip + srcSize;
3376 BYTE* const ostart = (BYTE*)dst;
3378 BYTE* const oend = ostart + maxDstSize;
3379 size_t remainingSize = srcSize;
3380 blockProperties_t blockProperties;
3381 memset(&blockProperties, 0, sizeof(blockProperties));
3384 { size_t frameHeaderSize;
3385 if (srcSize < ZSTDv05_frameHeaderSize_min+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3386 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3387 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3388 if (srcSize < frameHeaderSize+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3389 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3390 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part2(dctx, src, frameHeaderSize);
3391 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3394 /* Loop on each block */
3397 size_t decodedSize=0;
3398 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, iend-ip, &blockProperties);
3399 if (ZSTDv05_isError(cBlockSize)) return cBlockSize;
3401 ip += ZSTDv05_blockHeaderSize;
3402 remainingSize -= ZSTDv05_blockHeaderSize;
3403 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3405 switch(blockProperties.blockType)
3408 decodedSize = ZSTDv05_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3411 decodedSize = ZSTDv05_copyRawBlock(op, oend-op, ip, cBlockSize);
3414 return ERROR(GENERIC); /* not yet supported */
3418 if (remainingSize) return ERROR(srcSize_wrong);
3421 return ERROR(GENERIC); /* impossible */
3423 if (cBlockSize == 0) break; /* bt_end */
3425 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3428 remainingSize -= cBlockSize;
3435 size_t ZSTDv05_decompress_usingPreparedDCtx(ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* refDCtx,
3436 void* dst, size_t maxDstSize,
3437 const void* src, size_t srcSize)
3439 ZSTDv05_copyDCtx(dctx, refDCtx);
3440 ZSTDv05_checkContinuity(dctx, dst);
3441 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3445 size_t ZSTDv05_decompress_usingDict(ZSTDv05_DCtx* dctx,
3446 void* dst, size_t maxDstSize,
3447 const void* src, size_t srcSize,
3448 const void* dict, size_t dictSize)
3450 ZSTDv05_decompressBegin_usingDict(dctx, dict, dictSize);
3451 ZSTDv05_checkContinuity(dctx, dst);
3452 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3456 size_t ZSTDv05_decompressDCtx(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3458 return ZSTDv05_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
3461 size_t ZSTDv05_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3463 #if defined(ZSTDv05_HEAPMODE) && (ZSTDv05_HEAPMODE==1)
3465 ZSTDv05_DCtx* dctx = ZSTDv05_createDCtx();
3466 if (dctx==NULL) return ERROR(memory_allocation);
3467 regenSize = ZSTDv05_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
3468 ZSTDv05_freeDCtx(dctx);
3472 return ZSTDv05_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
3476 /* ZSTD_errorFrameSizeInfoLegacy() :
3477 assumes `cSize` and `dBound` are _not_ NULL */
3478 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3481 *dBound = ZSTD_CONTENTSIZE_ERROR;
3484 void ZSTDv05_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3486 const BYTE* ip = (const BYTE*)src;
3487 size_t remainingSize = srcSize;
3488 size_t nbBlocks = 0;
3489 blockProperties_t blockProperties;
3492 if (srcSize < ZSTDv05_frameHeaderSize_min) {
3493 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3496 if (MEM_readLE32(src) != ZSTDv05_MAGICNUMBER) {
3497 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3500 ip += ZSTDv05_frameHeaderSize_min; remainingSize -= ZSTDv05_frameHeaderSize_min;
3502 /* Loop on each block */
3505 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, remainingSize, &blockProperties);
3506 if (ZSTDv05_isError(cBlockSize)) {
3507 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3511 ip += ZSTDv05_blockHeaderSize;
3512 remainingSize -= ZSTDv05_blockHeaderSize;
3513 if (cBlockSize > remainingSize) {
3514 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3518 if (cBlockSize == 0) break; /* bt_end */
3521 remainingSize -= cBlockSize;
3525 *cSize = ip - (const BYTE*)src;
3526 *dBound = nbBlocks * BLOCKSIZE;
3529 /* ******************************
3530 * Streaming Decompression API
3531 ********************************/
3532 size_t ZSTDv05_nextSrcSizeToDecompress(ZSTDv05_DCtx* dctx)
3534 return dctx->expected;
3537 size_t ZSTDv05_decompressContinue(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3540 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3541 ZSTDv05_checkContinuity(dctx, dst);
3543 /* Decompress : frame header; part 1 */
3544 switch (dctx->stage)
3546 case ZSTDv05ds_getFrameHeaderSize :
3547 /* get frame header size */
3548 if (srcSize != ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3549 dctx->headerSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3550 if (ZSTDv05_isError(dctx->headerSize)) return dctx->headerSize;
3551 memcpy(dctx->headerBuffer, src, ZSTDv05_frameHeaderSize_min);
3552 if (dctx->headerSize > ZSTDv05_frameHeaderSize_min) return ERROR(GENERIC); /* should never happen */
3553 dctx->expected = 0; /* not necessary to copy more */
3555 case ZSTDv05ds_decodeFrameHeader:
3556 /* get frame header */
3557 { size_t const result = ZSTDv05_decodeFrameHeader_Part2(dctx, dctx->headerBuffer, dctx->headerSize);
3558 if (ZSTDv05_isError(result)) return result;
3559 dctx->expected = ZSTDv05_blockHeaderSize;
3560 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3563 case ZSTDv05ds_decodeBlockHeader:
3565 /* Decode block header */
3566 blockProperties_t bp;
3567 size_t blockSize = ZSTDv05_getcBlockSize(src, ZSTDv05_blockHeaderSize, &bp);
3568 if (ZSTDv05_isError(blockSize)) return blockSize;
3569 if (bp.blockType == bt_end) {
3571 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
3574 dctx->expected = blockSize;
3575 dctx->bType = bp.blockType;
3576 dctx->stage = ZSTDv05ds_decompressBlock;
3580 case ZSTDv05ds_decompressBlock:
3582 /* Decompress : block content */
3587 rSize = ZSTDv05_decompressBlock_internal(dctx, dst, maxDstSize, src, srcSize);
3590 rSize = ZSTDv05_copyRawBlock(dst, maxDstSize, src, srcSize);
3593 return ERROR(GENERIC); /* not yet handled */
3595 case bt_end : /* should never happen (filtered at phase 1) */
3599 return ERROR(GENERIC); /* impossible */
3601 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3602 dctx->expected = ZSTDv05_blockHeaderSize;
3603 dctx->previousDstEnd = (char*)dst + rSize;
3607 return ERROR(GENERIC); /* impossible */
3612 static void ZSTDv05_refDictContent(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3614 dctx->dictEnd = dctx->previousDstEnd;
3615 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3617 dctx->previousDstEnd = (const char*)dict + dictSize;
3620 static size_t ZSTDv05_loadEntropy(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3622 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, errorCode, litlengthHeaderSize;
3623 short offcodeNCount[MaxOff+1];
3624 unsigned offcodeMaxValue=MaxOff, offcodeLog;
3625 short matchlengthNCount[MaxML+1];
3626 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3627 short litlengthNCount[MaxLL+1];
3628 unsigned litlengthMaxValue = MaxLL, litlengthLog;
3630 hSize = HUFv05_readDTableX4(dctx->hufTableX4, dict, dictSize);
3631 if (HUFv05_isError(hSize)) return ERROR(dictionary_corrupted);
3632 dict = (const char*)dict + hSize;
3635 offcodeHeaderSize = FSEv05_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize);
3636 if (FSEv05_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3637 if (offcodeLog > OffFSEv05Log) return ERROR(dictionary_corrupted);
3638 errorCode = FSEv05_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
3639 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3640 dict = (const char*)dict + offcodeHeaderSize;
3641 dictSize -= offcodeHeaderSize;
3643 matchlengthHeaderSize = FSEv05_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize);
3644 if (FSEv05_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3645 if (matchlengthLog > MLFSEv05Log) return ERROR(dictionary_corrupted);
3646 errorCode = FSEv05_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
3647 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3648 dict = (const char*)dict + matchlengthHeaderSize;
3649 dictSize -= matchlengthHeaderSize;
3651 litlengthHeaderSize = FSEv05_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize);
3652 if (litlengthLog > LLFSEv05Log) return ERROR(dictionary_corrupted);
3653 if (FSEv05_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3654 errorCode = FSEv05_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
3655 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3657 dctx->flagStaticTables = 1;
3658 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize;
3661 static size_t ZSTDv05_decompress_insertDictionary(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3664 U32 magic = MEM_readLE32(dict);
3665 if (magic != ZSTDv05_DICT_MAGIC) {
3666 /* pure content mode */
3667 ZSTDv05_refDictContent(dctx, dict, dictSize);
3670 /* load entropy tables */
3671 dict = (const char*)dict + 4;
3673 eSize = ZSTDv05_loadEntropy(dctx, dict, dictSize);
3674 if (ZSTDv05_isError(eSize)) return ERROR(dictionary_corrupted);
3676 /* reference dictionary content */
3677 dict = (const char*)dict + eSize;
3679 ZSTDv05_refDictContent(dctx, dict, dictSize);
3685 size_t ZSTDv05_decompressBegin_usingDict(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3688 errorCode = ZSTDv05_decompressBegin(dctx);
3689 if (ZSTDv05_isError(errorCode)) return errorCode;
3691 if (dict && dictSize) {
3692 errorCode = ZSTDv05_decompress_insertDictionary(dctx, dict, dictSize);
3693 if (ZSTDv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3700 Buffered version of Zstd compression library
3701 Copyright (C) 2015-2016, Yann Collet.
3703 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
3705 Redistribution and use in source and binary forms, with or without
3706 modification, are permitted provided that the following conditions are
3708 * Redistributions of source code must retain the above copyright
3709 notice, this list of conditions and the following disclaimer.
3710 * Redistributions in binary form must reproduce the above
3711 copyright notice, this list of conditions and the following disclaimer
3712 in the documentation and/or other materials provided with the
3714 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3715 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3716 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3717 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3718 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3719 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3720 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3721 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3722 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3723 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3724 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3726 You can contact the author at :
3727 - zstd source repository : https://github.com/Cyan4973/zstd
3728 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3731 /* The objects defined into this file should be considered experimental.
3732 * They are not labelled stable, as their prototype may change in the future.
3733 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3738 /* *************************************
3740 ***************************************/
3741 static size_t ZBUFFv05_blockHeaderSize = 3;
3745 /* *** Compression *** */
3747 static size_t ZBUFFv05_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3749 size_t length = MIN(maxDstSize, srcSize);
3751 memcpy(dst, src, length);
3759 /** ************************************************
3760 * Streaming decompression
3762 * A ZBUFFv05_DCtx object is required to track streaming operation.
3763 * Use ZBUFFv05_createDCtx() and ZBUFFv05_freeDCtx() to create/release resources.
3764 * Use ZBUFFv05_decompressInit() to start a new decompression operation.
3765 * ZBUFFv05_DCtx objects can be reused multiple times.
3767 * Use ZBUFFv05_decompressContinue() repetitively to consume your input.
3768 * *srcSizePtr and *maxDstSizePtr can be any size.
3769 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3770 * Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input.
3771 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3772 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3773 * or 0 when a frame is completely decoded
3774 * or an error code, which can be tested using ZBUFFv05_isError().
3776 * Hint : recommended buffer sizes (not compulsory)
3777 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3778 * input : just follow indications from ZBUFFv05_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3779 * **************************************************/
3781 typedef enum { ZBUFFv05ds_init, ZBUFFv05ds_readHeader, ZBUFFv05ds_loadHeader, ZBUFFv05ds_decodeHeader,
3782 ZBUFFv05ds_read, ZBUFFv05ds_load, ZBUFFv05ds_flush } ZBUFFv05_dStage;
3784 /* *** Resource management *** */
3786 #define ZSTDv05_frameHeaderSize_max 5 /* too magical, should come from reference */
3787 struct ZBUFFv05_DCtx_s {
3789 ZSTDv05_parameters params;
3798 ZBUFFv05_dStage stage;
3799 unsigned char headerBuffer[ZSTDv05_frameHeaderSize_max];
3800 }; /* typedef'd to ZBUFFv05_DCtx within "zstd_buffered.h" */
3803 ZBUFFv05_DCtx* ZBUFFv05_createDCtx(void)
3805 ZBUFFv05_DCtx* zbc = (ZBUFFv05_DCtx*)malloc(sizeof(ZBUFFv05_DCtx));
3806 if (zbc==NULL) return NULL;
3807 memset(zbc, 0, sizeof(*zbc));
3808 zbc->zc = ZSTDv05_createDCtx();
3809 zbc->stage = ZBUFFv05ds_init;
3813 size_t ZBUFFv05_freeDCtx(ZBUFFv05_DCtx* zbc)
3815 if (zbc==NULL) return 0; /* support free on null */
3816 ZSTDv05_freeDCtx(zbc->zc);
3824 /* *** Initialization *** */
3826 size_t ZBUFFv05_decompressInitDictionary(ZBUFFv05_DCtx* zbc, const void* dict, size_t dictSize)
3828 zbc->stage = ZBUFFv05ds_readHeader;
3829 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = 0;
3830 return ZSTDv05_decompressBegin_usingDict(zbc->zc, dict, dictSize);
3833 size_t ZBUFFv05_decompressInit(ZBUFFv05_DCtx* zbc)
3835 return ZBUFFv05_decompressInitDictionary(zbc, NULL, 0);
3839 /* *** Decompression *** */
3841 size_t ZBUFFv05_decompressContinue(ZBUFFv05_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3843 const char* const istart = (const char*)src;
3844 const char* ip = istart;
3845 const char* const iend = istart + *srcSizePtr;
3846 char* const ostart = (char*)dst;
3848 char* const oend = ostart + *maxDstSizePtr;
3854 case ZBUFFv05ds_init :
3855 return ERROR(init_missing);
3857 case ZBUFFv05ds_readHeader :
3858 /* read header from src */
3860 size_t headerSize = ZSTDv05_getFrameParams(&(zbc->params), src, *srcSizePtr);
3861 if (ZSTDv05_isError(headerSize)) return headerSize;
3863 /* not enough input to decode header : tell how many bytes would be necessary */
3864 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
3865 zbc->hPos += *srcSizePtr;
3867 zbc->stage = ZBUFFv05ds_loadHeader;
3868 return headerSize - zbc->hPos;
3870 zbc->stage = ZBUFFv05ds_decodeHeader;
3874 case ZBUFFv05ds_loadHeader:
3875 /* complete header from src */
3877 size_t headerSize = ZBUFFv05_limitCopy(
3878 zbc->headerBuffer + zbc->hPos, ZSTDv05_frameHeaderSize_max - zbc->hPos,
3880 zbc->hPos += headerSize;
3882 headerSize = ZSTDv05_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
3883 if (ZSTDv05_isError(headerSize)) return headerSize;
3885 /* not enough input to decode header : tell how many bytes would be necessary */
3887 return headerSize - zbc->hPos;
3889 /* zbc->stage = ZBUFFv05ds_decodeHeader; break; */ /* useless : stage follows */
3892 case ZBUFFv05ds_decodeHeader:
3893 /* apply header to create / resize buffers */
3895 size_t neededOutSize = (size_t)1 << zbc->params.windowLog;
3896 size_t neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */
3897 if (zbc->inBuffSize < neededInSize) {
3899 zbc->inBuffSize = neededInSize;
3900 zbc->inBuff = (char*)malloc(neededInSize);
3901 if (zbc->inBuff == NULL) return ERROR(memory_allocation);
3903 if (zbc->outBuffSize < neededOutSize) {
3905 zbc->outBuffSize = neededOutSize;
3906 zbc->outBuff = (char*)malloc(neededOutSize);
3907 if (zbc->outBuff == NULL) return ERROR(memory_allocation);
3910 /* some data already loaded into headerBuffer : transfer into inBuff */
3911 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
3912 zbc->inPos = zbc->hPos;
3914 zbc->stage = ZBUFFv05ds_load;
3917 zbc->stage = ZBUFFv05ds_read;
3919 case ZBUFFv05ds_read:
3921 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3922 if (neededInSize==0) { /* end of frame */
3923 zbc->stage = ZBUFFv05ds_init;
3927 if ((size_t)(iend-ip) >= neededInSize) {
3928 /* directly decode from src */
3929 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3930 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3932 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3934 if (!decodedSize) break; /* this was just a header */
3935 zbc->outEnd = zbc->outStart + decodedSize;
3936 zbc->stage = ZBUFFv05ds_flush;
3939 if (ip==iend) { notDone = 0; break; } /* no more input */
3940 zbc->stage = ZBUFFv05ds_load;
3943 case ZBUFFv05ds_load:
3945 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3946 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */
3948 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */
3949 loadedSize = ZBUFFv05_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
3951 zbc->inPos += loadedSize;
3952 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
3954 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3955 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3956 zbc->inBuff, neededInSize);
3957 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3958 zbc->inPos = 0; /* input is consumed */
3959 if (!decodedSize) { zbc->stage = ZBUFFv05ds_read; break; } /* this was just a header */
3960 zbc->outEnd = zbc->outStart + decodedSize;
3961 zbc->stage = ZBUFFv05ds_flush;
3962 /* break; */ /* ZBUFFv05ds_flush follows */
3966 case ZBUFFv05ds_flush:
3968 size_t toFlushSize = zbc->outEnd - zbc->outStart;
3969 size_t flushedSize = ZBUFFv05_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
3971 zbc->outStart += flushedSize;
3972 if (flushedSize == toFlushSize) {
3973 zbc->stage = ZBUFFv05ds_read;
3974 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
3975 zbc->outStart = zbc->outEnd = 0;
3978 /* cannot flush everything */
3982 default: return ERROR(GENERIC); /* impossible */
3985 *srcSizePtr = ip-istart;
3986 *maxDstSizePtr = op-ostart;
3988 { size_t nextSrcSizeHint = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3989 if (nextSrcSizeHint > ZBUFFv05_blockHeaderSize) nextSrcSizeHint+= ZBUFFv05_blockHeaderSize; /* get next block header too */
3990 nextSrcSizeHint -= zbc->inPos; /* already loaded*/
3991 return nextSrcSizeHint;
3997 /* *************************************
3999 ***************************************/
4000 unsigned ZBUFFv05_isError(size_t errorCode) { return ERR_isError(errorCode); }
4001 const char* ZBUFFv05_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
4003 size_t ZBUFFv05_recommendedDInSize(void) { return BLOCKSIZE + ZBUFFv05_blockHeaderSize /* block header size*/ ; }
4004 size_t ZBUFFv05_recommendedDOutSize(void) { return BLOCKSIZE; }