2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
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 "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 (http://www.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 */)
101 typedef unsigned char BYTE;
102 typedef unsigned short U16;
103 typedef signed short S16;
104 typedef unsigned int U32;
105 typedef signed int S32;
106 typedef unsigned long long U64;
107 typedef signed long long S64;
111 /****************************************************************
113 *****************************************************************/
114 /* MEM_FORCE_MEMORY_ACCESS
115 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
116 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
117 * The below switch allow to select different access method for improved performance.
118 * Method 0 (default) : use `memcpy()`. Safe and portable.
119 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
120 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
121 * Method 2 : direct access. This method is portable but violate C standard.
122 * It can generate buggy code on targets generating assembly depending on alignment.
123 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
124 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
125 * Prefer these methods in priority order (0 > 1 > 2)
127 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
128 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
129 # define MEM_FORCE_MEMORY_ACCESS 2
130 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
131 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
132 # define MEM_FORCE_MEMORY_ACCESS 1
136 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
137 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
139 MEM_STATIC unsigned MEM_isLittleEndian(void)
141 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
145 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
147 /* violates C standard on structure alignment.
148 Only use if no other choice to achieve best performance on target platform */
149 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
150 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
151 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
153 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
155 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
157 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
158 /* currently only defined for gcc and icc */
159 typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;
161 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
162 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
163 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
165 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
169 /* default method, safe and standard.
170 can sometimes prove slower */
172 MEM_STATIC U16 MEM_read16(const void* memPtr)
174 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
177 MEM_STATIC U32 MEM_read32(const void* memPtr)
179 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
182 MEM_STATIC U64 MEM_read64(const void* memPtr)
184 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
187 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
189 memcpy(memPtr, &value, sizeof(value));
192 #endif // MEM_FORCE_MEMORY_ACCESS
195 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
197 if (MEM_isLittleEndian())
198 return MEM_read16(memPtr);
201 const BYTE* p = (const BYTE*)memPtr;
202 return (U16)(p[0] + (p[1]<<8));
206 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
208 if (MEM_isLittleEndian())
210 MEM_write16(memPtr, val);
214 BYTE* p = (BYTE*)memPtr;
216 p[1] = (BYTE)(val>>8);
220 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
222 if (MEM_isLittleEndian())
223 return MEM_read32(memPtr);
226 const BYTE* p = (const BYTE*)memPtr;
227 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
232 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
234 if (MEM_isLittleEndian())
235 return MEM_read64(memPtr);
238 const BYTE* p = (const BYTE*)memPtr;
239 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
240 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
245 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
248 return (size_t)MEM_readLE32(memPtr);
250 return (size_t)MEM_readLE64(memPtr);
253 #if defined (__cplusplus)
257 #endif /* MEM_H_MODULE */
260 /* ******************************************************************
262 Part of NewGen Entropy library
263 header file (to include)
264 Copyright (C) 2013-2015, Yann Collet.
266 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
268 Redistribution and use in source and binary forms, with or without
269 modification, are permitted provided that the following conditions are
272 * Redistributions of source code must retain the above copyright
273 notice, this list of conditions and the following disclaimer.
274 * Redistributions in binary form must reproduce the above
275 copyright notice, this list of conditions and the following disclaimer
276 in the documentation and/or other materials provided with the
279 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
280 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
281 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
282 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
283 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
284 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
285 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
286 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
287 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
288 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
289 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
291 You can contact the author at :
292 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
293 - Public forum : https://groups.google.com/forum/#!forum/lz4c
294 ****************************************************************** */
295 #ifndef BITSTREAM_H_MODULE
296 #define BITSTREAM_H_MODULE
298 #if defined (__cplusplus)
304 * This API consists of small unitary functions, which highly benefit from being inlined.
305 * Since link-time-optimization is not available for all compilers,
306 * these functions are defined into a .h to be included.
310 /**********************************************
311 * bitStream decompression API (read backward)
312 **********************************************/
316 unsigned bitsConsumed;
321 typedef enum { BIT_DStream_unfinished = 0,
322 BIT_DStream_endOfBuffer = 1,
323 BIT_DStream_completed = 2,
324 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
325 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
327 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
328 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
329 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
330 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
333 /******************************************
335 ******************************************/
336 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
337 /* faster, but works only if nbBits >= 1 */
341 /****************************************************************
343 ****************************************************************/
344 MEM_STATIC unsigned BIT_highbit32 (U32 val)
346 # if defined(_MSC_VER) /* Visual */
348 _BitScanReverse ( &r, val );
350 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
351 return 31 - __builtin_clz (val);
352 # else /* Software version */
353 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 };
361 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
368 /**********************************************************
370 **********************************************************/
373 * Initialize a BIT_DStream_t.
374 * @bitD : a pointer to an already allocated BIT_DStream_t structure
375 * @srcBuffer must point at the beginning of a bitStream
376 * @srcSize must be the exact size of the bitStream
377 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
379 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
381 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
383 if (srcSize >= sizeof(size_t)) /* normal case */
386 bitD->start = (const char*)srcBuffer;
387 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
388 bitD->bitContainer = MEM_readLEST(bitD->ptr);
389 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
390 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
391 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
396 bitD->start = (const char*)srcBuffer;
397 bitD->ptr = bitD->start;
398 bitD->bitContainer = *(const BYTE*)(bitD->start);
401 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
402 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
403 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
404 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
405 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
406 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
409 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
410 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
411 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
412 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
418 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
420 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
421 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
424 /*! BIT_lookBitsFast :
425 * unsafe version; only works only if nbBits >= 1 */
426 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
428 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
429 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
432 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
434 bitD->bitsConsumed += nbBits;
437 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
439 size_t value = BIT_lookBits(bitD, nbBits);
440 BIT_skipBits(bitD, nbBits);
444 /*!BIT_readBitsFast :
445 * unsafe version; only works only if nbBits >= 1 */
446 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
448 size_t value = BIT_lookBitsFast(bitD, nbBits);
449 BIT_skipBits(bitD, nbBits);
453 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
455 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
456 return BIT_DStream_overflow;
458 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
460 bitD->ptr -= bitD->bitsConsumed >> 3;
461 bitD->bitsConsumed &= 7;
462 bitD->bitContainer = MEM_readLEST(bitD->ptr);
463 return BIT_DStream_unfinished;
465 if (bitD->ptr == bitD->start)
467 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
468 return BIT_DStream_completed;
471 U32 nbBytes = bitD->bitsConsumed >> 3;
472 BIT_DStream_status result = BIT_DStream_unfinished;
473 if (bitD->ptr - nbBytes < bitD->start)
475 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
476 result = BIT_DStream_endOfBuffer;
478 bitD->ptr -= nbBytes;
479 bitD->bitsConsumed -= nbBytes*8;
480 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
486 * @return Tells if DStream has reached its exact end
488 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
490 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
493 #if defined (__cplusplus)
497 #endif /* BITSTREAM_H_MODULE */
498 /* ******************************************************************
499 Error codes and messages
500 Copyright (C) 2013-2015, Yann Collet
502 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
504 Redistribution and use in source and binary forms, with or without
505 modification, are permitted provided that the following conditions are
508 * Redistributions of source code must retain the above copyright
509 notice, this list of conditions and the following disclaimer.
510 * Redistributions in binary form must reproduce the above
511 copyright notice, this list of conditions and the following disclaimer
512 in the documentation and/or other materials provided with the
515 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
516 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
517 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
518 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
519 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
520 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
521 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
522 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
523 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
524 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
525 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
527 You can contact the author at :
528 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
529 - Public forum : https://groups.google.com/forum/#!forum/lz4c
530 ****************************************************************** */
531 #ifndef ERROR_H_MODULE
532 #define ERROR_H_MODULE
534 #if defined (__cplusplus)
539 /******************************************
541 ******************************************/
542 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
543 # define ERR_STATIC static inline
544 #elif defined(_MSC_VER)
545 # define ERR_STATIC static __inline
546 #elif defined(__GNUC__)
547 # define ERR_STATIC static __attribute__((unused))
549 # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
553 /******************************************
555 ******************************************/
556 #define PREFIX(name) ZSTD_error_##name
558 #define ERROR(name) (size_t)-PREFIX(name)
560 #define ERROR_LIST(ITEM) \
561 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
562 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
563 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
564 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
565 ITEM(PREFIX(maxCode))
567 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
568 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
570 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
571 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
572 static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
574 ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
576 ERR_STATIC const char* ERR_getErrorName(size_t code)
578 static const char* codeError = "Unspecified error code";
579 if (ERR_isError(code)) return ERR_strings[-(int)(code)];
584 #if defined (__cplusplus)
588 #endif /* ERROR_H_MODULE */
590 Constructor and Destructor of type FSE_CTable
591 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
592 typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
593 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
596 /* ******************************************************************
597 FSE : Finite State Entropy coder
598 header file for static linking (only)
599 Copyright (C) 2013-2015, Yann Collet
601 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
603 Redistribution and use in source and binary forms, with or without
604 modification, are permitted provided that the following conditions are
607 * Redistributions of source code must retain the above copyright
608 notice, this list of conditions and the following disclaimer.
609 * Redistributions in binary form must reproduce the above
610 copyright notice, this list of conditions and the following disclaimer
611 in the documentation and/or other materials provided with the
614 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
615 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
616 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
617 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
618 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
619 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
620 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
621 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
622 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
623 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
624 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
626 You can contact the author at :
627 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
628 - Public forum : https://groups.google.com/forum/#!forum/lz4c
629 ****************************************************************** */
630 #if defined (__cplusplus)
635 /******************************************
637 ******************************************/
638 /* FSE buffer bounds */
639 #define FSE_NCOUNTBOUND 512
640 #define FSE_BLOCKBOUND(size) (size + (size>>7))
641 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
643 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
644 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
645 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
648 /******************************************
650 ******************************************/
651 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
652 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
654 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
655 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
658 /******************************************
659 * FSE symbol decompression API
660 ******************************************/
664 const void* table; /* precise table may vary, depending on U16 */
668 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
670 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
672 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
675 /******************************************
677 ******************************************/
678 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
679 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
682 /******************************************
683 * Implementation of inline functions
684 ******************************************/
691 } FSE_DTableHeader; /* sizeof U32 */
695 unsigned short newState;
696 unsigned char symbol;
697 unsigned char nbBits;
698 } FSE_decode_t; /* size == U32 */
700 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
702 FSE_DTableHeader DTableH;
703 memcpy(&DTableH, dt, sizeof(DTableH));
704 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
705 BIT_reloadDStream(bitD);
706 DStatePtr->table = dt + 1;
709 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
711 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
712 const U32 nbBits = DInfo.nbBits;
713 BYTE symbol = DInfo.symbol;
714 size_t lowBits = BIT_readBits(bitD, nbBits);
716 DStatePtr->state = DInfo.newState + lowBits;
720 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
722 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
723 const U32 nbBits = DInfo.nbBits;
724 BYTE symbol = DInfo.symbol;
725 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
727 DStatePtr->state = DInfo.newState + lowBits;
731 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
733 return DStatePtr->state == 0;
737 #if defined (__cplusplus)
740 /* ******************************************************************
741 Huff0 : Huffman coder, part of New Generation Entropy library
742 header file for static linking (only)
743 Copyright (C) 2013-2015, Yann Collet
745 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
747 Redistribution and use in source and binary forms, with or without
748 modification, are permitted provided that the following conditions are
751 * Redistributions of source code must retain the above copyright
752 notice, this list of conditions and the following disclaimer.
753 * Redistributions in binary form must reproduce the above
754 copyright notice, this list of conditions and the following disclaimer
755 in the documentation and/or other materials provided with the
758 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
759 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
760 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
761 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
762 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
763 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
764 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
765 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
766 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
767 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
768 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
770 You can contact the author at :
771 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
772 - Public forum : https://groups.google.com/forum/#!forum/lz4c
773 ****************************************************************** */
775 #if defined (__cplusplus)
779 /******************************************
780 * Static allocation macros
781 ******************************************/
782 /* Huff0 buffer bounds */
783 #define HUF_CTABLEBOUND 129
784 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
785 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
787 /* static allocation of Huff0's DTable */
788 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
789 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
790 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
791 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
792 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
793 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
794 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
797 /******************************************
799 ******************************************/
800 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
801 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
802 static size_t HUF_decompress4X6 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* quad-symbols decoder */
805 #if defined (__cplusplus)
810 zstd - standard compression library
812 Copyright (C) 2014-2015, Yann Collet.
814 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
816 Redistribution and use in source and binary forms, with or without
817 modification, are permitted provided that the following conditions are
819 * Redistributions of source code must retain the above copyright
820 notice, this list of conditions and the following disclaimer.
821 * Redistributions in binary form must reproduce the above
822 copyright notice, this list of conditions and the following disclaimer
823 in the documentation and/or other materials provided with the
825 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
826 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
827 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
828 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
829 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
830 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
831 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
832 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
833 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
834 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
835 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
837 You can contact the author at :
838 - zstd source repository : https://github.com/Cyan4973/zstd
839 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
842 #if defined (__cplusplus)
846 /* *************************************
848 ***************************************/
849 #include <stddef.h> /* size_t */
852 /* *************************************
854 ***************************************/
855 #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
856 #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
857 #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
858 #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
861 /* *************************************
863 ***************************************/
864 typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */
866 #if defined (__cplusplus)
870 zstd - standard compression library
871 Header File for static linking only
872 Copyright (C) 2014-2015, Yann Collet.
874 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
876 Redistribution and use in source and binary forms, with or without
877 modification, are permitted provided that the following conditions are
879 * Redistributions of source code must retain the above copyright
880 notice, this list of conditions and the following disclaimer.
881 * Redistributions in binary form must reproduce the above
882 copyright notice, this list of conditions and the following disclaimer
883 in the documentation and/or other materials provided with the
885 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
886 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
887 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
888 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
889 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
890 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
891 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
892 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
893 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
894 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
895 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
897 You can contact the author at :
898 - zstd source repository : https://github.com/Cyan4973/zstd
899 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
902 /* The objects defined into this file should be considered experimental.
903 * They are not labelled stable, as their prototype may change in the future.
904 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
907 #if defined (__cplusplus)
911 /* *************************************
912 * Streaming functions
913 ***************************************/
915 typedef struct ZSTD_DCtx_s ZSTD_DCtx;
918 Use above functions alternatively.
919 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
920 ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
921 Result is the number of bytes regenerated within 'dst'.
922 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
925 /* *************************************
926 * Prefix - version detection
927 ***************************************/
928 #define ZSTD_magicNumber 0xFD2FB522 /* v0.2 (current)*/
931 #if defined (__cplusplus)
934 /* ******************************************************************
935 FSE : Finite State Entropy coder
936 Copyright (C) 2013-2015, Yann Collet.
938 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
940 Redistribution and use in source and binary forms, with or without
941 modification, are permitted provided that the following conditions are
944 * Redistributions of source code must retain the above copyright
945 notice, this list of conditions and the following disclaimer.
946 * Redistributions in binary form must reproduce the above
947 copyright notice, this list of conditions and the following disclaimer
948 in the documentation and/or other materials provided with the
951 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
952 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
953 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
954 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
955 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
956 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
957 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
958 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
959 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
960 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
961 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
963 You can contact the author at :
964 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
965 - Public forum : https://groups.google.com/forum/#!forum/lz4c
966 ****************************************************************** */
968 #ifndef FSE_COMMONDEFS_ONLY
970 /****************************************************************
972 ****************************************************************/
974 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
975 * Increasing memory usage improves compression ratio
976 * Reduced memory usage can improve speed, due to cache effect
977 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
978 #define FSE_MAX_MEMORY_USAGE 14
979 #define FSE_DEFAULT_MEMORY_USAGE 13
981 /* FSE_MAX_SYMBOL_VALUE :
982 * Maximum symbol value authorized.
983 * Required for proper stack allocation */
984 #define FSE_MAX_SYMBOL_VALUE 255
987 /****************************************************************
988 * template functions type & suffix
989 ****************************************************************/
990 #define FSE_FUNCTION_TYPE BYTE
991 #define FSE_FUNCTION_EXTENSION
994 /****************************************************************
996 ****************************************************************/
997 #endif /* !FSE_COMMONDEFS_ONLY */
1000 /****************************************************************
1001 * Compiler specifics
1002 ****************************************************************/
1003 #ifdef _MSC_VER /* Visual Studio */
1004 # define FORCE_INLINE static __forceinline
1005 # include <intrin.h> /* For Visual 2005 */
1006 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1007 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1009 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1011 # define FORCE_INLINE static inline __attribute__((always_inline))
1013 # define FORCE_INLINE static inline
1016 # define FORCE_INLINE static
1017 # endif /* __STDC_VERSION__ */
1021 /****************************************************************
1023 ****************************************************************/
1024 #include <stdlib.h> /* malloc, free, qsort */
1025 #include <string.h> /* memcpy, memset */
1026 #include <stdio.h> /* printf (debug) */
1028 /****************************************************************
1030 *****************************************************************/
1031 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
1032 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
1033 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
1034 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
1035 #define FSE_MIN_TABLELOG 5
1037 #define FSE_TABLELOG_ABSOLUTE_MAX 15
1038 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1039 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1043 /****************************************************************
1045 ****************************************************************/
1046 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1049 /****************************************************************
1051 ****************************************************************/
1052 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1055 /****************************************************************
1057 ****************************************************************/
1059 designed to be included
1060 for type-specific functions (template emulation in C)
1061 Objective is to write these functions only once, for improved maintenance
1065 #ifndef FSE_FUNCTION_EXTENSION
1066 # error "FSE_FUNCTION_EXTENSION must be defined"
1068 #ifndef FSE_FUNCTION_TYPE
1069 # error "FSE_FUNCTION_TYPE must be defined"
1072 /* Function names */
1073 #define FSE_CAT(X,Y) X##Y
1074 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1075 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1078 /* Function templates */
1080 #define FSE_DECODE_TYPE FSE_decode_t
1082 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1084 static size_t FSE_buildDTable
1085 (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1088 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1089 FSE_DTableHeader DTableH;
1090 const U32 tableSize = 1 << tableLog;
1091 const U32 tableMask = tableSize-1;
1092 const U32 step = FSE_tableStep(tableSize);
1093 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1095 U32 highThreshold = tableSize-1;
1096 const S16 largeLimit= (S16)(1 << (tableLog-1));
1101 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1102 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1104 /* Init, lay down lowprob symbols */
1105 DTableH.tableLog = (U16)tableLog;
1106 for (s=0; s<=maxSymbolValue; s++)
1108 if (normalizedCounter[s]==-1)
1110 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1115 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1116 symbolNext[s] = normalizedCounter[s];
1120 /* Spread symbols */
1121 for (s=0; s<=maxSymbolValue; s++)
1124 for (i=0; i<normalizedCounter[s]; i++)
1126 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1127 position = (position + step) & tableMask;
1128 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1132 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1134 /* Build Decoding table */
1137 for (i=0; i<tableSize; i++)
1139 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1140 U16 nextState = symbolNext[symbol]++;
1141 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1142 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1146 DTableH.fastMode = (U16)noLarge;
1147 memcpy(dt, &DTableH, sizeof(DTableH)); /* memcpy(), to avoid strict aliasing warnings */
1152 #ifndef FSE_COMMONDEFS_ONLY
1153 /******************************************
1154 * FSE helper functions
1155 ******************************************/
1156 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1159 /****************************************************************
1160 * FSE NCount encoding-decoding
1161 ****************************************************************/
1162 static short FSE_abs(short a)
1164 return (short)(a<0 ? -a : a);
1167 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1168 const void* headerBuffer, size_t hbSize)
1170 const BYTE* const istart = (const BYTE*) headerBuffer;
1171 const BYTE* const iend = istart + hbSize;
1172 const BYTE* ip = istart;
1178 unsigned charnum = 0;
1181 if (hbSize < 4) return ERROR(srcSize_wrong);
1182 bitStream = MEM_readLE32(ip);
1183 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1184 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1187 *tableLogPtr = nbBits;
1188 remaining = (1<<nbBits)+1;
1189 threshold = 1<<nbBits;
1192 while ((remaining>1) && (charnum<=*maxSVPtr))
1196 unsigned n0 = charnum;
1197 while ((bitStream & 0xFFFF) == 0xFFFF)
1203 bitStream = MEM_readLE32(ip) >> bitCount;
1211 while ((bitStream & 3) == 3)
1217 n0 += bitStream & 3;
1219 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1220 while (charnum < n0) normalizedCounter[charnum++] = 0;
1221 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1225 bitStream = MEM_readLE32(ip) >> bitCount;
1231 const short max = (short)((2*threshold-1)-remaining);
1234 if ((bitStream & (threshold-1)) < (U32)max)
1236 count = (short)(bitStream & (threshold-1));
1237 bitCount += nbBits-1;
1241 count = (short)(bitStream & (2*threshold-1));
1242 if (count >= threshold) count -= max;
1246 count--; /* extra accuracy */
1247 remaining -= FSE_abs(count);
1248 normalizedCounter[charnum++] = count;
1250 while (remaining < threshold)
1257 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1264 bitCount -= (int)(8 * (iend - 4 - ip));
1267 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1271 if (remaining != 1) return ERROR(GENERIC);
1272 *maxSVPtr = charnum-1;
1274 ip += (bitCount+7)>>3;
1275 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1280 /*********************************************************
1281 * Decompression (Byte symbols)
1282 *********************************************************/
1283 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1286 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1287 FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */
1289 DTableH->tableLog = 0;
1290 DTableH->fastMode = 0;
1293 cell->symbol = symbolValue;
1300 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1303 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1304 FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */
1305 const unsigned tableSize = 1 << nbBits;
1306 const unsigned tableMask = tableSize - 1;
1307 const unsigned maxSymbolValue = tableMask;
1311 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1313 /* Build Decoding Table */
1314 DTableH->tableLog = (U16)nbBits;
1315 DTableH->fastMode = 1;
1316 for (s=0; s<=maxSymbolValue; s++)
1318 dinfo[s].newState = 0;
1319 dinfo[s].symbol = (BYTE)s;
1320 dinfo[s].nbBits = (BYTE)nbBits;
1326 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1327 void* dst, size_t maxDstSize,
1328 const void* cSrc, size_t cSrcSize,
1329 const FSE_DTable* dt, const unsigned fast)
1331 BYTE* const ostart = (BYTE*) dst;
1333 BYTE* const omax = op + maxDstSize;
1334 BYTE* const olimit = omax-3;
1337 FSE_DState_t state1;
1338 FSE_DState_t state2;
1342 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1343 if (FSE_isError(errorCode)) return errorCode;
1345 FSE_initDState(&state1, &bitD, dt);
1346 FSE_initDState(&state2, &bitD, dt);
1348 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1350 /* 4 symbols per loop */
1351 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1353 op[0] = FSE_GETSYMBOL(&state1);
1355 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1356 BIT_reloadDStream(&bitD);
1358 op[1] = FSE_GETSYMBOL(&state2);
1360 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1361 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1363 op[2] = FSE_GETSYMBOL(&state1);
1365 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1366 BIT_reloadDStream(&bitD);
1368 op[3] = FSE_GETSYMBOL(&state2);
1372 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1375 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1378 *op++ = FSE_GETSYMBOL(&state1);
1380 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1383 *op++ = FSE_GETSYMBOL(&state2);
1387 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1390 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1392 return ERROR(corruption_detected);
1396 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1397 const void* cSrc, size_t cSrcSize,
1398 const FSE_DTable* dt)
1400 FSE_DTableHeader DTableH;
1401 memcpy(&DTableH, dt, sizeof(DTableH));
1403 /* select fast mode (static) */
1404 if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1405 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1409 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1411 const BYTE* const istart = (const BYTE*)cSrc;
1412 const BYTE* ip = istart;
1413 short counting[FSE_MAX_SYMBOL_VALUE+1];
1414 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1416 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1419 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1421 /* normal FSE decoding mode */
1422 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1423 if (FSE_isError(errorCode)) return errorCode;
1424 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1426 cSrcSize -= errorCode;
1428 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1429 if (FSE_isError(errorCode)) return errorCode;
1431 /* always return, even if it is an error code */
1432 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1437 #endif /* FSE_COMMONDEFS_ONLY */
1438 /* ******************************************************************
1439 Huff0 : Huffman coder, part of New Generation Entropy library
1440 Copyright (C) 2013-2015, Yann Collet.
1442 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1444 Redistribution and use in source and binary forms, with or without
1445 modification, are permitted provided that the following conditions are
1448 * Redistributions of source code must retain the above copyright
1449 notice, this list of conditions and the following disclaimer.
1450 * Redistributions in binary form must reproduce the above
1451 copyright notice, this list of conditions and the following disclaimer
1452 in the documentation and/or other materials provided with the
1455 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1456 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1457 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1458 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1459 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1460 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1461 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1462 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1463 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1464 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1465 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1467 You can contact the author at :
1468 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1469 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1470 ****************************************************************** */
1472 /****************************************************************
1473 * Compiler specifics
1474 ****************************************************************/
1475 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1476 /* inline is defined */
1477 #elif defined(_MSC_VER)
1478 # define inline __inline
1480 # define inline /* disable inline */
1484 #ifdef _MSC_VER /* Visual Studio */
1485 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1489 /****************************************************************
1491 ****************************************************************/
1492 #include <stdlib.h> /* malloc, free, qsort */
1493 #include <string.h> /* memcpy, memset */
1494 #include <stdio.h> /* printf (debug) */
1496 /****************************************************************
1498 ****************************************************************/
1499 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1502 /******************************************
1504 ******************************************/
1505 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1507 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1508 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1509 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1510 #define HUF_MAX_SYMBOL_VALUE 255
1511 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1512 # error "HUF_MAX_TABLELOG is too large !"
1517 /*********************************************************
1518 * Huff0 : Huffman block decompression
1519 *********************************************************/
1520 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1522 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1524 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1527 Read compact Huffman tree, saved by HUF_writeCTable
1528 @huffWeight : destination buffer
1529 @return : size read from `src`
1531 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1532 U32* nbSymbolsPtr, U32* tableLogPtr,
1533 const void* src, size_t srcSize)
1537 const BYTE* ip = (const BYTE*) src;
1542 if (!srcSize) return ERROR(srcSize_wrong);
1544 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1546 if (iSize >= 128) /* special header */
1548 if (iSize >= (242)) /* RLE */
1550 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1551 oSize = l[iSize-242];
1552 memset(huffWeight, 1, hwSize);
1555 else /* Incompressible */
1557 oSize = iSize - 127;
1558 iSize = ((oSize+1)/2);
1559 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1560 if (oSize >= hwSize) return ERROR(corruption_detected);
1562 for (n=0; n<oSize; n+=2)
1564 huffWeight[n] = ip[n/2] >> 4;
1565 huffWeight[n+1] = ip[n/2] & 15;
1569 else /* header compressed with FSE (normal case) */
1571 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1572 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1573 if (FSE_isError(oSize)) return oSize;
1576 /* collect weight stats */
1577 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1579 for (n=0; n<oSize; n++)
1581 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1582 rankStats[huffWeight[n]]++;
1583 weightTotal += (1 << huffWeight[n]) >> 1;
1585 if (weightTotal == 0) return ERROR(corruption_detected);
1587 /* get last non-null symbol weight (implied, total must be 2^n) */
1588 tableLog = BIT_highbit32(weightTotal) + 1;
1589 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1591 U32 total = 1 << tableLog;
1592 U32 rest = total - weightTotal;
1593 U32 verif = 1 << BIT_highbit32(rest);
1594 U32 lastWeight = BIT_highbit32(rest) + 1;
1595 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1596 huffWeight[oSize] = (BYTE)lastWeight;
1597 rankStats[lastWeight]++;
1600 /* check tree construction validity */
1601 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1604 *nbSymbolsPtr = (U32)(oSize+1);
1605 *tableLogPtr = tableLog;
1610 /**************************/
1611 /* single-symbol decoding */
1612 /**************************/
1614 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1616 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1617 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1619 const BYTE* ip = (const BYTE*) src;
1620 size_t iSize = ip[0];
1624 void* ptr = DTable+1;
1625 HUF_DEltX2* const dt = (HUF_DEltX2*)ptr;
1627 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1628 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1630 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1631 if (HUF_isError(iSize)) return iSize;
1634 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1635 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1639 for (n=1; n<=tableLog; n++)
1641 U32 current = nextRankStart;
1642 nextRankStart += (rankVal[n] << (n-1));
1643 rankVal[n] = current;
1647 for (n=0; n<nbSymbols; n++)
1649 const U32 w = huffWeight[n];
1650 const U32 length = (1 << w) >> 1;
1653 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1654 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1656 rankVal[w] += length;
1662 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1664 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1665 const BYTE c = dt[val].byte;
1666 BIT_skipBits(Dstream, dt[val].nbBits);
1670 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1671 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1673 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1674 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1675 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1677 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1679 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1681 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1683 BYTE* const pStart = p;
1685 /* up to 4 symbols at a time */
1686 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1688 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1689 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1690 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1691 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1694 /* closer to the end */
1695 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1696 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1698 /* no more data to retrieve from bitstream, hence no need to reload */
1700 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1706 static size_t HUF_decompress4X2_usingDTable(
1707 void* dst, size_t dstSize,
1708 const void* cSrc, size_t cSrcSize,
1711 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1714 const BYTE* const istart = (const BYTE*) cSrc;
1715 BYTE* const ostart = (BYTE*) dst;
1716 BYTE* const oend = ostart + dstSize;
1718 const void* ptr = DTable;
1719 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1720 const U32 dtLog = DTable[0];
1724 BIT_DStream_t bitD1;
1725 BIT_DStream_t bitD2;
1726 BIT_DStream_t bitD3;
1727 BIT_DStream_t bitD4;
1728 const size_t length1 = MEM_readLE16(istart);
1729 const size_t length2 = MEM_readLE16(istart+2);
1730 const size_t length3 = MEM_readLE16(istart+4);
1732 const BYTE* const istart1 = istart + 6; /* jumpTable */
1733 const BYTE* const istart2 = istart1 + length1;
1734 const BYTE* const istart3 = istart2 + length2;
1735 const BYTE* const istart4 = istart3 + length3;
1736 const size_t segmentSize = (dstSize+3) / 4;
1737 BYTE* const opStart2 = ostart + segmentSize;
1738 BYTE* const opStart3 = opStart2 + segmentSize;
1739 BYTE* const opStart4 = opStart3 + segmentSize;
1741 BYTE* op2 = opStart2;
1742 BYTE* op3 = opStart3;
1743 BYTE* op4 = opStart4;
1746 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1747 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1748 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1749 if (HUF_isError(errorCode)) return errorCode;
1750 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1751 if (HUF_isError(errorCode)) return errorCode;
1752 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1753 if (HUF_isError(errorCode)) return errorCode;
1754 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1755 if (HUF_isError(errorCode)) return errorCode;
1757 /* 16-32 symbols per loop (4-8 symbols per stream) */
1758 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1759 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1761 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1762 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1763 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1764 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1765 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1766 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1767 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1768 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1769 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1770 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1771 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1772 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1773 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1774 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1775 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1776 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1778 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1781 /* check corruption */
1782 if (op1 > opStart2) return ERROR(corruption_detected);
1783 if (op2 > opStart3) return ERROR(corruption_detected);
1784 if (op3 > opStart4) return ERROR(corruption_detected);
1785 /* note : op4 supposed already verified within main loop */
1787 /* finish bitStreams one by one */
1788 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1789 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1790 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1791 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1794 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1795 if (!endSignal) return ERROR(corruption_detected);
1803 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1805 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1806 const BYTE* ip = (const BYTE*) cSrc;
1809 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1810 if (HUF_isError(errorCode)) return errorCode;
1811 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1813 cSrcSize -= errorCode;
1815 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1819 /***************************/
1820 /* double-symbols decoding */
1821 /***************************/
1823 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1824 const U32* rankValOrigin, const int minWeight,
1825 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1826 U32 nbBitsBaseline, U16 baseSeq)
1829 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1832 /* get pre-calculated rankVal */
1833 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1835 /* fill skipped values */
1838 U32 i, skipSize = rankVal[minWeight];
1839 MEM_writeLE16(&(DElt.sequence), baseSeq);
1840 DElt.nbBits = (BYTE)(consumed);
1842 for (i = 0; i < skipSize; i++)
1847 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1849 const U32 symbol = sortedSymbols[s].symbol;
1850 const U32 weight = sortedSymbols[s].weight;
1851 const U32 nbBits = nbBitsBaseline - weight;
1852 const U32 length = 1 << (sizeLog-nbBits);
1853 const U32 start = rankVal[weight];
1855 const U32 end = start + length;
1857 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1858 DElt.nbBits = (BYTE)(nbBits + consumed);
1860 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1862 rankVal[weight] += length;
1866 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1868 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1869 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1870 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1871 const U32 nbBitsBaseline)
1873 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1874 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1875 const U32 minBits = nbBitsBaseline - maxWeight;
1878 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1881 for (s=0; s<sortedListSize; s++)
1883 const U16 symbol = sortedList[s].symbol;
1884 const U32 weight = sortedList[s].weight;
1885 const U32 nbBits = nbBitsBaseline - weight;
1886 const U32 start = rankVal[weight];
1887 const U32 length = 1 << (targetLog-nbBits);
1889 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1892 int minWeight = nbBits + scaleLog;
1893 if (minWeight < 1) minWeight = 1;
1894 sortedRank = rankStart[minWeight];
1895 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1896 rankValOrigin[nbBits], minWeight,
1897 sortedList+sortedRank, sortedListSize-sortedRank,
1898 nbBitsBaseline, symbol);
1903 const U32 end = start + length;
1906 MEM_writeLE16(&(DElt.sequence), symbol);
1907 DElt.nbBits = (BYTE)(nbBits);
1909 for (i = start; i < end; i++)
1912 rankVal[weight] += length;
1916 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1918 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1919 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1920 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1921 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1922 U32* const rankStart = rankStart0+1;
1924 U32 tableLog, maxW, sizeOfSort, nbSymbols;
1925 const U32 memLog = DTable[0];
1926 const BYTE* ip = (const BYTE*) src;
1927 size_t iSize = ip[0];
1929 HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1931 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
1932 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1933 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1935 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1936 if (HUF_isError(iSize)) return iSize;
1939 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
1941 /* find maxWeight */
1942 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1943 {if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
1945 /* Get start index of each weight */
1947 U32 w, nextRankStart = 0;
1948 for (w=1; w<=maxW; w++)
1950 U32 current = nextRankStart;
1951 nextRankStart += rankStats[w];
1952 rankStart[w] = current;
1954 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
1955 sizeOfSort = nextRankStart;
1958 /* sort symbols by weight */
1961 for (s=0; s<nbSymbols; s++)
1963 U32 w = weightList[s];
1964 U32 r = rankStart[w]++;
1965 sortedSymbol[r].symbol = (BYTE)s;
1966 sortedSymbol[r].weight = (BYTE)w;
1968 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1973 const U32 minBits = tableLog+1 - maxW;
1974 U32 nextRankVal = 0;
1976 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
1977 U32* rankVal0 = rankVal[0];
1978 for (w=1; w<=maxW; w++)
1980 U32 current = nextRankVal;
1981 nextRankVal += rankStats[w] << (w+rescale);
1982 rankVal0[w] = current;
1984 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1986 U32* rankValPtr = rankVal[consumed];
1987 for (w = 1; w <= maxW; w++)
1989 rankValPtr[w] = rankVal0[w] >> consumed;
1994 HUF_fillDTableX4(dt, memLog,
1995 sortedSymbol, sizeOfSort,
1996 rankStart0, rankVal, maxW,
2003 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2005 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2006 memcpy(op, dt+val, 2);
2007 BIT_skipBits(DStream, dt[val].nbBits);
2008 return dt[val].length;
2011 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2013 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2014 memcpy(op, dt+val, 1);
2015 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2018 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2020 BIT_skipBits(DStream, dt[val].nbBits);
2021 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2022 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 */
2029 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2030 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2032 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2033 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2034 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2036 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2038 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2040 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2042 BYTE* const pStart = p;
2044 /* up to 8 symbols at a time */
2045 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2047 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2048 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2049 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2050 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2053 /* closer to the end */
2054 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2055 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2058 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2061 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2068 static size_t HUF_decompress4X4_usingDTable(
2069 void* dst, size_t dstSize,
2070 const void* cSrc, size_t cSrcSize,
2073 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2076 const BYTE* const istart = (const BYTE*) cSrc;
2077 BYTE* const ostart = (BYTE*) dst;
2078 BYTE* const oend = ostart + dstSize;
2080 const void* ptr = DTable;
2081 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2082 const U32 dtLog = DTable[0];
2086 BIT_DStream_t bitD1;
2087 BIT_DStream_t bitD2;
2088 BIT_DStream_t bitD3;
2089 BIT_DStream_t bitD4;
2090 const size_t length1 = MEM_readLE16(istart);
2091 const size_t length2 = MEM_readLE16(istart+2);
2092 const size_t length3 = MEM_readLE16(istart+4);
2094 const BYTE* const istart1 = istart + 6; /* jumpTable */
2095 const BYTE* const istart2 = istart1 + length1;
2096 const BYTE* const istart3 = istart2 + length2;
2097 const BYTE* const istart4 = istart3 + length3;
2098 const size_t segmentSize = (dstSize+3) / 4;
2099 BYTE* const opStart2 = ostart + segmentSize;
2100 BYTE* const opStart3 = opStart2 + segmentSize;
2101 BYTE* const opStart4 = opStart3 + segmentSize;
2103 BYTE* op2 = opStart2;
2104 BYTE* op3 = opStart3;
2105 BYTE* op4 = opStart4;
2108 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2109 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2110 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2111 if (HUF_isError(errorCode)) return errorCode;
2112 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2113 if (HUF_isError(errorCode)) return errorCode;
2114 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2115 if (HUF_isError(errorCode)) return errorCode;
2116 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2117 if (HUF_isError(errorCode)) return errorCode;
2119 /* 16-32 symbols per loop (4-8 symbols per stream) */
2120 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2121 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2123 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2124 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2125 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2126 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2127 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2128 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2129 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2130 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2131 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2132 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2133 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2134 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2135 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2136 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2137 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2138 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2140 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2143 /* check corruption */
2144 if (op1 > opStart2) return ERROR(corruption_detected);
2145 if (op2 > opStart3) return ERROR(corruption_detected);
2146 if (op3 > opStart4) return ERROR(corruption_detected);
2147 /* note : op4 supposed already verified within main loop */
2149 /* finish bitStreams one by one */
2150 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2151 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2152 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2153 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2156 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2157 if (!endSignal) return ERROR(corruption_detected);
2165 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2167 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2168 const BYTE* ip = (const BYTE*) cSrc;
2170 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2171 if (HUF_isError(hSize)) return hSize;
2172 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2176 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2180 /**********************************/
2181 /* quad-symbol decoding */
2182 /**********************************/
2183 typedef struct { BYTE nbBits; BYTE nbBytes; } HUF_DDescX6;
2184 typedef union { BYTE byte[4]; U32 sequence; } HUF_DSeqX6;
2186 /* recursive, up to level 3; may benefit from <template>-like strategy to nest each level inline */
2187 static void HUF_fillDTableX6LevelN(HUF_DDescX6* DDescription, HUF_DSeqX6* DSequence, int sizeLog,
2188 const rankVal_t rankValOrigin, const U32 consumed, const int minWeight, const U32 maxWeight,
2189 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, const U32* rankStart,
2190 const U32 nbBitsBaseline, HUF_DSeqX6 baseSeq, HUF_DDescX6 DDesc)
2192 const int scaleLog = nbBitsBaseline - sizeLog; /* note : targetLog >= (nbBitsBaseline-1), hence scaleLog <= 1 */
2193 const int minBits = nbBitsBaseline - maxWeight;
2194 const U32 level = DDesc.nbBytes;
2195 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
2196 U32 symbolStartPos, s;
2198 /* local rankVal, will be modified */
2199 memcpy(rankVal, rankValOrigin[consumed], sizeof(rankVal));
2201 /* fill skipped values */
2205 const U32 skipSize = rankVal[minWeight];
2206 for (i = 0; i < skipSize; i++)
2208 DSequence[i] = baseSeq;
2209 DDescription[i] = DDesc;
2215 symbolStartPos = rankStart[minWeight];
2216 for (s=symbolStartPos; s<sortedListSize; s++)
2218 const BYTE symbol = sortedSymbols[s].symbol;
2219 const U32 weight = sortedSymbols[s].weight; /* >= 1 (sorted) */
2220 const int nbBits = nbBitsBaseline - weight; /* >= 1 (by construction) */
2221 const int totalBits = consumed+nbBits;
2222 const U32 start = rankVal[weight];
2223 const U32 length = 1 << (sizeLog-nbBits);
2224 baseSeq.byte[level] = symbol;
2225 DDesc.nbBits = (BYTE)totalBits;
2227 if ((level<3) && (sizeLog-totalBits >= minBits)) /* enough room for another symbol */
2229 int nextMinWeight = totalBits + scaleLog;
2230 if (nextMinWeight < 1) nextMinWeight = 1;
2231 HUF_fillDTableX6LevelN(DDescription+start, DSequence+start, sizeLog-nbBits,
2232 rankValOrigin, totalBits, nextMinWeight, maxWeight,
2233 sortedSymbols, sortedListSize, rankStart,
2234 nbBitsBaseline, baseSeq, DDesc); /* recursive (max : level 3) */
2239 const U32 end = start + length;
2240 for (i = start; i < end; i++)
2242 DDescription[i] = DDesc;
2243 DSequence[i] = baseSeq;
2246 rankVal[weight] += length;
2251 /* note : same preparation as X4 */
2252 static size_t HUF_readDTableX6 (U32* DTable, const void* src, size_t srcSize)
2254 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
2255 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
2256 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2257 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2258 U32* const rankStart = rankStart0+1;
2259 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2261 const U32 memLog = DTable[0];
2262 const BYTE* ip = (const BYTE*) src;
2263 size_t iSize = ip[0];
2265 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2266 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2268 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2269 if (HUF_isError(iSize)) return iSize;
2272 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable is too small */
2274 /* find maxWeight */
2275 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2276 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
2279 /* Get start index of each weight */
2281 U32 w, nextRankStart = 0;
2282 for (w=1; w<=maxW; w++)
2284 U32 current = nextRankStart;
2285 nextRankStart += rankStats[w];
2286 rankStart[w] = current;
2288 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2289 sizeOfSort = nextRankStart;
2292 /* sort symbols by weight */
2295 for (s=0; s<nbSymbols; s++)
2297 U32 w = weightList[s];
2298 U32 r = rankStart[w]++;
2299 sortedSymbol[r].symbol = (BYTE)s;
2300 sortedSymbol[r].weight = (BYTE)w;
2302 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2307 const U32 minBits = tableLog+1 - maxW;
2308 U32 nextRankVal = 0;
2310 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2311 U32* rankVal0 = rankVal[0];
2312 for (w=1; w<=maxW; w++)
2314 U32 current = nextRankVal;
2315 nextRankVal += rankStats[w] << (w+rescale);
2316 rankVal0[w] = current;
2318 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2320 U32* rankValPtr = rankVal[consumed];
2321 for (w = 1; w <= maxW; w++)
2323 rankValPtr[w] = rankVal0[w] >> consumed;
2331 void* ptr = DTable+1;
2332 HUF_DDescX6* DDescription = (HUF_DDescX6*)(ptr);
2333 void* dSeqStart = DTable + 1 + ((size_t)1<<(memLog-1));
2334 HUF_DSeqX6* DSequence = (HUF_DSeqX6*)(dSeqStart);
2340 HUF_fillDTableX6LevelN(DDescription, DSequence, memLog,
2341 (const U32 (*)[HUF_ABSOLUTEMAX_TABLELOG + 1])rankVal, 0, 1, maxW,
2342 sortedSymbol, sizeOfSort, rankStart0,
2343 tableLog+1, DSeq, DDesc);
2350 static U32 HUF_decodeSymbolX6(void* op, BIT_DStream_t* DStream, const HUF_DDescX6* dd, const HUF_DSeqX6* ds, const U32 dtLog)
2352 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2353 memcpy(op, ds+val, sizeof(HUF_DSeqX6));
2354 BIT_skipBits(DStream, dd[val].nbBits);
2355 return dd[val].nbBytes;
2358 static U32 HUF_decodeLastSymbolsX6(void* op, const U32 maxL, BIT_DStream_t* DStream,
2359 const HUF_DDescX6* dd, const HUF_DSeqX6* ds, const U32 dtLog)
2361 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2362 U32 length = dd[val].nbBytes;
2365 memcpy(op, ds+val, length);
2366 BIT_skipBits(DStream, dd[val].nbBits);
2369 memcpy(op, ds+val, maxL);
2370 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2372 BIT_skipBits(DStream, dd[val].nbBits);
2373 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2374 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 */
2380 #define HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr) \
2381 ptr += HUF_decodeSymbolX6(ptr, DStreamPtr, dd, ds, dtLog)
2383 #define HUF_DECODE_SYMBOLX6_1(ptr, DStreamPtr) \
2384 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2385 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2387 #define HUF_DECODE_SYMBOLX6_2(ptr, DStreamPtr) \
2389 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2391 static inline size_t HUF_decodeStreamX6(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const U32* DTable, const U32 dtLog)
2393 const void* ddPtr = DTable+1;
2394 const HUF_DDescX6* dd = (const HUF_DDescX6*)(ddPtr);
2395 const void* dsPtr = DTable + 1 + ((size_t)1<<(dtLog-1));
2396 const HUF_DSeqX6* ds = (const HUF_DSeqX6*)(dsPtr);
2397 BYTE* const pStart = p;
2399 /* up to 16 symbols at a time */
2400 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-16))
2402 HUF_DECODE_SYMBOLX6_2(p, bitDPtr);
2403 HUF_DECODE_SYMBOLX6_1(p, bitDPtr);
2404 HUF_DECODE_SYMBOLX6_2(p, bitDPtr);
2405 HUF_DECODE_SYMBOLX6_0(p, bitDPtr);
2408 /* closer to the end, up to 4 symbols at a time */
2409 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
2410 HUF_DECODE_SYMBOLX6_0(p, bitDPtr);
2413 HUF_DECODE_SYMBOLX6_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2416 p += HUF_decodeLastSymbolsX6(p, (U32)(pEnd-p), bitDPtr, dd, ds, dtLog);
2423 static size_t HUF_decompress4X6_usingDTable(
2424 void* dst, size_t dstSize,
2425 const void* cSrc, size_t cSrcSize,
2428 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2431 const BYTE* const istart = (const BYTE*) cSrc;
2432 BYTE* const ostart = (BYTE*) dst;
2433 BYTE* const oend = ostart + dstSize;
2435 const U32 dtLog = DTable[0];
2436 const void* ddPtr = DTable+1;
2437 const HUF_DDescX6* dd = (const HUF_DDescX6*)(ddPtr);
2438 const void* dsPtr = DTable + 1 + ((size_t)1<<(dtLog-1));
2439 const HUF_DSeqX6* ds = (const HUF_DSeqX6*)(dsPtr);
2443 BIT_DStream_t bitD1;
2444 BIT_DStream_t bitD2;
2445 BIT_DStream_t bitD3;
2446 BIT_DStream_t bitD4;
2447 const size_t length1 = MEM_readLE16(istart);
2448 const size_t length2 = MEM_readLE16(istart+2);
2449 const size_t length3 = MEM_readLE16(istart+4);
2451 const BYTE* const istart1 = istart + 6; /* jumpTable */
2452 const BYTE* const istart2 = istart1 + length1;
2453 const BYTE* const istart3 = istart2 + length2;
2454 const BYTE* const istart4 = istart3 + length3;
2455 const size_t segmentSize = (dstSize+3) / 4;
2456 BYTE* const opStart2 = ostart + segmentSize;
2457 BYTE* const opStart3 = opStart2 + segmentSize;
2458 BYTE* const opStart4 = opStart3 + segmentSize;
2460 BYTE* op2 = opStart2;
2461 BYTE* op3 = opStart3;
2462 BYTE* op4 = opStart4;
2465 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2466 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2467 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2468 if (HUF_isError(errorCode)) return errorCode;
2469 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2470 if (HUF_isError(errorCode)) return errorCode;
2471 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2472 if (HUF_isError(errorCode)) return errorCode;
2473 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2474 if (HUF_isError(errorCode)) return errorCode;
2476 /* 16-64 symbols per loop (4-16 symbols per stream) */
2477 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2478 for ( ; (op3 <= opStart4) && (endSignal==BIT_DStream_unfinished) && (op4<=(oend-16)) ; )
2480 HUF_DECODE_SYMBOLX6_2(op1, &bitD1);
2481 HUF_DECODE_SYMBOLX6_2(op2, &bitD2);
2482 HUF_DECODE_SYMBOLX6_2(op3, &bitD3);
2483 HUF_DECODE_SYMBOLX6_2(op4, &bitD4);
2484 HUF_DECODE_SYMBOLX6_1(op1, &bitD1);
2485 HUF_DECODE_SYMBOLX6_1(op2, &bitD2);
2486 HUF_DECODE_SYMBOLX6_1(op3, &bitD3);
2487 HUF_DECODE_SYMBOLX6_1(op4, &bitD4);
2488 HUF_DECODE_SYMBOLX6_2(op1, &bitD1);
2489 HUF_DECODE_SYMBOLX6_2(op2, &bitD2);
2490 HUF_DECODE_SYMBOLX6_2(op3, &bitD3);
2491 HUF_DECODE_SYMBOLX6_2(op4, &bitD4);
2492 HUF_DECODE_SYMBOLX6_0(op1, &bitD1);
2493 HUF_DECODE_SYMBOLX6_0(op2, &bitD2);
2494 HUF_DECODE_SYMBOLX6_0(op3, &bitD3);
2495 HUF_DECODE_SYMBOLX6_0(op4, &bitD4);
2497 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2500 /* check corruption */
2501 if (op1 > opStart2) return ERROR(corruption_detected);
2502 if (op2 > opStart3) return ERROR(corruption_detected);
2503 if (op3 > opStart4) return ERROR(corruption_detected);
2504 /* note : op4 supposed already verified within main loop */
2506 /* finish bitStreams one by one */
2507 HUF_decodeStreamX6(op1, &bitD1, opStart2, DTable, dtLog);
2508 HUF_decodeStreamX6(op2, &bitD2, opStart3, DTable, dtLog);
2509 HUF_decodeStreamX6(op3, &bitD3, opStart4, DTable, dtLog);
2510 HUF_decodeStreamX6(op4, &bitD4, oend, DTable, dtLog);
2513 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2514 if (!endSignal) return ERROR(corruption_detected);
2522 static size_t HUF_decompress4X6 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2524 HUF_CREATE_STATIC_DTABLEX6(DTable, HUF_MAX_TABLELOG);
2525 const BYTE* ip = (const BYTE*) cSrc;
2527 size_t hSize = HUF_readDTableX6 (DTable, cSrc, cSrcSize);
2528 if (HUF_isError(hSize)) return hSize;
2529 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2533 return HUF_decompress4X6_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2537 /**********************************/
2538 /* Generic decompression selector */
2539 /**********************************/
2541 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2542 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2544 /* single, double, quad */
2545 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2546 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2547 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2548 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2549 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2550 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2551 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2552 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2553 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2554 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2555 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2556 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2557 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2558 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2559 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2560 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2563 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2565 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2567 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, HUF_decompress4X6 };
2568 /* estimate decompression time */
2570 const U32 D256 = (U32)(dstSize >> 8);
2575 /* validation checks */
2576 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2577 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2578 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2579 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2581 /* decoder timing evaluation */
2582 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2584 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2586 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2588 if (Dtime[1] < Dtime[0]) algoNb = 1;
2589 if (Dtime[2] < Dtime[algoNb]) algoNb = 2;
2591 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2593 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2594 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2595 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2598 zstd - standard compression library
2599 Copyright (C) 2014-2015, Yann Collet.
2601 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2603 Redistribution and use in source and binary forms, with or without
2604 modification, are permitted provided that the following conditions are
2606 * Redistributions of source code must retain the above copyright
2607 notice, this list of conditions and the following disclaimer.
2608 * Redistributions in binary form must reproduce the above
2609 copyright notice, this list of conditions and the following disclaimer
2610 in the documentation and/or other materials provided with the
2612 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2613 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2614 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2615 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2616 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2617 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2618 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2619 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2620 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2621 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2622 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2624 You can contact the author at :
2625 - zstd source repository : https://github.com/Cyan4973/zstd
2626 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2629 /* ***************************************************************
2631 *****************************************************************/
2634 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2635 * Increasing memory usage improves compression ratio
2636 * Reduced memory usage can improve speed, due to cache effect
2638 #define ZSTD_MEMORY_USAGE 17
2642 * Select how default compression functions will allocate memory for their hash table,
2643 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2644 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2646 #ifndef ZSTD_HEAPMODE
2647 # define ZSTD_HEAPMODE 1
2648 #endif /* ZSTD_HEAPMODE */
2652 * decompressor can decode older formats (starting from Zstd 0.1+)
2654 #ifndef ZSTD_LEGACY_SUPPORT
2655 # define ZSTD_LEGACY_SUPPORT 1
2659 /* *******************************************************
2661 *********************************************************/
2662 #include <stdlib.h> /* calloc */
2663 #include <string.h> /* memcpy, memmove */
2664 #include <stdio.h> /* debug : printf */
2667 /* *******************************************************
2668 * Compiler specifics
2669 *********************************************************/
2671 # include <immintrin.h> /* AVX2 intrinsics */
2674 #ifdef _MSC_VER /* Visual Studio */
2675 # include <intrin.h> /* For Visual 2005 */
2676 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2677 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2681 /* *******************************************************
2683 *********************************************************/
2684 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2685 #define HASH_TABLESIZE (1 << HASH_LOG)
2686 #define HASH_MASK (HASH_TABLESIZE - 1)
2688 #define KNUTH 2654435761
2697 #define KB *(1 <<10)
2698 #define MB *(1 <<20)
2699 #define GB *(1U<<30)
2701 #define BLOCKSIZE (128 KB) /* define, for static allocation */
2702 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2703 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2707 #define WORKPLACESIZE (BLOCKSIZE*3)
2712 #define MaxML ((1<<MLbits )-1)
2713 #define MaxLL ((1<<LLbits )-1)
2715 #define LitFSELog 11
2719 #define MAX(a,b) ((a)<(b)?(b):(a))
2720 #define MaxSeq MAX(MaxLL, MaxML)
2722 #define LITERAL_NOENTROPY 63
2723 #define COMMAND_NOENTROPY 7 /* to remove */
2725 static const size_t ZSTD_blockHeaderSize = 3;
2726 static const size_t ZSTD_frameHeaderSize = 4;
2729 /* *******************************************************
2731 **********************************************************/
2732 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2734 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2736 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2738 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2739 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2741 const BYTE* ip = (const BYTE*)src;
2742 BYTE* op = (BYTE*)dst;
2743 BYTE* const oend = op + length;
2744 do COPY8(op, ip) while (op < oend);
2748 /* **************************************
2750 ****************************************/
2751 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2755 blockType_t blockType;
2757 } blockProperties_t;
2767 BYTE* litLengthStart;
2769 BYTE* matchLengthStart;
2776 /* *************************************
2778 ***************************************/
2780 * tells if a return value is an error code */
2781 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2785 /* *************************************************************
2786 * Decompression section
2787 ***************************************************************/
2790 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2791 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2792 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2793 void* previousDstEnd;
2800 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2801 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2804 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2806 const BYTE* const in = (const BYTE* const)src;
2810 if (srcSize < 3) return ERROR(srcSize_wrong);
2813 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2815 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2816 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2818 if (bpPtr->blockType == bt_end) return 0;
2819 if (bpPtr->blockType == bt_rle) return 1;
2823 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2825 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2826 memcpy(dst, src, srcSize);
2831 /** ZSTD_decompressLiterals
2832 @return : nb of bytes read from src, or an error code*/
2833 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2834 const void* src, size_t srcSize)
2836 const BYTE* ip = (const BYTE*)src;
2838 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2839 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2841 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2842 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2844 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2846 *maxDstSizePtr = litSize;
2847 return litCSize + 5;
2851 /** ZSTD_decodeLiteralsBlock
2852 @return : nb of bytes read from src (< srcSize )*/
2853 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2854 const void* src, size_t srcSize)
2856 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2857 const BYTE* const istart = (const BYTE* const)src;
2859 /* any compressed block with literals segment must be at least this size */
2860 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2867 size_t litSize = BLOCKSIZE;
2868 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2869 dctx->litPtr = dctx->litBuffer;
2870 dctx->litSize = litSize;
2871 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2872 return readSize; /* works if it's an error too */
2876 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2877 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2879 if (litSize > srcSize-3) return ERROR(corruption_detected);
2880 memcpy(dctx->litBuffer, istart, litSize);
2881 dctx->litPtr = dctx->litBuffer;
2882 dctx->litSize = litSize;
2883 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2886 /* direct reference into compressed stream */
2887 dctx->litPtr = istart+3;
2888 dctx->litSize = litSize;
2893 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2894 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2895 memset(dctx->litBuffer, istart[3], litSize + 8);
2896 dctx->litPtr = dctx->litBuffer;
2897 dctx->litSize = litSize;
2904 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2905 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2906 const void* src, size_t srcSize)
2908 const BYTE* const istart = (const BYTE* const)src;
2909 const BYTE* ip = istart;
2910 const BYTE* const iend = istart + srcSize;
2911 U32 LLtype, Offtype, MLtype;
2912 U32 LLlog, Offlog, MLlog;
2916 if (srcSize < 5) return ERROR(srcSize_wrong);
2919 *nbSeq = MEM_readLE16(ip); ip+=2;
2921 Offtype = (*ip >> 4) & 3;
2922 MLtype = (*ip >> 2) & 3;
2925 dumpsLength = ip[2];
2926 dumpsLength += ip[1] << 8;
2931 dumpsLength = ip[1];
2932 dumpsLength += (ip[0] & 1) << 8;
2937 *dumpsLengthPtr = dumpsLength;
2940 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2944 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2952 FSE_buildDTable_rle(DTableLL, *ip++); break;
2955 FSE_buildDTable_raw(DTableLL, LLbits); break;
2958 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2959 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2960 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2962 FSE_buildDTable(DTableLL, norm, max, LLlog);
2969 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2970 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2974 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2977 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2978 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2979 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2981 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2988 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2989 FSE_buildDTable_rle(DTableML, *ip++); break;
2992 FSE_buildDTable_raw(DTableML, MLbits); break;
2995 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2996 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2997 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2999 FSE_buildDTable(DTableML, norm, max, MLlog);
3013 BIT_DStream_t DStream;
3014 FSE_DState_t stateLL;
3015 FSE_DState_t stateOffb;
3016 FSE_DState_t stateML;
3019 const BYTE* dumpsEnd;
3023 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
3029 const BYTE* dumps = seqState->dumps;
3030 const BYTE* const de = seqState->dumpsEnd;
3032 /* Literal length */
3033 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
3034 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3035 seqState->prevOffset = seq->offset;
3036 if (litLength == MaxLL)
3039 if (add < 255) litLength += add;
3042 litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3045 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3050 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
3051 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3052 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3053 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3054 U32 offsetCode, nbBits;
3055 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
3056 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3057 nbBits = offsetCode - 1;
3058 if (offsetCode==0) nbBits = 0; /* cmove */
3059 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
3060 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3061 if (offsetCode==0) offset = prevOffset; /* cmove */
3065 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3066 if (matchLength == MaxML)
3069 if (add < 255) matchLength += add;
3072 matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3075 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3077 matchLength += MINMATCH;
3080 seq->litLength = litLength;
3081 seq->offset = offset;
3082 seq->matchLength = matchLength;
3083 seqState->dumps = dumps;
3087 static size_t ZSTD_execSequence(BYTE* op,
3089 const BYTE** litPtr, const BYTE* const litLimit,
3090 BYTE* const base, BYTE* const oend)
3092 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
3093 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* substracted */
3094 const BYTE* const ostart = op;
3095 BYTE* const oLitEnd = op + sequence.litLength;
3096 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
3097 BYTE* const oend_8 = oend-8;
3098 const BYTE* const litEnd = *litPtr + sequence.litLength;
3101 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
3102 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3103 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
3106 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3108 *litPtr = litEnd; /* update for next sequence */
3112 const BYTE* match = op - sequence.offset;
3115 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
3116 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
3117 if (match < base) return ERROR(corruption_detected);
3119 /* close range match, overlap */
3120 if (sequence.offset < 8)
3122 const int dec64 = dec64table[sequence.offset];
3127 match += dec32table[sequence.offset];
3128 ZSTD_copy4(op+4, match);
3133 ZSTD_copy8(op, match);
3135 op += 8; match += 8;
3137 if (oMatchEnd > oend-(16-MINMATCH))
3141 ZSTD_wildcopy(op, match, oend_8 - op);
3142 match += oend_8 - op;
3145 while (op < oMatchEnd) *op++ = *match++;
3149 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3153 return oMatchEnd - ostart;
3156 static size_t ZSTD_decompressSequences(
3158 void* dst, size_t maxDstSize,
3159 const void* seqStart, size_t seqSize)
3161 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
3162 const BYTE* ip = (const BYTE*)seqStart;
3163 const BYTE* const iend = ip + seqSize;
3164 BYTE* const ostart = (BYTE* const)dst;
3166 BYTE* const oend = ostart + maxDstSize;
3167 size_t errorCode, dumpsLength;
3168 const BYTE* litPtr = dctx->litPtr;
3169 const BYTE* const litEnd = litPtr + dctx->litSize;
3172 U32* DTableLL = dctx->LLTable;
3173 U32* DTableML = dctx->MLTable;
3174 U32* DTableOffb = dctx->OffTable;
3175 BYTE* const base = (BYTE*) (dctx->base);
3177 /* Build Decoding Tables */
3178 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3179 DTableLL, DTableML, DTableOffb,
3181 if (ZSTD_isError(errorCode)) return errorCode;
3184 /* Regen sequences */
3187 seqState_t seqState;
3189 memset(&sequence, 0, sizeof(sequence));
3190 seqState.dumps = dumps;
3191 seqState.dumpsEnd = dumps + dumpsLength;
3192 seqState.prevOffset = 1;
3193 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
3194 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3195 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3196 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3197 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3199 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
3203 ZSTD_decodeSequence(&sequence, &seqState);
3204 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
3205 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
3209 /* check if reached exact end */
3210 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
3211 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
3213 /* last literal segment */
3215 size_t lastLLSize = litEnd - litPtr;
3216 if (litPtr > litEnd) return ERROR(corruption_detected);
3217 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3218 if (op != litPtr) memmove(op, litPtr, lastLLSize);
3227 static size_t ZSTD_decompressBlock(
3229 void* dst, size_t maxDstSize,
3230 const void* src, size_t srcSize)
3232 /* blockType == blockCompressed */
3233 const BYTE* ip = (const BYTE*)src;
3235 /* Decode literals sub-block */
3236 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
3237 if (ZSTD_isError(litCSize)) return litCSize;
3239 srcSize -= litCSize;
3241 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
3245 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3247 const BYTE* ip = (const BYTE*)src;
3248 const BYTE* iend = ip + srcSize;
3249 BYTE* const ostart = (BYTE* const)dst;
3251 BYTE* const oend = ostart + maxDstSize;
3252 size_t remainingSize = srcSize;
3254 blockProperties_t blockProperties;
3257 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3258 magicNumber = MEM_readLE32(src);
3259 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3260 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
3262 /* Loop on each block */
3265 size_t decodedSize=0;
3266 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
3267 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3269 ip += ZSTD_blockHeaderSize;
3270 remainingSize -= ZSTD_blockHeaderSize;
3271 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3273 switch(blockProperties.blockType)
3276 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
3279 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
3282 return ERROR(GENERIC); /* not yet supported */
3286 if (remainingSize) return ERROR(srcSize_wrong);
3289 return ERROR(GENERIC); /* impossible */
3291 if (cBlockSize == 0) break; /* bt_end */
3293 if (ZSTD_isError(decodedSize)) return decodedSize;
3296 remainingSize -= cBlockSize;
3302 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3306 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
3309 static size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
3312 const BYTE* ip = (const BYTE*)src;
3313 size_t remainingSize = srcSize;
3315 blockProperties_t blockProperties;
3318 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3319 magicNumber = MEM_readLE32(src);
3320 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3321 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
3323 /* Loop on each block */
3326 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
3327 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3329 ip += ZSTD_blockHeaderSize;
3330 remainingSize -= ZSTD_blockHeaderSize;
3331 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3333 if (cBlockSize == 0) break; /* bt_end */
3336 remainingSize -= cBlockSize;
3339 return ip - (const BYTE*)src;
3342 /*******************************
3343 * Streaming Decompression API
3344 *******************************/
3346 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
3348 dctx->expected = ZSTD_frameHeaderSize;
3350 dctx->previousDstEnd = NULL;
3355 static ZSTD_DCtx* ZSTD_createDCtx(void)
3357 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
3358 if (dctx==NULL) return NULL;
3359 ZSTD_resetDCtx(dctx);
3363 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3369 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3371 return dctx->expected;
3374 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3377 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3378 if (dst != ctx->previousDstEnd) /* not contiguous */
3381 /* Decompress : frame header */
3382 if (ctx->phase == 0)
3384 /* Check frame magic header */
3385 U32 magicNumber = MEM_readLE32(src);
3386 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3388 ctx->expected = ZSTD_blockHeaderSize;
3392 /* Decompress : block header */
3393 if (ctx->phase == 1)
3395 blockProperties_t bp;
3396 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3397 if (ZSTD_isError(blockSize)) return blockSize;
3398 if (bp.blockType == bt_end)
3405 ctx->expected = blockSize;
3406 ctx->bType = bp.blockType;
3413 /* Decompress : block content */
3419 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3422 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3425 return ERROR(GENERIC); /* not yet handled */
3427 case bt_end : /* should never happen (filtered at phase 1) */
3431 return ERROR(GENERIC);
3434 ctx->expected = ZSTD_blockHeaderSize;
3435 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3444 unsigned ZSTDv02_isError(size_t code)
3446 return ZSTD_isError(code);
3449 size_t ZSTDv02_decompress( void* dst, size_t maxOriginalSize,
3450 const void* src, size_t compressedSize)
3452 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3455 size_t ZSTDv02_findFrameCompressedSize(const void *src, size_t compressedSize)
3457 return ZSTD_findFrameCompressedSize(src, compressedSize);
3460 ZSTDv02_Dctx* ZSTDv02_createDCtx(void)
3462 return (ZSTDv02_Dctx*)ZSTD_createDCtx();
3465 size_t ZSTDv02_freeDCtx(ZSTDv02_Dctx* dctx)
3467 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3470 size_t ZSTDv02_resetDCtx(ZSTDv02_Dctx* dctx)
3472 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3475 size_t ZSTDv02_nextSrcSizeToDecompress(ZSTDv02_Dctx* dctx)
3477 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3480 size_t ZSTDv02_decompressContinue(ZSTDv02_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3482 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);