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 #include <stddef.h> /* size_t, ptrdiff_t */
14 #include "../common/compiler.h"
15 #include "../common/error_private.h"
18 /******************************************
20 ******************************************/
21 #if defined(_MSC_VER) /* Visual Studio */
22 # include <stdlib.h> /* _byteswap_ulong */
23 # include <intrin.h> /* _byteswap_* */
28 /* ******************************************************************
30 low-level memory access routines
31 Copyright (C) 2013-2015, Yann Collet.
33 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
35 Redistribution and use in source and binary forms, with or without
36 modification, are permitted provided that the following conditions are
39 * Redistributions of source code must retain the above copyright
40 notice, this list of conditions and the following disclaimer.
41 * Redistributions in binary form must reproduce the above
42 copyright notice, this list of conditions and the following disclaimer
43 in the documentation and/or other materials provided with the
46 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
47 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
48 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
49 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
50 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
51 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
52 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
53 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
54 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
55 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
56 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
58 You can contact the author at :
59 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
60 - Public forum : https://groups.google.com/forum/#!forum/lz4c
61 ****************************************************************** */
65 #if defined (__cplusplus)
69 /******************************************
71 ******************************************/
72 #include <stddef.h> /* size_t, ptrdiff_t */
73 #include <string.h> /* memcpy */
76 /****************************************************************
78 *****************************************************************/
79 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
81 # include <inttypes.h>
83 # include <stdint.h> /* intptr_t */
93 typedef unsigned char BYTE;
94 typedef unsigned short U16;
95 typedef signed short S16;
96 typedef unsigned int U32;
97 typedef signed int S32;
98 typedef unsigned long long U64;
99 typedef signed long long S64;
103 /****************************************************************
105 *****************************************************************/
107 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
108 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
110 MEM_STATIC unsigned MEM_isLittleEndian(void)
112 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
116 MEM_STATIC U16 MEM_read16(const void* memPtr)
118 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
121 MEM_STATIC U32 MEM_read32(const void* memPtr)
123 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
126 MEM_STATIC U64 MEM_read64(const void* memPtr)
128 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
131 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
133 memcpy(memPtr, &value, sizeof(value));
136 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
138 if (MEM_isLittleEndian())
139 return MEM_read16(memPtr);
142 const BYTE* p = (const BYTE*)memPtr;
143 return (U16)(p[0] + (p[1]<<8));
147 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
149 if (MEM_isLittleEndian())
151 MEM_write16(memPtr, val);
155 BYTE* p = (BYTE*)memPtr;
157 p[1] = (BYTE)(val>>8);
161 MEM_STATIC U32 MEM_readLE24(const void* memPtr)
163 return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
166 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
168 if (MEM_isLittleEndian())
169 return MEM_read32(memPtr);
172 const BYTE* p = (const BYTE*)memPtr;
173 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
177 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
179 if (MEM_isLittleEndian())
180 return MEM_read64(memPtr);
183 const BYTE* p = (const BYTE*)memPtr;
184 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
185 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
190 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
193 return (size_t)MEM_readLE32(memPtr);
195 return (size_t)MEM_readLE64(memPtr);
199 #if defined (__cplusplus)
203 #endif /* MEM_H_MODULE */
206 /* ******************************************************************
208 Part of NewGen Entropy library
209 header file (to include)
210 Copyright (C) 2013-2015, Yann Collet.
212 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
214 Redistribution and use in source and binary forms, with or without
215 modification, are permitted provided that the following conditions are
218 * Redistributions of source code must retain the above copyright
219 notice, this list of conditions and the following disclaimer.
220 * Redistributions in binary form must reproduce the above
221 copyright notice, this list of conditions and the following disclaimer
222 in the documentation and/or other materials provided with the
225 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
226 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
227 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
228 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
229 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
230 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
231 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
232 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
233 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
234 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
235 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
237 You can contact the author at :
238 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
239 - Public forum : https://groups.google.com/forum/#!forum/lz4c
240 ****************************************************************** */
241 #ifndef BITSTREAM_H_MODULE
242 #define BITSTREAM_H_MODULE
244 #if defined (__cplusplus)
250 * This API consists of small unitary functions, which highly benefit from being inlined.
251 * Since link-time-optimization is not available for all compilers,
252 * these functions are defined into a .h to be included.
256 /**********************************************
257 * bitStream decompression API (read backward)
258 **********************************************/
262 unsigned bitsConsumed;
267 typedef enum { BIT_DStream_unfinished = 0,
268 BIT_DStream_endOfBuffer = 1,
269 BIT_DStream_completed = 2,
270 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
271 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
273 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
274 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
275 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
276 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
280 /******************************************
282 ******************************************/
283 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
284 /* faster, but works only if nbBits >= 1 */
288 /****************************************************************
290 ****************************************************************/
291 MEM_STATIC unsigned BIT_highbit32 (U32 val)
293 # if defined(_MSC_VER) /* Visual */
295 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
296 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
297 return __builtin_clz (val) ^ 31;
298 # else /* Software version */
299 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 };
307 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
314 /**********************************************************
316 **********************************************************/
319 * Initialize a BIT_DStream_t.
320 * @bitD : a pointer to an already allocated BIT_DStream_t structure
321 * @srcBuffer must point at the beginning of a bitStream
322 * @srcSize must be the exact size of the bitStream
323 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
325 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
327 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
329 if (srcSize >= sizeof(size_t)) /* normal case */
332 bitD->start = (const char*)srcBuffer;
333 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
334 bitD->bitContainer = MEM_readLEST(bitD->ptr);
335 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
336 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
337 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
342 bitD->start = (const char*)srcBuffer;
343 bitD->ptr = bitD->start;
344 bitD->bitContainer = *(const BYTE*)(bitD->start);
347 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
349 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
351 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
353 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
355 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
357 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
361 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
362 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
363 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
364 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
369 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
371 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
372 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
375 /*! BIT_lookBitsFast :
376 * unsafe version; only works if nbBits >= 1 */
377 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
379 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
380 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
383 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
385 bitD->bitsConsumed += nbBits;
388 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
390 size_t value = BIT_lookBits(bitD, nbBits);
391 BIT_skipBits(bitD, nbBits);
395 /*!BIT_readBitsFast :
396 * unsafe version; only works if nbBits >= 1 */
397 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
399 size_t value = BIT_lookBitsFast(bitD, nbBits);
400 BIT_skipBits(bitD, nbBits);
404 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
406 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
407 return BIT_DStream_overflow;
409 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
411 bitD->ptr -= bitD->bitsConsumed >> 3;
412 bitD->bitsConsumed &= 7;
413 bitD->bitContainer = MEM_readLEST(bitD->ptr);
414 return BIT_DStream_unfinished;
416 if (bitD->ptr == bitD->start)
418 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
419 return BIT_DStream_completed;
422 U32 nbBytes = bitD->bitsConsumed >> 3;
423 BIT_DStream_status result = BIT_DStream_unfinished;
424 if (bitD->ptr - nbBytes < bitD->start)
426 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
427 result = BIT_DStream_endOfBuffer;
429 bitD->ptr -= nbBytes;
430 bitD->bitsConsumed -= nbBytes*8;
431 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
437 * @return Tells if DStream has reached its exact end
439 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
441 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
444 #if defined (__cplusplus)
448 #endif /* BITSTREAM_H_MODULE */
449 /* ******************************************************************
450 Error codes and messages
451 Copyright (C) 2013-2015, Yann Collet
453 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
455 Redistribution and use in source and binary forms, with or without
456 modification, are permitted provided that the following conditions are
459 * Redistributions of source code must retain the above copyright
460 notice, this list of conditions and the following disclaimer.
461 * Redistributions in binary form must reproduce the above
462 copyright notice, this list of conditions and the following disclaimer
463 in the documentation and/or other materials provided with the
466 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
467 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
468 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
469 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
470 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
471 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
472 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
473 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
474 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
475 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
476 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
478 You can contact the author at :
479 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
480 - Public forum : https://groups.google.com/forum/#!forum/lz4c
481 ****************************************************************** */
482 #ifndef ERROR_H_MODULE
483 #define ERROR_H_MODULE
485 #if defined (__cplusplus)
490 /******************************************
492 ******************************************/
493 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
494 # define ERR_STATIC static inline
495 #elif defined(_MSC_VER)
496 # define ERR_STATIC static __inline
497 #elif defined(__GNUC__)
498 # define ERR_STATIC static __attribute__((unused))
500 # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
504 /******************************************
506 ******************************************/
507 #define PREFIX(name) ZSTD_error_##name
509 #define ERROR(name) (size_t)-PREFIX(name)
511 #define ERROR_LIST(ITEM) \
512 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
513 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
514 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
515 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
516 ITEM(PREFIX(maxCode))
518 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
519 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
521 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
522 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
523 static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
525 ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
527 ERR_STATIC const char* ERR_getErrorName(size_t code)
529 static const char* codeError = "Unspecified error code";
530 if (ERR_isError(code)) return ERR_strings[-(int)(code)];
535 #if defined (__cplusplus)
539 #endif /* ERROR_H_MODULE */
541 Constructor and Destructor of type FSE_CTable
542 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
543 typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
544 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
547 /* ******************************************************************
548 FSE : Finite State Entropy coder
549 header file for static linking (only)
550 Copyright (C) 2013-2015, Yann Collet
552 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
554 Redistribution and use in source and binary forms, with or without
555 modification, are permitted provided that the following conditions are
558 * Redistributions of source code must retain the above copyright
559 notice, this list of conditions and the following disclaimer.
560 * Redistributions in binary form must reproduce the above
561 copyright notice, this list of conditions and the following disclaimer
562 in the documentation and/or other materials provided with the
565 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
566 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
567 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
568 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
569 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
570 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
571 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
572 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
573 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
574 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
575 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
577 You can contact the author at :
578 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
579 - Public forum : https://groups.google.com/forum/#!forum/lz4c
580 ****************************************************************** */
581 #if defined (__cplusplus)
586 /******************************************
588 ******************************************/
589 /* FSE buffer bounds */
590 #define FSE_NCOUNTBOUND 512
591 #define FSE_BLOCKBOUND(size) (size + (size>>7))
592 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
594 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
595 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
596 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
599 /******************************************
601 ******************************************/
602 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
603 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
605 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
606 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
609 /******************************************
610 * FSE symbol decompression API
611 ******************************************/
615 const void* table; /* precise table may vary, depending on U16 */
619 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
621 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
623 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
626 /******************************************
628 ******************************************/
629 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
630 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
633 /******************************************
634 * Implementation of inline functions
635 ******************************************/
642 } FSE_DTableHeader; /* sizeof U32 */
646 unsigned short newState;
647 unsigned char symbol;
648 unsigned char nbBits;
649 } FSE_decode_t; /* size == U32 */
651 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
653 FSE_DTableHeader DTableH;
654 memcpy(&DTableH, dt, sizeof(DTableH));
655 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
656 BIT_reloadDStream(bitD);
657 DStatePtr->table = dt + 1;
660 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
662 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
663 const U32 nbBits = DInfo.nbBits;
664 BYTE symbol = DInfo.symbol;
665 size_t lowBits = BIT_readBits(bitD, nbBits);
667 DStatePtr->state = DInfo.newState + lowBits;
671 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
673 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
674 const U32 nbBits = DInfo.nbBits;
675 BYTE symbol = DInfo.symbol;
676 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
678 DStatePtr->state = DInfo.newState + lowBits;
682 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
684 return DStatePtr->state == 0;
688 #if defined (__cplusplus)
691 /* ******************************************************************
692 Huff0 : Huffman coder, part of New Generation Entropy library
693 header file for static linking (only)
694 Copyright (C) 2013-2015, Yann Collet
696 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
698 Redistribution and use in source and binary forms, with or without
699 modification, are permitted provided that the following conditions are
702 * Redistributions of source code must retain the above copyright
703 notice, this list of conditions and the following disclaimer.
704 * Redistributions in binary form must reproduce the above
705 copyright notice, this list of conditions and the following disclaimer
706 in the documentation and/or other materials provided with the
709 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
710 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
711 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
712 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
713 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
714 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
715 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
716 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
717 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
718 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
719 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
721 You can contact the author at :
722 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
723 - Public forum : https://groups.google.com/forum/#!forum/lz4c
724 ****************************************************************** */
726 #if defined (__cplusplus)
730 /******************************************
731 * Static allocation macros
732 ******************************************/
733 /* Huff0 buffer bounds */
734 #define HUF_CTABLEBOUND 129
735 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
736 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
738 /* static allocation of Huff0's DTable */
739 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
740 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
741 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
742 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
743 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
744 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
745 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
748 /******************************************
750 ******************************************/
751 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
752 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
755 #if defined (__cplusplus)
760 zstd - standard compression library
762 Copyright (C) 2014-2015, Yann Collet.
764 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
766 Redistribution and use in source and binary forms, with or without
767 modification, are permitted provided that the following conditions are
769 * Redistributions of source code must retain the above copyright
770 notice, this list of conditions and the following disclaimer.
771 * Redistributions in binary form must reproduce the above
772 copyright notice, this list of conditions and the following disclaimer
773 in the documentation and/or other materials provided with the
775 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
776 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
777 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
778 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
779 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
780 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
781 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
782 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
783 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
784 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
785 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
787 You can contact the author at :
788 - zstd source repository : https://github.com/Cyan4973/zstd
789 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
792 #if defined (__cplusplus)
796 /* *************************************
798 ***************************************/
799 #include <stddef.h> /* size_t */
802 /* *************************************
804 ***************************************/
805 #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
806 #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
807 #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
808 #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
811 /* *************************************
813 ***************************************/
814 typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */
816 #if defined (__cplusplus)
820 zstd - standard compression library
821 Header File for static linking only
822 Copyright (C) 2014-2015, Yann Collet.
824 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
826 Redistribution and use in source and binary forms, with or without
827 modification, are permitted provided that the following conditions are
829 * Redistributions of source code must retain the above copyright
830 notice, this list of conditions and the following disclaimer.
831 * Redistributions in binary form must reproduce the above
832 copyright notice, this list of conditions and the following disclaimer
833 in the documentation and/or other materials provided with the
835 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
836 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
837 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
838 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
839 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
840 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
841 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
842 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
843 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
844 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
845 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
847 You can contact the author at :
848 - zstd source repository : https://github.com/Cyan4973/zstd
849 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
852 /* The objects defined into this file should be considered experimental.
853 * They are not labelled stable, as their prototype may change in the future.
854 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
857 #if defined (__cplusplus)
861 /* *************************************
862 * Streaming functions
863 ***************************************/
865 typedef struct ZSTDv03_Dctx_s ZSTD_DCtx;
868 Use above functions alternatively.
869 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
870 ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
871 Result is the number of bytes regenerated within 'dst'.
872 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
875 /* *************************************
876 * Prefix - version detection
877 ***************************************/
878 #define ZSTD_magicNumber 0xFD2FB523 /* v0.3 */
881 #if defined (__cplusplus)
884 /* ******************************************************************
885 FSE : Finite State Entropy coder
886 Copyright (C) 2013-2015, Yann Collet.
888 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
890 Redistribution and use in source and binary forms, with or without
891 modification, are permitted provided that the following conditions are
894 * Redistributions of source code must retain the above copyright
895 notice, this list of conditions and the following disclaimer.
896 * Redistributions in binary form must reproduce the above
897 copyright notice, this list of conditions and the following disclaimer
898 in the documentation and/or other materials provided with the
901 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
902 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
903 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
904 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
905 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
906 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
907 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
908 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
909 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
910 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
911 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
913 You can contact the author at :
914 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
915 - Public forum : https://groups.google.com/forum/#!forum/lz4c
916 ****************************************************************** */
918 #ifndef FSE_COMMONDEFS_ONLY
920 /****************************************************************
922 ****************************************************************/
924 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
925 * Increasing memory usage improves compression ratio
926 * Reduced memory usage can improve speed, due to cache effect
927 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
928 #define FSE_MAX_MEMORY_USAGE 14
929 #define FSE_DEFAULT_MEMORY_USAGE 13
931 /* FSE_MAX_SYMBOL_VALUE :
932 * Maximum symbol value authorized.
933 * Required for proper stack allocation */
934 #define FSE_MAX_SYMBOL_VALUE 255
937 /****************************************************************
938 * template functions type & suffix
939 ****************************************************************/
940 #define FSE_FUNCTION_TYPE BYTE
941 #define FSE_FUNCTION_EXTENSION
944 /****************************************************************
946 ****************************************************************/
947 #endif /* !FSE_COMMONDEFS_ONLY */
950 /****************************************************************
952 ****************************************************************/
953 #ifdef _MSC_VER /* Visual Studio */
954 # define FORCE_INLINE static __forceinline
955 # include <intrin.h> /* For Visual 2005 */
956 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
957 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
959 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
961 # define FORCE_INLINE static inline __attribute__((always_inline))
963 # define FORCE_INLINE static inline
966 # define FORCE_INLINE static
967 # endif /* __STDC_VERSION__ */
971 /****************************************************************
973 ****************************************************************/
974 #include <stdlib.h> /* malloc, free, qsort */
975 #include <string.h> /* memcpy, memset */
976 #include <stdio.h> /* printf (debug) */
978 /****************************************************************
980 *****************************************************************/
981 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
982 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
983 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
984 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
985 #define FSE_MIN_TABLELOG 5
987 #define FSE_TABLELOG_ABSOLUTE_MAX 15
988 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
989 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
993 /****************************************************************
995 ****************************************************************/
996 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
999 /****************************************************************
1001 ****************************************************************/
1002 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1005 /****************************************************************
1007 ****************************************************************/
1009 designed to be included
1010 for type-specific functions (template emulation in C)
1011 Objective is to write these functions only once, for improved maintenance
1015 #ifndef FSE_FUNCTION_EXTENSION
1016 # error "FSE_FUNCTION_EXTENSION must be defined"
1018 #ifndef FSE_FUNCTION_TYPE
1019 # error "FSE_FUNCTION_TYPE must be defined"
1022 /* Function names */
1023 #define FSE_CAT(X,Y) X##Y
1024 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1025 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1028 /* Function templates */
1030 #define FSE_DECODE_TYPE FSE_decode_t
1032 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1034 static size_t FSE_buildDTable
1035 (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1038 FSE_DTableHeader DTableH;
1039 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1040 const U32 tableSize = 1 << tableLog;
1041 const U32 tableMask = tableSize-1;
1042 const U32 step = FSE_tableStep(tableSize);
1043 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1045 U32 highThreshold = tableSize-1;
1046 const S16 largeLimit= (S16)(1 << (tableLog-1));
1051 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1052 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1054 /* Init, lay down lowprob symbols */
1055 DTableH.tableLog = (U16)tableLog;
1056 for (s=0; s<=maxSymbolValue; s++)
1058 if (normalizedCounter[s]==-1)
1060 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1065 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1066 symbolNext[s] = normalizedCounter[s];
1070 /* Spread symbols */
1071 for (s=0; s<=maxSymbolValue; s++)
1074 for (i=0; i<normalizedCounter[s]; i++)
1076 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1077 position = (position + step) & tableMask;
1078 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1082 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1084 /* Build Decoding table */
1087 for (i=0; i<tableSize; i++)
1089 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1090 U16 nextState = symbolNext[symbol]++;
1091 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1092 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1096 DTableH.fastMode = (U16)noLarge;
1097 memcpy(dt, &DTableH, sizeof(DTableH));
1102 #ifndef FSE_COMMONDEFS_ONLY
1103 /******************************************
1104 * FSE helper functions
1105 ******************************************/
1106 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1109 /****************************************************************
1110 * FSE NCount encoding-decoding
1111 ****************************************************************/
1112 static short FSE_abs(short a)
1114 return a<0 ? -a : a;
1117 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1118 const void* headerBuffer, size_t hbSize)
1120 const BYTE* const istart = (const BYTE*) headerBuffer;
1121 const BYTE* const iend = istart + hbSize;
1122 const BYTE* ip = istart;
1128 unsigned charnum = 0;
1131 if (hbSize < 4) return ERROR(srcSize_wrong);
1132 bitStream = MEM_readLE32(ip);
1133 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1134 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1137 *tableLogPtr = nbBits;
1138 remaining = (1<<nbBits)+1;
1139 threshold = 1<<nbBits;
1142 while ((remaining>1) && (charnum<=*maxSVPtr))
1146 unsigned n0 = charnum;
1147 while ((bitStream & 0xFFFF) == 0xFFFF)
1153 bitStream = MEM_readLE32(ip) >> bitCount;
1161 while ((bitStream & 3) == 3)
1167 n0 += bitStream & 3;
1169 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1170 while (charnum < n0) normalizedCounter[charnum++] = 0;
1171 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1175 bitStream = MEM_readLE32(ip) >> bitCount;
1181 const short max = (short)((2*threshold-1)-remaining);
1184 if ((bitStream & (threshold-1)) < (U32)max)
1186 count = (short)(bitStream & (threshold-1));
1187 bitCount += nbBits-1;
1191 count = (short)(bitStream & (2*threshold-1));
1192 if (count >= threshold) count -= max;
1196 count--; /* extra accuracy */
1197 remaining -= FSE_abs(count);
1198 normalizedCounter[charnum++] = count;
1200 while (remaining < threshold)
1207 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1214 bitCount -= (int)(8 * (iend - 4 - ip));
1217 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1221 if (remaining != 1) return ERROR(GENERIC);
1222 *maxSVPtr = charnum-1;
1224 ip += (bitCount+7)>>3;
1225 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1230 /*********************************************************
1231 * Decompression (Byte symbols)
1232 *********************************************************/
1233 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1236 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1237 FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1;
1239 DTableH->tableLog = 0;
1240 DTableH->fastMode = 0;
1243 cell->symbol = symbolValue;
1250 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1253 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1254 FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1;
1255 const unsigned tableSize = 1 << nbBits;
1256 const unsigned tableMask = tableSize - 1;
1257 const unsigned maxSymbolValue = tableMask;
1261 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1263 /* Build Decoding Table */
1264 DTableH->tableLog = (U16)nbBits;
1265 DTableH->fastMode = 1;
1266 for (s=0; s<=maxSymbolValue; s++)
1268 dinfo[s].newState = 0;
1269 dinfo[s].symbol = (BYTE)s;
1270 dinfo[s].nbBits = (BYTE)nbBits;
1276 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1277 void* dst, size_t maxDstSize,
1278 const void* cSrc, size_t cSrcSize,
1279 const FSE_DTable* dt, const unsigned fast)
1281 BYTE* const ostart = (BYTE*) dst;
1283 BYTE* const omax = op + maxDstSize;
1284 BYTE* const olimit = omax-3;
1287 FSE_DState_t state1;
1288 FSE_DState_t state2;
1292 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1293 if (FSE_isError(errorCode)) return errorCode;
1295 FSE_initDState(&state1, &bitD, dt);
1296 FSE_initDState(&state2, &bitD, dt);
1298 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1300 /* 4 symbols per loop */
1301 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1303 op[0] = FSE_GETSYMBOL(&state1);
1305 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1306 BIT_reloadDStream(&bitD);
1308 op[1] = FSE_GETSYMBOL(&state2);
1310 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1311 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1313 op[2] = FSE_GETSYMBOL(&state1);
1315 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1316 BIT_reloadDStream(&bitD);
1318 op[3] = FSE_GETSYMBOL(&state2);
1322 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1325 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1328 *op++ = FSE_GETSYMBOL(&state1);
1330 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1333 *op++ = FSE_GETSYMBOL(&state2);
1337 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1340 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1342 return ERROR(corruption_detected);
1346 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1347 const void* cSrc, size_t cSrcSize,
1348 const FSE_DTable* dt)
1350 FSE_DTableHeader DTableH;
1351 memcpy(&DTableH, dt, sizeof(DTableH));
1353 /* select fast mode (static) */
1354 if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1355 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1359 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1361 const BYTE* const istart = (const BYTE*)cSrc;
1362 const BYTE* ip = istart;
1363 short counting[FSE_MAX_SYMBOL_VALUE+1];
1364 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1366 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1369 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1371 /* normal FSE decoding mode */
1372 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1373 if (FSE_isError(errorCode)) return errorCode;
1374 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1376 cSrcSize -= errorCode;
1378 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1379 if (FSE_isError(errorCode)) return errorCode;
1381 /* always return, even if it is an error code */
1382 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1387 #endif /* FSE_COMMONDEFS_ONLY */
1388 /* ******************************************************************
1389 Huff0 : Huffman coder, part of New Generation Entropy library
1390 Copyright (C) 2013-2015, Yann Collet.
1392 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1394 Redistribution and use in source and binary forms, with or without
1395 modification, are permitted provided that the following conditions are
1398 * Redistributions of source code must retain the above copyright
1399 notice, this list of conditions and the following disclaimer.
1400 * Redistributions in binary form must reproduce the above
1401 copyright notice, this list of conditions and the following disclaimer
1402 in the documentation and/or other materials provided with the
1405 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1406 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1407 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1408 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1409 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1410 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1411 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1412 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1413 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1414 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1415 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1417 You can contact the author at :
1418 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1419 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1420 ****************************************************************** */
1422 /****************************************************************
1423 * Compiler specifics
1424 ****************************************************************/
1425 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1426 /* inline is defined */
1427 #elif defined(_MSC_VER)
1428 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1429 # define inline __inline
1431 # define inline /* disable inline */
1435 /****************************************************************
1437 ****************************************************************/
1438 #include <stdlib.h> /* malloc, free, qsort */
1439 #include <string.h> /* memcpy, memset */
1440 #include <stdio.h> /* printf (debug) */
1442 /****************************************************************
1444 ****************************************************************/
1445 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1448 /******************************************
1450 ******************************************/
1451 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1453 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1454 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1455 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1456 #define HUF_MAX_SYMBOL_VALUE 255
1457 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1458 # error "HUF_MAX_TABLELOG is too large !"
1463 /*********************************************************
1464 * Huff0 : Huffman block decompression
1465 *********************************************************/
1466 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1468 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1470 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1473 Read compact Huffman tree, saved by HUF_writeCTable
1474 @huffWeight : destination buffer
1475 @return : size read from `src`
1477 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1478 U32* nbSymbolsPtr, U32* tableLogPtr,
1479 const void* src, size_t srcSize)
1483 const BYTE* ip = (const BYTE*) src;
1488 if (!srcSize) return ERROR(srcSize_wrong);
1490 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1492 if (iSize >= 128) /* special header */
1494 if (iSize >= (242)) /* RLE */
1496 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1497 oSize = l[iSize-242];
1498 memset(huffWeight, 1, hwSize);
1501 else /* Incompressible */
1503 oSize = iSize - 127;
1504 iSize = ((oSize+1)/2);
1505 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1506 if (oSize >= hwSize) return ERROR(corruption_detected);
1508 for (n=0; n<oSize; n+=2)
1510 huffWeight[n] = ip[n/2] >> 4;
1511 huffWeight[n+1] = ip[n/2] & 15;
1515 else /* header compressed with FSE (normal case) */
1517 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1518 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1519 if (FSE_isError(oSize)) return oSize;
1522 /* collect weight stats */
1523 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1525 for (n=0; n<oSize; n++)
1527 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1528 rankStats[huffWeight[n]]++;
1529 weightTotal += (1 << huffWeight[n]) >> 1;
1531 if (weightTotal == 0) return ERROR(corruption_detected);
1533 /* get last non-null symbol weight (implied, total must be 2^n) */
1534 tableLog = BIT_highbit32(weightTotal) + 1;
1535 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1537 U32 total = 1 << tableLog;
1538 U32 rest = total - weightTotal;
1539 U32 verif = 1 << BIT_highbit32(rest);
1540 U32 lastWeight = BIT_highbit32(rest) + 1;
1541 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1542 huffWeight[oSize] = (BYTE)lastWeight;
1543 rankStats[lastWeight]++;
1546 /* check tree construction validity */
1547 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1550 *nbSymbolsPtr = (U32)(oSize+1);
1551 *tableLogPtr = tableLog;
1556 /**************************/
1557 /* single-symbol decoding */
1558 /**************************/
1560 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1562 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1563 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1565 const BYTE* ip = (const BYTE*) src;
1566 size_t iSize = ip[0];
1570 void* ptr = DTable+1;
1571 HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr);
1573 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1574 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1576 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1577 if (HUF_isError(iSize)) return iSize;
1580 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1581 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1585 for (n=1; n<=tableLog; n++)
1587 U32 current = nextRankStart;
1588 nextRankStart += (rankVal[n] << (n-1));
1589 rankVal[n] = current;
1593 for (n=0; n<nbSymbols; n++)
1595 const U32 w = huffWeight[n];
1596 const U32 length = (1 << w) >> 1;
1599 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1600 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1602 rankVal[w] += length;
1608 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1610 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1611 const BYTE c = dt[val].byte;
1612 BIT_skipBits(Dstream, dt[val].nbBits);
1616 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1617 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1619 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1620 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1621 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1623 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1625 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1627 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1629 BYTE* const pStart = p;
1631 /* up to 4 symbols at a time */
1632 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1634 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1635 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1636 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1637 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1640 /* closer to the end */
1641 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1642 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1644 /* no more data to retrieve from bitstream, hence no need to reload */
1646 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1652 static size_t HUF_decompress4X2_usingDTable(
1653 void* dst, size_t dstSize,
1654 const void* cSrc, size_t cSrcSize,
1657 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1660 const BYTE* const istart = (const BYTE*) cSrc;
1661 BYTE* const ostart = (BYTE*) dst;
1662 BYTE* const oend = ostart + dstSize;
1664 const void* ptr = DTable;
1665 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1666 const U32 dtLog = DTable[0];
1670 BIT_DStream_t bitD1;
1671 BIT_DStream_t bitD2;
1672 BIT_DStream_t bitD3;
1673 BIT_DStream_t bitD4;
1674 const size_t length1 = MEM_readLE16(istart);
1675 const size_t length2 = MEM_readLE16(istart+2);
1676 const size_t length3 = MEM_readLE16(istart+4);
1678 const BYTE* const istart1 = istart + 6; /* jumpTable */
1679 const BYTE* const istart2 = istart1 + length1;
1680 const BYTE* const istart3 = istart2 + length2;
1681 const BYTE* const istart4 = istart3 + length3;
1682 const size_t segmentSize = (dstSize+3) / 4;
1683 BYTE* const opStart2 = ostart + segmentSize;
1684 BYTE* const opStart3 = opStart2 + segmentSize;
1685 BYTE* const opStart4 = opStart3 + segmentSize;
1687 BYTE* op2 = opStart2;
1688 BYTE* op3 = opStart3;
1689 BYTE* op4 = opStart4;
1692 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1693 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1694 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1695 if (HUF_isError(errorCode)) return errorCode;
1696 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1697 if (HUF_isError(errorCode)) return errorCode;
1698 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1699 if (HUF_isError(errorCode)) return errorCode;
1700 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1701 if (HUF_isError(errorCode)) return errorCode;
1703 /* 16-32 symbols per loop (4-8 symbols per stream) */
1704 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1705 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1707 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1708 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1709 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1710 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1711 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1712 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1713 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1714 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1715 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1716 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1717 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1718 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1719 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1720 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1721 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1722 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1724 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1727 /* check corruption */
1728 if (op1 > opStart2) return ERROR(corruption_detected);
1729 if (op2 > opStart3) return ERROR(corruption_detected);
1730 if (op3 > opStart4) return ERROR(corruption_detected);
1731 /* note : op4 supposed already verified within main loop */
1733 /* finish bitStreams one by one */
1734 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1735 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1736 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1737 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1740 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1741 if (!endSignal) return ERROR(corruption_detected);
1749 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1751 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1752 const BYTE* ip = (const BYTE*) cSrc;
1755 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1756 if (HUF_isError(errorCode)) return errorCode;
1757 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1759 cSrcSize -= errorCode;
1761 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1765 /***************************/
1766 /* double-symbols decoding */
1767 /***************************/
1769 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1770 const U32* rankValOrigin, const int minWeight,
1771 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1772 U32 nbBitsBaseline, U16 baseSeq)
1775 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1778 /* get pre-calculated rankVal */
1779 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1781 /* fill skipped values */
1784 U32 i, skipSize = rankVal[minWeight];
1785 MEM_writeLE16(&(DElt.sequence), baseSeq);
1786 DElt.nbBits = (BYTE)(consumed);
1788 for (i = 0; i < skipSize; i++)
1793 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1795 const U32 symbol = sortedSymbols[s].symbol;
1796 const U32 weight = sortedSymbols[s].weight;
1797 const U32 nbBits = nbBitsBaseline - weight;
1798 const U32 length = 1 << (sizeLog-nbBits);
1799 const U32 start = rankVal[weight];
1801 const U32 end = start + length;
1803 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1804 DElt.nbBits = (BYTE)(nbBits + consumed);
1806 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1808 rankVal[weight] += length;
1812 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1814 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1815 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1816 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1817 const U32 nbBitsBaseline)
1819 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1820 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1821 const U32 minBits = nbBitsBaseline - maxWeight;
1824 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1827 for (s=0; s<sortedListSize; s++)
1829 const U16 symbol = sortedList[s].symbol;
1830 const U32 weight = sortedList[s].weight;
1831 const U32 nbBits = nbBitsBaseline - weight;
1832 const U32 start = rankVal[weight];
1833 const U32 length = 1 << (targetLog-nbBits);
1835 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1838 int minWeight = nbBits + scaleLog;
1839 if (minWeight < 1) minWeight = 1;
1840 sortedRank = rankStart[minWeight];
1841 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1842 rankValOrigin[nbBits], minWeight,
1843 sortedList+sortedRank, sortedListSize-sortedRank,
1844 nbBitsBaseline, symbol);
1849 const U32 end = start + length;
1852 MEM_writeLE16(&(DElt.sequence), symbol);
1853 DElt.nbBits = (BYTE)(nbBits);
1855 for (i = start; i < end; i++)
1858 rankVal[weight] += length;
1862 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1864 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1865 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1866 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1867 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1868 U32* const rankStart = rankStart0+1;
1870 U32 tableLog, maxW, sizeOfSort, nbSymbols;
1871 const U32 memLog = DTable[0];
1872 const BYTE* ip = (const BYTE*) src;
1873 size_t iSize = ip[0];
1875 HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1877 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
1878 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1879 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1881 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1882 if (HUF_isError(iSize)) return iSize;
1885 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
1887 /* find maxWeight */
1888 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1889 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
1891 /* Get start index of each weight */
1893 U32 w, nextRankStart = 0;
1894 for (w=1; w<=maxW; w++)
1896 U32 current = nextRankStart;
1897 nextRankStart += rankStats[w];
1898 rankStart[w] = current;
1900 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
1901 sizeOfSort = nextRankStart;
1904 /* sort symbols by weight */
1907 for (s=0; s<nbSymbols; s++)
1909 U32 w = weightList[s];
1910 U32 r = rankStart[w]++;
1911 sortedSymbol[r].symbol = (BYTE)s;
1912 sortedSymbol[r].weight = (BYTE)w;
1914 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1919 const U32 minBits = tableLog+1 - maxW;
1920 U32 nextRankVal = 0;
1922 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
1923 U32* rankVal0 = rankVal[0];
1924 for (w=1; w<=maxW; w++)
1926 U32 current = nextRankVal;
1927 nextRankVal += rankStats[w] << (w+rescale);
1928 rankVal0[w] = current;
1930 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1932 U32* rankValPtr = rankVal[consumed];
1933 for (w = 1; w <= maxW; w++)
1935 rankValPtr[w] = rankVal0[w] >> consumed;
1940 HUF_fillDTableX4(dt, memLog,
1941 sortedSymbol, sizeOfSort,
1942 rankStart0, rankVal, maxW,
1949 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1951 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1952 memcpy(op, dt+val, 2);
1953 BIT_skipBits(DStream, dt[val].nbBits);
1954 return dt[val].length;
1957 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1959 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1960 memcpy(op, dt+val, 1);
1961 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
1964 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
1966 BIT_skipBits(DStream, dt[val].nbBits);
1967 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
1968 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 */
1975 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
1976 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1978 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
1979 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1980 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1982 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
1984 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1986 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
1988 BYTE* const pStart = p;
1990 /* up to 8 symbols at a time */
1991 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
1993 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
1994 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
1995 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
1996 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
1999 /* closer to the end */
2000 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2001 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2004 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2007 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2014 static size_t HUF_decompress4X4_usingDTable(
2015 void* dst, size_t dstSize,
2016 const void* cSrc, size_t cSrcSize,
2019 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2022 const BYTE* const istart = (const BYTE*) cSrc;
2023 BYTE* const ostart = (BYTE*) dst;
2024 BYTE* const oend = ostart + dstSize;
2026 const void* ptr = DTable;
2027 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2028 const U32 dtLog = DTable[0];
2032 BIT_DStream_t bitD1;
2033 BIT_DStream_t bitD2;
2034 BIT_DStream_t bitD3;
2035 BIT_DStream_t bitD4;
2036 const size_t length1 = MEM_readLE16(istart);
2037 const size_t length2 = MEM_readLE16(istart+2);
2038 const size_t length3 = MEM_readLE16(istart+4);
2040 const BYTE* const istart1 = istart + 6; /* jumpTable */
2041 const BYTE* const istart2 = istart1 + length1;
2042 const BYTE* const istart3 = istart2 + length2;
2043 const BYTE* const istart4 = istart3 + length3;
2044 const size_t segmentSize = (dstSize+3) / 4;
2045 BYTE* const opStart2 = ostart + segmentSize;
2046 BYTE* const opStart3 = opStart2 + segmentSize;
2047 BYTE* const opStart4 = opStart3 + segmentSize;
2049 BYTE* op2 = opStart2;
2050 BYTE* op3 = opStart3;
2051 BYTE* op4 = opStart4;
2054 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2055 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2056 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2057 if (HUF_isError(errorCode)) return errorCode;
2058 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2059 if (HUF_isError(errorCode)) return errorCode;
2060 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2061 if (HUF_isError(errorCode)) return errorCode;
2062 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2063 if (HUF_isError(errorCode)) return errorCode;
2065 /* 16-32 symbols per loop (4-8 symbols per stream) */
2066 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2067 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2069 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2070 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2071 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2072 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2073 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2074 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2075 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2076 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2077 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2078 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2079 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2080 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2081 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2082 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2083 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2084 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2086 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2089 /* check corruption */
2090 if (op1 > opStart2) return ERROR(corruption_detected);
2091 if (op2 > opStart3) return ERROR(corruption_detected);
2092 if (op3 > opStart4) return ERROR(corruption_detected);
2093 /* note : op4 supposed already verified within main loop */
2095 /* finish bitStreams one by one */
2096 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2097 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2098 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2099 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2102 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2103 if (!endSignal) return ERROR(corruption_detected);
2111 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2113 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2114 const BYTE* ip = (const BYTE*) cSrc;
2116 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2117 if (HUF_isError(hSize)) return hSize;
2118 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2122 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2126 /**********************************/
2127 /* Generic decompression selector */
2128 /**********************************/
2130 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2131 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2133 /* single, double, quad */
2134 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2135 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2136 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2137 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2138 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2139 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2140 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2141 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2142 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2143 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2144 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2145 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2146 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2147 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2148 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2149 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2152 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2154 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2156 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2157 /* estimate decompression time */
2159 const U32 D256 = (U32)(dstSize >> 8);
2164 /* validation checks */
2165 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2166 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2167 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2168 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2170 /* decoder timing evaluation */
2171 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2173 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2175 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2177 if (Dtime[1] < Dtime[0]) algoNb = 1;
2179 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2181 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2182 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2183 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2186 zstd - standard compression library
2187 Copyright (C) 2014-2015, Yann Collet.
2189 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2191 Redistribution and use in source and binary forms, with or without
2192 modification, are permitted provided that the following conditions are
2194 * Redistributions of source code must retain the above copyright
2195 notice, this list of conditions and the following disclaimer.
2196 * Redistributions in binary form must reproduce the above
2197 copyright notice, this list of conditions and the following disclaimer
2198 in the documentation and/or other materials provided with the
2200 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2201 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2202 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2203 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2204 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2205 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2206 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2207 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2208 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2209 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2210 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2212 You can contact the author at :
2213 - zstd source repository : https://github.com/Cyan4973/zstd
2214 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2217 /* ***************************************************************
2219 *****************************************************************/
2222 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2223 * Increasing memory usage improves compression ratio
2224 * Reduced memory usage can improve speed, due to cache effect
2226 #define ZSTD_MEMORY_USAGE 17
2230 * Select how default compression functions will allocate memory for their hash table,
2231 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2232 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2234 #ifndef ZSTD_HEAPMODE
2235 # define ZSTD_HEAPMODE 1
2236 #endif /* ZSTD_HEAPMODE */
2240 * decompressor can decode older formats (starting from Zstd 0.1+)
2242 #ifndef ZSTD_LEGACY_SUPPORT
2243 # define ZSTD_LEGACY_SUPPORT 1
2247 /* *******************************************************
2249 *********************************************************/
2250 #include <stdlib.h> /* calloc */
2251 #include <string.h> /* memcpy, memmove */
2252 #include <stdio.h> /* debug : printf */
2255 /* *******************************************************
2256 * Compiler specifics
2257 *********************************************************/
2259 # include <immintrin.h> /* AVX2 intrinsics */
2262 #ifdef _MSC_VER /* Visual Studio */
2263 # include <intrin.h> /* For Visual 2005 */
2264 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2265 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2267 # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
2271 /* *******************************************************
2273 *********************************************************/
2274 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2275 #define HASH_TABLESIZE (1 << HASH_LOG)
2276 #define HASH_MASK (HASH_TABLESIZE - 1)
2278 #define KNUTH 2654435761
2287 #define KB *(1 <<10)
2288 #define MB *(1 <<20)
2289 #define GB *(1U<<30)
2291 #define BLOCKSIZE (128 KB) /* define, for static allocation */
2292 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2293 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2297 #define WORKPLACESIZE (BLOCKSIZE*3)
2302 #define MaxML ((1<<MLbits )-1)
2303 #define MaxLL ((1<<LLbits )-1)
2305 #define LitFSELog 11
2309 #define MAX(a,b) ((a)<(b)?(b):(a))
2310 #define MaxSeq MAX(MaxLL, MaxML)
2312 #define LITERAL_NOENTROPY 63
2313 #define COMMAND_NOENTROPY 7 /* to remove */
2315 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2317 static const size_t ZSTD_blockHeaderSize = 3;
2318 static const size_t ZSTD_frameHeaderSize = 4;
2321 /* *******************************************************
2323 **********************************************************/
2324 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2326 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2328 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2330 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2331 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2333 const BYTE* ip = (const BYTE*)src;
2334 BYTE* op = (BYTE*)dst;
2335 BYTE* const oend = op + length;
2336 do COPY8(op, ip) while (op < oend);
2340 /* **************************************
2342 ****************************************/
2343 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2347 blockType_t blockType;
2349 } blockProperties_t;
2359 BYTE* litLengthStart;
2361 BYTE* matchLengthStart;
2368 /* *************************************
2370 ***************************************/
2372 * tells if a return value is an error code */
2373 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2377 /* *************************************************************
2378 * Decompression section
2379 ***************************************************************/
2380 struct ZSTDv03_Dctx_s
2382 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2383 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2384 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2385 void* previousDstEnd;
2392 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2393 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2396 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2398 const BYTE* const in = (const BYTE* const)src;
2402 if (srcSize < 3) return ERROR(srcSize_wrong);
2405 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2407 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2408 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2410 if (bpPtr->blockType == bt_end) return 0;
2411 if (bpPtr->blockType == bt_rle) return 1;
2415 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2417 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2419 memcpy(dst, src, srcSize);
2425 /** ZSTD_decompressLiterals
2426 @return : nb of bytes read from src, or an error code*/
2427 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2428 const void* src, size_t srcSize)
2430 const BYTE* ip = (const BYTE*)src;
2432 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2433 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2435 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2436 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2438 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2440 *maxDstSizePtr = litSize;
2441 return litCSize + 5;
2445 /** ZSTD_decodeLiteralsBlock
2446 @return : nb of bytes read from src (< srcSize )*/
2447 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2448 const void* src, size_t srcSize)
2450 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2451 const BYTE* const istart = (const BYTE* const)src;
2453 /* any compressed block with literals segment must be at least this size */
2454 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2461 size_t litSize = BLOCKSIZE;
2462 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2463 dctx->litPtr = dctx->litBuffer;
2464 dctx->litSize = litSize;
2465 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2466 return readSize; /* works if it's an error too */
2470 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2471 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2473 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2474 if (litSize > srcSize-3) return ERROR(corruption_detected);
2475 memcpy(dctx->litBuffer, istart, litSize);
2476 dctx->litPtr = dctx->litBuffer;
2477 dctx->litSize = litSize;
2478 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2481 /* direct reference into compressed stream */
2482 dctx->litPtr = istart+3;
2483 dctx->litSize = litSize;
2488 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2489 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2490 memset(dctx->litBuffer, istart[3], litSize + 8);
2491 dctx->litPtr = dctx->litBuffer;
2492 dctx->litSize = litSize;
2499 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2500 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2501 const void* src, size_t srcSize)
2503 const BYTE* const istart = (const BYTE* const)src;
2504 const BYTE* ip = istart;
2505 const BYTE* const iend = istart + srcSize;
2506 U32 LLtype, Offtype, MLtype;
2507 U32 LLlog, Offlog, MLlog;
2511 if (srcSize < 5) return ERROR(srcSize_wrong);
2514 *nbSeq = MEM_readLE16(ip); ip+=2;
2516 Offtype = (*ip >> 4) & 3;
2517 MLtype = (*ip >> 2) & 3;
2520 dumpsLength = ip[2];
2521 dumpsLength += ip[1] << 8;
2526 dumpsLength = ip[1];
2527 dumpsLength += (ip[0] & 1) << 8;
2532 *dumpsLengthPtr = dumpsLength;
2535 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2539 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2547 FSE_buildDTable_rle(DTableLL, *ip++); break;
2550 FSE_buildDTable_raw(DTableLL, LLbits); break;
2553 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2554 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2555 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2557 FSE_buildDTable(DTableLL, norm, max, LLlog);
2564 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2565 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2569 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2572 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2573 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2574 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2576 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2583 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2584 FSE_buildDTable_rle(DTableML, *ip++); break;
2587 FSE_buildDTable_raw(DTableML, MLbits); break;
2590 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2591 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2592 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2594 FSE_buildDTable(DTableML, norm, max, MLlog);
2608 BIT_DStream_t DStream;
2609 FSE_DState_t stateLL;
2610 FSE_DState_t stateOffb;
2611 FSE_DState_t stateML;
2614 const BYTE* dumpsEnd;
2618 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2624 const BYTE* dumps = seqState->dumps;
2625 const BYTE* const de = seqState->dumpsEnd;
2627 /* Literal length */
2628 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2629 prevOffset = litLength ? seq->offset : seqState->prevOffset;
2630 seqState->prevOffset = seq->offset;
2631 if (litLength == MaxLL)
2633 const U32 add = dumps<de ? *dumps++ : 0;
2634 if (add < 255) litLength += add;
2635 else if (dumps + 3 <= de)
2637 litLength = MEM_readLE24(dumps);
2640 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2645 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
2646 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2647 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2648 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2649 U32 offsetCode, nbBits;
2650 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
2651 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2652 nbBits = offsetCode - 1;
2653 if (offsetCode==0) nbBits = 0; /* cmove */
2654 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2655 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2656 if (offsetCode==0) offset = prevOffset; /* cmove */
2660 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2661 if (matchLength == MaxML)
2663 const U32 add = dumps<de ? *dumps++ : 0;
2664 if (add < 255) matchLength += add;
2665 else if (dumps + 3 <= de)
2667 matchLength = MEM_readLE24(dumps);
2670 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2672 matchLength += MINMATCH;
2675 seq->litLength = litLength;
2676 seq->offset = offset;
2677 seq->matchLength = matchLength;
2678 seqState->dumps = dumps;
2682 static size_t ZSTD_execSequence(BYTE* op,
2684 const BYTE** litPtr, const BYTE* const litLimit,
2685 BYTE* const base, BYTE* const oend)
2687 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
2688 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */
2689 const BYTE* const ostart = op;
2690 BYTE* const oLitEnd = op + sequence.litLength;
2691 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
2692 BYTE* const oend_8 = oend-8;
2693 const BYTE* const litEnd = *litPtr + sequence.litLength;
2696 size_t const seqLength = sequence.litLength + sequence.matchLength;
2698 if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
2699 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
2700 /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
2701 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
2702 if (sequence.offset > (U32)(oLitEnd - base)) return ERROR(corruption_detected);
2704 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
2705 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
2708 ZSTD_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2710 *litPtr = litEnd; /* update for next sequence */
2713 { const BYTE* match = op - sequence.offset;
2716 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
2717 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
2718 if (match < base) return ERROR(corruption_detected);
2720 /* close range match, overlap */
2721 if (sequence.offset < 8)
2723 const int dec64 = dec64table[sequence.offset];
2728 match += dec32table[sequence.offset];
2729 ZSTD_copy4(op+4, match);
2734 ZSTD_copy8(op, match);
2736 op += 8; match += 8;
2738 if (oMatchEnd > oend-(16-MINMATCH))
2742 ZSTD_wildcopy(op, match, oend_8 - op);
2743 match += oend_8 - op;
2746 while (op < oMatchEnd) *op++ = *match++;
2750 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
2754 return oMatchEnd - ostart;
2757 static size_t ZSTD_decompressSequences(
2759 void* dst, size_t maxDstSize,
2760 const void* seqStart, size_t seqSize)
2762 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2763 const BYTE* ip = (const BYTE*)seqStart;
2764 const BYTE* const iend = ip + seqSize;
2765 BYTE* const ostart = (BYTE* const)dst;
2767 BYTE* const oend = ostart + maxDstSize;
2768 size_t errorCode, dumpsLength;
2769 const BYTE* litPtr = dctx->litPtr;
2770 const BYTE* const litEnd = litPtr + dctx->litSize;
2773 U32* DTableLL = dctx->LLTable;
2774 U32* DTableML = dctx->MLTable;
2775 U32* DTableOffb = dctx->OffTable;
2776 BYTE* const base = (BYTE*) (dctx->base);
2778 /* Build Decoding Tables */
2779 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2780 DTableLL, DTableML, DTableOffb,
2782 if (ZSTD_isError(errorCode)) return errorCode;
2785 /* Regen sequences */
2788 seqState_t seqState;
2790 memset(&sequence, 0, sizeof(sequence));
2791 seqState.dumps = dumps;
2792 seqState.dumpsEnd = dumps + dumpsLength;
2793 seqState.prevOffset = sequence.offset = 4;
2794 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2795 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2796 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2797 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2798 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2800 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
2804 ZSTD_decodeSequence(&sequence, &seqState);
2805 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
2806 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2810 /* check if reached exact end */
2811 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
2812 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
2814 /* last literal segment */
2816 size_t lastLLSize = litEnd - litPtr;
2817 if (litPtr > litEnd) return ERROR(corruption_detected);
2818 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2819 if (lastLLSize > 0) {
2820 if (op != litPtr) memmove(op, litPtr, lastLLSize);
2830 static size_t ZSTD_decompressBlock(
2832 void* dst, size_t maxDstSize,
2833 const void* src, size_t srcSize)
2835 /* blockType == blockCompressed */
2836 const BYTE* ip = (const BYTE*)src;
2838 /* Decode literals sub-block */
2839 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
2840 if (ZSTD_isError(litCSize)) return litCSize;
2842 srcSize -= litCSize;
2844 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
2848 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2850 const BYTE* ip = (const BYTE*)src;
2851 const BYTE* iend = ip + srcSize;
2852 BYTE* const ostart = (BYTE* const)dst;
2854 BYTE* const oend = ostart + maxDstSize;
2855 size_t remainingSize = srcSize;
2857 blockProperties_t blockProperties;
2860 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2861 magicNumber = MEM_readLE32(src);
2862 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2863 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2865 /* Loop on each block */
2868 size_t decodedSize=0;
2869 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
2870 if (ZSTD_isError(cBlockSize)) return cBlockSize;
2872 ip += ZSTD_blockHeaderSize;
2873 remainingSize -= ZSTD_blockHeaderSize;
2874 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2876 switch(blockProperties.blockType)
2879 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
2882 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
2885 return ERROR(GENERIC); /* not yet supported */
2889 if (remainingSize) return ERROR(srcSize_wrong);
2892 return ERROR(GENERIC); /* impossible */
2894 if (cBlockSize == 0) break; /* bt_end */
2896 if (ZSTD_isError(decodedSize)) return decodedSize;
2899 remainingSize -= cBlockSize;
2905 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2909 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
2912 /* ZSTD_errorFrameSizeInfoLegacy() :
2913 assumes `cSize` and `dBound` are _not_ NULL */
2914 MEM_STATIC void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
2917 *dBound = ZSTD_CONTENTSIZE_ERROR;
2920 void ZSTDv03_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
2922 const BYTE* ip = (const BYTE*)src;
2923 size_t remainingSize = srcSize;
2924 size_t nbBlocks = 0;
2926 blockProperties_t blockProperties;
2929 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
2930 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2933 magicNumber = MEM_readLE32(src);
2934 if (magicNumber != ZSTD_magicNumber) {
2935 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
2938 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2940 /* Loop on each block */
2943 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
2944 if (ZSTD_isError(cBlockSize)) {
2945 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
2949 ip += ZSTD_blockHeaderSize;
2950 remainingSize -= ZSTD_blockHeaderSize;
2951 if (cBlockSize > remainingSize) {
2952 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2956 if (cBlockSize == 0) break; /* bt_end */
2959 remainingSize -= cBlockSize;
2963 *cSize = ip - (const BYTE*)src;
2964 *dBound = nbBlocks * BLOCKSIZE;
2968 /*******************************
2969 * Streaming Decompression API
2970 *******************************/
2972 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2974 dctx->expected = ZSTD_frameHeaderSize;
2976 dctx->previousDstEnd = NULL;
2981 static ZSTD_DCtx* ZSTD_createDCtx(void)
2983 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2984 if (dctx==NULL) return NULL;
2985 ZSTD_resetDCtx(dctx);
2989 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
2995 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
2997 return dctx->expected;
3000 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3003 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3004 if (dst != ctx->previousDstEnd) /* not contiguous */
3007 /* Decompress : frame header */
3008 if (ctx->phase == 0)
3010 /* Check frame magic header */
3011 U32 magicNumber = MEM_readLE32(src);
3012 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3014 ctx->expected = ZSTD_blockHeaderSize;
3018 /* Decompress : block header */
3019 if (ctx->phase == 1)
3021 blockProperties_t bp;
3022 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3023 if (ZSTD_isError(blockSize)) return blockSize;
3024 if (bp.blockType == bt_end)
3031 ctx->expected = blockSize;
3032 ctx->bType = bp.blockType;
3039 /* Decompress : block content */
3045 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3048 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3051 return ERROR(GENERIC); /* not yet handled */
3053 case bt_end : /* should never happen (filtered at phase 1) */
3057 return ERROR(GENERIC);
3060 ctx->expected = ZSTD_blockHeaderSize;
3061 if (ZSTD_isError(rSize)) return rSize;
3062 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3071 unsigned ZSTDv03_isError(size_t code)
3073 return ZSTD_isError(code);
3076 size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3077 const void* src, size_t compressedSize)
3079 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3082 ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3084 return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3087 size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3089 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3092 size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3094 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3097 size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3099 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3102 size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3104 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);