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.
12 /******************************************
14 ******************************************/
15 #include <stddef.h> /* size_t, ptrdiff_t */
16 #include <string.h> /* memcpy */
19 #include "../common/error_private.h"
22 /* ******************************************************************
24 *******************************************************************/
28 #if defined (__cplusplus)
33 /******************************************
35 ******************************************/
36 #if defined(_MSC_VER) /* Visual Studio */
37 # include <stdlib.h> /* _byteswap_ulong */
38 # include <intrin.h> /* _byteswap_* */
41 # define MEM_STATIC static __attribute__((unused))
42 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
43 # define MEM_STATIC static inline
44 #elif defined(_MSC_VER)
45 # define MEM_STATIC static __inline
47 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
51 /****************************************************************
53 *****************************************************************/
54 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
56 # include <inttypes.h>
58 # include <stdint.h> /* intptr_t */
68 typedef unsigned char BYTE;
69 typedef unsigned short U16;
70 typedef signed short S16;
71 typedef unsigned int U32;
72 typedef signed int S32;
73 typedef unsigned long long U64;
74 typedef signed long long S64;
78 /*-*************************************
80 ***************************************/
81 #include "../common/debug.h"
83 # define assert(condition) ((void)0)
87 /****************************************************************
89 *****************************************************************/
91 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
92 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
94 MEM_STATIC unsigned MEM_isLittleEndian(void)
96 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
100 MEM_STATIC U16 MEM_read16(const void* memPtr)
102 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
105 MEM_STATIC U32 MEM_read32(const void* memPtr)
107 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
110 MEM_STATIC U64 MEM_read64(const void* memPtr)
112 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
115 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
117 memcpy(memPtr, &value, sizeof(value));
120 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
122 if (MEM_isLittleEndian())
123 return MEM_read16(memPtr);
126 const BYTE* p = (const BYTE*)memPtr;
127 return (U16)(p[0] + (p[1]<<8));
131 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
133 if (MEM_isLittleEndian())
135 MEM_write16(memPtr, val);
139 BYTE* p = (BYTE*)memPtr;
141 p[1] = (BYTE)(val>>8);
145 MEM_STATIC U32 MEM_readLE24(const void* memPtr)
147 return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
150 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
152 if (MEM_isLittleEndian())
153 return MEM_read32(memPtr);
156 const BYTE* p = (const BYTE*)memPtr;
157 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
162 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
164 if (MEM_isLittleEndian())
165 return MEM_read64(memPtr);
168 const BYTE* p = (const BYTE*)memPtr;
169 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
170 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
175 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
178 return (size_t)MEM_readLE32(memPtr);
180 return (size_t)MEM_readLE64(memPtr);
184 #if defined (__cplusplus)
188 #endif /* MEM_H_MODULE */
191 zstd - standard compression library
192 Header File for static linking only
194 #ifndef ZSTD_STATIC_H
195 #define ZSTD_STATIC_H
198 /* *************************************
200 ***************************************/
201 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 11
203 /** from faster to stronger */
204 typedef enum { ZSTD_fast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2 } ZSTD_strategy;
208 U64 srcSize; /* optional : tells how much bytes are present in the frame. Use 0 if not known. */
209 U32 windowLog; /* largest match distance : larger == more compression, more memory needed during decompression */
210 U32 contentLog; /* full search segment : larger == more compression, slower, more memory (useless for fast) */
211 U32 hashLog; /* dispatch table : larger == more memory, faster */
212 U32 searchLog; /* nb of searches : larger == more compression, slower */
213 U32 searchLength; /* size of matches : larger == faster decompression, sometimes less compression */
214 ZSTD_strategy strategy;
217 typedef ZSTDv04_Dctx ZSTD_DCtx;
219 /* *************************************
221 ***************************************/
222 /** ZSTD_decompress_usingDict
223 * Same as ZSTD_decompressDCtx, using a Dictionary content as prefix
224 * Note : dict can be NULL, in which case, it's equivalent to ZSTD_decompressDCtx() */
225 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
226 void* dst, size_t maxDstSize,
227 const void* src, size_t srcSize,
228 const void* dict,size_t dictSize);
231 /* **************************************
232 * Streaming functions (direct mode)
233 ****************************************/
234 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx);
235 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize);
236 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* src, size_t srcSize);
238 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx);
239 static size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize);
242 Streaming decompression, bufferless mode
244 A ZSTD_DCtx object is required to track streaming operations.
245 Use ZSTD_createDCtx() / ZSTD_freeDCtx() to manage it.
246 A ZSTD_DCtx object can be re-used multiple times. Use ZSTD_resetDCtx() to return to fresh status.
248 First operation is to retrieve frame parameters, using ZSTD_getFrameParams().
249 This function doesn't consume its input. It needs enough input data to properly decode the frame header.
250 Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.
251 Result : 0 when successful, it means the ZSTD_parameters structure has been filled.
252 >0 : means there is not enough data into src. Provides the expected size to successfully decode header.
253 errorCode, which can be tested using ZSTD_isError() (For example, if it's not a ZSTD header)
255 Then, you can optionally insert a dictionary.
256 This operation must mimic the compressor behavior, otherwise decompression will fail or be corrupted.
258 Then it's possible to start decompression.
259 Use ZSTD_nextSrcSizeToDecompress() and ZSTD_decompressContinue() alternatively.
260 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
261 ZSTD_decompressContinue() requires this exact amount of bytes, or it will fail.
262 ZSTD_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
263 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
265 @result of ZSTD_decompressContinue() is the number of bytes regenerated within 'dst'.
266 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
268 A frame is fully decoded when ZSTD_nextSrcSizeToDecompress() returns zero.
269 Context can then be reset to start a new decompression.
275 #endif /* ZSTD_STATIC_H */
279 zstd_internal - common functions to include
280 Header File for include
282 #ifndef ZSTD_CCOMMON_H_MODULE
283 #define ZSTD_CCOMMON_H_MODULE
285 /* *************************************
287 ***************************************/
288 #define MIN(a,b) ((a)<(b) ? (a) : (b))
289 #define MAX(a,b) ((a)>(b) ? (a) : (b))
292 /* *************************************
294 ***************************************/
295 #define ZSTD_MAGICNUMBER 0xFD2FB524 /* v0.4 */
301 #define BLOCKSIZE (128 KB) /* define, for static allocation */
303 static const size_t ZSTD_blockHeaderSize = 3;
304 static const size_t ZSTD_frameHeaderSize_min = 5;
305 #define ZSTD_frameHeaderSize_max 5 /* define, for static allocation */
318 #define REPCODE_STARTVALUE 4
323 #define MaxML ((1<<MLbits) - 1)
324 #define MaxLL ((1<<LLbits) - 1)
325 #define MaxOff ((1<<Offbits)- 1)
329 #define MaxSeq MAX(MaxLL, MaxML)
331 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
332 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
334 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
336 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
339 /* ******************************************
340 * Shared functions to include for inlining
341 ********************************************/
342 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
344 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
346 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
347 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
349 const BYTE* ip = (const BYTE*)src;
350 BYTE* op = (BYTE*)dst;
351 BYTE* const oend = op + length;
359 /* ******************************************************************
360 FSE : Finite State Entropy coder
362 ****************************************************************** */
366 #if defined (__cplusplus)
371 /* *****************************************
373 ******************************************/
374 #include <stddef.h> /* size_t, ptrdiff_t */
377 /* *****************************************
378 * FSE simple functions
379 ******************************************/
380 static size_t FSE_decompress(void* dst, size_t maxDstSize,
381 const void* cSrc, size_t cSrcSize);
384 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
385 into already allocated destination buffer 'dst', of size 'maxDstSize'.
386 return : size of regenerated data (<= maxDstSize)
387 or an error code, which can be tested using FSE_isError()
389 ** Important ** : FSE_decompress() doesn't decompress non-compressible nor RLE data !!!
390 Why ? : making this distinction requires a header.
391 Header management is intentionally delegated to the user layer, which can better manage special cases.
395 /* *****************************************
397 ******************************************/
398 /* Error Management */
399 static unsigned FSE_isError(size_t code); /* tells if a return value is an error code */
403 /* *****************************************
405 ******************************************/
407 FSE_compress() does the following:
408 1. count symbol occurrence from source[] into table count[]
409 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
410 3. save normalized counters to memory buffer using writeNCount()
411 4. build encoding table 'CTable' from normalized counters
412 5. encode the data stream using encoding table 'CTable'
414 FSE_decompress() does the following:
415 1. read normalized counters with readNCount()
416 2. build decoding table 'DTable' from normalized counters
417 3. decode the data stream using decoding table 'DTable'
419 The following API allows targeting specific sub-functions for advanced tasks.
420 For example, it's possible to compress several blocks using the same 'CTable',
421 or to save and provide normalized distribution using external method.
425 /* *** DECOMPRESSION *** */
429 Read compactly saved 'normalizedCounter' from 'rBuffer'.
430 return : size read from 'rBuffer'
431 or an errorCode, which can be tested using FSE_isError()
432 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
433 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
436 Constructor and Destructor of type FSE_DTable
437 Note that its size depends on 'tableLog' */
438 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
442 Builds 'dt', which must be already allocated, using FSE_createDTable()
444 or an errorCode, which can be tested using FSE_isError() */
445 static size_t FSE_buildDTable ( FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
448 FSE_decompress_usingDTable():
449 Decompress compressed source 'cSrc' of size 'cSrcSize' using 'dt'
450 into 'dst' which must be already allocated.
451 return : size of regenerated data (necessarily <= maxDstSize)
452 or an errorCode, which can be tested using FSE_isError() */
453 static size_t FSE_decompress_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt);
458 (Note : these functions only decompress FSE-compressed blocks.
459 If block is uncompressed, use memcpy() instead
460 If block is a single repeated byte, use memset() instead )
462 The first step is to obtain the normalized frequencies of symbols.
463 This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount().
464 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
465 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
466 or size the table to handle worst case situations (typically 256).
467 FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
468 The result of FSE_readNCount() is the number of bytes read from 'rBuffer'.
469 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
470 If there is an error, the function will return an error code, which can be tested using FSE_isError().
472 The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'.
473 This is performed by the function FSE_buildDTable().
474 The space required by 'FSE_DTable' must be already allocated using FSE_createDTable().
475 If there is an error, the function will return an error code, which can be tested using FSE_isError().
477 'FSE_DTable' can then be used to decompress 'cSrc', with FSE_decompress_usingDTable().
478 'cSrcSize' must be strictly correct, otherwise decompression will fail.
479 FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=maxDstSize).
480 If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small)
484 #if defined (__cplusplus)
491 /* ******************************************************************
493 Part of NewGen Entropy library
494 header file (to include)
495 Copyright (C) 2013-2015, Yann Collet.
497 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
499 Redistribution and use in source and binary forms, with or without
500 modification, are permitted provided that the following conditions are
503 * Redistributions of source code must retain the above copyright
504 notice, this list of conditions and the following disclaimer.
505 * Redistributions in binary form must reproduce the above
506 copyright notice, this list of conditions and the following disclaimer
507 in the documentation and/or other materials provided with the
510 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
511 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
512 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
513 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
514 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
515 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
516 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
517 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
518 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
519 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
520 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
522 You can contact the author at :
523 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
524 - Public forum : https://groups.google.com/forum/#!forum/lz4c
525 ****************************************************************** */
526 #ifndef BITSTREAM_H_MODULE
527 #define BITSTREAM_H_MODULE
529 #if defined (__cplusplus)
535 * This API consists of small unitary functions, which highly benefit from being inlined.
536 * Since link-time-optimization is not available for all compilers,
537 * these functions are defined into a .h to be included.
540 /**********************************************
541 * bitStream decompression API (read backward)
542 **********************************************/
546 unsigned bitsConsumed;
551 typedef enum { BIT_DStream_unfinished = 0,
552 BIT_DStream_endOfBuffer = 1,
553 BIT_DStream_completed = 2,
554 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
555 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
557 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
558 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
559 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
560 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
565 /******************************************
567 ******************************************/
568 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
569 /* faster, but works only if nbBits >= 1 */
573 /****************************************************************
575 ****************************************************************/
576 MEM_STATIC unsigned BIT_highbit32 (U32 val)
578 # if defined(_MSC_VER) /* Visual */
580 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
581 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
582 return __builtin_clz (val) ^ 31;
583 # else /* Software version */
584 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 };
592 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
598 /**********************************************************
600 **********************************************************/
603 * Initialize a BIT_DStream_t.
604 * @bitD : a pointer to an already allocated BIT_DStream_t structure
605 * @srcBuffer must point at the beginning of a bitStream
606 * @srcSize must be the exact size of the bitStream
607 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
609 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
611 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
613 if (srcSize >= sizeof(size_t)) /* normal case */
616 bitD->start = (const char*)srcBuffer;
617 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
618 bitD->bitContainer = MEM_readLEST(bitD->ptr);
619 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
620 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
621 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
626 bitD->start = (const char*)srcBuffer;
627 bitD->ptr = bitD->start;
628 bitD->bitContainer = *(const BYTE*)(bitD->start);
631 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
632 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
633 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
634 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
635 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
636 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */
639 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
640 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
641 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
642 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
648 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
650 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
651 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
654 /*! BIT_lookBitsFast :
655 * unsafe version; only works if nbBits >= 1 */
656 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
658 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
659 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
662 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
664 bitD->bitsConsumed += nbBits;
667 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
669 size_t value = BIT_lookBits(bitD, nbBits);
670 BIT_skipBits(bitD, nbBits);
674 /*!BIT_readBitsFast :
675 * unsafe version; only works if nbBits >= 1 */
676 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
678 size_t value = BIT_lookBitsFast(bitD, nbBits);
679 BIT_skipBits(bitD, nbBits);
683 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
685 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
686 return BIT_DStream_overflow;
688 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
690 bitD->ptr -= bitD->bitsConsumed >> 3;
691 bitD->bitsConsumed &= 7;
692 bitD->bitContainer = MEM_readLEST(bitD->ptr);
693 return BIT_DStream_unfinished;
695 if (bitD->ptr == bitD->start)
697 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
698 return BIT_DStream_completed;
701 U32 nbBytes = bitD->bitsConsumed >> 3;
702 BIT_DStream_status result = BIT_DStream_unfinished;
703 if (bitD->ptr - nbBytes < bitD->start)
705 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
706 result = BIT_DStream_endOfBuffer;
708 bitD->ptr -= nbBytes;
709 bitD->bitsConsumed -= nbBytes*8;
710 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
716 * @return Tells if DStream has reached its exact end
718 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
720 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
723 #if defined (__cplusplus)
727 #endif /* BITSTREAM_H_MODULE */
731 /* ******************************************************************
732 FSE : Finite State Entropy coder
733 header file for static linking (only)
734 Copyright (C) 2013-2015, Yann Collet
736 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
738 Redistribution and use in source and binary forms, with or without
739 modification, are permitted provided that the following conditions are
742 * Redistributions of source code must retain the above copyright
743 notice, this list of conditions and the following disclaimer.
744 * Redistributions in binary form must reproduce the above
745 copyright notice, this list of conditions and the following disclaimer
746 in the documentation and/or other materials provided with the
749 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
750 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
751 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
752 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
753 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
754 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
755 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
756 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
757 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
758 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
759 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
761 You can contact the author at :
762 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
763 - Public forum : https://groups.google.com/forum/#!forum/lz4c
764 ****************************************************************** */
768 #if defined (__cplusplus)
773 /* *****************************************
775 *******************************************/
776 /* FSE buffer bounds */
777 #define FSE_NCOUNTBOUND 512
778 #define FSE_BLOCKBOUND(size) (size + (size>>7))
779 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
781 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
782 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
783 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
786 /* *****************************************
788 *******************************************/
789 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
790 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
792 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
793 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
797 /* *****************************************
798 * FSE symbol decompression API
799 *******************************************/
803 const void* table; /* precise table may vary, depending on U16 */
807 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
809 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
811 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
814 /* *****************************************
816 *******************************************/
817 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
818 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
821 /* *****************************************
822 * Implementation of inlined functions
823 *******************************************/
829 } FSE_DTableHeader; /* sizeof U32 */
833 unsigned short newState;
834 unsigned char symbol;
835 unsigned char nbBits;
836 } FSE_decode_t; /* size == U32 */
838 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
840 FSE_DTableHeader DTableH;
841 memcpy(&DTableH, dt, sizeof(DTableH));
842 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
843 BIT_reloadDStream(bitD);
844 DStatePtr->table = dt + 1;
847 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
849 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
850 const U32 nbBits = DInfo.nbBits;
851 BYTE symbol = DInfo.symbol;
852 size_t lowBits = BIT_readBits(bitD, nbBits);
854 DStatePtr->state = DInfo.newState + lowBits;
858 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
860 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
861 const U32 nbBits = DInfo.nbBits;
862 BYTE symbol = DInfo.symbol;
863 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
865 DStatePtr->state = DInfo.newState + lowBits;
869 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
871 return DStatePtr->state == 0;
875 #if defined (__cplusplus)
879 #endif /* FSE_STATIC_H */
881 /* ******************************************************************
882 FSE : Finite State Entropy coder
883 Copyright (C) 2013-2015, Yann Collet.
885 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
887 Redistribution and use in source and binary forms, with or without
888 modification, are permitted provided that the following conditions are
891 * Redistributions of source code must retain the above copyright
892 notice, this list of conditions and the following disclaimer.
893 * Redistributions in binary form must reproduce the above
894 copyright notice, this list of conditions and the following disclaimer
895 in the documentation and/or other materials provided with the
898 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
899 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
900 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
901 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
902 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
903 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
904 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
905 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
906 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
907 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
908 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
910 You can contact the author at :
911 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
912 - Public forum : https://groups.google.com/forum/#!forum/lz4c
913 ****************************************************************** */
915 #ifndef FSE_COMMONDEFS_ONLY
917 /* **************************************************************
919 ****************************************************************/
921 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
922 * Increasing memory usage improves compression ratio
923 * Reduced memory usage can improve speed, due to cache effect
924 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
925 #define FSE_MAX_MEMORY_USAGE 14
926 #define FSE_DEFAULT_MEMORY_USAGE 13
928 /*!FSE_MAX_SYMBOL_VALUE :
929 * Maximum symbol value authorized.
930 * Required for proper stack allocation */
931 #define FSE_MAX_SYMBOL_VALUE 255
934 /* **************************************************************
935 * template functions type & suffix
936 ****************************************************************/
937 #define FSE_FUNCTION_TYPE BYTE
938 #define FSE_FUNCTION_EXTENSION
939 #define FSE_DECODE_TYPE FSE_decode_t
942 #endif /* !FSE_COMMONDEFS_ONLY */
944 /* **************************************************************
946 ****************************************************************/
947 #ifdef _MSC_VER /* Visual Studio */
948 # define FORCE_INLINE static __forceinline
949 # include <intrin.h> /* For Visual 2005 */
950 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
951 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
953 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
955 # define FORCE_INLINE static inline __attribute__((always_inline))
957 # define FORCE_INLINE static inline
960 # define FORCE_INLINE static
961 # endif /* __STDC_VERSION__ */
965 /* **************************************************************
967 ****************************************************************/
968 #include <stdlib.h> /* malloc, free, qsort */
969 #include <string.h> /* memcpy, memset */
970 #include <stdio.h> /* printf (debug) */
973 /* ***************************************************************
975 *****************************************************************/
976 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
977 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
978 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
979 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
980 #define FSE_MIN_TABLELOG 5
982 #define FSE_TABLELOG_ABSOLUTE_MAX 15
983 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
984 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
988 /* **************************************************************
990 ****************************************************************/
991 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
994 /* **************************************************************
996 ****************************************************************/
997 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1000 /*-**************************************************************
1002 ****************************************************************/
1004 designed to be included
1005 for type-specific functions (template emulation in C)
1006 Objective is to write these functions only once, for improved maintenance
1010 #ifndef FSE_FUNCTION_EXTENSION
1011 # error "FSE_FUNCTION_EXTENSION must be defined"
1013 #ifndef FSE_FUNCTION_TYPE
1014 # error "FSE_FUNCTION_TYPE must be defined"
1017 /* Function names */
1018 #define FSE_CAT(X,Y) X##Y
1019 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1020 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1022 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1025 static size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1027 FSE_DTableHeader DTableH;
1028 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */
1029 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
1030 const U32 tableSize = 1 << tableLog;
1031 const U32 tableMask = tableSize-1;
1032 const U32 step = FSE_tableStep(tableSize);
1033 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1035 U32 highThreshold = tableSize-1;
1036 const S16 largeLimit= (S16)(1 << (tableLog-1));
1041 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1042 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1044 /* Init, lay down lowprob symbols */
1045 memset(tableDecode, 0, sizeof(FSE_DECODE_TYPE) * (maxSymbolValue+1) ); /* useless init, but keep static analyzer happy, and we don't need to performance optimize legacy decoders */
1046 DTableH.tableLog = (U16)tableLog;
1047 for (s=0; s<=maxSymbolValue; s++)
1049 if (normalizedCounter[s]==-1)
1051 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1056 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1057 symbolNext[s] = normalizedCounter[s];
1061 /* Spread symbols */
1062 for (s=0; s<=maxSymbolValue; s++)
1065 for (i=0; i<normalizedCounter[s]; i++)
1067 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1068 position = (position + step) & tableMask;
1069 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1073 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1075 /* Build Decoding table */
1078 for (i=0; i<tableSize; i++)
1080 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1081 U16 nextState = symbolNext[symbol]++;
1082 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1083 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1087 DTableH.fastMode = (U16)noLarge;
1088 memcpy(dt, &DTableH, sizeof(DTableH));
1093 #ifndef FSE_COMMONDEFS_ONLY
1094 /******************************************
1095 * FSE helper functions
1096 ******************************************/
1097 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1100 /****************************************************************
1101 * FSE NCount encoding-decoding
1102 ****************************************************************/
1103 static short FSE_abs(short a)
1105 return a<0 ? -a : a;
1108 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1109 const void* headerBuffer, size_t hbSize)
1111 const BYTE* const istart = (const BYTE*) headerBuffer;
1112 const BYTE* const iend = istart + hbSize;
1113 const BYTE* ip = istart;
1119 unsigned charnum = 0;
1122 if (hbSize < 4) return ERROR(srcSize_wrong);
1123 bitStream = MEM_readLE32(ip);
1124 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1125 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1128 *tableLogPtr = nbBits;
1129 remaining = (1<<nbBits)+1;
1130 threshold = 1<<nbBits;
1133 while ((remaining>1) && (charnum<=*maxSVPtr))
1137 unsigned n0 = charnum;
1138 while ((bitStream & 0xFFFF) == 0xFFFF)
1144 bitStream = MEM_readLE32(ip) >> bitCount;
1152 while ((bitStream & 3) == 3)
1158 n0 += bitStream & 3;
1160 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1161 while (charnum < n0) normalizedCounter[charnum++] = 0;
1162 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1166 bitStream = MEM_readLE32(ip) >> bitCount;
1172 const short max = (short)((2*threshold-1)-remaining);
1175 if ((bitStream & (threshold-1)) < (U32)max)
1177 count = (short)(bitStream & (threshold-1));
1178 bitCount += nbBits-1;
1182 count = (short)(bitStream & (2*threshold-1));
1183 if (count >= threshold) count -= max;
1187 count--; /* extra accuracy */
1188 remaining -= FSE_abs(count);
1189 normalizedCounter[charnum++] = count;
1191 while (remaining < threshold)
1198 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1205 bitCount -= (int)(8 * (iend - 4 - ip));
1208 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1212 if (remaining != 1) return ERROR(GENERIC);
1213 *maxSVPtr = charnum-1;
1215 ip += (bitCount+7)>>3;
1216 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1221 /*********************************************************
1222 * Decompression (Byte symbols)
1223 *********************************************************/
1224 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1227 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1228 void* dPtr = dt + 1;
1229 FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
1231 DTableH->tableLog = 0;
1232 DTableH->fastMode = 0;
1235 cell->symbol = symbolValue;
1242 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1245 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1246 void* dPtr = dt + 1;
1247 FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
1248 const unsigned tableSize = 1 << nbBits;
1249 const unsigned tableMask = tableSize - 1;
1250 const unsigned maxSymbolValue = tableMask;
1254 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1256 /* Build Decoding Table */
1257 DTableH->tableLog = (U16)nbBits;
1258 DTableH->fastMode = 1;
1259 for (s=0; s<=maxSymbolValue; s++)
1261 dinfo[s].newState = 0;
1262 dinfo[s].symbol = (BYTE)s;
1263 dinfo[s].nbBits = (BYTE)nbBits;
1269 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1270 void* dst, size_t maxDstSize,
1271 const void* cSrc, size_t cSrcSize,
1272 const FSE_DTable* dt, const unsigned fast)
1274 BYTE* const ostart = (BYTE*) dst;
1276 BYTE* const omax = op + maxDstSize;
1277 BYTE* const olimit = omax-3;
1280 FSE_DState_t state1;
1281 FSE_DState_t state2;
1285 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1286 if (FSE_isError(errorCode)) return errorCode;
1288 FSE_initDState(&state1, &bitD, dt);
1289 FSE_initDState(&state2, &bitD, dt);
1291 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1293 /* 4 symbols per loop */
1294 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1296 op[0] = FSE_GETSYMBOL(&state1);
1298 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1299 BIT_reloadDStream(&bitD);
1301 op[1] = FSE_GETSYMBOL(&state2);
1303 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1304 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1306 op[2] = FSE_GETSYMBOL(&state1);
1308 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1309 BIT_reloadDStream(&bitD);
1311 op[3] = FSE_GETSYMBOL(&state2);
1315 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1318 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1321 *op++ = FSE_GETSYMBOL(&state1);
1323 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1326 *op++ = FSE_GETSYMBOL(&state2);
1330 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1333 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1335 return ERROR(corruption_detected);
1339 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1340 const void* cSrc, size_t cSrcSize,
1341 const FSE_DTable* dt)
1343 FSE_DTableHeader DTableH;
1346 memcpy(&DTableH, dt, sizeof(DTableH));
1347 fastMode = DTableH.fastMode;
1349 /* select fast mode (static) */
1350 if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1351 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1355 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1357 const BYTE* const istart = (const BYTE*)cSrc;
1358 const BYTE* ip = istart;
1359 short counting[FSE_MAX_SYMBOL_VALUE+1];
1360 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1362 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1365 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1367 /* normal FSE decoding mode */
1368 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1369 if (FSE_isError(errorCode)) return errorCode;
1370 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1372 cSrcSize -= errorCode;
1374 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1375 if (FSE_isError(errorCode)) return errorCode;
1377 /* always return, even if it is an error code */
1378 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1383 #endif /* FSE_COMMONDEFS_ONLY */
1386 /* ******************************************************************
1387 Huff0 : Huffman coder, part of New Generation Entropy library
1389 Copyright (C) 2013-2015, Yann Collet.
1391 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1393 Redistribution and use in source and binary forms, with or without
1394 modification, are permitted provided that the following conditions are
1397 * Redistributions of source code must retain the above copyright
1398 notice, this list of conditions and the following disclaimer.
1399 * Redistributions in binary form must reproduce the above
1400 copyright notice, this list of conditions and the following disclaimer
1401 in the documentation and/or other materials provided with the
1404 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1405 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1406 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1407 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1408 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1409 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1410 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1411 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1412 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1413 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1414 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1416 You can contact the author at :
1417 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1418 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1419 ****************************************************************** */
1423 #if defined (__cplusplus)
1428 /* ****************************************
1430 ******************************************/
1431 #include <stddef.h> /* size_t */
1434 /* ****************************************
1435 * Huff0 simple functions
1436 ******************************************/
1437 static size_t HUF_decompress(void* dst, size_t dstSize,
1438 const void* cSrc, size_t cSrcSize);
1441 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1442 into already allocated destination buffer 'dst', of size 'dstSize'.
1443 'dstSize' must be the exact size of original (uncompressed) data.
1444 Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate.
1445 @return : size of regenerated data (== dstSize)
1446 or an error code, which can be tested using HUF_isError()
1450 /* ****************************************
1452 ******************************************/
1453 /* Error Management */
1454 static unsigned HUF_isError(size_t code); /* tells if a return value is an error code */
1457 #if defined (__cplusplus)
1461 #endif /* HUFF0_H */
1464 /* ******************************************************************
1465 Huff0 : Huffman coder, part of New Generation Entropy library
1466 header file for static linking (only)
1467 Copyright (C) 2013-2015, Yann Collet
1469 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1471 Redistribution and use in source and binary forms, with or without
1472 modification, are permitted provided that the following conditions are
1475 * Redistributions of source code must retain the above copyright
1476 notice, this list of conditions and the following disclaimer.
1477 * Redistributions in binary form must reproduce the above
1478 copyright notice, this list of conditions and the following disclaimer
1479 in the documentation and/or other materials provided with the
1482 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1483 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1484 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1485 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1486 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1487 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1488 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1489 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1490 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1491 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1492 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1494 You can contact the author at :
1495 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1496 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1497 ****************************************************************** */
1498 #ifndef HUFF0_STATIC_H
1499 #define HUFF0_STATIC_H
1501 #if defined (__cplusplus)
1507 /* ****************************************
1508 * Static allocation macros
1509 ******************************************/
1510 /* static allocation of Huff0's DTable */
1511 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
1512 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1513 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1514 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1515 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1516 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1517 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1520 /* ****************************************
1521 * Advanced decompression functions
1522 ******************************************/
1523 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1524 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1527 /* ****************************************
1528 * Huff0 detailed API
1529 ******************************************/
1531 HUF_decompress() does the following:
1532 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1533 2. build Huffman table from save, using HUF_readDTableXn()
1534 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable
1537 static size_t HUF_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1538 static size_t HUF_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1540 static size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1541 static size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1544 #if defined (__cplusplus)
1548 #endif /* HUFF0_STATIC_H */
1552 /* ******************************************************************
1553 Huff0 : Huffman coder, part of New Generation Entropy library
1554 Copyright (C) 2013-2015, Yann Collet.
1556 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1558 Redistribution and use in source and binary forms, with or without
1559 modification, are permitted provided that the following conditions are
1562 * Redistributions of source code must retain the above copyright
1563 notice, this list of conditions and the following disclaimer.
1564 * Redistributions in binary form must reproduce the above
1565 copyright notice, this list of conditions and the following disclaimer
1566 in the documentation and/or other materials provided with the
1569 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1570 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1571 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1572 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1573 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1574 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1575 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1576 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1577 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1578 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1579 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1581 You can contact the author at :
1582 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1583 ****************************************************************** */
1585 /* **************************************************************
1586 * Compiler specifics
1587 ****************************************************************/
1588 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1589 /* inline is defined */
1590 #elif defined(_MSC_VER)
1591 # define inline __inline
1593 # define inline /* disable inline */
1597 #ifdef _MSC_VER /* Visual Studio */
1598 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1602 /* **************************************************************
1604 ****************************************************************/
1605 #include <stdlib.h> /* malloc, free, qsort */
1606 #include <string.h> /* memcpy, memset */
1607 #include <stdio.h> /* printf (debug) */
1610 /* **************************************************************
1612 ****************************************************************/
1613 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1614 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1615 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1616 #define HUF_MAX_SYMBOL_VALUE 255
1617 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1618 # error "HUF_MAX_TABLELOG is too large !"
1622 /* **************************************************************
1624 ****************************************************************/
1625 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1626 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1630 /*-*******************************************************
1631 * Huff0 : Huffman block decompression
1632 *********************************************************/
1633 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1635 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1637 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1640 Read compact Huffman tree, saved by HUF_writeCTable
1641 @huffWeight : destination buffer
1642 @return : size read from `src`
1644 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1645 U32* nbSymbolsPtr, U32* tableLogPtr,
1646 const void* src, size_t srcSize)
1650 const BYTE* ip = (const BYTE*) src;
1655 if (!srcSize) return ERROR(srcSize_wrong);
1657 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1659 if (iSize >= 128) /* special header */
1661 if (iSize >= (242)) /* RLE */
1663 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1664 oSize = l[iSize-242];
1665 memset(huffWeight, 1, hwSize);
1668 else /* Incompressible */
1670 oSize = iSize - 127;
1671 iSize = ((oSize+1)/2);
1672 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1673 if (oSize >= hwSize) return ERROR(corruption_detected);
1675 for (n=0; n<oSize; n+=2)
1677 huffWeight[n] = ip[n/2] >> 4;
1678 huffWeight[n+1] = ip[n/2] & 15;
1682 else /* header compressed with FSE (normal case) */
1684 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1685 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1686 if (FSE_isError(oSize)) return oSize;
1689 /* collect weight stats */
1690 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1692 for (n=0; n<oSize; n++)
1694 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1695 rankStats[huffWeight[n]]++;
1696 weightTotal += (1 << huffWeight[n]) >> 1;
1698 if (weightTotal == 0) return ERROR(corruption_detected);
1700 /* get last non-null symbol weight (implied, total must be 2^n) */
1701 tableLog = BIT_highbit32(weightTotal) + 1;
1702 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1704 U32 total = 1 << tableLog;
1705 U32 rest = total - weightTotal;
1706 U32 verif = 1 << BIT_highbit32(rest);
1707 U32 lastWeight = BIT_highbit32(rest) + 1;
1708 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1709 huffWeight[oSize] = (BYTE)lastWeight;
1710 rankStats[lastWeight]++;
1713 /* check tree construction validity */
1714 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1717 *nbSymbolsPtr = (U32)(oSize+1);
1718 *tableLogPtr = tableLog;
1723 /**************************/
1724 /* single-symbol decoding */
1725 /**************************/
1727 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1729 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1730 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1736 void* const dtPtr = DTable + 1;
1737 HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;
1739 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1740 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1742 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1743 if (HUF_isError(iSize)) return iSize;
1746 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1747 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1751 for (n=1; n<=tableLog; n++)
1753 U32 current = nextRankStart;
1754 nextRankStart += (rankVal[n] << (n-1));
1755 rankVal[n] = current;
1759 for (n=0; n<nbSymbols; n++)
1761 const U32 w = huffWeight[n];
1762 const U32 length = (1 << w) >> 1;
1765 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1766 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1768 rankVal[w] += length;
1774 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1776 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1777 const BYTE c = dt[val].byte;
1778 BIT_skipBits(Dstream, dt[val].nbBits);
1782 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1783 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1785 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1786 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1787 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1789 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1791 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1793 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1795 BYTE* const pStart = p;
1797 /* up to 4 symbols at a time */
1798 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1800 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1801 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1802 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1803 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1806 /* closer to the end */
1807 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1808 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1810 /* no more data to retrieve from bitstream, hence no need to reload */
1812 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1818 static size_t HUF_decompress4X2_usingDTable(
1819 void* dst, size_t dstSize,
1820 const void* cSrc, size_t cSrcSize,
1823 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1826 const BYTE* const istart = (const BYTE*) cSrc;
1827 BYTE* const ostart = (BYTE*) dst;
1828 BYTE* const oend = ostart + dstSize;
1829 const void* const dtPtr = DTable;
1830 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)dtPtr) +1;
1831 const U32 dtLog = DTable[0];
1835 BIT_DStream_t bitD1;
1836 BIT_DStream_t bitD2;
1837 BIT_DStream_t bitD3;
1838 BIT_DStream_t bitD4;
1839 const size_t length1 = MEM_readLE16(istart);
1840 const size_t length2 = MEM_readLE16(istart+2);
1841 const size_t length3 = MEM_readLE16(istart+4);
1843 const BYTE* const istart1 = istart + 6; /* jumpTable */
1844 const BYTE* const istart2 = istart1 + length1;
1845 const BYTE* const istart3 = istart2 + length2;
1846 const BYTE* const istart4 = istart3 + length3;
1847 const size_t segmentSize = (dstSize+3) / 4;
1848 BYTE* const opStart2 = ostart + segmentSize;
1849 BYTE* const opStart3 = opStart2 + segmentSize;
1850 BYTE* const opStart4 = opStart3 + segmentSize;
1852 BYTE* op2 = opStart2;
1853 BYTE* op3 = opStart3;
1854 BYTE* op4 = opStart4;
1857 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1858 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1859 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1860 if (HUF_isError(errorCode)) return errorCode;
1861 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1862 if (HUF_isError(errorCode)) return errorCode;
1863 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1864 if (HUF_isError(errorCode)) return errorCode;
1865 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1866 if (HUF_isError(errorCode)) return errorCode;
1868 /* 16-32 symbols per loop (4-8 symbols per stream) */
1869 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1870 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1872 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1873 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1874 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1875 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1876 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1877 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1878 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1879 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1880 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1881 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1882 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1883 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1884 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1885 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1886 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1887 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1889 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1892 /* check corruption */
1893 if (op1 > opStart2) return ERROR(corruption_detected);
1894 if (op2 > opStart3) return ERROR(corruption_detected);
1895 if (op3 > opStart4) return ERROR(corruption_detected);
1896 /* note : op4 supposed already verified within main loop */
1898 /* finish bitStreams one by one */
1899 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1900 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1901 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1902 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1905 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1906 if (!endSignal) return ERROR(corruption_detected);
1914 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1916 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1917 const BYTE* ip = (const BYTE*) cSrc;
1920 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1921 if (HUF_isError(errorCode)) return errorCode;
1922 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1924 cSrcSize -= errorCode;
1926 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1930 /***************************/
1931 /* double-symbols decoding */
1932 /***************************/
1934 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1935 const U32* rankValOrigin, const int minWeight,
1936 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1937 U32 nbBitsBaseline, U16 baseSeq)
1940 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1943 /* get pre-calculated rankVal */
1944 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1946 /* fill skipped values */
1949 U32 i, skipSize = rankVal[minWeight];
1950 MEM_writeLE16(&(DElt.sequence), baseSeq);
1951 DElt.nbBits = (BYTE)(consumed);
1953 for (i = 0; i < skipSize; i++)
1958 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1960 const U32 symbol = sortedSymbols[s].symbol;
1961 const U32 weight = sortedSymbols[s].weight;
1962 const U32 nbBits = nbBitsBaseline - weight;
1963 const U32 length = 1 << (sizeLog-nbBits);
1964 const U32 start = rankVal[weight];
1966 const U32 end = start + length;
1968 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1969 DElt.nbBits = (BYTE)(nbBits + consumed);
1971 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1973 rankVal[weight] += length;
1977 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1979 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1980 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1981 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1982 const U32 nbBitsBaseline)
1984 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1985 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1986 const U32 minBits = nbBitsBaseline - maxWeight;
1989 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1992 for (s=0; s<sortedListSize; s++)
1994 const U16 symbol = sortedList[s].symbol;
1995 const U32 weight = sortedList[s].weight;
1996 const U32 nbBits = nbBitsBaseline - weight;
1997 const U32 start = rankVal[weight];
1998 const U32 length = 1 << (targetLog-nbBits);
2000 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
2003 int minWeight = nbBits + scaleLog;
2004 if (minWeight < 1) minWeight = 1;
2005 sortedRank = rankStart[minWeight];
2006 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2007 rankValOrigin[nbBits], minWeight,
2008 sortedList+sortedRank, sortedListSize-sortedRank,
2009 nbBitsBaseline, symbol);
2014 const U32 end = start + length;
2017 MEM_writeLE16(&(DElt.sequence), symbol);
2018 DElt.nbBits = (BYTE)(nbBits);
2020 for (i = start; i < end; i++)
2023 rankVal[weight] += length;
2027 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2029 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
2030 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
2031 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2032 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2033 U32* const rankStart = rankStart0+1;
2035 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2036 const U32 memLog = DTable[0];
2038 void* dtPtr = DTable;
2039 HUF_DEltX4* const dt = ((HUF_DEltX4*)dtPtr) + 1;
2041 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
2042 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2043 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2045 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2046 if (HUF_isError(iSize)) return iSize;
2049 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2051 /* find maxWeight */
2052 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2053 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
2055 /* Get start index of each weight */
2057 U32 w, nextRankStart = 0;
2058 for (w=1; w<=maxW; w++)
2060 U32 current = nextRankStart;
2061 nextRankStart += rankStats[w];
2062 rankStart[w] = current;
2064 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2065 sizeOfSort = nextRankStart;
2068 /* sort symbols by weight */
2071 for (s=0; s<nbSymbols; s++)
2073 U32 w = weightList[s];
2074 U32 r = rankStart[w]++;
2075 sortedSymbol[r].symbol = (BYTE)s;
2076 sortedSymbol[r].weight = (BYTE)w;
2078 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2083 const U32 minBits = tableLog+1 - maxW;
2084 U32 nextRankVal = 0;
2086 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2087 U32* rankVal0 = rankVal[0];
2088 for (w=1; w<=maxW; w++)
2090 U32 current = nextRankVal;
2091 nextRankVal += rankStats[w] << (w+rescale);
2092 rankVal0[w] = current;
2094 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2096 U32* rankValPtr = rankVal[consumed];
2097 for (w = 1; w <= maxW; w++)
2099 rankValPtr[w] = rankVal0[w] >> consumed;
2104 HUF_fillDTableX4(dt, memLog,
2105 sortedSymbol, sizeOfSort,
2106 rankStart0, rankVal, maxW,
2113 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2115 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2116 memcpy(op, dt+val, 2);
2117 BIT_skipBits(DStream, dt[val].nbBits);
2118 return dt[val].length;
2121 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2123 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2124 memcpy(op, dt+val, 1);
2125 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2128 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2130 BIT_skipBits(DStream, dt[val].nbBits);
2131 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2132 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 */
2139 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2140 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2142 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2143 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2144 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2146 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2148 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2150 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2152 BYTE* const pStart = p;
2154 /* up to 8 symbols at a time */
2155 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2157 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2158 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2159 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2160 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2163 /* closer to the end */
2164 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2165 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2168 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2171 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2176 static size_t HUF_decompress4X4_usingDTable(
2177 void* dst, size_t dstSize,
2178 const void* cSrc, size_t cSrcSize,
2181 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2184 const BYTE* const istart = (const BYTE*) cSrc;
2185 BYTE* const ostart = (BYTE*) dst;
2186 BYTE* const oend = ostart + dstSize;
2187 const void* const dtPtr = DTable;
2188 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)dtPtr) +1;
2189 const U32 dtLog = DTable[0];
2193 BIT_DStream_t bitD1;
2194 BIT_DStream_t bitD2;
2195 BIT_DStream_t bitD3;
2196 BIT_DStream_t bitD4;
2197 const size_t length1 = MEM_readLE16(istart);
2198 const size_t length2 = MEM_readLE16(istart+2);
2199 const size_t length3 = MEM_readLE16(istart+4);
2201 const BYTE* const istart1 = istart + 6; /* jumpTable */
2202 const BYTE* const istart2 = istart1 + length1;
2203 const BYTE* const istart3 = istart2 + length2;
2204 const BYTE* const istart4 = istart3 + length3;
2205 const size_t segmentSize = (dstSize+3) / 4;
2206 BYTE* const opStart2 = ostart + segmentSize;
2207 BYTE* const opStart3 = opStart2 + segmentSize;
2208 BYTE* const opStart4 = opStart3 + segmentSize;
2210 BYTE* op2 = opStart2;
2211 BYTE* op3 = opStart3;
2212 BYTE* op4 = opStart4;
2215 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2216 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2217 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2218 if (HUF_isError(errorCode)) return errorCode;
2219 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2220 if (HUF_isError(errorCode)) return errorCode;
2221 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2222 if (HUF_isError(errorCode)) return errorCode;
2223 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2224 if (HUF_isError(errorCode)) return errorCode;
2226 /* 16-32 symbols per loop (4-8 symbols per stream) */
2227 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2228 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2230 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2231 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2232 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2233 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2234 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2235 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2236 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2237 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2238 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2239 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2240 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2241 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2242 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2243 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2244 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2245 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2247 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2250 /* check corruption */
2251 if (op1 > opStart2) return ERROR(corruption_detected);
2252 if (op2 > opStart3) return ERROR(corruption_detected);
2253 if (op3 > opStart4) return ERROR(corruption_detected);
2254 /* note : op4 supposed already verified within main loop */
2256 /* finish bitStreams one by one */
2257 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2258 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2259 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2260 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2263 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2264 if (!endSignal) return ERROR(corruption_detected);
2272 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2274 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2275 const BYTE* ip = (const BYTE*) cSrc;
2277 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2278 if (HUF_isError(hSize)) return hSize;
2279 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2283 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2287 /**********************************/
2288 /* Generic decompression selector */
2289 /**********************************/
2291 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2292 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2294 /* single, double, quad */
2295 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2296 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2297 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2298 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2299 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2300 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2301 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2302 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2303 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2304 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2305 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2306 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2307 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2308 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2309 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2310 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2313 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2315 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2317 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2318 /* estimate decompression time */
2320 const U32 D256 = (U32)(dstSize >> 8);
2325 /* validation checks */
2326 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2327 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2328 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2329 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2331 /* decoder timing evaluation */
2332 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2334 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2336 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2338 if (Dtime[1] < Dtime[0]) algoNb = 1;
2340 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2342 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2343 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2344 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2349 #endif /* ZSTD_CCOMMON_H_MODULE */
2353 zstd - decompression module fo v0.4 legacy format
2354 Copyright (C) 2015-2016, Yann Collet.
2356 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2358 Redistribution and use in source and binary forms, with or without
2359 modification, are permitted provided that the following conditions are
2361 * Redistributions of source code must retain the above copyright
2362 notice, this list of conditions and the following disclaimer.
2363 * Redistributions in binary form must reproduce the above
2364 copyright notice, this list of conditions and the following disclaimer
2365 in the documentation and/or other materials provided with the
2367 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2368 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2369 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2370 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2371 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2372 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2373 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2374 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2375 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2376 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2377 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2379 You can contact the author at :
2380 - zstd source repository : https://github.com/Cyan4973/zstd
2381 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2384 /* ***************************************************************
2386 *****************************************************************/
2389 * Select how default decompression function ZSTD_decompress() will allocate memory,
2390 * in memory stack (0), or in memory heap (1, requires malloc())
2392 #ifndef ZSTD_HEAPMODE
2393 # define ZSTD_HEAPMODE 1
2397 /* *******************************************************
2399 *********************************************************/
2400 #include <stdlib.h> /* calloc */
2401 #include <string.h> /* memcpy, memmove */
2402 #include <stdio.h> /* debug : printf */
2405 /* *******************************************************
2406 * Compiler specifics
2407 *********************************************************/
2408 #ifdef _MSC_VER /* Visual Studio */
2409 # include <intrin.h> /* For Visual 2005 */
2410 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2411 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2415 /* *************************************
2417 ***************************************/
2420 blockType_t blockType;
2422 } blockProperties_t;
2425 /* *******************************************************
2427 **********************************************************/
2428 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2431 /* *************************************
2433 ***************************************/
2436 * tells if a return value is an error code */
2437 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2440 /* *************************************************************
2441 * Context management
2442 ***************************************************************/
2443 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2444 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTD_dStage;
2446 struct ZSTDv04_Dctx_s
2448 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2449 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2450 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2451 const void* previousDstEnd;
2454 const void* dictEnd;
2457 ZSTD_parameters params;
2462 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2463 BYTE headerBuffer[ZSTD_frameHeaderSize_max];
2464 }; /* typedef'd to ZSTD_DCtx within "zstd_static.h" */
2466 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2468 dctx->expected = ZSTD_frameHeaderSize_min;
2469 dctx->stage = ZSTDds_getFrameHeaderSize;
2470 dctx->previousDstEnd = NULL;
2473 dctx->dictEnd = NULL;
2477 static ZSTD_DCtx* ZSTD_createDCtx(void)
2479 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2480 if (dctx==NULL) return NULL;
2481 ZSTD_resetDCtx(dctx);
2485 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
2492 /* *************************************************************
2493 * Decompression section
2494 ***************************************************************/
2495 /** ZSTD_decodeFrameHeader_Part1
2496 * decode the 1st part of the Frame Header, which tells Frame Header size.
2497 * srcSize must be == ZSTD_frameHeaderSize_min
2498 * @return : the full size of the Frame Header */
2499 static size_t ZSTD_decodeFrameHeader_Part1(ZSTD_DCtx* zc, const void* src, size_t srcSize)
2502 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);
2503 magicNumber = MEM_readLE32(src);
2504 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
2505 zc->headerSize = ZSTD_frameHeaderSize_min;
2506 return zc->headerSize;
2510 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize)
2513 if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_max;
2514 magicNumber = MEM_readLE32(src);
2515 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
2516 memset(params, 0, sizeof(*params));
2517 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
2518 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */
2522 /** ZSTD_decodeFrameHeader_Part2
2523 * decode the full Frame Header
2524 * srcSize must be the size provided by ZSTD_decodeFrameHeader_Part1
2525 * @return : 0, or an error code, which can be tested using ZSTD_isError() */
2526 static size_t ZSTD_decodeFrameHeader_Part2(ZSTD_DCtx* zc, const void* src, size_t srcSize)
2529 if (srcSize != zc->headerSize) return ERROR(srcSize_wrong);
2530 result = ZSTD_getFrameParams(&(zc->params), src, srcSize);
2531 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported);
2536 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2538 const BYTE* const in = (const BYTE* const)src;
2542 if (srcSize < 3) return ERROR(srcSize_wrong);
2545 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2547 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2548 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2550 if (bpPtr->blockType == bt_end) return 0;
2551 if (bpPtr->blockType == bt_rle) return 1;
2555 static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2557 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2559 memcpy(dst, src, srcSize);
2565 /** ZSTD_decompressLiterals
2566 @return : nb of bytes read from src, or an error code*/
2567 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2568 const void* src, size_t srcSize)
2570 const BYTE* ip = (const BYTE*)src;
2572 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2573 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2575 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2576 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2578 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2580 *maxDstSizePtr = litSize;
2581 return litCSize + 5;
2585 /** ZSTD_decodeLiteralsBlock
2586 @return : nb of bytes read from src (< srcSize ) */
2587 static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
2588 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
2590 const BYTE* const istart = (const BYTE*) src;
2592 /* any compressed block with literals segment must be at least this size */
2593 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2600 size_t litSize = BLOCKSIZE;
2601 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2602 dctx->litPtr = dctx->litBuffer;
2603 dctx->litSize = litSize;
2604 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2605 return readSize; /* works if it's an error too */
2609 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2610 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2612 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2613 if (litSize > srcSize-3) return ERROR(corruption_detected);
2614 memcpy(dctx->litBuffer, istart, litSize);
2615 dctx->litPtr = dctx->litBuffer;
2616 dctx->litSize = litSize;
2617 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2620 /* direct reference into compressed stream */
2621 dctx->litPtr = istart+3;
2622 dctx->litSize = litSize;
2626 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2627 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2628 memset(dctx->litBuffer, istart[3], litSize + 8);
2629 dctx->litPtr = dctx->litBuffer;
2630 dctx->litSize = litSize;
2634 return ERROR(corruption_detected); /* forbidden nominal case */
2639 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2640 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2641 const void* src, size_t srcSize)
2643 const BYTE* const istart = (const BYTE* const)src;
2644 const BYTE* ip = istart;
2645 const BYTE* const iend = istart + srcSize;
2646 U32 LLtype, Offtype, MLtype;
2647 U32 LLlog, Offlog, MLlog;
2651 if (srcSize < 5) return ERROR(srcSize_wrong);
2654 *nbSeq = MEM_readLE16(ip); ip+=2;
2656 Offtype = (*ip >> 4) & 3;
2657 MLtype = (*ip >> 2) & 3;
2660 dumpsLength = ip[2];
2661 dumpsLength += ip[1] << 8;
2666 dumpsLength = ip[1];
2667 dumpsLength += (ip[0] & 1) << 8;
2672 *dumpsLengthPtr = dumpsLength;
2675 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2679 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */
2687 FSE_buildDTable_rle(DTableLL, *ip++); break;
2690 FSE_buildDTable_raw(DTableLL, LLbits); break;
2693 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2694 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2695 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2697 FSE_buildDTable(DTableLL, norm, max, LLlog);
2704 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2705 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2709 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2712 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2713 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2714 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2716 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2723 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2724 FSE_buildDTable_rle(DTableML, *ip++); break;
2727 FSE_buildDTable_raw(DTableML, MLbits); break;
2730 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2731 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2732 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2734 FSE_buildDTable(DTableML, norm, max, MLlog);
2748 BIT_DStream_t DStream;
2749 FSE_DState_t stateLL;
2750 FSE_DState_t stateOffb;
2751 FSE_DState_t stateML;
2754 const BYTE* dumpsEnd;
2758 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2764 const BYTE* dumps = seqState->dumps;
2765 const BYTE* const de = seqState->dumpsEnd;
2767 /* Literal length */
2768 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2769 prevOffset = litLength ? seq->offset : seqState->prevOffset;
2770 if (litLength == MaxLL) {
2771 const U32 add = dumps<de ? *dumps++ : 0;
2772 if (add < 255) litLength += add;
2773 else if (dumps + 3 <= de) {
2774 litLength = MEM_readLE24(dumps);
2777 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
2781 { static const U32 offsetPrefix[MaxOff+1] = {
2782 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2783 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2784 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2785 U32 offsetCode, nbBits;
2786 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
2787 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2788 nbBits = offsetCode - 1;
2789 if (offsetCode==0) nbBits = 0; /* cmove */
2790 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2791 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2792 if (offsetCode==0) offset = prevOffset; /* cmove */
2793 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */
2797 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2798 if (matchLength == MaxML) {
2799 const U32 add = dumps<de ? *dumps++ : 0;
2800 if (add < 255) matchLength += add;
2801 else if (dumps + 3 <= de){
2802 matchLength = MEM_readLE24(dumps);
2805 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
2807 matchLength += MINMATCH;
2810 seq->litLength = litLength;
2811 seq->offset = offset;
2812 seq->matchLength = matchLength;
2813 seqState->dumps = dumps;
2817 static size_t ZSTD_execSequence(BYTE* op,
2818 BYTE* const oend, seq_t sequence,
2819 const BYTE** litPtr, const BYTE* const litLimit,
2820 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
2822 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
2823 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
2824 BYTE* const oLitEnd = op + sequence.litLength;
2825 const size_t sequenceLength = sequence.litLength + sequence.matchLength;
2826 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
2827 BYTE* const oend_8 = oend-8;
2828 const BYTE* const litEnd = *litPtr + sequence.litLength;
2829 const BYTE* match = oLitEnd - sequence.offset;
2832 size_t const seqLength = sequence.litLength + sequence.matchLength;
2834 if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
2835 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
2836 /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
2837 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
2839 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
2840 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
2843 ZSTD_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2845 *litPtr = litEnd; /* update for next sequence */
2848 if (sequence.offset > (size_t)(oLitEnd - base))
2850 /* offset beyond prefix */
2851 if (sequence.offset > (size_t)(oLitEnd - vBase))
2852 return ERROR(corruption_detected);
2853 match = dictEnd - (base-match);
2854 if (match + sequence.matchLength <= dictEnd)
2856 memmove(oLitEnd, match, sequence.matchLength);
2857 return sequenceLength;
2859 /* span extDict & currentPrefixSegment */
2861 size_t length1 = dictEnd - match;
2862 memmove(oLitEnd, match, length1);
2863 op = oLitEnd + length1;
2864 sequence.matchLength -= length1;
2866 if (op > oend_8 || sequence.matchLength < MINMATCH) {
2867 while (op < oMatchEnd) *op++ = *match++;
2868 return sequenceLength;
2872 /* Requirement: op <= oend_8 */
2874 /* match within prefix */
2875 if (sequence.offset < 8) {
2876 /* close range match, overlap */
2877 const int sub2 = dec64table[sequence.offset];
2882 match += dec32table[sequence.offset];
2883 ZSTD_copy4(op+4, match);
2886 ZSTD_copy8(op, match);
2888 op += 8; match += 8;
2890 if (oMatchEnd > oend-(16-MINMATCH))
2894 ZSTD_wildcopy(op, match, oend_8 - op);
2895 match += oend_8 - op;
2898 while (op < oMatchEnd) *op++ = *match++;
2902 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8, but must be signed */
2904 return sequenceLength;
2908 static size_t ZSTD_decompressSequences(
2910 void* dst, size_t maxDstSize,
2911 const void* seqStart, size_t seqSize)
2913 const BYTE* ip = (const BYTE*)seqStart;
2914 const BYTE* const iend = ip + seqSize;
2915 BYTE* const ostart = (BYTE* const)dst;
2917 BYTE* const oend = ostart + maxDstSize;
2918 size_t errorCode, dumpsLength;
2919 const BYTE* litPtr = dctx->litPtr;
2920 const BYTE* const litEnd = litPtr + dctx->litSize;
2923 U32* DTableLL = dctx->LLTable;
2924 U32* DTableML = dctx->MLTable;
2925 U32* DTableOffb = dctx->OffTable;
2926 const BYTE* const base = (const BYTE*) (dctx->base);
2927 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
2928 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
2930 /* Build Decoding Tables */
2931 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2932 DTableLL, DTableML, DTableOffb,
2934 if (ZSTD_isError(errorCode)) return errorCode;
2937 /* Regen sequences */
2940 seqState_t seqState;
2942 memset(&sequence, 0, sizeof(sequence));
2943 sequence.offset = 4;
2944 seqState.dumps = dumps;
2945 seqState.dumpsEnd = dumps + dumpsLength;
2946 seqState.prevOffset = 4;
2947 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2948 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2949 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2950 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2951 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2953 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; )
2957 ZSTD_decodeSequence(&sequence, &seqState);
2958 oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
2959 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2963 /* check if reached exact end */
2964 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* DStream should be entirely and exactly consumed; otherwise data is corrupted */
2966 /* last literal segment */
2968 size_t lastLLSize = litEnd - litPtr;
2969 if (litPtr > litEnd) return ERROR(corruption_detected);
2970 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2971 if (lastLLSize > 0) {
2972 if (op != litPtr) memcpy(op, litPtr, lastLLSize);
2982 static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
2984 if (dst != dctx->previousDstEnd) /* not contiguous */
2986 dctx->dictEnd = dctx->previousDstEnd;
2987 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
2989 dctx->previousDstEnd = dst;
2994 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
2995 void* dst, size_t maxDstSize,
2996 const void* src, size_t srcSize)
2998 /* blockType == blockCompressed */
2999 const BYTE* ip = (const BYTE*)src;
3002 if (srcSize > BLOCKSIZE) return ERROR(corruption_detected);
3004 /* Decode literals sub-block */
3005 litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
3006 if (ZSTD_isError(litCSize)) return litCSize;
3008 srcSize -= litCSize;
3010 return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize);
3014 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
3015 void* dst, size_t maxDstSize,
3016 const void* src, size_t srcSize,
3017 const void* dict, size_t dictSize)
3019 const BYTE* ip = (const BYTE*)src;
3020 const BYTE* iend = ip + srcSize;
3021 BYTE* const ostart = (BYTE* const)dst;
3023 BYTE* const oend = ostart + maxDstSize;
3024 size_t remainingSize = srcSize;
3025 blockProperties_t blockProperties;
3028 ZSTD_resetDCtx(ctx);
3031 ZSTD_decompress_insertDictionary(ctx, dict, dictSize);
3032 ctx->dictEnd = ctx->previousDstEnd;
3033 ctx->vBase = (const char*)dst - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
3038 ctx->vBase = ctx->base = ctx->dictEnd = dst;
3043 size_t frameHeaderSize;
3044 if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3045 frameHeaderSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
3046 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
3047 if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3048 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3049 frameHeaderSize = ZSTD_decodeFrameHeader_Part2(ctx, src, frameHeaderSize);
3050 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
3053 /* Loop on each block */
3056 size_t decodedSize=0;
3057 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
3058 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3060 ip += ZSTD_blockHeaderSize;
3061 remainingSize -= ZSTD_blockHeaderSize;
3062 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3064 switch(blockProperties.blockType)
3067 decodedSize = ZSTD_decompressBlock_internal(ctx, op, oend-op, ip, cBlockSize);
3070 decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
3073 return ERROR(GENERIC); /* not yet supported */
3077 if (remainingSize) return ERROR(srcSize_wrong);
3080 return ERROR(GENERIC); /* impossible */
3082 if (cBlockSize == 0) break; /* bt_end */
3084 if (ZSTD_isError(decodedSize)) return decodedSize;
3087 remainingSize -= cBlockSize;
3093 /* ZSTD_errorFrameSizeInfoLegacy() :
3094 assumes `cSize` and `dBound` are _not_ NULL */
3095 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3098 *dBound = ZSTD_CONTENTSIZE_ERROR;
3101 void ZSTDv04_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3103 const BYTE* ip = (const BYTE*)src;
3104 size_t remainingSize = srcSize;
3105 size_t nbBlocks = 0;
3106 blockProperties_t blockProperties;
3109 if (srcSize < ZSTD_frameHeaderSize_min) {
3110 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3113 if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) {
3114 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3117 ip += ZSTD_frameHeaderSize_min; remainingSize -= ZSTD_frameHeaderSize_min;
3119 /* Loop on each block */
3122 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
3123 if (ZSTD_isError(cBlockSize)) {
3124 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3128 ip += ZSTD_blockHeaderSize;
3129 remainingSize -= ZSTD_blockHeaderSize;
3130 if (cBlockSize > remainingSize) {
3131 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3135 if (cBlockSize == 0) break; /* bt_end */
3138 remainingSize -= cBlockSize;
3142 *cSize = ip - (const BYTE*)src;
3143 *dBound = nbBlocks * BLOCKSIZE;
3146 /* ******************************
3147 * Streaming Decompression API
3148 ********************************/
3149 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3151 return dctx->expected;
3154 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3157 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3158 ZSTD_checkContinuity(ctx, dst);
3160 /* Decompress : frame header; part 1 */
3163 case ZSTDds_getFrameHeaderSize :
3164 /* get frame header size */
3165 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3166 ctx->headerSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
3167 if (ZSTD_isError(ctx->headerSize)) return ctx->headerSize;
3168 memcpy(ctx->headerBuffer, src, ZSTD_frameHeaderSize_min);
3169 if (ctx->headerSize > ZSTD_frameHeaderSize_min) return ERROR(GENERIC); /* impossible */
3170 ctx->expected = 0; /* not necessary to copy more */
3172 case ZSTDds_decodeFrameHeader:
3173 /* get frame header */
3174 { size_t const result = ZSTD_decodeFrameHeader_Part2(ctx, ctx->headerBuffer, ctx->headerSize);
3175 if (ZSTD_isError(result)) return result;
3176 ctx->expected = ZSTD_blockHeaderSize;
3177 ctx->stage = ZSTDds_decodeBlockHeader;
3180 case ZSTDds_decodeBlockHeader:
3181 /* Decode block header */
3182 { blockProperties_t bp;
3183 size_t const blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3184 if (ZSTD_isError(blockSize)) return blockSize;
3185 if (bp.blockType == bt_end)
3188 ctx->stage = ZSTDds_getFrameHeaderSize;
3192 ctx->expected = blockSize;
3193 ctx->bType = bp.blockType;
3194 ctx->stage = ZSTDds_decompressBlock;
3198 case ZSTDds_decompressBlock:
3200 /* Decompress : block content */
3205 rSize = ZSTD_decompressBlock_internal(ctx, dst, maxDstSize, src, srcSize);
3208 rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize);
3211 return ERROR(GENERIC); /* not yet handled */
3213 case bt_end : /* should never happen (filtered at phase 1) */
3217 return ERROR(GENERIC);
3219 ctx->stage = ZSTDds_decodeBlockHeader;
3220 ctx->expected = ZSTD_blockHeaderSize;
3221 ctx->previousDstEnd = (char*)dst + rSize;
3225 return ERROR(GENERIC); /* impossible */
3230 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* dict, size_t dictSize)
3232 ctx->dictEnd = ctx->previousDstEnd;
3233 ctx->vBase = (const char*)dict - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
3235 ctx->previousDstEnd = (const char*)dict + dictSize;
3241 Buffered version of Zstd compression library
3242 Copyright (C) 2015, Yann Collet.
3244 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
3246 Redistribution and use in source and binary forms, with or without
3247 modification, are permitted provided that the following conditions are
3249 * Redistributions of source code must retain the above copyright
3250 notice, this list of conditions and the following disclaimer.
3251 * Redistributions in binary form must reproduce the above
3252 copyright notice, this list of conditions and the following disclaimer
3253 in the documentation and/or other materials provided with the
3255 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3256 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3257 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3258 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3259 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3260 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3261 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3262 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3263 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3264 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3265 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3267 You can contact the author at :
3268 - zstd source repository : https://github.com/Cyan4973/zstd
3269 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3272 /* The objects defined into this file should be considered experimental.
3273 * They are not labelled stable, as their prototype may change in the future.
3274 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3277 /* *************************************
3279 ***************************************/
3283 /** ************************************************
3284 * Streaming decompression
3286 * A ZBUFF_DCtx object is required to track streaming operation.
3287 * Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources.
3288 * Use ZBUFF_decompressInit() to start a new decompression operation.
3289 * ZBUFF_DCtx objects can be reused multiple times.
3291 * Use ZBUFF_decompressContinue() repetitively to consume your input.
3292 * *srcSizePtr and *maxDstSizePtr can be any size.
3293 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3294 * 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.
3295 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3296 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3297 * or 0 when a frame is completely decoded
3298 * or an error code, which can be tested using ZBUFF_isError().
3300 * Hint : recommended buffer sizes (not compulsory)
3301 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3302 * input : just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3303 * **************************************************/
3305 typedef enum { ZBUFFds_init, ZBUFFds_readHeader, ZBUFFds_loadHeader, ZBUFFds_decodeHeader,
3306 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage;
3308 /* *** Resource management *** */
3310 #define ZSTD_frameHeaderSize_max 5 /* too magical, should come from reference */
3311 struct ZBUFFv04_DCtx_s {
3313 ZSTD_parameters params;
3325 unsigned char headerBuffer[ZSTD_frameHeaderSize_max];
3326 }; /* typedef'd to ZBUFF_DCtx within "zstd_buffered.h" */
3328 typedef ZBUFFv04_DCtx ZBUFF_DCtx;
3331 static ZBUFF_DCtx* ZBUFF_createDCtx(void)
3333 ZBUFF_DCtx* zbc = (ZBUFF_DCtx*)malloc(sizeof(ZBUFF_DCtx));
3334 if (zbc==NULL) return NULL;
3335 memset(zbc, 0, sizeof(*zbc));
3336 zbc->zc = ZSTD_createDCtx();
3337 zbc->stage = ZBUFFds_init;
3341 static size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbc)
3343 if (zbc==NULL) return 0; /* support free on null */
3344 ZSTD_freeDCtx(zbc->zc);
3352 /* *** Initialization *** */
3354 static size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbc)
3356 zbc->stage = ZBUFFds_readHeader;
3357 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = zbc->dictSize = 0;
3358 return ZSTD_resetDCtx(zbc->zc);
3362 static size_t ZBUFF_decompressWithDictionary(ZBUFF_DCtx* zbc, const void* src, size_t srcSize)
3364 zbc->dict = (const char*)src;
3365 zbc->dictSize = srcSize;
3369 static size_t ZBUFF_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3371 size_t length = MIN(maxDstSize, srcSize);
3373 memcpy(dst, src, length);
3378 /* *** Decompression *** */
3380 static size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3382 const char* const istart = (const char*)src;
3383 const char* ip = istart;
3384 const char* const iend = istart + *srcSizePtr;
3385 char* const ostart = (char*)dst;
3387 char* const oend = ostart + *maxDstSizePtr;
3390 DEBUGLOG(5, "ZBUFF_decompressContinue");
3397 DEBUGLOG(5, "ZBUFF_decompressContinue: stage==ZBUFFds_init => ERROR(init_missing)");
3398 return ERROR(init_missing);
3400 case ZBUFFds_readHeader :
3401 /* read header from src */
3402 { size_t const headerSize = ZSTD_getFrameParams(&(zbc->params), src, *srcSizePtr);
3403 if (ZSTD_isError(headerSize)) return headerSize;
3405 /* not enough input to decode header : tell how many bytes would be necessary */
3406 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
3407 zbc->hPos += *srcSizePtr;
3409 zbc->stage = ZBUFFds_loadHeader;
3410 return headerSize - zbc->hPos;
3412 zbc->stage = ZBUFFds_decodeHeader;
3416 case ZBUFFds_loadHeader:
3417 /* complete header from src */
3418 { size_t headerSize = ZBUFF_limitCopy(
3419 zbc->headerBuffer + zbc->hPos, ZSTD_frameHeaderSize_max - zbc->hPos,
3421 zbc->hPos += headerSize;
3423 headerSize = ZSTD_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
3424 if (ZSTD_isError(headerSize)) return headerSize;
3426 /* not enough input to decode header : tell how many bytes would be necessary */
3428 return headerSize - zbc->hPos;
3430 /* intentional fallthrough */
3432 case ZBUFFds_decodeHeader:
3433 /* apply header to create / resize buffers */
3434 { size_t const neededOutSize = (size_t)1 << zbc->params.windowLog;
3435 size_t const neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */
3436 if (zbc->inBuffSize < neededInSize) {
3438 zbc->inBuffSize = neededInSize;
3439 zbc->inBuff = (char*)malloc(neededInSize);
3440 if (zbc->inBuff == NULL) return ERROR(memory_allocation);
3442 if (zbc->outBuffSize < neededOutSize) {
3444 zbc->outBuffSize = neededOutSize;
3445 zbc->outBuff = (char*)malloc(neededOutSize);
3446 if (zbc->outBuff == NULL) return ERROR(memory_allocation);
3449 ZSTD_decompress_insertDictionary(zbc->zc, zbc->dict, zbc->dictSize);
3451 /* some data already loaded into headerBuffer : transfer into inBuff */
3452 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
3453 zbc->inPos = zbc->hPos;
3455 zbc->stage = ZBUFFds_load;
3458 zbc->stage = ZBUFFds_read;
3462 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3463 if (neededInSize==0) /* end of frame */
3465 zbc->stage = ZBUFFds_init;
3469 if ((size_t)(iend-ip) >= neededInSize)
3471 /* directly decode from src */
3472 size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
3473 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3475 if (ZSTD_isError(decodedSize)) return decodedSize;
3477 if (!decodedSize) break; /* this was just a header */
3478 zbc->outEnd = zbc->outStart + decodedSize;
3479 zbc->stage = ZBUFFds_flush;
3482 if (ip==iend) { notDone = 0; break; } /* no more input */
3483 zbc->stage = ZBUFFds_load;
3488 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3489 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */
3491 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */
3492 loadedSize = ZBUFF_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
3494 zbc->inPos += loadedSize;
3495 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
3497 size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
3498 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3499 zbc->inBuff, neededInSize);
3500 if (ZSTD_isError(decodedSize)) return decodedSize;
3501 zbc->inPos = 0; /* input is consumed */
3502 if (!decodedSize) { zbc->stage = ZBUFFds_read; break; } /* this was just a header */
3503 zbc->outEnd = zbc->outStart + decodedSize;
3504 zbc->stage = ZBUFFds_flush;
3505 /* ZBUFFds_flush follows */
3511 size_t toFlushSize = zbc->outEnd - zbc->outStart;
3512 size_t flushedSize = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
3514 zbc->outStart += flushedSize;
3515 if (flushedSize == toFlushSize)
3517 zbc->stage = ZBUFFds_read;
3518 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
3519 zbc->outStart = zbc->outEnd = 0;
3522 /* cannot flush everything */
3526 default: return ERROR(GENERIC); /* impossible */
3530 *srcSizePtr = ip-istart;
3531 *maxDstSizePtr = op-ostart;
3534 size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3535 if (nextSrcSizeHint > 3) nextSrcSizeHint+= 3; /* get the next block header while at it */
3536 nextSrcSizeHint -= zbc->inPos; /* already loaded*/
3537 return nextSrcSizeHint;
3542 /* *************************************
3544 ***************************************/
3545 unsigned ZBUFFv04_isError(size_t errorCode) { return ERR_isError(errorCode); }
3546 const char* ZBUFFv04_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
3548 size_t ZBUFFv04_recommendedDInSize() { return BLOCKSIZE + 3; }
3549 size_t ZBUFFv04_recommendedDOutSize() { return BLOCKSIZE; }
3553 /*- ========================================================================= -*/
3555 /* final wrapping stage */
3557 size_t ZSTDv04_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3559 return ZSTD_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
3562 size_t ZSTDv04_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3564 #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1)
3566 ZSTD_DCtx* dctx = ZSTD_createDCtx();
3567 if (dctx==NULL) return ERROR(memory_allocation);
3568 regenSize = ZSTDv04_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
3569 ZSTD_freeDCtx(dctx);
3573 return ZSTDv04_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
3577 size_t ZSTDv04_resetDCtx(ZSTDv04_Dctx* dctx) { return ZSTD_resetDCtx(dctx); }
3579 size_t ZSTDv04_nextSrcSizeToDecompress(ZSTDv04_Dctx* dctx)
3581 return ZSTD_nextSrcSizeToDecompress(dctx);
3584 size_t ZSTDv04_decompressContinue(ZSTDv04_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3586 return ZSTD_decompressContinue(dctx, dst, maxDstSize, src, srcSize);
3591 ZBUFFv04_DCtx* ZBUFFv04_createDCtx(void) { return ZBUFF_createDCtx(); }
3592 size_t ZBUFFv04_freeDCtx(ZBUFFv04_DCtx* dctx) { return ZBUFF_freeDCtx(dctx); }
3594 size_t ZBUFFv04_decompressInit(ZBUFFv04_DCtx* dctx) { return ZBUFF_decompressInit(dctx); }
3595 size_t ZBUFFv04_decompressWithDictionary(ZBUFFv04_DCtx* dctx, const void* src, size_t srcSize)
3596 { return ZBUFF_decompressWithDictionary(dctx, src, srcSize); }
3598 size_t ZBUFFv04_decompressContinue(ZBUFFv04_DCtx* dctx, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3600 DEBUGLOG(5, "ZBUFFv04_decompressContinue");
3601 return ZBUFF_decompressContinue(dctx, dst, maxDstSizePtr, src, srcSizePtr);
3604 ZSTD_DCtx* ZSTDv04_createDCtx(void) { return ZSTD_createDCtx(); }
3605 size_t ZSTDv04_freeDCtx(ZSTD_DCtx* dctx) { return ZSTD_freeDCtx(dctx); }