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/error_private.h"
17 /******************************************
19 ******************************************/
20 #if defined(_MSC_VER) /* Visual Studio */
21 # include <stdlib.h> /* _byteswap_ulong */
22 # include <intrin.h> /* _byteswap_* */
27 /* ******************************************************************
29 low-level memory access routines
30 Copyright (C) 2013-2015, Yann Collet.
32 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
34 Redistribution and use in source and binary forms, with or without
35 modification, are permitted provided that the following conditions are
38 * Redistributions of source code must retain the above copyright
39 notice, this list of conditions and the following disclaimer.
40 * Redistributions in binary form must reproduce the above
41 copyright notice, this list of conditions and the following disclaimer
42 in the documentation and/or other materials provided with the
45 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
46 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
47 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
48 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
49 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
50 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
51 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
52 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
53 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
54 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
55 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
57 You can contact the author at :
58 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
59 - Public forum : https://groups.google.com/forum/#!forum/lz4c
60 ****************************************************************** */
64 #if defined (__cplusplus)
68 /******************************************
70 ******************************************/
71 #include <stddef.h> /* size_t, ptrdiff_t */
72 #include <string.h> /* memcpy */
75 /******************************************
77 ******************************************/
79 # define MEM_STATIC static __attribute__((unused))
80 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
81 # define MEM_STATIC static inline
82 #elif defined(_MSC_VER)
83 # define MEM_STATIC static __inline
85 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
89 /****************************************************************
91 *****************************************************************/
92 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
94 # include <inttypes.h>
96 # include <stdint.h> /* intptr_t */
101 typedef uint32_t U32;
103 typedef uint64_t U64;
106 typedef unsigned char BYTE;
107 typedef unsigned short U16;
108 typedef signed short S16;
109 typedef unsigned int U32;
110 typedef signed int S32;
111 typedef unsigned long long U64;
112 typedef signed long long S64;
116 /****************************************************************
118 *****************************************************************/
120 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
121 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
123 MEM_STATIC unsigned MEM_isLittleEndian(void)
125 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
129 MEM_STATIC U16 MEM_read16(const void* memPtr)
131 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
134 MEM_STATIC U32 MEM_read32(const void* memPtr)
136 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
139 MEM_STATIC U64 MEM_read64(const void* memPtr)
141 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
144 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
146 memcpy(memPtr, &value, sizeof(value));
149 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
151 if (MEM_isLittleEndian())
152 return MEM_read16(memPtr);
155 const BYTE* p = (const BYTE*)memPtr;
156 return (U16)(p[0] + (p[1]<<8));
160 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
162 if (MEM_isLittleEndian())
164 MEM_write16(memPtr, val);
168 BYTE* p = (BYTE*)memPtr;
170 p[1] = (BYTE)(val>>8);
174 MEM_STATIC U32 MEM_readLE24(const void* memPtr)
176 return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
179 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
181 if (MEM_isLittleEndian())
182 return MEM_read32(memPtr);
185 const BYTE* p = (const BYTE*)memPtr;
186 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
190 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
192 if (MEM_isLittleEndian())
193 return MEM_read64(memPtr);
196 const BYTE* p = (const BYTE*)memPtr;
197 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
198 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
203 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
206 return (size_t)MEM_readLE32(memPtr);
208 return (size_t)MEM_readLE64(memPtr);
212 #if defined (__cplusplus)
216 #endif /* MEM_H_MODULE */
219 /* ******************************************************************
221 Part of NewGen Entropy library
222 header file (to include)
223 Copyright (C) 2013-2015, Yann Collet.
225 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
227 Redistribution and use in source and binary forms, with or without
228 modification, are permitted provided that the following conditions are
231 * Redistributions of source code must retain the above copyright
232 notice, this list of conditions and the following disclaimer.
233 * Redistributions in binary form must reproduce the above
234 copyright notice, this list of conditions and the following disclaimer
235 in the documentation and/or other materials provided with the
238 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
239 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
240 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
241 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
242 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
243 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
244 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
245 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
246 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
247 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
248 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
250 You can contact the author at :
251 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
252 - Public forum : https://groups.google.com/forum/#!forum/lz4c
253 ****************************************************************** */
254 #ifndef BITSTREAM_H_MODULE
255 #define BITSTREAM_H_MODULE
257 #if defined (__cplusplus)
263 * This API consists of small unitary functions, which highly benefit from being inlined.
264 * Since link-time-optimization is not available for all compilers,
265 * these functions are defined into a .h to be included.
269 /**********************************************
270 * bitStream decompression API (read backward)
271 **********************************************/
275 unsigned bitsConsumed;
280 typedef enum { BIT_DStream_unfinished = 0,
281 BIT_DStream_endOfBuffer = 1,
282 BIT_DStream_completed = 2,
283 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
284 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
286 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
287 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
288 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
289 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
293 /******************************************
295 ******************************************/
296 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
297 /* faster, but works only if nbBits >= 1 */
301 /****************************************************************
303 ****************************************************************/
304 MEM_STATIC unsigned BIT_highbit32 (U32 val)
306 # if defined(_MSC_VER) /* Visual */
308 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
309 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
310 return __builtin_clz (val) ^ 31;
311 # else /* Software version */
312 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 };
320 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
327 /**********************************************************
329 **********************************************************/
332 * Initialize a BIT_DStream_t.
333 * @bitD : a pointer to an already allocated BIT_DStream_t structure
334 * @srcBuffer must point at the beginning of a bitStream
335 * @srcSize must be the exact size of the bitStream
336 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
338 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
340 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
342 if (srcSize >= sizeof(size_t)) /* normal case */
345 bitD->start = (const char*)srcBuffer;
346 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
347 bitD->bitContainer = MEM_readLEST(bitD->ptr);
348 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
349 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
350 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
355 bitD->start = (const char*)srcBuffer;
356 bitD->ptr = bitD->start;
357 bitD->bitContainer = *(const BYTE*)(bitD->start);
360 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
362 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
364 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
366 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
368 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
370 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
374 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
375 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
376 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
377 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
382 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
384 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
385 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
388 /*! BIT_lookBitsFast :
389 * unsafe version; only works if nbBits >= 1 */
390 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
392 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
393 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
396 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
398 bitD->bitsConsumed += nbBits;
401 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
403 size_t value = BIT_lookBits(bitD, nbBits);
404 BIT_skipBits(bitD, nbBits);
408 /*!BIT_readBitsFast :
409 * unsafe version; only works if nbBits >= 1 */
410 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
412 size_t value = BIT_lookBitsFast(bitD, nbBits);
413 BIT_skipBits(bitD, nbBits);
417 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
419 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
420 return BIT_DStream_overflow;
422 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
424 bitD->ptr -= bitD->bitsConsumed >> 3;
425 bitD->bitsConsumed &= 7;
426 bitD->bitContainer = MEM_readLEST(bitD->ptr);
427 return BIT_DStream_unfinished;
429 if (bitD->ptr == bitD->start)
431 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
432 return BIT_DStream_completed;
435 U32 nbBytes = bitD->bitsConsumed >> 3;
436 BIT_DStream_status result = BIT_DStream_unfinished;
437 if (bitD->ptr - nbBytes < bitD->start)
439 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
440 result = BIT_DStream_endOfBuffer;
442 bitD->ptr -= nbBytes;
443 bitD->bitsConsumed -= nbBytes*8;
444 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
450 * @return Tells if DStream has reached its exact end
452 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
454 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
457 #if defined (__cplusplus)
461 #endif /* BITSTREAM_H_MODULE */
462 /* ******************************************************************
463 Error codes and messages
464 Copyright (C) 2013-2015, Yann Collet
466 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
468 Redistribution and use in source and binary forms, with or without
469 modification, are permitted provided that the following conditions are
472 * Redistributions of source code must retain the above copyright
473 notice, this list of conditions and the following disclaimer.
474 * Redistributions in binary form must reproduce the above
475 copyright notice, this list of conditions and the following disclaimer
476 in the documentation and/or other materials provided with the
479 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
480 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
481 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
482 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
483 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
484 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
485 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
486 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
487 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
488 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
489 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
491 You can contact the author at :
492 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
493 - Public forum : https://groups.google.com/forum/#!forum/lz4c
494 ****************************************************************** */
495 #ifndef ERROR_H_MODULE
496 #define ERROR_H_MODULE
498 #if defined (__cplusplus)
503 /******************************************
505 ******************************************/
506 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
507 # define ERR_STATIC static inline
508 #elif defined(_MSC_VER)
509 # define ERR_STATIC static __inline
510 #elif defined(__GNUC__)
511 # define ERR_STATIC static __attribute__((unused))
513 # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
517 /******************************************
519 ******************************************/
520 #define PREFIX(name) ZSTD_error_##name
522 #define ERROR(name) (size_t)-PREFIX(name)
524 #define ERROR_LIST(ITEM) \
525 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
526 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
527 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
528 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
529 ITEM(PREFIX(maxCode))
531 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
532 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
534 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
535 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
536 static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
538 ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
540 ERR_STATIC const char* ERR_getErrorName(size_t code)
542 static const char* codeError = "Unspecified error code";
543 if (ERR_isError(code)) return ERR_strings[-(int)(code)];
548 #if defined (__cplusplus)
552 #endif /* ERROR_H_MODULE */
554 Constructor and Destructor of type FSE_CTable
555 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
556 typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
557 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
560 /* ******************************************************************
561 FSE : Finite State Entropy coder
562 header file for static linking (only)
563 Copyright (C) 2013-2015, Yann Collet
565 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
567 Redistribution and use in source and binary forms, with or without
568 modification, are permitted provided that the following conditions are
571 * Redistributions of source code must retain the above copyright
572 notice, this list of conditions and the following disclaimer.
573 * Redistributions in binary form must reproduce the above
574 copyright notice, this list of conditions and the following disclaimer
575 in the documentation and/or other materials provided with the
578 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
579 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
580 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
581 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
582 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
583 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
584 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
585 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
586 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
587 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
588 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
590 You can contact the author at :
591 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
592 - Public forum : https://groups.google.com/forum/#!forum/lz4c
593 ****************************************************************** */
594 #if defined (__cplusplus)
599 /******************************************
601 ******************************************/
602 /* FSE buffer bounds */
603 #define FSE_NCOUNTBOUND 512
604 #define FSE_BLOCKBOUND(size) (size + (size>>7))
605 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
607 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
608 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
609 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
612 /******************************************
614 ******************************************/
615 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
616 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
618 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
619 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
622 /******************************************
623 * FSE symbol decompression API
624 ******************************************/
628 const void* table; /* precise table may vary, depending on U16 */
632 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
634 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
636 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
639 /******************************************
641 ******************************************/
642 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
643 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
646 /******************************************
647 * Implementation of inline functions
648 ******************************************/
655 } FSE_DTableHeader; /* sizeof U32 */
659 unsigned short newState;
660 unsigned char symbol;
661 unsigned char nbBits;
662 } FSE_decode_t; /* size == U32 */
664 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
666 FSE_DTableHeader DTableH;
667 memcpy(&DTableH, dt, sizeof(DTableH));
668 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
669 BIT_reloadDStream(bitD);
670 DStatePtr->table = dt + 1;
673 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
675 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
676 const U32 nbBits = DInfo.nbBits;
677 BYTE symbol = DInfo.symbol;
678 size_t lowBits = BIT_readBits(bitD, nbBits);
680 DStatePtr->state = DInfo.newState + lowBits;
684 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
686 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
687 const U32 nbBits = DInfo.nbBits;
688 BYTE symbol = DInfo.symbol;
689 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
691 DStatePtr->state = DInfo.newState + lowBits;
695 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
697 return DStatePtr->state == 0;
701 #if defined (__cplusplus)
704 /* ******************************************************************
705 Huff0 : Huffman coder, part of New Generation Entropy library
706 header file for static linking (only)
707 Copyright (C) 2013-2015, Yann Collet
709 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
711 Redistribution and use in source and binary forms, with or without
712 modification, are permitted provided that the following conditions are
715 * Redistributions of source code must retain the above copyright
716 notice, this list of conditions and the following disclaimer.
717 * Redistributions in binary form must reproduce the above
718 copyright notice, this list of conditions and the following disclaimer
719 in the documentation and/or other materials provided with the
722 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
723 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
724 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
725 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
726 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
727 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
728 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
729 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
730 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
731 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
732 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
734 You can contact the author at :
735 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
736 - Public forum : https://groups.google.com/forum/#!forum/lz4c
737 ****************************************************************** */
739 #if defined (__cplusplus)
743 /******************************************
744 * Static allocation macros
745 ******************************************/
746 /* Huff0 buffer bounds */
747 #define HUF_CTABLEBOUND 129
748 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
749 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
751 /* static allocation of Huff0's DTable */
752 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
753 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
754 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
755 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
756 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
757 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
758 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
761 /******************************************
763 ******************************************/
764 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
765 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
768 #if defined (__cplusplus)
773 zstd - standard compression library
775 Copyright (C) 2014-2015, Yann Collet.
777 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
779 Redistribution and use in source and binary forms, with or without
780 modification, are permitted provided that the following conditions are
782 * Redistributions of source code must retain the above copyright
783 notice, this list of conditions and the following disclaimer.
784 * Redistributions in binary form must reproduce the above
785 copyright notice, this list of conditions and the following disclaimer
786 in the documentation and/or other materials provided with the
788 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
789 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
790 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
791 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
792 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
793 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
794 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
795 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
796 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
797 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
798 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
800 You can contact the author at :
801 - zstd source repository : https://github.com/Cyan4973/zstd
802 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
805 #if defined (__cplusplus)
809 /* *************************************
811 ***************************************/
812 #include <stddef.h> /* size_t */
815 /* *************************************
817 ***************************************/
818 #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
819 #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
820 #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
821 #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
824 /* *************************************
826 ***************************************/
827 typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */
829 #if defined (__cplusplus)
833 zstd - standard compression library
834 Header File for static linking only
835 Copyright (C) 2014-2015, Yann Collet.
837 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
839 Redistribution and use in source and binary forms, with or without
840 modification, are permitted provided that the following conditions are
842 * Redistributions of source code must retain the above copyright
843 notice, this list of conditions and the following disclaimer.
844 * Redistributions in binary form must reproduce the above
845 copyright notice, this list of conditions and the following disclaimer
846 in the documentation and/or other materials provided with the
848 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
849 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
850 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
851 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
852 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
853 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
854 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
855 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
856 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
857 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
858 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
860 You can contact the author at :
861 - zstd source repository : https://github.com/Cyan4973/zstd
862 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
865 /* The objects defined into this file should be considered experimental.
866 * They are not labelled stable, as their prototype may change in the future.
867 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
870 #if defined (__cplusplus)
874 /* *************************************
875 * Streaming functions
876 ***************************************/
878 typedef struct ZSTD_DCtx_s ZSTD_DCtx;
881 Use above functions alternatively.
882 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
883 ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
884 Result is the number of bytes regenerated within 'dst'.
885 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
888 /* *************************************
889 * Prefix - version detection
890 ***************************************/
891 #define ZSTD_magicNumber 0xFD2FB523 /* v0.3 */
894 #if defined (__cplusplus)
897 /* ******************************************************************
898 FSE : Finite State Entropy coder
899 Copyright (C) 2013-2015, Yann Collet.
901 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
903 Redistribution and use in source and binary forms, with or without
904 modification, are permitted provided that the following conditions are
907 * Redistributions of source code must retain the above copyright
908 notice, this list of conditions and the following disclaimer.
909 * Redistributions in binary form must reproduce the above
910 copyright notice, this list of conditions and the following disclaimer
911 in the documentation and/or other materials provided with the
914 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
915 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
916 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
917 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
918 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
919 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
920 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
921 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
922 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
923 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
924 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
926 You can contact the author at :
927 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
928 - Public forum : https://groups.google.com/forum/#!forum/lz4c
929 ****************************************************************** */
931 #ifndef FSE_COMMONDEFS_ONLY
933 /****************************************************************
935 ****************************************************************/
937 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
938 * Increasing memory usage improves compression ratio
939 * Reduced memory usage can improve speed, due to cache effect
940 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
941 #define FSE_MAX_MEMORY_USAGE 14
942 #define FSE_DEFAULT_MEMORY_USAGE 13
944 /* FSE_MAX_SYMBOL_VALUE :
945 * Maximum symbol value authorized.
946 * Required for proper stack allocation */
947 #define FSE_MAX_SYMBOL_VALUE 255
950 /****************************************************************
951 * template functions type & suffix
952 ****************************************************************/
953 #define FSE_FUNCTION_TYPE BYTE
954 #define FSE_FUNCTION_EXTENSION
957 /****************************************************************
959 ****************************************************************/
960 #endif /* !FSE_COMMONDEFS_ONLY */
963 /****************************************************************
965 ****************************************************************/
966 #ifdef _MSC_VER /* Visual Studio */
967 # define FORCE_INLINE static __forceinline
968 # include <intrin.h> /* For Visual 2005 */
969 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
970 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
972 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
974 # define FORCE_INLINE static inline __attribute__((always_inline))
976 # define FORCE_INLINE static inline
979 # define FORCE_INLINE static
980 # endif /* __STDC_VERSION__ */
984 /****************************************************************
986 ****************************************************************/
987 #include <stdlib.h> /* malloc, free, qsort */
988 #include <string.h> /* memcpy, memset */
989 #include <stdio.h> /* printf (debug) */
991 /****************************************************************
993 *****************************************************************/
994 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
995 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
996 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
997 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
998 #define FSE_MIN_TABLELOG 5
1000 #define FSE_TABLELOG_ABSOLUTE_MAX 15
1001 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1002 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1006 /****************************************************************
1008 ****************************************************************/
1009 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1012 /****************************************************************
1014 ****************************************************************/
1015 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1018 /****************************************************************
1020 ****************************************************************/
1022 designed to be included
1023 for type-specific functions (template emulation in C)
1024 Objective is to write these functions only once, for improved maintenance
1028 #ifndef FSE_FUNCTION_EXTENSION
1029 # error "FSE_FUNCTION_EXTENSION must be defined"
1031 #ifndef FSE_FUNCTION_TYPE
1032 # error "FSE_FUNCTION_TYPE must be defined"
1035 /* Function names */
1036 #define FSE_CAT(X,Y) X##Y
1037 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1038 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1041 /* Function templates */
1043 #define FSE_DECODE_TYPE FSE_decode_t
1045 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1047 static size_t FSE_buildDTable
1048 (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1051 FSE_DTableHeader DTableH;
1052 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1053 const U32 tableSize = 1 << tableLog;
1054 const U32 tableMask = tableSize-1;
1055 const U32 step = FSE_tableStep(tableSize);
1056 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1058 U32 highThreshold = tableSize-1;
1059 const S16 largeLimit= (S16)(1 << (tableLog-1));
1064 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1065 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1067 /* Init, lay down lowprob symbols */
1068 DTableH.tableLog = (U16)tableLog;
1069 for (s=0; s<=maxSymbolValue; s++)
1071 if (normalizedCounter[s]==-1)
1073 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1078 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1079 symbolNext[s] = normalizedCounter[s];
1083 /* Spread symbols */
1084 for (s=0; s<=maxSymbolValue; s++)
1087 for (i=0; i<normalizedCounter[s]; i++)
1089 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1090 position = (position + step) & tableMask;
1091 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1095 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1097 /* Build Decoding table */
1100 for (i=0; i<tableSize; i++)
1102 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1103 U16 nextState = symbolNext[symbol]++;
1104 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1105 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1109 DTableH.fastMode = (U16)noLarge;
1110 memcpy(dt, &DTableH, sizeof(DTableH));
1115 #ifndef FSE_COMMONDEFS_ONLY
1116 /******************************************
1117 * FSE helper functions
1118 ******************************************/
1119 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1122 /****************************************************************
1123 * FSE NCount encoding-decoding
1124 ****************************************************************/
1125 static short FSE_abs(short a)
1127 return a<0 ? -a : a;
1130 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1131 const void* headerBuffer, size_t hbSize)
1133 const BYTE* const istart = (const BYTE*) headerBuffer;
1134 const BYTE* const iend = istart + hbSize;
1135 const BYTE* ip = istart;
1141 unsigned charnum = 0;
1144 if (hbSize < 4) return ERROR(srcSize_wrong);
1145 bitStream = MEM_readLE32(ip);
1146 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1147 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1150 *tableLogPtr = nbBits;
1151 remaining = (1<<nbBits)+1;
1152 threshold = 1<<nbBits;
1155 while ((remaining>1) && (charnum<=*maxSVPtr))
1159 unsigned n0 = charnum;
1160 while ((bitStream & 0xFFFF) == 0xFFFF)
1166 bitStream = MEM_readLE32(ip) >> bitCount;
1174 while ((bitStream & 3) == 3)
1180 n0 += bitStream & 3;
1182 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1183 while (charnum < n0) normalizedCounter[charnum++] = 0;
1184 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1188 bitStream = MEM_readLE32(ip) >> bitCount;
1194 const short max = (short)((2*threshold-1)-remaining);
1197 if ((bitStream & (threshold-1)) < (U32)max)
1199 count = (short)(bitStream & (threshold-1));
1200 bitCount += nbBits-1;
1204 count = (short)(bitStream & (2*threshold-1));
1205 if (count >= threshold) count -= max;
1209 count--; /* extra accuracy */
1210 remaining -= FSE_abs(count);
1211 normalizedCounter[charnum++] = count;
1213 while (remaining < threshold)
1220 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1227 bitCount -= (int)(8 * (iend - 4 - ip));
1230 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1234 if (remaining != 1) return ERROR(GENERIC);
1235 *maxSVPtr = charnum-1;
1237 ip += (bitCount+7)>>3;
1238 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1243 /*********************************************************
1244 * Decompression (Byte symbols)
1245 *********************************************************/
1246 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1249 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1250 FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1;
1252 DTableH->tableLog = 0;
1253 DTableH->fastMode = 0;
1256 cell->symbol = symbolValue;
1263 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1266 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1267 FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1;
1268 const unsigned tableSize = 1 << nbBits;
1269 const unsigned tableMask = tableSize - 1;
1270 const unsigned maxSymbolValue = tableMask;
1274 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1276 /* Build Decoding Table */
1277 DTableH->tableLog = (U16)nbBits;
1278 DTableH->fastMode = 1;
1279 for (s=0; s<=maxSymbolValue; s++)
1281 dinfo[s].newState = 0;
1282 dinfo[s].symbol = (BYTE)s;
1283 dinfo[s].nbBits = (BYTE)nbBits;
1289 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1290 void* dst, size_t maxDstSize,
1291 const void* cSrc, size_t cSrcSize,
1292 const FSE_DTable* dt, const unsigned fast)
1294 BYTE* const ostart = (BYTE*) dst;
1296 BYTE* const omax = op + maxDstSize;
1297 BYTE* const olimit = omax-3;
1300 FSE_DState_t state1;
1301 FSE_DState_t state2;
1305 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1306 if (FSE_isError(errorCode)) return errorCode;
1308 FSE_initDState(&state1, &bitD, dt);
1309 FSE_initDState(&state2, &bitD, dt);
1311 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1313 /* 4 symbols per loop */
1314 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1316 op[0] = FSE_GETSYMBOL(&state1);
1318 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1319 BIT_reloadDStream(&bitD);
1321 op[1] = FSE_GETSYMBOL(&state2);
1323 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1324 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1326 op[2] = FSE_GETSYMBOL(&state1);
1328 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1329 BIT_reloadDStream(&bitD);
1331 op[3] = FSE_GETSYMBOL(&state2);
1335 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1338 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1341 *op++ = FSE_GETSYMBOL(&state1);
1343 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1346 *op++ = FSE_GETSYMBOL(&state2);
1350 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1353 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1355 return ERROR(corruption_detected);
1359 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1360 const void* cSrc, size_t cSrcSize,
1361 const FSE_DTable* dt)
1363 FSE_DTableHeader DTableH;
1364 memcpy(&DTableH, dt, sizeof(DTableH));
1366 /* select fast mode (static) */
1367 if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1368 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1372 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1374 const BYTE* const istart = (const BYTE*)cSrc;
1375 const BYTE* ip = istart;
1376 short counting[FSE_MAX_SYMBOL_VALUE+1];
1377 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1379 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1382 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1384 /* normal FSE decoding mode */
1385 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1386 if (FSE_isError(errorCode)) return errorCode;
1387 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1389 cSrcSize -= errorCode;
1391 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1392 if (FSE_isError(errorCode)) return errorCode;
1394 /* always return, even if it is an error code */
1395 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1400 #endif /* FSE_COMMONDEFS_ONLY */
1401 /* ******************************************************************
1402 Huff0 : Huffman coder, part of New Generation Entropy library
1403 Copyright (C) 2013-2015, Yann Collet.
1405 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1407 Redistribution and use in source and binary forms, with or without
1408 modification, are permitted provided that the following conditions are
1411 * Redistributions of source code must retain the above copyright
1412 notice, this list of conditions and the following disclaimer.
1413 * Redistributions in binary form must reproduce the above
1414 copyright notice, this list of conditions and the following disclaimer
1415 in the documentation and/or other materials provided with the
1418 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1419 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1420 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1421 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1422 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1423 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1424 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1425 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1426 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1427 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1428 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1430 You can contact the author at :
1431 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1432 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1433 ****************************************************************** */
1435 /****************************************************************
1436 * Compiler specifics
1437 ****************************************************************/
1438 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1439 /* inline is defined */
1440 #elif defined(_MSC_VER)
1441 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1442 # define inline __inline
1444 # define inline /* disable inline */
1448 /****************************************************************
1450 ****************************************************************/
1451 #include <stdlib.h> /* malloc, free, qsort */
1452 #include <string.h> /* memcpy, memset */
1453 #include <stdio.h> /* printf (debug) */
1455 /****************************************************************
1457 ****************************************************************/
1458 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1461 /******************************************
1463 ******************************************/
1464 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1466 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1467 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1468 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1469 #define HUF_MAX_SYMBOL_VALUE 255
1470 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1471 # error "HUF_MAX_TABLELOG is too large !"
1476 /*********************************************************
1477 * Huff0 : Huffman block decompression
1478 *********************************************************/
1479 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1481 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1483 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1486 Read compact Huffman tree, saved by HUF_writeCTable
1487 @huffWeight : destination buffer
1488 @return : size read from `src`
1490 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1491 U32* nbSymbolsPtr, U32* tableLogPtr,
1492 const void* src, size_t srcSize)
1496 const BYTE* ip = (const BYTE*) src;
1501 if (!srcSize) return ERROR(srcSize_wrong);
1503 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1505 if (iSize >= 128) /* special header */
1507 if (iSize >= (242)) /* RLE */
1509 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1510 oSize = l[iSize-242];
1511 memset(huffWeight, 1, hwSize);
1514 else /* Incompressible */
1516 oSize = iSize - 127;
1517 iSize = ((oSize+1)/2);
1518 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1519 if (oSize >= hwSize) return ERROR(corruption_detected);
1521 for (n=0; n<oSize; n+=2)
1523 huffWeight[n] = ip[n/2] >> 4;
1524 huffWeight[n+1] = ip[n/2] & 15;
1528 else /* header compressed with FSE (normal case) */
1530 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1531 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1532 if (FSE_isError(oSize)) return oSize;
1535 /* collect weight stats */
1536 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1538 for (n=0; n<oSize; n++)
1540 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1541 rankStats[huffWeight[n]]++;
1542 weightTotal += (1 << huffWeight[n]) >> 1;
1544 if (weightTotal == 0) return ERROR(corruption_detected);
1546 /* get last non-null symbol weight (implied, total must be 2^n) */
1547 tableLog = BIT_highbit32(weightTotal) + 1;
1548 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1550 U32 total = 1 << tableLog;
1551 U32 rest = total - weightTotal;
1552 U32 verif = 1 << BIT_highbit32(rest);
1553 U32 lastWeight = BIT_highbit32(rest) + 1;
1554 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1555 huffWeight[oSize] = (BYTE)lastWeight;
1556 rankStats[lastWeight]++;
1559 /* check tree construction validity */
1560 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1563 *nbSymbolsPtr = (U32)(oSize+1);
1564 *tableLogPtr = tableLog;
1569 /**************************/
1570 /* single-symbol decoding */
1571 /**************************/
1573 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1575 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1576 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1578 const BYTE* ip = (const BYTE*) src;
1579 size_t iSize = ip[0];
1583 void* ptr = DTable+1;
1584 HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr);
1586 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1587 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1589 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1590 if (HUF_isError(iSize)) return iSize;
1593 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1594 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1598 for (n=1; n<=tableLog; n++)
1600 U32 current = nextRankStart;
1601 nextRankStart += (rankVal[n] << (n-1));
1602 rankVal[n] = current;
1606 for (n=0; n<nbSymbols; n++)
1608 const U32 w = huffWeight[n];
1609 const U32 length = (1 << w) >> 1;
1612 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1613 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1615 rankVal[w] += length;
1621 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1623 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1624 const BYTE c = dt[val].byte;
1625 BIT_skipBits(Dstream, dt[val].nbBits);
1629 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1630 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1632 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1633 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1634 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1636 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1638 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1640 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1642 BYTE* const pStart = p;
1644 /* up to 4 symbols at a time */
1645 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1647 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1648 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1649 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1650 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1653 /* closer to the end */
1654 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1655 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1657 /* no more data to retrieve from bitstream, hence no need to reload */
1659 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1665 static size_t HUF_decompress4X2_usingDTable(
1666 void* dst, size_t dstSize,
1667 const void* cSrc, size_t cSrcSize,
1670 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1673 const BYTE* const istart = (const BYTE*) cSrc;
1674 BYTE* const ostart = (BYTE*) dst;
1675 BYTE* const oend = ostart + dstSize;
1677 const void* ptr = DTable;
1678 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1679 const U32 dtLog = DTable[0];
1683 BIT_DStream_t bitD1;
1684 BIT_DStream_t bitD2;
1685 BIT_DStream_t bitD3;
1686 BIT_DStream_t bitD4;
1687 const size_t length1 = MEM_readLE16(istart);
1688 const size_t length2 = MEM_readLE16(istart+2);
1689 const size_t length3 = MEM_readLE16(istart+4);
1691 const BYTE* const istart1 = istart + 6; /* jumpTable */
1692 const BYTE* const istart2 = istart1 + length1;
1693 const BYTE* const istart3 = istart2 + length2;
1694 const BYTE* const istart4 = istart3 + length3;
1695 const size_t segmentSize = (dstSize+3) / 4;
1696 BYTE* const opStart2 = ostart + segmentSize;
1697 BYTE* const opStart3 = opStart2 + segmentSize;
1698 BYTE* const opStart4 = opStart3 + segmentSize;
1700 BYTE* op2 = opStart2;
1701 BYTE* op3 = opStart3;
1702 BYTE* op4 = opStart4;
1705 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1706 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1707 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1708 if (HUF_isError(errorCode)) return errorCode;
1709 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1710 if (HUF_isError(errorCode)) return errorCode;
1711 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1712 if (HUF_isError(errorCode)) return errorCode;
1713 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1714 if (HUF_isError(errorCode)) return errorCode;
1716 /* 16-32 symbols per loop (4-8 symbols per stream) */
1717 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1718 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1720 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1721 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1722 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1723 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1724 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1725 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1726 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1727 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1728 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1729 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1730 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1731 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1732 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1733 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1734 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1735 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1737 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1740 /* check corruption */
1741 if (op1 > opStart2) return ERROR(corruption_detected);
1742 if (op2 > opStart3) return ERROR(corruption_detected);
1743 if (op3 > opStart4) return ERROR(corruption_detected);
1744 /* note : op4 supposed already verified within main loop */
1746 /* finish bitStreams one by one */
1747 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1748 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1749 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1750 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1753 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1754 if (!endSignal) return ERROR(corruption_detected);
1762 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1764 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1765 const BYTE* ip = (const BYTE*) cSrc;
1768 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1769 if (HUF_isError(errorCode)) return errorCode;
1770 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1772 cSrcSize -= errorCode;
1774 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1778 /***************************/
1779 /* double-symbols decoding */
1780 /***************************/
1782 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1783 const U32* rankValOrigin, const int minWeight,
1784 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1785 U32 nbBitsBaseline, U16 baseSeq)
1788 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1791 /* get pre-calculated rankVal */
1792 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1794 /* fill skipped values */
1797 U32 i, skipSize = rankVal[minWeight];
1798 MEM_writeLE16(&(DElt.sequence), baseSeq);
1799 DElt.nbBits = (BYTE)(consumed);
1801 for (i = 0; i < skipSize; i++)
1806 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1808 const U32 symbol = sortedSymbols[s].symbol;
1809 const U32 weight = sortedSymbols[s].weight;
1810 const U32 nbBits = nbBitsBaseline - weight;
1811 const U32 length = 1 << (sizeLog-nbBits);
1812 const U32 start = rankVal[weight];
1814 const U32 end = start + length;
1816 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1817 DElt.nbBits = (BYTE)(nbBits + consumed);
1819 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1821 rankVal[weight] += length;
1825 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1827 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1828 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1829 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1830 const U32 nbBitsBaseline)
1832 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1833 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1834 const U32 minBits = nbBitsBaseline - maxWeight;
1837 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1840 for (s=0; s<sortedListSize; s++)
1842 const U16 symbol = sortedList[s].symbol;
1843 const U32 weight = sortedList[s].weight;
1844 const U32 nbBits = nbBitsBaseline - weight;
1845 const U32 start = rankVal[weight];
1846 const U32 length = 1 << (targetLog-nbBits);
1848 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1851 int minWeight = nbBits + scaleLog;
1852 if (minWeight < 1) minWeight = 1;
1853 sortedRank = rankStart[minWeight];
1854 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1855 rankValOrigin[nbBits], minWeight,
1856 sortedList+sortedRank, sortedListSize-sortedRank,
1857 nbBitsBaseline, symbol);
1862 const U32 end = start + length;
1865 MEM_writeLE16(&(DElt.sequence), symbol);
1866 DElt.nbBits = (BYTE)(nbBits);
1868 for (i = start; i < end; i++)
1871 rankVal[weight] += length;
1875 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1877 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1878 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1879 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1880 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1881 U32* const rankStart = rankStart0+1;
1883 U32 tableLog, maxW, sizeOfSort, nbSymbols;
1884 const U32 memLog = DTable[0];
1885 const BYTE* ip = (const BYTE*) src;
1886 size_t iSize = ip[0];
1888 HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1890 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
1891 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1892 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1894 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1895 if (HUF_isError(iSize)) return iSize;
1898 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
1900 /* find maxWeight */
1901 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1902 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
1904 /* Get start index of each weight */
1906 U32 w, nextRankStart = 0;
1907 for (w=1; w<=maxW; w++)
1909 U32 current = nextRankStart;
1910 nextRankStart += rankStats[w];
1911 rankStart[w] = current;
1913 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
1914 sizeOfSort = nextRankStart;
1917 /* sort symbols by weight */
1920 for (s=0; s<nbSymbols; s++)
1922 U32 w = weightList[s];
1923 U32 r = rankStart[w]++;
1924 sortedSymbol[r].symbol = (BYTE)s;
1925 sortedSymbol[r].weight = (BYTE)w;
1927 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1932 const U32 minBits = tableLog+1 - maxW;
1933 U32 nextRankVal = 0;
1935 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
1936 U32* rankVal0 = rankVal[0];
1937 for (w=1; w<=maxW; w++)
1939 U32 current = nextRankVal;
1940 nextRankVal += rankStats[w] << (w+rescale);
1941 rankVal0[w] = current;
1943 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1945 U32* rankValPtr = rankVal[consumed];
1946 for (w = 1; w <= maxW; w++)
1948 rankValPtr[w] = rankVal0[w] >> consumed;
1953 HUF_fillDTableX4(dt, memLog,
1954 sortedSymbol, sizeOfSort,
1955 rankStart0, rankVal, maxW,
1962 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1964 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1965 memcpy(op, dt+val, 2);
1966 BIT_skipBits(DStream, dt[val].nbBits);
1967 return dt[val].length;
1970 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1972 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1973 memcpy(op, dt+val, 1);
1974 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
1977 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
1979 BIT_skipBits(DStream, dt[val].nbBits);
1980 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
1981 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 */
1988 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
1989 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1991 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
1992 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1993 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1995 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
1997 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1999 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2001 BYTE* const pStart = p;
2003 /* up to 8 symbols at a time */
2004 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2006 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2007 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2008 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2009 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2012 /* closer to the end */
2013 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2014 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2017 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2020 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2027 static size_t HUF_decompress4X4_usingDTable(
2028 void* dst, size_t dstSize,
2029 const void* cSrc, size_t cSrcSize,
2032 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2035 const BYTE* const istart = (const BYTE*) cSrc;
2036 BYTE* const ostart = (BYTE*) dst;
2037 BYTE* const oend = ostart + dstSize;
2039 const void* ptr = DTable;
2040 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2041 const U32 dtLog = DTable[0];
2045 BIT_DStream_t bitD1;
2046 BIT_DStream_t bitD2;
2047 BIT_DStream_t bitD3;
2048 BIT_DStream_t bitD4;
2049 const size_t length1 = MEM_readLE16(istart);
2050 const size_t length2 = MEM_readLE16(istart+2);
2051 const size_t length3 = MEM_readLE16(istart+4);
2053 const BYTE* const istart1 = istart + 6; /* jumpTable */
2054 const BYTE* const istart2 = istart1 + length1;
2055 const BYTE* const istart3 = istart2 + length2;
2056 const BYTE* const istart4 = istart3 + length3;
2057 const size_t segmentSize = (dstSize+3) / 4;
2058 BYTE* const opStart2 = ostart + segmentSize;
2059 BYTE* const opStart3 = opStart2 + segmentSize;
2060 BYTE* const opStart4 = opStart3 + segmentSize;
2062 BYTE* op2 = opStart2;
2063 BYTE* op3 = opStart3;
2064 BYTE* op4 = opStart4;
2067 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2068 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2069 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2070 if (HUF_isError(errorCode)) return errorCode;
2071 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2072 if (HUF_isError(errorCode)) return errorCode;
2073 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2074 if (HUF_isError(errorCode)) return errorCode;
2075 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2076 if (HUF_isError(errorCode)) return errorCode;
2078 /* 16-32 symbols per loop (4-8 symbols per stream) */
2079 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2080 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2082 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2083 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2084 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2085 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2086 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2087 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2088 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2089 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2090 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2091 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2092 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2093 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2094 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2095 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2096 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2097 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2099 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2102 /* check corruption */
2103 if (op1 > opStart2) return ERROR(corruption_detected);
2104 if (op2 > opStart3) return ERROR(corruption_detected);
2105 if (op3 > opStart4) return ERROR(corruption_detected);
2106 /* note : op4 supposed already verified within main loop */
2108 /* finish bitStreams one by one */
2109 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2110 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2111 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2112 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2115 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2116 if (!endSignal) return ERROR(corruption_detected);
2124 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2126 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2127 const BYTE* ip = (const BYTE*) cSrc;
2129 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2130 if (HUF_isError(hSize)) return hSize;
2131 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2135 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2139 /**********************************/
2140 /* Generic decompression selector */
2141 /**********************************/
2143 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2144 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2146 /* single, double, quad */
2147 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2148 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2149 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2150 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2151 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2152 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2153 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2154 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2155 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2156 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2157 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2158 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2159 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2160 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2161 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2162 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2165 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2167 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2169 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2170 /* estimate decompression time */
2172 const U32 D256 = (U32)(dstSize >> 8);
2177 /* validation checks */
2178 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2179 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2180 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2181 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2183 /* decoder timing evaluation */
2184 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2186 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2188 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2190 if (Dtime[1] < Dtime[0]) algoNb = 1;
2192 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2194 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2195 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2196 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2199 zstd - standard compression library
2200 Copyright (C) 2014-2015, Yann Collet.
2202 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2204 Redistribution and use in source and binary forms, with or without
2205 modification, are permitted provided that the following conditions are
2207 * Redistributions of source code must retain the above copyright
2208 notice, this list of conditions and the following disclaimer.
2209 * Redistributions in binary form must reproduce the above
2210 copyright notice, this list of conditions and the following disclaimer
2211 in the documentation and/or other materials provided with the
2213 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2214 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2215 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2216 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2217 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2218 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2219 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2220 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2221 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2222 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2223 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2225 You can contact the author at :
2226 - zstd source repository : https://github.com/Cyan4973/zstd
2227 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2230 /* ***************************************************************
2232 *****************************************************************/
2235 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2236 * Increasing memory usage improves compression ratio
2237 * Reduced memory usage can improve speed, due to cache effect
2239 #define ZSTD_MEMORY_USAGE 17
2243 * Select how default compression functions will allocate memory for their hash table,
2244 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2245 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2247 #ifndef ZSTD_HEAPMODE
2248 # define ZSTD_HEAPMODE 1
2249 #endif /* ZSTD_HEAPMODE */
2253 * decompressor can decode older formats (starting from Zstd 0.1+)
2255 #ifndef ZSTD_LEGACY_SUPPORT
2256 # define ZSTD_LEGACY_SUPPORT 1
2260 /* *******************************************************
2262 *********************************************************/
2263 #include <stdlib.h> /* calloc */
2264 #include <string.h> /* memcpy, memmove */
2265 #include <stdio.h> /* debug : printf */
2268 /* *******************************************************
2269 * Compiler specifics
2270 *********************************************************/
2272 # include <immintrin.h> /* AVX2 intrinsics */
2275 #ifdef _MSC_VER /* Visual Studio */
2276 # include <intrin.h> /* For Visual 2005 */
2277 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2278 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2280 # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
2284 /* *******************************************************
2286 *********************************************************/
2287 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2288 #define HASH_TABLESIZE (1 << HASH_LOG)
2289 #define HASH_MASK (HASH_TABLESIZE - 1)
2291 #define KNUTH 2654435761
2300 #define KB *(1 <<10)
2301 #define MB *(1 <<20)
2302 #define GB *(1U<<30)
2304 #define BLOCKSIZE (128 KB) /* define, for static allocation */
2305 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2306 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2310 #define WORKPLACESIZE (BLOCKSIZE*3)
2315 #define MaxML ((1<<MLbits )-1)
2316 #define MaxLL ((1<<LLbits )-1)
2318 #define LitFSELog 11
2322 #define MAX(a,b) ((a)<(b)?(b):(a))
2323 #define MaxSeq MAX(MaxLL, MaxML)
2325 #define LITERAL_NOENTROPY 63
2326 #define COMMAND_NOENTROPY 7 /* to remove */
2328 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2330 static const size_t ZSTD_blockHeaderSize = 3;
2331 static const size_t ZSTD_frameHeaderSize = 4;
2334 /* *******************************************************
2336 **********************************************************/
2337 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2339 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2341 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2343 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2344 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2346 const BYTE* ip = (const BYTE*)src;
2347 BYTE* op = (BYTE*)dst;
2348 BYTE* const oend = op + length;
2349 do COPY8(op, ip) while (op < oend);
2353 /* **************************************
2355 ****************************************/
2356 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2360 blockType_t blockType;
2362 } blockProperties_t;
2372 BYTE* litLengthStart;
2374 BYTE* matchLengthStart;
2381 /* *************************************
2383 ***************************************/
2385 * tells if a return value is an error code */
2386 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2390 /* *************************************************************
2391 * Decompression section
2392 ***************************************************************/
2395 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2396 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2397 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2398 void* previousDstEnd;
2405 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2406 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2409 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2411 const BYTE* const in = (const BYTE* const)src;
2415 if (srcSize < 3) return ERROR(srcSize_wrong);
2418 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2420 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2421 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2423 if (bpPtr->blockType == bt_end) return 0;
2424 if (bpPtr->blockType == bt_rle) return 1;
2428 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2430 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2432 memcpy(dst, src, srcSize);
2438 /** ZSTD_decompressLiterals
2439 @return : nb of bytes read from src, or an error code*/
2440 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2441 const void* src, size_t srcSize)
2443 const BYTE* ip = (const BYTE*)src;
2445 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2446 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2448 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2449 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2451 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2453 *maxDstSizePtr = litSize;
2454 return litCSize + 5;
2458 /** ZSTD_decodeLiteralsBlock
2459 @return : nb of bytes read from src (< srcSize )*/
2460 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2461 const void* src, size_t srcSize)
2463 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2464 const BYTE* const istart = (const BYTE* const)src;
2466 /* any compressed block with literals segment must be at least this size */
2467 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2474 size_t litSize = BLOCKSIZE;
2475 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2476 dctx->litPtr = dctx->litBuffer;
2477 dctx->litSize = litSize;
2478 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2479 return readSize; /* works if it's an error too */
2483 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2484 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2486 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2487 if (litSize > srcSize-3) return ERROR(corruption_detected);
2488 memcpy(dctx->litBuffer, istart, litSize);
2489 dctx->litPtr = dctx->litBuffer;
2490 dctx->litSize = litSize;
2491 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2494 /* direct reference into compressed stream */
2495 dctx->litPtr = istart+3;
2496 dctx->litSize = litSize;
2501 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2502 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2503 memset(dctx->litBuffer, istart[3], litSize + 8);
2504 dctx->litPtr = dctx->litBuffer;
2505 dctx->litSize = litSize;
2512 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2513 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2514 const void* src, size_t srcSize)
2516 const BYTE* const istart = (const BYTE* const)src;
2517 const BYTE* ip = istart;
2518 const BYTE* const iend = istart + srcSize;
2519 U32 LLtype, Offtype, MLtype;
2520 U32 LLlog, Offlog, MLlog;
2524 if (srcSize < 5) return ERROR(srcSize_wrong);
2527 *nbSeq = MEM_readLE16(ip); ip+=2;
2529 Offtype = (*ip >> 4) & 3;
2530 MLtype = (*ip >> 2) & 3;
2533 dumpsLength = ip[2];
2534 dumpsLength += ip[1] << 8;
2539 dumpsLength = ip[1];
2540 dumpsLength += (ip[0] & 1) << 8;
2545 *dumpsLengthPtr = dumpsLength;
2548 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2552 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2560 FSE_buildDTable_rle(DTableLL, *ip++); break;
2563 FSE_buildDTable_raw(DTableLL, LLbits); break;
2566 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2567 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2568 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2570 FSE_buildDTable(DTableLL, norm, max, LLlog);
2577 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2578 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2582 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2585 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2586 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2587 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2589 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2596 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2597 FSE_buildDTable_rle(DTableML, *ip++); break;
2600 FSE_buildDTable_raw(DTableML, MLbits); break;
2603 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2604 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2605 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2607 FSE_buildDTable(DTableML, norm, max, MLlog);
2621 BIT_DStream_t DStream;
2622 FSE_DState_t stateLL;
2623 FSE_DState_t stateOffb;
2624 FSE_DState_t stateML;
2627 const BYTE* dumpsEnd;
2631 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2637 const BYTE* dumps = seqState->dumps;
2638 const BYTE* const de = seqState->dumpsEnd;
2640 /* Literal length */
2641 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2642 prevOffset = litLength ? seq->offset : seqState->prevOffset;
2643 seqState->prevOffset = seq->offset;
2644 if (litLength == MaxLL)
2646 const U32 add = dumps<de ? *dumps++ : 0;
2647 if (add < 255) litLength += add;
2648 else if (dumps + 3 <= de)
2650 litLength = MEM_readLE24(dumps);
2653 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2658 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
2659 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2660 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2661 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2662 U32 offsetCode, nbBits;
2663 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
2664 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2665 nbBits = offsetCode - 1;
2666 if (offsetCode==0) nbBits = 0; /* cmove */
2667 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2668 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2669 if (offsetCode==0) offset = prevOffset; /* cmove */
2673 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2674 if (matchLength == MaxML)
2676 const U32 add = dumps<de ? *dumps++ : 0;
2677 if (add < 255) matchLength += add;
2678 else if (dumps + 3 <= de)
2680 matchLength = MEM_readLE24(dumps);
2683 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2685 matchLength += MINMATCH;
2688 seq->litLength = litLength;
2689 seq->offset = offset;
2690 seq->matchLength = matchLength;
2691 seqState->dumps = dumps;
2695 static size_t ZSTD_execSequence(BYTE* op,
2697 const BYTE** litPtr, const BYTE* const litLimit,
2698 BYTE* const base, BYTE* const oend)
2700 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
2701 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */
2702 const BYTE* const ostart = op;
2703 BYTE* const oLitEnd = op + sequence.litLength;
2704 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
2705 BYTE* const oend_8 = oend-8;
2706 const BYTE* const litEnd = *litPtr + sequence.litLength;
2709 size_t const seqLength = sequence.litLength + sequence.matchLength;
2711 if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
2712 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
2713 /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
2714 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
2715 if (sequence.offset > (U32)(oLitEnd - base)) return ERROR(corruption_detected);
2717 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
2718 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
2721 ZSTD_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2723 *litPtr = litEnd; /* update for next sequence */
2726 { const BYTE* match = op - sequence.offset;
2729 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
2730 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
2731 if (match < base) return ERROR(corruption_detected);
2733 /* close range match, overlap */
2734 if (sequence.offset < 8)
2736 const int dec64 = dec64table[sequence.offset];
2741 match += dec32table[sequence.offset];
2742 ZSTD_copy4(op+4, match);
2747 ZSTD_copy8(op, match);
2749 op += 8; match += 8;
2751 if (oMatchEnd > oend-(16-MINMATCH))
2755 ZSTD_wildcopy(op, match, oend_8 - op);
2756 match += oend_8 - op;
2759 while (op < oMatchEnd) *op++ = *match++;
2763 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
2767 return oMatchEnd - ostart;
2770 static size_t ZSTD_decompressSequences(
2772 void* dst, size_t maxDstSize,
2773 const void* seqStart, size_t seqSize)
2775 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2776 const BYTE* ip = (const BYTE*)seqStart;
2777 const BYTE* const iend = ip + seqSize;
2778 BYTE* const ostart = (BYTE* const)dst;
2780 BYTE* const oend = ostart + maxDstSize;
2781 size_t errorCode, dumpsLength;
2782 const BYTE* litPtr = dctx->litPtr;
2783 const BYTE* const litEnd = litPtr + dctx->litSize;
2786 U32* DTableLL = dctx->LLTable;
2787 U32* DTableML = dctx->MLTable;
2788 U32* DTableOffb = dctx->OffTable;
2789 BYTE* const base = (BYTE*) (dctx->base);
2791 /* Build Decoding Tables */
2792 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2793 DTableLL, DTableML, DTableOffb,
2795 if (ZSTD_isError(errorCode)) return errorCode;
2798 /* Regen sequences */
2801 seqState_t seqState;
2803 memset(&sequence, 0, sizeof(sequence));
2804 seqState.dumps = dumps;
2805 seqState.dumpsEnd = dumps + dumpsLength;
2806 seqState.prevOffset = sequence.offset = 4;
2807 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2808 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2809 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2810 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2811 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2813 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
2817 ZSTD_decodeSequence(&sequence, &seqState);
2818 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
2819 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2823 /* check if reached exact end */
2824 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
2825 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
2827 /* last literal segment */
2829 size_t lastLLSize = litEnd - litPtr;
2830 if (litPtr > litEnd) return ERROR(corruption_detected);
2831 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2832 if (lastLLSize > 0) {
2833 if (op != litPtr) memmove(op, litPtr, lastLLSize);
2843 static size_t ZSTD_decompressBlock(
2845 void* dst, size_t maxDstSize,
2846 const void* src, size_t srcSize)
2848 /* blockType == blockCompressed */
2849 const BYTE* ip = (const BYTE*)src;
2851 /* Decode literals sub-block */
2852 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
2853 if (ZSTD_isError(litCSize)) return litCSize;
2855 srcSize -= litCSize;
2857 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
2861 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2863 const BYTE* ip = (const BYTE*)src;
2864 const BYTE* iend = ip + srcSize;
2865 BYTE* const ostart = (BYTE* const)dst;
2867 BYTE* const oend = ostart + maxDstSize;
2868 size_t remainingSize = srcSize;
2870 blockProperties_t blockProperties;
2873 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2874 magicNumber = MEM_readLE32(src);
2875 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2876 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2878 /* Loop on each block */
2881 size_t decodedSize=0;
2882 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
2883 if (ZSTD_isError(cBlockSize)) return cBlockSize;
2885 ip += ZSTD_blockHeaderSize;
2886 remainingSize -= ZSTD_blockHeaderSize;
2887 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2889 switch(blockProperties.blockType)
2892 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
2895 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
2898 return ERROR(GENERIC); /* not yet supported */
2902 if (remainingSize) return ERROR(srcSize_wrong);
2905 return ERROR(GENERIC); /* impossible */
2907 if (cBlockSize == 0) break; /* bt_end */
2909 if (ZSTD_isError(decodedSize)) return decodedSize;
2912 remainingSize -= cBlockSize;
2918 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2922 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
2925 /* ZSTD_errorFrameSizeInfoLegacy() :
2926 assumes `cSize` and `dBound` are _not_ NULL */
2927 MEM_STATIC void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
2930 *dBound = ZSTD_CONTENTSIZE_ERROR;
2933 void ZSTDv03_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
2935 const BYTE* ip = (const BYTE*)src;
2936 size_t remainingSize = srcSize;
2937 size_t nbBlocks = 0;
2939 blockProperties_t blockProperties;
2942 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
2943 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2946 magicNumber = MEM_readLE32(src);
2947 if (magicNumber != ZSTD_magicNumber) {
2948 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
2951 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2953 /* Loop on each block */
2956 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
2957 if (ZSTD_isError(cBlockSize)) {
2958 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
2962 ip += ZSTD_blockHeaderSize;
2963 remainingSize -= ZSTD_blockHeaderSize;
2964 if (cBlockSize > remainingSize) {
2965 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2969 if (cBlockSize == 0) break; /* bt_end */
2972 remainingSize -= cBlockSize;
2976 *cSize = ip - (const BYTE*)src;
2977 *dBound = nbBlocks * BLOCKSIZE;
2981 /*******************************
2982 * Streaming Decompression API
2983 *******************************/
2985 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2987 dctx->expected = ZSTD_frameHeaderSize;
2989 dctx->previousDstEnd = NULL;
2994 static ZSTD_DCtx* ZSTD_createDCtx(void)
2996 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2997 if (dctx==NULL) return NULL;
2998 ZSTD_resetDCtx(dctx);
3002 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3008 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3010 return dctx->expected;
3013 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3016 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3017 if (dst != ctx->previousDstEnd) /* not contiguous */
3020 /* Decompress : frame header */
3021 if (ctx->phase == 0)
3023 /* Check frame magic header */
3024 U32 magicNumber = MEM_readLE32(src);
3025 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3027 ctx->expected = ZSTD_blockHeaderSize;
3031 /* Decompress : block header */
3032 if (ctx->phase == 1)
3034 blockProperties_t bp;
3035 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3036 if (ZSTD_isError(blockSize)) return blockSize;
3037 if (bp.blockType == bt_end)
3044 ctx->expected = blockSize;
3045 ctx->bType = bp.blockType;
3052 /* Decompress : block content */
3058 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3061 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3064 return ERROR(GENERIC); /* not yet handled */
3066 case bt_end : /* should never happen (filtered at phase 1) */
3070 return ERROR(GENERIC);
3073 ctx->expected = ZSTD_blockHeaderSize;
3074 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3083 unsigned ZSTDv03_isError(size_t code)
3085 return ZSTD_isError(code);
3088 size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3089 const void* src, size_t compressedSize)
3091 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3094 ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3096 return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3099 size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3101 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3104 size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3106 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3109 size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3111 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3114 size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3116 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);