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_* */
26 /* ******************************************************************
28 low-level memory access routines
29 Copyright (C) 2013-2015, Yann Collet.
31 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
33 Redistribution and use in source and binary forms, with or without
34 modification, are permitted provided that the following conditions are
37 * Redistributions of source code must retain the above copyright
38 notice, this list of conditions and the following disclaimer.
39 * Redistributions in binary form must reproduce the above
40 copyright notice, this list of conditions and the following disclaimer
41 in the documentation and/or other materials provided with the
44 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
45 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
46 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
47 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
48 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
49 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
50 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
51 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
52 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
53 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
54 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
56 You can contact the author at :
57 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
58 - Public forum : https://groups.google.com/forum/#!forum/lz4c
59 ****************************************************************** */
63 #if defined (__cplusplus)
67 /******************************************
69 ******************************************/
70 #include <stddef.h> /* size_t, ptrdiff_t */
71 #include <string.h> /* memcpy */
74 /******************************************
76 ******************************************/
78 # define MEM_STATIC static __attribute__((unused))
79 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
80 # define MEM_STATIC static inline
81 #elif defined(_MSC_VER)
82 # define MEM_STATIC static __inline
84 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
88 /****************************************************************
90 *****************************************************************/
91 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
93 # include <inttypes.h>
95 # include <stdint.h> /* intptr_t */
100 typedef uint32_t U32;
102 typedef uint64_t U64;
105 typedef unsigned char BYTE;
106 typedef unsigned short U16;
107 typedef signed short S16;
108 typedef unsigned int U32;
109 typedef signed int S32;
110 typedef unsigned long long U64;
111 typedef signed long long S64;
115 /****************************************************************
117 *****************************************************************/
119 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
120 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
122 MEM_STATIC unsigned MEM_isLittleEndian(void)
124 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
128 MEM_STATIC U16 MEM_read16(const void* memPtr)
130 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
133 MEM_STATIC U32 MEM_read32(const void* memPtr)
135 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
138 MEM_STATIC U64 MEM_read64(const void* memPtr)
140 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
143 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
145 memcpy(memPtr, &value, sizeof(value));
148 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
150 if (MEM_isLittleEndian())
151 return MEM_read16(memPtr);
154 const BYTE* p = (const BYTE*)memPtr;
155 return (U16)(p[0] + (p[1]<<8));
159 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
161 if (MEM_isLittleEndian())
163 MEM_write16(memPtr, val);
167 BYTE* p = (BYTE*)memPtr;
169 p[1] = (BYTE)(val>>8);
173 MEM_STATIC U32 MEM_readLE24(const void* memPtr)
175 return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
178 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
180 if (MEM_isLittleEndian())
181 return MEM_read32(memPtr);
184 const BYTE* p = (const BYTE*)memPtr;
185 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);
211 #if defined (__cplusplus)
215 #endif /* MEM_H_MODULE */
218 /* ******************************************************************
220 Part of NewGen Entropy library
221 header file (to include)
222 Copyright (C) 2013-2015, Yann Collet.
224 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
226 Redistribution and use in source and binary forms, with or without
227 modification, are permitted provided that the following conditions are
230 * Redistributions of source code must retain the above copyright
231 notice, this list of conditions and the following disclaimer.
232 * Redistributions in binary form must reproduce the above
233 copyright notice, this list of conditions and the following disclaimer
234 in the documentation and/or other materials provided with the
237 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
238 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
239 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
240 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
241 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
242 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
243 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
244 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
245 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
246 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
247 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
249 You can contact the author at :
250 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
251 - Public forum : https://groups.google.com/forum/#!forum/lz4c
252 ****************************************************************** */
253 #ifndef BITSTREAM_H_MODULE
254 #define BITSTREAM_H_MODULE
256 #if defined (__cplusplus)
262 * This API consists of small unitary functions, which highly benefit from being inlined.
263 * Since link-time-optimization is not available for all compilers,
264 * these functions are defined into a .h to be included.
268 /**********************************************
269 * bitStream decompression API (read backward)
270 **********************************************/
274 unsigned bitsConsumed;
279 typedef enum { BIT_DStream_unfinished = 0,
280 BIT_DStream_endOfBuffer = 1,
281 BIT_DStream_completed = 2,
282 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
283 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
285 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
286 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
287 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
288 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
291 /******************************************
293 ******************************************/
294 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
295 /* faster, but works only if nbBits >= 1 */
299 /****************************************************************
301 ****************************************************************/
302 MEM_STATIC unsigned BIT_highbit32 (U32 val)
304 # if defined(_MSC_VER) /* Visual */
306 return _BitScanReverse(&r, val) ? (unsigned)r : 0;
307 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
308 return __builtin_clz (val) ^ 31;
309 # else /* Software version */
310 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 };
318 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
325 /**********************************************************
327 **********************************************************/
330 * Initialize a BIT_DStream_t.
331 * @bitD : a pointer to an already allocated BIT_DStream_t structure
332 * @srcBuffer must point at the beginning of a bitStream
333 * @srcSize must be the exact size of the bitStream
334 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
336 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
338 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
340 if (srcSize >= sizeof(size_t)) /* normal case */
343 bitD->start = (const char*)srcBuffer;
344 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
345 bitD->bitContainer = MEM_readLEST(bitD->ptr);
346 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
347 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
348 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
353 bitD->start = (const char*)srcBuffer;
354 bitD->ptr = bitD->start;
355 bitD->bitContainer = *(const BYTE*)(bitD->start);
358 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
360 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
362 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
364 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
366 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
368 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
372 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
373 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
374 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
375 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
381 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
383 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
384 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
387 /*! BIT_lookBitsFast :
388 * unsafe version; only works if nbBits >= 1 */
389 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
391 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
392 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
395 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
397 bitD->bitsConsumed += nbBits;
400 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
402 size_t value = BIT_lookBits(bitD, nbBits);
403 BIT_skipBits(bitD, nbBits);
407 /*!BIT_readBitsFast :
408 * unsafe version; only works if nbBits >= 1 */
409 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
411 size_t value = BIT_lookBitsFast(bitD, nbBits);
412 BIT_skipBits(bitD, nbBits);
416 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
418 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
419 return BIT_DStream_overflow;
421 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
423 bitD->ptr -= bitD->bitsConsumed >> 3;
424 bitD->bitsConsumed &= 7;
425 bitD->bitContainer = MEM_readLEST(bitD->ptr);
426 return BIT_DStream_unfinished;
428 if (bitD->ptr == bitD->start)
430 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
431 return BIT_DStream_completed;
434 U32 nbBytes = bitD->bitsConsumed >> 3;
435 BIT_DStream_status result = BIT_DStream_unfinished;
436 if (bitD->ptr - nbBytes < bitD->start)
438 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
439 result = BIT_DStream_endOfBuffer;
441 bitD->ptr -= nbBytes;
442 bitD->bitsConsumed -= nbBytes*8;
443 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
449 * @return Tells if DStream has reached its exact end
451 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
453 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
456 #if defined (__cplusplus)
460 #endif /* BITSTREAM_H_MODULE */
461 /* ******************************************************************
462 Error codes and messages
463 Copyright (C) 2013-2015, Yann Collet
465 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
467 Redistribution and use in source and binary forms, with or without
468 modification, are permitted provided that the following conditions are
471 * Redistributions of source code must retain the above copyright
472 notice, this list of conditions and the following disclaimer.
473 * Redistributions in binary form must reproduce the above
474 copyright notice, this list of conditions and the following disclaimer
475 in the documentation and/or other materials provided with the
478 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
479 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
480 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
481 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
482 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
483 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
484 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
485 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
486 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
487 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
488 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
490 You can contact the author at :
491 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
492 - Public forum : https://groups.google.com/forum/#!forum/lz4c
493 ****************************************************************** */
494 #ifndef ERROR_H_MODULE
495 #define ERROR_H_MODULE
497 #if defined (__cplusplus)
502 /******************************************
504 ******************************************/
505 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
506 # define ERR_STATIC static inline
507 #elif defined(_MSC_VER)
508 # define ERR_STATIC static __inline
509 #elif defined(__GNUC__)
510 # define ERR_STATIC static __attribute__((unused))
512 # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
516 /******************************************
518 ******************************************/
519 #define PREFIX(name) ZSTD_error_##name
521 #define ERROR(name) (size_t)-PREFIX(name)
523 #define ERROR_LIST(ITEM) \
524 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
525 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
526 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
527 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
528 ITEM(PREFIX(maxCode))
530 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
531 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
533 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
534 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
535 static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
537 ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
539 ERR_STATIC const char* ERR_getErrorName(size_t code)
541 static const char* codeError = "Unspecified error code";
542 if (ERR_isError(code)) return ERR_strings[-(int)(code)];
547 #if defined (__cplusplus)
551 #endif /* ERROR_H_MODULE */
553 Constructor and Destructor of type FSE_CTable
554 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
555 typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
556 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
559 /* ******************************************************************
560 FSE : Finite State Entropy coder
561 header file for static linking (only)
562 Copyright (C) 2013-2015, Yann Collet
564 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
566 Redistribution and use in source and binary forms, with or without
567 modification, are permitted provided that the following conditions are
570 * Redistributions of source code must retain the above copyright
571 notice, this list of conditions and the following disclaimer.
572 * Redistributions in binary form must reproduce the above
573 copyright notice, this list of conditions and the following disclaimer
574 in the documentation and/or other materials provided with the
577 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
578 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
579 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
580 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
581 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
582 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
583 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
584 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
585 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
586 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
587 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
589 You can contact the author at :
590 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
591 - Public forum : https://groups.google.com/forum/#!forum/lz4c
592 ****************************************************************** */
593 #if defined (__cplusplus)
598 /******************************************
600 ******************************************/
601 /* FSE buffer bounds */
602 #define FSE_NCOUNTBOUND 512
603 #define FSE_BLOCKBOUND(size) (size + (size>>7))
604 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
606 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
607 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
608 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
611 /******************************************
613 ******************************************/
614 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
615 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
617 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
618 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
621 /******************************************
622 * FSE symbol decompression API
623 ******************************************/
627 const void* table; /* precise table may vary, depending on U16 */
631 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
633 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
635 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
638 /******************************************
640 ******************************************/
641 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
642 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
645 /******************************************
646 * Implementation of inline functions
647 ******************************************/
654 } FSE_DTableHeader; /* sizeof U32 */
658 unsigned short newState;
659 unsigned char symbol;
660 unsigned char nbBits;
661 } FSE_decode_t; /* size == U32 */
663 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
665 FSE_DTableHeader DTableH;
666 memcpy(&DTableH, dt, sizeof(DTableH));
667 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
668 BIT_reloadDStream(bitD);
669 DStatePtr->table = dt + 1;
672 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
674 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
675 const U32 nbBits = DInfo.nbBits;
676 BYTE symbol = DInfo.symbol;
677 size_t lowBits = BIT_readBits(bitD, nbBits);
679 DStatePtr->state = DInfo.newState + lowBits;
683 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
685 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
686 const U32 nbBits = DInfo.nbBits;
687 BYTE symbol = DInfo.symbol;
688 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
690 DStatePtr->state = DInfo.newState + lowBits;
694 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
696 return DStatePtr->state == 0;
700 #if defined (__cplusplus)
703 /* ******************************************************************
704 Huff0 : Huffman coder, part of New Generation Entropy library
705 header file for static linking (only)
706 Copyright (C) 2013-2015, Yann Collet
708 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
710 Redistribution and use in source and binary forms, with or without
711 modification, are permitted provided that the following conditions are
714 * Redistributions of source code must retain the above copyright
715 notice, this list of conditions and the following disclaimer.
716 * Redistributions in binary form must reproduce the above
717 copyright notice, this list of conditions and the following disclaimer
718 in the documentation and/or other materials provided with the
721 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
722 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
723 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
724 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
725 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
726 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
727 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
728 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
729 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
730 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
731 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
733 You can contact the author at :
734 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
735 - Public forum : https://groups.google.com/forum/#!forum/lz4c
736 ****************************************************************** */
738 #if defined (__cplusplus)
742 /******************************************
743 * Static allocation macros
744 ******************************************/
745 /* Huff0 buffer bounds */
746 #define HUF_CTABLEBOUND 129
747 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
748 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
750 /* static allocation of Huff0's DTable */
751 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
752 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
753 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
754 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
755 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
756 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
757 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
760 /******************************************
762 ******************************************/
763 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
764 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
765 static size_t HUF_decompress4X6 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* quad-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 0xFD2FB522 /* v0.2 (current)*/
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_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1052 FSE_DTableHeader DTableH;
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)); /* memcpy(), to avoid strict aliasing warnings */
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 (short)(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; /* because dt is unsigned */
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; /* because dt is unsigned */
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 # define inline __inline
1443 # define inline /* disable inline */
1447 #ifdef _MSC_VER /* Visual Studio */
1448 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1452 /****************************************************************
1454 ****************************************************************/
1455 #include <stdlib.h> /* malloc, free, qsort */
1456 #include <string.h> /* memcpy, memset */
1457 #include <stdio.h> /* printf (debug) */
1459 /****************************************************************
1461 ****************************************************************/
1462 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1465 /******************************************
1467 ******************************************/
1468 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1470 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1471 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1472 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1473 #define HUF_MAX_SYMBOL_VALUE 255
1474 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1475 # error "HUF_MAX_TABLELOG is too large !"
1480 /*********************************************************
1481 * Huff0 : Huffman block decompression
1482 *********************************************************/
1483 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1485 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1487 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1490 Read compact Huffman tree, saved by HUF_writeCTable
1491 @huffWeight : destination buffer
1492 @return : size read from `src`
1494 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1495 U32* nbSymbolsPtr, U32* tableLogPtr,
1496 const void* src, size_t srcSize)
1500 const BYTE* ip = (const BYTE*) src;
1505 if (!srcSize) return ERROR(srcSize_wrong);
1507 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1509 if (iSize >= 128) /* special header */
1511 if (iSize >= (242)) /* RLE */
1513 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1514 oSize = l[iSize-242];
1515 memset(huffWeight, 1, hwSize);
1518 else /* Incompressible */
1520 oSize = iSize - 127;
1521 iSize = ((oSize+1)/2);
1522 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1523 if (oSize >= hwSize) return ERROR(corruption_detected);
1525 for (n=0; n<oSize; n+=2)
1527 huffWeight[n] = ip[n/2] >> 4;
1528 huffWeight[n+1] = ip[n/2] & 15;
1532 else /* header compressed with FSE (normal case) */
1534 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1535 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1536 if (FSE_isError(oSize)) return oSize;
1539 /* collect weight stats */
1540 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1542 for (n=0; n<oSize; n++)
1544 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1545 rankStats[huffWeight[n]]++;
1546 weightTotal += (1 << huffWeight[n]) >> 1;
1548 if (weightTotal == 0) return ERROR(corruption_detected);
1550 /* get last non-null symbol weight (implied, total must be 2^n) */
1551 tableLog = BIT_highbit32(weightTotal) + 1;
1552 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1554 U32 total = 1 << tableLog;
1555 U32 rest = total - weightTotal;
1556 U32 verif = 1 << BIT_highbit32(rest);
1557 U32 lastWeight = BIT_highbit32(rest) + 1;
1558 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1559 huffWeight[oSize] = (BYTE)lastWeight;
1560 rankStats[lastWeight]++;
1563 /* check tree construction validity */
1564 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1567 *nbSymbolsPtr = (U32)(oSize+1);
1568 *tableLogPtr = tableLog;
1573 /**************************/
1574 /* single-symbol decoding */
1575 /**************************/
1577 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1579 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1580 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1582 const BYTE* ip = (const BYTE*) src;
1583 size_t iSize = ip[0];
1587 void* ptr = DTable+1;
1588 HUF_DEltX2* const dt = (HUF_DEltX2*)ptr;
1590 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1591 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1593 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1594 if (HUF_isError(iSize)) return iSize;
1597 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1598 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1602 for (n=1; n<=tableLog; n++)
1604 U32 current = nextRankStart;
1605 nextRankStart += (rankVal[n] << (n-1));
1606 rankVal[n] = current;
1610 for (n=0; n<nbSymbols; n++)
1612 const U32 w = huffWeight[n];
1613 const U32 length = (1 << w) >> 1;
1616 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1617 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1619 rankVal[w] += length;
1625 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1627 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1628 const BYTE c = dt[val].byte;
1629 BIT_skipBits(Dstream, dt[val].nbBits);
1633 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1634 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1636 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1637 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1638 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1640 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1642 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1644 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1646 BYTE* const pStart = p;
1648 /* up to 4 symbols at a time */
1649 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1651 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1652 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1653 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1654 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1657 /* closer to the end */
1658 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1659 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1661 /* no more data to retrieve from bitstream, hence no need to reload */
1663 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1669 static size_t HUF_decompress4X2_usingDTable(
1670 void* dst, size_t dstSize,
1671 const void* cSrc, size_t cSrcSize,
1674 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1677 const BYTE* const istart = (const BYTE*) cSrc;
1678 BYTE* const ostart = (BYTE*) dst;
1679 BYTE* const oend = ostart + dstSize;
1681 const void* ptr = DTable;
1682 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1683 const U32 dtLog = DTable[0];
1687 BIT_DStream_t bitD1;
1688 BIT_DStream_t bitD2;
1689 BIT_DStream_t bitD3;
1690 BIT_DStream_t bitD4;
1691 const size_t length1 = MEM_readLE16(istart);
1692 const size_t length2 = MEM_readLE16(istart+2);
1693 const size_t length3 = MEM_readLE16(istart+4);
1695 const BYTE* const istart1 = istart + 6; /* jumpTable */
1696 const BYTE* const istart2 = istart1 + length1;
1697 const BYTE* const istart3 = istart2 + length2;
1698 const BYTE* const istart4 = istart3 + length3;
1699 const size_t segmentSize = (dstSize+3) / 4;
1700 BYTE* const opStart2 = ostart + segmentSize;
1701 BYTE* const opStart3 = opStart2 + segmentSize;
1702 BYTE* const opStart4 = opStart3 + segmentSize;
1704 BYTE* op2 = opStart2;
1705 BYTE* op3 = opStart3;
1706 BYTE* op4 = opStart4;
1709 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1710 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1711 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1712 if (HUF_isError(errorCode)) return errorCode;
1713 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1714 if (HUF_isError(errorCode)) return errorCode;
1715 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1716 if (HUF_isError(errorCode)) return errorCode;
1717 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1718 if (HUF_isError(errorCode)) return errorCode;
1720 /* 16-32 symbols per loop (4-8 symbols per stream) */
1721 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1722 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1724 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1725 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1726 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1727 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1728 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1729 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1730 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1731 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1732 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1733 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1734 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1735 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1736 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1737 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1738 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1739 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1741 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1744 /* check corruption */
1745 if (op1 > opStart2) return ERROR(corruption_detected);
1746 if (op2 > opStart3) return ERROR(corruption_detected);
1747 if (op3 > opStart4) return ERROR(corruption_detected);
1748 /* note : op4 supposed already verified within main loop */
1750 /* finish bitStreams one by one */
1751 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1752 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1753 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1754 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1757 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1758 if (!endSignal) return ERROR(corruption_detected);
1766 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1768 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1769 const BYTE* ip = (const BYTE*) cSrc;
1772 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1773 if (HUF_isError(errorCode)) return errorCode;
1774 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1776 cSrcSize -= errorCode;
1778 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1782 /***************************/
1783 /* double-symbols decoding */
1784 /***************************/
1786 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1787 const U32* rankValOrigin, const int minWeight,
1788 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1789 U32 nbBitsBaseline, U16 baseSeq)
1792 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1795 /* get pre-calculated rankVal */
1796 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1798 /* fill skipped values */
1801 U32 i, skipSize = rankVal[minWeight];
1802 MEM_writeLE16(&(DElt.sequence), baseSeq);
1803 DElt.nbBits = (BYTE)(consumed);
1805 for (i = 0; i < skipSize; i++)
1810 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1812 const U32 symbol = sortedSymbols[s].symbol;
1813 const U32 weight = sortedSymbols[s].weight;
1814 const U32 nbBits = nbBitsBaseline - weight;
1815 const U32 length = 1 << (sizeLog-nbBits);
1816 const U32 start = rankVal[weight];
1818 const U32 end = start + length;
1820 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1821 DElt.nbBits = (BYTE)(nbBits + consumed);
1823 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1825 rankVal[weight] += length;
1829 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1831 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1832 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1833 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1834 const U32 nbBitsBaseline)
1836 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1837 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1838 const U32 minBits = nbBitsBaseline - maxWeight;
1841 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1844 for (s=0; s<sortedListSize; s++)
1846 const U16 symbol = sortedList[s].symbol;
1847 const U32 weight = sortedList[s].weight;
1848 const U32 nbBits = nbBitsBaseline - weight;
1849 const U32 start = rankVal[weight];
1850 const U32 length = 1 << (targetLog-nbBits);
1852 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1855 int minWeight = nbBits + scaleLog;
1856 if (minWeight < 1) minWeight = 1;
1857 sortedRank = rankStart[minWeight];
1858 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1859 rankValOrigin[nbBits], minWeight,
1860 sortedList+sortedRank, sortedListSize-sortedRank,
1861 nbBitsBaseline, symbol);
1866 const U32 end = start + length;
1869 MEM_writeLE16(&(DElt.sequence), symbol);
1870 DElt.nbBits = (BYTE)(nbBits);
1872 for (i = start; i < end; i++)
1875 rankVal[weight] += length;
1879 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1881 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1882 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1883 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1884 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1885 U32* const rankStart = rankStart0+1;
1887 U32 tableLog, maxW, sizeOfSort, nbSymbols;
1888 const U32 memLog = DTable[0];
1889 const BYTE* ip = (const BYTE*) src;
1890 size_t iSize = ip[0];
1892 HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1894 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
1895 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1896 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1898 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1899 if (HUF_isError(iSize)) return iSize;
1902 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
1904 /* find maxWeight */
1905 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1906 {if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
1908 /* Get start index of each weight */
1910 U32 w, nextRankStart = 0;
1911 for (w=1; w<=maxW; w++)
1913 U32 current = nextRankStart;
1914 nextRankStart += rankStats[w];
1915 rankStart[w] = current;
1917 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
1918 sizeOfSort = nextRankStart;
1921 /* sort symbols by weight */
1924 for (s=0; s<nbSymbols; s++)
1926 U32 w = weightList[s];
1927 U32 r = rankStart[w]++;
1928 sortedSymbol[r].symbol = (BYTE)s;
1929 sortedSymbol[r].weight = (BYTE)w;
1931 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1936 const U32 minBits = tableLog+1 - maxW;
1937 U32 nextRankVal = 0;
1939 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
1940 U32* rankVal0 = rankVal[0];
1941 for (w=1; w<=maxW; w++)
1943 U32 current = nextRankVal;
1944 nextRankVal += rankStats[w] << (w+rescale);
1945 rankVal0[w] = current;
1947 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1949 U32* rankValPtr = rankVal[consumed];
1950 for (w = 1; w <= maxW; w++)
1952 rankValPtr[w] = rankVal0[w] >> consumed;
1957 HUF_fillDTableX4(dt, memLog,
1958 sortedSymbol, sizeOfSort,
1959 rankStart0, rankVal, maxW,
1966 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1968 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1969 memcpy(op, dt+val, 2);
1970 BIT_skipBits(DStream, dt[val].nbBits);
1971 return dt[val].length;
1974 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1976 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
1977 memcpy(op, dt+val, 1);
1978 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
1981 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
1983 BIT_skipBits(DStream, dt[val].nbBits);
1984 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
1985 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 */
1992 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
1993 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1995 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
1996 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1997 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1999 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2001 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2003 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2005 BYTE* const pStart = p;
2007 /* up to 8 symbols at a time */
2008 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2010 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2011 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2012 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2013 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2016 /* closer to the end */
2017 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2018 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2021 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2024 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2031 static size_t HUF_decompress4X4_usingDTable(
2032 void* dst, size_t dstSize,
2033 const void* cSrc, size_t cSrcSize,
2036 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2039 const BYTE* const istart = (const BYTE*) cSrc;
2040 BYTE* const ostart = (BYTE*) dst;
2041 BYTE* const oend = ostart + dstSize;
2043 const void* ptr = DTable;
2044 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2045 const U32 dtLog = DTable[0];
2049 BIT_DStream_t bitD1;
2050 BIT_DStream_t bitD2;
2051 BIT_DStream_t bitD3;
2052 BIT_DStream_t bitD4;
2053 const size_t length1 = MEM_readLE16(istart);
2054 const size_t length2 = MEM_readLE16(istart+2);
2055 const size_t length3 = MEM_readLE16(istart+4);
2057 const BYTE* const istart1 = istart + 6; /* jumpTable */
2058 const BYTE* const istart2 = istart1 + length1;
2059 const BYTE* const istart3 = istart2 + length2;
2060 const BYTE* const istart4 = istart3 + length3;
2061 const size_t segmentSize = (dstSize+3) / 4;
2062 BYTE* const opStart2 = ostart + segmentSize;
2063 BYTE* const opStart3 = opStart2 + segmentSize;
2064 BYTE* const opStart4 = opStart3 + segmentSize;
2066 BYTE* op2 = opStart2;
2067 BYTE* op3 = opStart3;
2068 BYTE* op4 = opStart4;
2071 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2072 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2073 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2074 if (HUF_isError(errorCode)) return errorCode;
2075 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2076 if (HUF_isError(errorCode)) return errorCode;
2077 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2078 if (HUF_isError(errorCode)) return errorCode;
2079 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2080 if (HUF_isError(errorCode)) return errorCode;
2082 /* 16-32 symbols per loop (4-8 symbols per stream) */
2083 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2084 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2086 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2087 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2088 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2089 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2090 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2091 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2092 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2093 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2094 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2095 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2096 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2097 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2098 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2099 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2100 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2101 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2103 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2106 /* check corruption */
2107 if (op1 > opStart2) return ERROR(corruption_detected);
2108 if (op2 > opStart3) return ERROR(corruption_detected);
2109 if (op3 > opStart4) return ERROR(corruption_detected);
2110 /* note : op4 supposed already verified within main loop */
2112 /* finish bitStreams one by one */
2113 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2114 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2115 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2116 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2119 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2120 if (!endSignal) return ERROR(corruption_detected);
2128 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2130 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2131 const BYTE* ip = (const BYTE*) cSrc;
2133 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2134 if (HUF_isError(hSize)) return hSize;
2135 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2139 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2143 /**********************************/
2144 /* quad-symbol decoding */
2145 /**********************************/
2146 typedef struct { BYTE nbBits; BYTE nbBytes; } HUF_DDescX6;
2147 typedef union { BYTE byte[4]; U32 sequence; } HUF_DSeqX6;
2149 /* recursive, up to level 3; may benefit from <template>-like strategy to nest each level inline */
2150 static void HUF_fillDTableX6LevelN(HUF_DDescX6* DDescription, HUF_DSeqX6* DSequence, int sizeLog,
2151 const rankVal_t rankValOrigin, const U32 consumed, const int minWeight, const U32 maxWeight,
2152 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, const U32* rankStart,
2153 const U32 nbBitsBaseline, HUF_DSeqX6 baseSeq, HUF_DDescX6 DDesc)
2155 const int scaleLog = nbBitsBaseline - sizeLog; /* note : targetLog >= (nbBitsBaseline-1), hence scaleLog <= 1 */
2156 const int minBits = nbBitsBaseline - maxWeight;
2157 const U32 level = DDesc.nbBytes;
2158 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
2159 U32 symbolStartPos, s;
2161 /* local rankVal, will be modified */
2162 memcpy(rankVal, rankValOrigin[consumed], sizeof(rankVal));
2164 /* fill skipped values */
2168 const U32 skipSize = rankVal[minWeight];
2169 for (i = 0; i < skipSize; i++)
2171 DSequence[i] = baseSeq;
2172 DDescription[i] = DDesc;
2178 symbolStartPos = rankStart[minWeight];
2179 for (s=symbolStartPos; s<sortedListSize; s++)
2181 const BYTE symbol = sortedSymbols[s].symbol;
2182 const U32 weight = sortedSymbols[s].weight; /* >= 1 (sorted) */
2183 const int nbBits = nbBitsBaseline - weight; /* >= 1 (by construction) */
2184 const int totalBits = consumed+nbBits;
2185 const U32 start = rankVal[weight];
2186 const U32 length = 1 << (sizeLog-nbBits);
2187 baseSeq.byte[level] = symbol;
2188 DDesc.nbBits = (BYTE)totalBits;
2190 if ((level<3) && (sizeLog-totalBits >= minBits)) /* enough room for another symbol */
2192 int nextMinWeight = totalBits + scaleLog;
2193 if (nextMinWeight < 1) nextMinWeight = 1;
2194 HUF_fillDTableX6LevelN(DDescription+start, DSequence+start, sizeLog-nbBits,
2195 rankValOrigin, totalBits, nextMinWeight, maxWeight,
2196 sortedSymbols, sortedListSize, rankStart,
2197 nbBitsBaseline, baseSeq, DDesc); /* recursive (max : level 3) */
2202 const U32 end = start + length;
2203 for (i = start; i < end; i++)
2205 DDescription[i] = DDesc;
2206 DSequence[i] = baseSeq;
2209 rankVal[weight] += length;
2214 /* note : same preparation as X4 */
2215 static size_t HUF_readDTableX6 (U32* DTable, const void* src, size_t srcSize)
2217 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
2218 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
2219 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2220 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2221 U32* const rankStart = rankStart0+1;
2222 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2224 const U32 memLog = DTable[0];
2225 const BYTE* ip = (const BYTE*) src;
2226 size_t iSize = ip[0];
2228 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2229 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2231 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2232 if (HUF_isError(iSize)) return iSize;
2235 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable is too small */
2237 /* find maxWeight */
2238 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2239 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
2242 /* Get start index of each weight */
2244 U32 w, nextRankStart = 0;
2245 for (w=1; w<=maxW; w++)
2247 U32 current = nextRankStart;
2248 nextRankStart += rankStats[w];
2249 rankStart[w] = current;
2251 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2252 sizeOfSort = nextRankStart;
2255 /* sort symbols by weight */
2258 for (s=0; s<nbSymbols; s++)
2260 U32 w = weightList[s];
2261 U32 r = rankStart[w]++;
2262 sortedSymbol[r].symbol = (BYTE)s;
2263 sortedSymbol[r].weight = (BYTE)w;
2265 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2270 const U32 minBits = tableLog+1 - maxW;
2271 U32 nextRankVal = 0;
2273 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2274 U32* rankVal0 = rankVal[0];
2275 for (w=1; w<=maxW; w++)
2277 U32 current = nextRankVal;
2278 nextRankVal += rankStats[w] << (w+rescale);
2279 rankVal0[w] = current;
2281 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2283 U32* rankValPtr = rankVal[consumed];
2284 for (w = 1; w <= maxW; w++)
2286 rankValPtr[w] = rankVal0[w] >> consumed;
2294 void* ptr = DTable+1;
2295 HUF_DDescX6* DDescription = (HUF_DDescX6*)(ptr);
2296 void* dSeqStart = DTable + 1 + ((size_t)1<<(memLog-1));
2297 HUF_DSeqX6* DSequence = (HUF_DSeqX6*)(dSeqStart);
2303 HUF_fillDTableX6LevelN(DDescription, DSequence, memLog,
2304 (const U32 (*)[HUF_ABSOLUTEMAX_TABLELOG + 1])rankVal, 0, 1, maxW,
2305 sortedSymbol, sizeOfSort, rankStart0,
2306 tableLog+1, DSeq, DDesc);
2313 static U32 HUF_decodeSymbolX6(void* op, BIT_DStream_t* DStream, const HUF_DDescX6* dd, const HUF_DSeqX6* ds, const U32 dtLog)
2315 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2316 memcpy(op, ds+val, sizeof(HUF_DSeqX6));
2317 BIT_skipBits(DStream, dd[val].nbBits);
2318 return dd[val].nbBytes;
2321 static U32 HUF_decodeLastSymbolsX6(void* op, const U32 maxL, BIT_DStream_t* DStream,
2322 const HUF_DDescX6* dd, const HUF_DSeqX6* ds, const U32 dtLog)
2324 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2325 U32 length = dd[val].nbBytes;
2328 memcpy(op, ds+val, length);
2329 BIT_skipBits(DStream, dd[val].nbBits);
2332 memcpy(op, ds+val, maxL);
2333 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2335 BIT_skipBits(DStream, dd[val].nbBits);
2336 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2337 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 */
2343 #define HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr) \
2344 ptr += HUF_decodeSymbolX6(ptr, DStreamPtr, dd, ds, dtLog)
2346 #define HUF_DECODE_SYMBOLX6_1(ptr, DStreamPtr) \
2347 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2348 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2350 #define HUF_DECODE_SYMBOLX6_2(ptr, DStreamPtr) \
2352 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2354 static inline size_t HUF_decodeStreamX6(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const U32* DTable, const U32 dtLog)
2356 const void* ddPtr = DTable+1;
2357 const HUF_DDescX6* dd = (const HUF_DDescX6*)(ddPtr);
2358 const void* dsPtr = DTable + 1 + ((size_t)1<<(dtLog-1));
2359 const HUF_DSeqX6* ds = (const HUF_DSeqX6*)(dsPtr);
2360 BYTE* const pStart = p;
2362 /* up to 16 symbols at a time */
2363 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-16))
2365 HUF_DECODE_SYMBOLX6_2(p, bitDPtr);
2366 HUF_DECODE_SYMBOLX6_1(p, bitDPtr);
2367 HUF_DECODE_SYMBOLX6_2(p, bitDPtr);
2368 HUF_DECODE_SYMBOLX6_0(p, bitDPtr);
2371 /* closer to the end, up to 4 symbols at a time */
2372 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
2373 HUF_DECODE_SYMBOLX6_0(p, bitDPtr);
2376 HUF_DECODE_SYMBOLX6_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2379 p += HUF_decodeLastSymbolsX6(p, (U32)(pEnd-p), bitDPtr, dd, ds, dtLog);
2386 static size_t HUF_decompress4X6_usingDTable(
2387 void* dst, size_t dstSize,
2388 const void* cSrc, size_t cSrcSize,
2391 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2394 const BYTE* const istart = (const BYTE*) cSrc;
2395 BYTE* const ostart = (BYTE*) dst;
2396 BYTE* const oend = ostart + dstSize;
2398 const U32 dtLog = DTable[0];
2399 const void* ddPtr = DTable+1;
2400 const HUF_DDescX6* dd = (const HUF_DDescX6*)(ddPtr);
2401 const void* dsPtr = DTable + 1 + ((size_t)1<<(dtLog-1));
2402 const HUF_DSeqX6* ds = (const HUF_DSeqX6*)(dsPtr);
2406 BIT_DStream_t bitD1;
2407 BIT_DStream_t bitD2;
2408 BIT_DStream_t bitD3;
2409 BIT_DStream_t bitD4;
2410 const size_t length1 = MEM_readLE16(istart);
2411 const size_t length2 = MEM_readLE16(istart+2);
2412 const size_t length3 = MEM_readLE16(istart+4);
2414 const BYTE* const istart1 = istart + 6; /* jumpTable */
2415 const BYTE* const istart2 = istart1 + length1;
2416 const BYTE* const istart3 = istart2 + length2;
2417 const BYTE* const istart4 = istart3 + length3;
2418 const size_t segmentSize = (dstSize+3) / 4;
2419 BYTE* const opStart2 = ostart + segmentSize;
2420 BYTE* const opStart3 = opStart2 + segmentSize;
2421 BYTE* const opStart4 = opStart3 + segmentSize;
2423 BYTE* op2 = opStart2;
2424 BYTE* op3 = opStart3;
2425 BYTE* op4 = opStart4;
2428 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2429 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2430 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2431 if (HUF_isError(errorCode)) return errorCode;
2432 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2433 if (HUF_isError(errorCode)) return errorCode;
2434 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2435 if (HUF_isError(errorCode)) return errorCode;
2436 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2437 if (HUF_isError(errorCode)) return errorCode;
2439 /* 16-64 symbols per loop (4-16 symbols per stream) */
2440 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2441 for ( ; (op3 <= opStart4) && (endSignal==BIT_DStream_unfinished) && (op4<=(oend-16)) ; )
2443 HUF_DECODE_SYMBOLX6_2(op1, &bitD1);
2444 HUF_DECODE_SYMBOLX6_2(op2, &bitD2);
2445 HUF_DECODE_SYMBOLX6_2(op3, &bitD3);
2446 HUF_DECODE_SYMBOLX6_2(op4, &bitD4);
2447 HUF_DECODE_SYMBOLX6_1(op1, &bitD1);
2448 HUF_DECODE_SYMBOLX6_1(op2, &bitD2);
2449 HUF_DECODE_SYMBOLX6_1(op3, &bitD3);
2450 HUF_DECODE_SYMBOLX6_1(op4, &bitD4);
2451 HUF_DECODE_SYMBOLX6_2(op1, &bitD1);
2452 HUF_DECODE_SYMBOLX6_2(op2, &bitD2);
2453 HUF_DECODE_SYMBOLX6_2(op3, &bitD3);
2454 HUF_DECODE_SYMBOLX6_2(op4, &bitD4);
2455 HUF_DECODE_SYMBOLX6_0(op1, &bitD1);
2456 HUF_DECODE_SYMBOLX6_0(op2, &bitD2);
2457 HUF_DECODE_SYMBOLX6_0(op3, &bitD3);
2458 HUF_DECODE_SYMBOLX6_0(op4, &bitD4);
2460 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2463 /* check corruption */
2464 if (op1 > opStart2) return ERROR(corruption_detected);
2465 if (op2 > opStart3) return ERROR(corruption_detected);
2466 if (op3 > opStart4) return ERROR(corruption_detected);
2467 /* note : op4 supposed already verified within main loop */
2469 /* finish bitStreams one by one */
2470 HUF_decodeStreamX6(op1, &bitD1, opStart2, DTable, dtLog);
2471 HUF_decodeStreamX6(op2, &bitD2, opStart3, DTable, dtLog);
2472 HUF_decodeStreamX6(op3, &bitD3, opStart4, DTable, dtLog);
2473 HUF_decodeStreamX6(op4, &bitD4, oend, DTable, dtLog);
2476 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2477 if (!endSignal) return ERROR(corruption_detected);
2485 static size_t HUF_decompress4X6 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2487 HUF_CREATE_STATIC_DTABLEX6(DTable, HUF_MAX_TABLELOG);
2488 const BYTE* ip = (const BYTE*) cSrc;
2490 size_t hSize = HUF_readDTableX6 (DTable, cSrc, cSrcSize);
2491 if (HUF_isError(hSize)) return hSize;
2492 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2496 return HUF_decompress4X6_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2500 /**********************************/
2501 /* Generic decompression selector */
2502 /**********************************/
2504 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2505 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2507 /* single, double, quad */
2508 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2509 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2510 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2511 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2512 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2513 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2514 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2515 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2516 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2517 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2518 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2519 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2520 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2521 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2522 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2523 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2526 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2528 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2530 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, HUF_decompress4X6 };
2531 /* estimate decompression time */
2533 const U32 D256 = (U32)(dstSize >> 8);
2538 /* validation checks */
2539 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2540 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2541 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2542 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2544 /* decoder timing evaluation */
2545 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2547 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2549 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2551 if (Dtime[1] < Dtime[0]) algoNb = 1;
2552 if (Dtime[2] < Dtime[algoNb]) algoNb = 2;
2554 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2556 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2557 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2558 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2561 zstd - standard compression library
2562 Copyright (C) 2014-2015, Yann Collet.
2564 BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2566 Redistribution and use in source and binary forms, with or without
2567 modification, are permitted provided that the following conditions are
2569 * Redistributions of source code must retain the above copyright
2570 notice, this list of conditions and the following disclaimer.
2571 * Redistributions in binary form must reproduce the above
2572 copyright notice, this list of conditions and the following disclaimer
2573 in the documentation and/or other materials provided with the
2575 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2576 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2577 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2578 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2579 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2580 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2581 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2582 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2583 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2584 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2585 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2587 You can contact the author at :
2588 - zstd source repository : https://github.com/Cyan4973/zstd
2589 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2592 /* ***************************************************************
2594 *****************************************************************/
2597 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2598 * Increasing memory usage improves compression ratio
2599 * Reduced memory usage can improve speed, due to cache effect
2601 #define ZSTD_MEMORY_USAGE 17
2605 * Select how default compression functions will allocate memory for their hash table,
2606 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2607 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2609 #ifndef ZSTD_HEAPMODE
2610 # define ZSTD_HEAPMODE 1
2611 #endif /* ZSTD_HEAPMODE */
2615 * decompressor can decode older formats (starting from Zstd 0.1+)
2617 #ifndef ZSTD_LEGACY_SUPPORT
2618 # define ZSTD_LEGACY_SUPPORT 1
2622 /* *******************************************************
2624 *********************************************************/
2625 #include <stdlib.h> /* calloc */
2626 #include <string.h> /* memcpy, memmove */
2627 #include <stdio.h> /* debug : printf */
2630 /* *******************************************************
2631 * Compiler specifics
2632 *********************************************************/
2634 # include <immintrin.h> /* AVX2 intrinsics */
2637 #ifdef _MSC_VER /* Visual Studio */
2638 # include <intrin.h> /* For Visual 2005 */
2639 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2640 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2644 /* *******************************************************
2646 *********************************************************/
2647 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2648 #define HASH_TABLESIZE (1 << HASH_LOG)
2649 #define HASH_MASK (HASH_TABLESIZE - 1)
2651 #define KNUTH 2654435761
2660 #define KB *(1 <<10)
2661 #define MB *(1 <<20)
2662 #define GB *(1U<<30)
2664 #define BLOCKSIZE (128 KB) /* define, for static allocation */
2665 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2666 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2670 #define WORKPLACESIZE (BLOCKSIZE*3)
2675 #define MaxML ((1<<MLbits )-1)
2676 #define MaxLL ((1<<LLbits )-1)
2678 #define LitFSELog 11
2682 #define MAX(a,b) ((a)<(b)?(b):(a))
2683 #define MaxSeq MAX(MaxLL, MaxML)
2685 #define LITERAL_NOENTROPY 63
2686 #define COMMAND_NOENTROPY 7 /* to remove */
2688 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2690 static const size_t ZSTD_blockHeaderSize = 3;
2691 static const size_t ZSTD_frameHeaderSize = 4;
2694 /* *******************************************************
2696 **********************************************************/
2697 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2699 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2701 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2703 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2704 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2706 const BYTE* ip = (const BYTE*)src;
2707 BYTE* op = (BYTE*)dst;
2708 BYTE* const oend = op + length;
2709 do COPY8(op, ip) while (op < oend);
2713 /* **************************************
2715 ****************************************/
2716 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2720 blockType_t blockType;
2722 } blockProperties_t;
2732 BYTE* litLengthStart;
2734 BYTE* matchLengthStart;
2741 /* *************************************
2743 ***************************************/
2745 * tells if a return value is an error code */
2746 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2750 /* *************************************************************
2751 * Decompression section
2752 ***************************************************************/
2755 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2756 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2757 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2758 void* previousDstEnd;
2765 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2766 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2769 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2771 const BYTE* const in = (const BYTE* const)src;
2775 if (srcSize < 3) return ERROR(srcSize_wrong);
2778 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2780 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2781 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2783 if (bpPtr->blockType == bt_end) return 0;
2784 if (bpPtr->blockType == bt_rle) return 1;
2788 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2790 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2792 memcpy(dst, src, srcSize);
2798 /** ZSTD_decompressLiterals
2799 @return : nb of bytes read from src, or an error code*/
2800 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2801 const void* src, size_t srcSize)
2803 const BYTE* ip = (const BYTE*)src;
2805 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2806 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2808 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2809 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2811 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2813 *maxDstSizePtr = litSize;
2814 return litCSize + 5;
2818 /** ZSTD_decodeLiteralsBlock
2819 @return : nb of bytes read from src (< srcSize )*/
2820 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2821 const void* src, size_t srcSize)
2823 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2824 const BYTE* const istart = (const BYTE* const)src;
2826 /* any compressed block with literals segment must be at least this size */
2827 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2834 size_t litSize = BLOCKSIZE;
2835 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2836 dctx->litPtr = dctx->litBuffer;
2837 dctx->litSize = litSize;
2838 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2839 return readSize; /* works if it's an error too */
2843 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2844 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2846 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2847 if (litSize > srcSize-3) return ERROR(corruption_detected);
2848 memcpy(dctx->litBuffer, istart, litSize);
2849 dctx->litPtr = dctx->litBuffer;
2850 dctx->litSize = litSize;
2851 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2854 /* direct reference into compressed stream */
2855 dctx->litPtr = istart+3;
2856 dctx->litSize = litSize;
2861 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2862 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2863 memset(dctx->litBuffer, istart[3], litSize + 8);
2864 dctx->litPtr = dctx->litBuffer;
2865 dctx->litSize = litSize;
2872 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2873 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2874 const void* src, size_t srcSize)
2876 const BYTE* const istart = (const BYTE* const)src;
2877 const BYTE* ip = istart;
2878 const BYTE* const iend = istart + srcSize;
2879 U32 LLtype, Offtype, MLtype;
2880 U32 LLlog, Offlog, MLlog;
2884 if (srcSize < 5) return ERROR(srcSize_wrong);
2887 *nbSeq = MEM_readLE16(ip); ip+=2;
2889 Offtype = (*ip >> 4) & 3;
2890 MLtype = (*ip >> 2) & 3;
2893 dumpsLength = ip[2];
2894 dumpsLength += ip[1] << 8;
2899 dumpsLength = ip[1];
2900 dumpsLength += (ip[0] & 1) << 8;
2905 *dumpsLengthPtr = dumpsLength;
2908 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2912 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2920 FSE_buildDTable_rle(DTableLL, *ip++); break;
2923 FSE_buildDTable_raw(DTableLL, LLbits); break;
2926 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2927 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2928 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2930 FSE_buildDTable(DTableLL, norm, max, LLlog);
2937 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2938 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2942 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2945 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2946 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2947 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2949 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2956 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2957 FSE_buildDTable_rle(DTableML, *ip++); break;
2960 FSE_buildDTable_raw(DTableML, MLbits); break;
2963 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2964 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2965 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2967 FSE_buildDTable(DTableML, norm, max, MLlog);
2981 BIT_DStream_t DStream;
2982 FSE_DState_t stateLL;
2983 FSE_DState_t stateOffb;
2984 FSE_DState_t stateML;
2987 const BYTE* dumpsEnd;
2991 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2997 const BYTE* dumps = seqState->dumps;
2998 const BYTE* const de = seqState->dumpsEnd;
3000 /* Literal length */
3001 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
3002 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3003 seqState->prevOffset = seq->offset;
3004 if (litLength == MaxLL)
3006 const U32 add = dumps<de ? *dumps++ : 0;
3007 if (add < 255) litLength += add;
3008 else if (dumps + 3 <= de)
3010 litLength = MEM_readLE24(dumps);
3013 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3018 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
3019 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3020 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3021 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3022 U32 offsetCode, nbBits;
3023 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
3024 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3025 nbBits = offsetCode - 1;
3026 if (offsetCode==0) nbBits = 0; /* cmove */
3027 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
3028 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3029 if (offsetCode==0) offset = prevOffset; /* cmove */
3033 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3034 if (matchLength == MaxML)
3036 const U32 add = dumps<de ? *dumps++ : 0;
3037 if (add < 255) matchLength += add;
3038 else if (dumps + 3 <= de)
3040 matchLength = MEM_readLE24(dumps);
3043 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3045 matchLength += MINMATCH;
3048 seq->litLength = litLength;
3049 seq->offset = offset;
3050 seq->matchLength = matchLength;
3051 seqState->dumps = dumps;
3055 static size_t ZSTD_execSequence(BYTE* op,
3057 const BYTE** litPtr, const BYTE* const litLimit,
3058 BYTE* const base, BYTE* const oend)
3060 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
3061 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */
3062 const BYTE* const ostart = op;
3063 BYTE* const oLitEnd = op + sequence.litLength;
3064 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
3065 BYTE* const oend_8 = oend-8;
3066 const BYTE* const litEnd = *litPtr + sequence.litLength;
3069 size_t const seqLength = sequence.litLength + sequence.matchLength;
3071 if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3072 if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
3073 /* Now we know there are no overflow in literal nor match lengths, can use the pointer check */
3074 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
3075 if (sequence.offset > (U32)(oLitEnd - base)) return ERROR(corruption_detected);
3077 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3078 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
3081 ZSTD_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3083 *litPtr = litEnd; /* update for next sequence */
3087 const BYTE* match = op - sequence.offset;
3090 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
3091 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
3092 if (match < base) return ERROR(corruption_detected);
3094 /* close range match, overlap */
3095 if (sequence.offset < 8)
3097 const int dec64 = dec64table[sequence.offset];
3102 match += dec32table[sequence.offset];
3103 ZSTD_copy4(op+4, match);
3108 ZSTD_copy8(op, match);
3110 op += 8; match += 8;
3112 if (oMatchEnd > oend-(16-MINMATCH))
3116 ZSTD_wildcopy(op, match, oend_8 - op);
3117 match += oend_8 - op;
3120 while (op < oMatchEnd) *op++ = *match++;
3124 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3128 return oMatchEnd - ostart;
3131 static size_t ZSTD_decompressSequences(
3133 void* dst, size_t maxDstSize,
3134 const void* seqStart, size_t seqSize)
3136 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
3137 const BYTE* ip = (const BYTE*)seqStart;
3138 const BYTE* const iend = ip + seqSize;
3139 BYTE* const ostart = (BYTE* const)dst;
3141 BYTE* const oend = ostart + maxDstSize;
3142 size_t errorCode, dumpsLength;
3143 const BYTE* litPtr = dctx->litPtr;
3144 const BYTE* const litEnd = litPtr + dctx->litSize;
3147 U32* DTableLL = dctx->LLTable;
3148 U32* DTableML = dctx->MLTable;
3149 U32* DTableOffb = dctx->OffTable;
3150 BYTE* const base = (BYTE*) (dctx->base);
3152 /* Build Decoding Tables */
3153 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3154 DTableLL, DTableML, DTableOffb,
3156 if (ZSTD_isError(errorCode)) return errorCode;
3159 /* Regen sequences */
3162 seqState_t seqState;
3164 memset(&sequence, 0, sizeof(sequence));
3165 seqState.dumps = dumps;
3166 seqState.dumpsEnd = dumps + dumpsLength;
3167 seqState.prevOffset = 1;
3168 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
3169 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3170 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3171 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3172 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3174 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
3178 ZSTD_decodeSequence(&sequence, &seqState);
3179 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
3180 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
3184 /* check if reached exact end */
3185 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
3186 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
3188 /* last literal segment */
3190 size_t lastLLSize = litEnd - litPtr;
3191 if (litPtr > litEnd) return ERROR(corruption_detected);
3192 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3193 if (lastLLSize > 0) {
3194 if (op != litPtr) memmove(op, litPtr, lastLLSize);
3204 static size_t ZSTD_decompressBlock(
3206 void* dst, size_t maxDstSize,
3207 const void* src, size_t srcSize)
3209 /* blockType == blockCompressed */
3210 const BYTE* ip = (const BYTE*)src;
3212 /* Decode literals sub-block */
3213 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
3214 if (ZSTD_isError(litCSize)) return litCSize;
3216 srcSize -= litCSize;
3218 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
3222 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3224 const BYTE* ip = (const BYTE*)src;
3225 const BYTE* iend = ip + srcSize;
3226 BYTE* const ostart = (BYTE* const)dst;
3228 BYTE* const oend = ostart + maxDstSize;
3229 size_t remainingSize = srcSize;
3231 blockProperties_t blockProperties;
3234 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3235 magicNumber = MEM_readLE32(src);
3236 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3237 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
3239 /* Loop on each block */
3242 size_t decodedSize=0;
3243 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
3244 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3246 ip += ZSTD_blockHeaderSize;
3247 remainingSize -= ZSTD_blockHeaderSize;
3248 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3250 switch(blockProperties.blockType)
3253 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
3256 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
3259 return ERROR(GENERIC); /* not yet supported */
3263 if (remainingSize) return ERROR(srcSize_wrong);
3266 return ERROR(GENERIC); /* impossible */
3268 if (cBlockSize == 0) break; /* bt_end */
3270 if (ZSTD_isError(decodedSize)) return decodedSize;
3273 remainingSize -= cBlockSize;
3279 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3283 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
3286 /* ZSTD_errorFrameSizeInfoLegacy() :
3287 assumes `cSize` and `dBound` are _not_ NULL */
3288 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3291 *dBound = ZSTD_CONTENTSIZE_ERROR;
3294 void ZSTDv02_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3296 const BYTE* ip = (const BYTE*)src;
3297 size_t remainingSize = srcSize;
3298 size_t nbBlocks = 0;
3300 blockProperties_t blockProperties;
3303 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
3304 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3307 magicNumber = MEM_readLE32(src);
3308 if (magicNumber != ZSTD_magicNumber) {
3309 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3312 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
3314 /* Loop on each block */
3317 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
3318 if (ZSTD_isError(cBlockSize)) {
3319 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3323 ip += ZSTD_blockHeaderSize;
3324 remainingSize -= ZSTD_blockHeaderSize;
3325 if (cBlockSize > remainingSize) {
3326 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3330 if (cBlockSize == 0) break; /* bt_end */
3333 remainingSize -= cBlockSize;
3337 *cSize = ip - (const BYTE*)src;
3338 *dBound = nbBlocks * BLOCKSIZE;
3341 /*******************************
3342 * Streaming Decompression API
3343 *******************************/
3345 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
3347 dctx->expected = ZSTD_frameHeaderSize;
3349 dctx->previousDstEnd = NULL;
3354 static ZSTD_DCtx* ZSTD_createDCtx(void)
3356 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
3357 if (dctx==NULL) return NULL;
3358 ZSTD_resetDCtx(dctx);
3362 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3368 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3370 return dctx->expected;
3373 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3376 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3377 if (dst != ctx->previousDstEnd) /* not contiguous */
3380 /* Decompress : frame header */
3381 if (ctx->phase == 0)
3383 /* Check frame magic header */
3384 U32 magicNumber = MEM_readLE32(src);
3385 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3387 ctx->expected = ZSTD_blockHeaderSize;
3391 /* Decompress : block header */
3392 if (ctx->phase == 1)
3394 blockProperties_t bp;
3395 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3396 if (ZSTD_isError(blockSize)) return blockSize;
3397 if (bp.blockType == bt_end)
3404 ctx->expected = blockSize;
3405 ctx->bType = bp.blockType;
3412 /* Decompress : block content */
3418 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3421 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3424 return ERROR(GENERIC); /* not yet handled */
3426 case bt_end : /* should never happen (filtered at phase 1) */
3430 return ERROR(GENERIC);
3433 ctx->expected = ZSTD_blockHeaderSize;
3434 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3443 unsigned ZSTDv02_isError(size_t code)
3445 return ZSTD_isError(code);
3448 size_t ZSTDv02_decompress( void* dst, size_t maxOriginalSize,
3449 const void* src, size_t compressedSize)
3451 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3454 ZSTDv02_Dctx* ZSTDv02_createDCtx(void)
3456 return (ZSTDv02_Dctx*)ZSTD_createDCtx();
3459 size_t ZSTDv02_freeDCtx(ZSTDv02_Dctx* dctx)
3461 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3464 size_t ZSTDv02_resetDCtx(ZSTDv02_Dctx* dctx)
3466 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3469 size_t ZSTDv02_nextSrcSizeToDecompress(ZSTDv02_Dctx* dctx)
3471 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3474 size_t ZSTDv02_decompressContinue(ZSTDv02_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3476 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);