2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of this source tree. An additional grant
7 * of patent rights can be found in the PATENTS file in the same directory.
11 #include <stddef.h> /* size_t, ptrdiff_t */
13 #include "error_private.h"
16 /******************************************
18 ******************************************/
19 #if defined(_MSC_VER) /* Visual Studio */
20 # include <stdlib.h> /* _byteswap_ulong */
21 # include <intrin.h> /* _byteswap_* */
25 /* ******************************************************************
27 low-level memory access routines
28 Copyright (C) 2013-2015, Yann Collet.
30 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
32 Redistribution and use in source and binary forms, with or without
33 modification, are permitted provided that the following conditions are
36 * Redistributions of source code must retain the above copyright
37 notice, this list of conditions and the following disclaimer.
38 * Redistributions in binary form must reproduce the above
39 copyright notice, this list of conditions and the following disclaimer
40 in the documentation and/or other materials provided with the
43 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
44 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
45 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
46 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
47 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
48 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
49 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
50 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
51 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
52 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
53 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
55 You can contact the author at :
56 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
57 - Public forum : https://groups.google.com/forum/#!forum/lz4c
58 ****************************************************************** */
62 #if defined (__cplusplus)
66 /******************************************
68 ******************************************/
69 #include <stddef.h> /* size_t, ptrdiff_t */
70 #include <string.h> /* memcpy */
73 /******************************************
75 ******************************************/
77 # define MEM_STATIC static __attribute__((unused))
78 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
79 # define MEM_STATIC static inline
80 #elif defined(_MSC_VER)
81 # define MEM_STATIC static __inline
83 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
87 /****************************************************************
89 *****************************************************************/
90 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
100 typedef unsigned char BYTE;
101 typedef unsigned short U16;
102 typedef signed short S16;
103 typedef unsigned int U32;
104 typedef signed int S32;
105 typedef unsigned long long U64;
106 typedef signed long long S64;
110 /****************************************************************
112 *****************************************************************/
113 /* MEM_FORCE_MEMORY_ACCESS
114 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
115 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
116 * The below switch allow to select different access method for improved performance.
117 * Method 0 (default) : use `memcpy()`. Safe and portable.
118 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
119 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
120 * Method 2 : direct access. This method is portable but violate C standard.
121 * It can generate buggy code on targets generating assembly depending on alignment.
122 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
123 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
124 * Prefer these methods in priority order (0 > 1 > 2)
126 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
127 # 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__) )
128 # define MEM_FORCE_MEMORY_ACCESS 2
129 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
130 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
131 # define MEM_FORCE_MEMORY_ACCESS 1
135 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
136 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
138 MEM_STATIC unsigned MEM_isLittleEndian(void)
140 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
144 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
146 /* violates C standard on structure alignment.
147 Only use if no other choice to achieve best performance on target platform */
148 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
149 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
150 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
152 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
154 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
156 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
157 /* currently only defined for gcc and icc */
158 typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;
160 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
161 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
162 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
164 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
168 /* default method, safe and standard.
169 can sometimes prove slower */
171 MEM_STATIC U16 MEM_read16(const void* memPtr)
173 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
176 MEM_STATIC U32 MEM_read32(const void* memPtr)
178 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
181 MEM_STATIC U64 MEM_read64(const void* memPtr)
183 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
186 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
188 memcpy(memPtr, &value, sizeof(value));
191 #endif // MEM_FORCE_MEMORY_ACCESS
194 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
196 if (MEM_isLittleEndian())
197 return MEM_read16(memPtr);
200 const BYTE* p = (const BYTE*)memPtr;
201 return (U16)(p[0] + (p[1]<<8));
205 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
207 if (MEM_isLittleEndian())
209 MEM_write16(memPtr, val);
213 BYTE* p = (BYTE*)memPtr;
215 p[1] = (BYTE)(val>>8);
219 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
221 if (MEM_isLittleEndian())
222 return MEM_read32(memPtr);
225 const BYTE* p = (const BYTE*)memPtr;
226 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
231 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
233 if (MEM_isLittleEndian())
234 return MEM_read64(memPtr);
237 const BYTE* p = (const BYTE*)memPtr;
238 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
239 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
244 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
247 return (size_t)MEM_readLE32(memPtr);
249 return (size_t)MEM_readLE64(memPtr);
252 #if defined (__cplusplus)
256 #endif /* MEM_H_MODULE */
259 /* ******************************************************************
261 Part of NewGen Entropy library
262 header file (to include)
263 Copyright (C) 2013-2015, Yann Collet.
265 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
267 Redistribution and use in source and binary forms, with or without
268 modification, are permitted provided that the following conditions are
271 * Redistributions of source code must retain the above copyright
272 notice, this list of conditions and the following disclaimer.
273 * Redistributions in binary form must reproduce the above
274 copyright notice, this list of conditions and the following disclaimer
275 in the documentation and/or other materials provided with the
278 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
279 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
280 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
281 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
282 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
283 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
284 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
285 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
286 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
287 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
288 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
290 You can contact the author at :
291 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
292 - Public forum : https://groups.google.com/forum/#!forum/lz4c
293 ****************************************************************** */
294 #ifndef BITSTREAM_H_MODULE
295 #define BITSTREAM_H_MODULE
297 #if defined (__cplusplus)
303 * This API consists of small unitary functions, which highly benefit from being inlined.
304 * Since link-time-optimization is not available for all compilers,
305 * these functions are defined into a .h to be included.
309 /**********************************************
310 * bitStream decompression API (read backward)
311 **********************************************/
315 unsigned bitsConsumed;
320 typedef enum { BIT_DStream_unfinished = 0,
321 BIT_DStream_endOfBuffer = 1,
322 BIT_DStream_completed = 2,
323 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
324 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
326 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
327 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
328 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
329 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
333 * Start by invoking BIT_initDStream().
334 * A chunk of the bitStream is then stored into a local register.
335 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
336 * You can then retrieve bitFields stored into the local register, **in reverse order**.
337 * Local register is manually filled from memory by the BIT_reloadDStream() method.
338 * A reload guarantee a minimum of ((8*sizeof(size_t))-7) bits when its result is BIT_DStream_unfinished.
339 * Otherwise, it can be less than that, so proceed accordingly.
340 * Checking if DStream has reached its end can be performed with BIT_endOfDStream()
344 /******************************************
346 ******************************************/
347 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
348 /* faster, but works only if nbBits >= 1 */
352 /****************************************************************
354 ****************************************************************/
355 MEM_STATIC unsigned BIT_highbit32 (register U32 val)
357 # if defined(_MSC_VER) /* Visual */
359 _BitScanReverse ( &r, val );
361 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
362 return 31 - __builtin_clz (val);
363 # else /* Software version */
364 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 };
372 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
379 /**********************************************************
381 **********************************************************/
384 * Initialize a BIT_DStream_t.
385 * @bitD : a pointer to an already allocated BIT_DStream_t structure
386 * @srcBuffer must point at the beginning of a bitStream
387 * @srcSize must be the exact size of the bitStream
388 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
390 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
392 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
394 if (srcSize >= sizeof(size_t)) /* normal case */
397 bitD->start = (const char*)srcBuffer;
398 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
399 bitD->bitContainer = MEM_readLEST(bitD->ptr);
400 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
401 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
402 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
407 bitD->start = (const char*)srcBuffer;
408 bitD->ptr = bitD->start;
409 bitD->bitContainer = *(const BYTE*)(bitD->start);
412 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
413 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
414 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
415 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
416 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
417 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
420 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
421 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
422 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
423 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
430 * Provides next n bits from local register
431 * local register is not modified (bits are still present for next read/look)
432 * On 32-bits, maxNbBits==25
433 * On 64-bits, maxNbBits==57
434 * @return : value extracted
436 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
438 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
439 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
442 /*! BIT_lookBitsFast :
443 * unsafe version; only works only if nbBits >= 1 */
444 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
446 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
447 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
450 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
452 bitD->bitsConsumed += nbBits;
456 * Read next n bits from local register.
457 * pay attention to not read more than nbBits contained into local register.
458 * @return : extracted value.
460 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
462 size_t value = BIT_lookBits(bitD, nbBits);
463 BIT_skipBits(bitD, nbBits);
467 /*!BIT_readBitsFast :
468 * unsafe version; only works only if nbBits >= 1 */
469 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
471 size_t value = BIT_lookBitsFast(bitD, nbBits);
472 BIT_skipBits(bitD, nbBits);
476 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
478 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
479 return BIT_DStream_overflow;
481 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
483 bitD->ptr -= bitD->bitsConsumed >> 3;
484 bitD->bitsConsumed &= 7;
485 bitD->bitContainer = MEM_readLEST(bitD->ptr);
486 return BIT_DStream_unfinished;
488 if (bitD->ptr == bitD->start)
490 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
491 return BIT_DStream_completed;
494 U32 nbBytes = bitD->bitsConsumed >> 3;
495 BIT_DStream_status result = BIT_DStream_unfinished;
496 if (bitD->ptr - nbBytes < bitD->start)
498 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
499 result = BIT_DStream_endOfBuffer;
501 bitD->ptr -= nbBytes;
502 bitD->bitsConsumed -= nbBytes*8;
503 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
509 * @return Tells if DStream has reached its exact end
511 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
513 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
516 #if defined (__cplusplus)
520 #endif /* BITSTREAM_H_MODULE */
521 /* ******************************************************************
522 Error codes and messages
523 Copyright (C) 2013-2015, Yann Collet
525 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
527 Redistribution and use in source and binary forms, with or without
528 modification, are permitted provided that the following conditions are
531 * Redistributions of source code must retain the above copyright
532 notice, this list of conditions and the following disclaimer.
533 * Redistributions in binary form must reproduce the above
534 copyright notice, this list of conditions and the following disclaimer
535 in the documentation and/or other materials provided with the
538 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
539 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
540 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
541 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
542 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
543 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
544 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
545 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
546 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
547 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
548 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
550 You can contact the author at :
551 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
552 - Public forum : https://groups.google.com/forum/#!forum/lz4c
553 ****************************************************************** */
554 #ifndef ERROR_H_MODULE
555 #define ERROR_H_MODULE
557 #if defined (__cplusplus)
562 /******************************************
564 ******************************************/
565 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
566 # define ERR_STATIC static inline
567 #elif defined(_MSC_VER)
568 # define ERR_STATIC static __inline
569 #elif defined(__GNUC__)
570 # define ERR_STATIC static __attribute__((unused))
572 # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
576 /******************************************
578 ******************************************/
579 #define PREFIX(name) ZSTD_error_##name
581 #define ERROR(name) (size_t)-PREFIX(name)
583 #define ERROR_LIST(ITEM) \
584 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
585 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
586 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
587 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
588 ITEM(PREFIX(maxCode))
590 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
591 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
593 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
594 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
595 static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
597 ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
599 ERR_STATIC const char* ERR_getErrorName(size_t code)
601 static const char* codeError = "Unspecified error code";
602 if (ERR_isError(code)) return ERR_strings[-(int)(code)];
607 #if defined (__cplusplus)
611 #endif /* ERROR_H_MODULE */
613 Constructor and Destructor of type FSE_CTable
614 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
615 typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
616 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
619 /* ******************************************************************
620 FSE : Finite State Entropy coder
621 header file for static linking (only)
622 Copyright (C) 2013-2015, Yann Collet
624 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
626 Redistribution and use in source and binary forms, with or without
627 modification, are permitted provided that the following conditions are
630 * Redistributions of source code must retain the above copyright
631 notice, this list of conditions and the following disclaimer.
632 * Redistributions in binary form must reproduce the above
633 copyright notice, this list of conditions and the following disclaimer
634 in the documentation and/or other materials provided with the
637 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
638 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
639 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
640 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
641 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
642 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
643 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
644 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
645 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
646 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
647 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
649 You can contact the author at :
650 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
651 - Public forum : https://groups.google.com/forum/#!forum/lz4c
652 ****************************************************************** */
653 #if defined (__cplusplus)
658 /******************************************
660 ******************************************/
661 /* FSE buffer bounds */
662 #define FSE_NCOUNTBOUND 512
663 #define FSE_BLOCKBOUND(size) (size + (size>>7))
664 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
666 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
667 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
668 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
671 /******************************************
673 ******************************************/
674 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
675 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
677 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
678 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
681 /******************************************
682 * FSE symbol decompression API
683 ******************************************/
687 const void* table; /* precise table may vary, depending on U16 */
691 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
693 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
695 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
698 Let's now decompose FSE_decompress_usingDTable() into its unitary components.
699 You will decode FSE-encoded symbols from the bitStream,
700 and also any other bitFields you put in, **in reverse order**.
702 You will need a few variables to track your bitStream. They are :
704 BIT_DStream_t DStream; // Stream context
705 FSE_DState_t DState; // State context. Multiple ones are possible
706 FSE_DTable* DTablePtr; // Decoding table, provided by FSE_buildDTable()
708 The first thing to do is to init the bitStream.
709 errorCode = BIT_initDStream(&DStream, srcBuffer, srcSize);
711 You should then retrieve your initial state(s)
712 (in reverse flushing order if you have several ones) :
713 errorCode = FSE_initDState(&DState, &DStream, DTablePtr);
715 You can then decode your data, symbol after symbol.
716 For information the maximum number of bits read by FSE_decodeSymbol() is 'tableLog'.
717 Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
718 unsigned char symbol = FSE_decodeSymbol(&DState, &DStream);
720 You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
721 Note : maximum allowed nbBits is 25, for 32-bits compatibility
722 size_t bitField = BIT_readBits(&DStream, nbBits);
724 All above operations only read from local register (which size depends on size_t).
725 Refueling the register from memory is manually performed by the reload method.
726 endSignal = FSE_reloadDStream(&DStream);
728 BIT_reloadDStream() result tells if there is still some more data to read from DStream.
729 BIT_DStream_unfinished : there is still some data left into the DStream.
730 BIT_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
731 BIT_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
732 BIT_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
734 When reaching end of buffer (BIT_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
735 to properly detect the exact end of stream.
736 After each decoded symbol, check if DStream is fully consumed using this simple test :
737 BIT_reloadDStream(&DStream) >= BIT_DStream_completed
739 When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
740 Checking if DStream has reached its end is performed by :
741 BIT_endOfDStream(&DStream);
742 Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
743 FSE_endOfDState(&DState);
747 /******************************************
749 ******************************************/
750 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
751 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
754 /******************************************
755 * Implementation of inline functions
756 ******************************************/
763 } FSE_DTableHeader; /* sizeof U32 */
767 unsigned short newState;
768 unsigned char symbol;
769 unsigned char nbBits;
770 } FSE_decode_t; /* size == U32 */
772 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
774 FSE_DTableHeader DTableH;
775 memcpy(&DTableH, dt, sizeof(DTableH));
776 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
777 BIT_reloadDStream(bitD);
778 DStatePtr->table = dt + 1;
781 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
783 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
784 const U32 nbBits = DInfo.nbBits;
785 BYTE symbol = DInfo.symbol;
786 size_t lowBits = BIT_readBits(bitD, nbBits);
788 DStatePtr->state = DInfo.newState + lowBits;
792 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
794 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
795 const U32 nbBits = DInfo.nbBits;
796 BYTE symbol = DInfo.symbol;
797 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
799 DStatePtr->state = DInfo.newState + lowBits;
803 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
805 return DStatePtr->state == 0;
809 #if defined (__cplusplus)
812 /* ******************************************************************
813 Huff0 : Huffman coder, part of New Generation Entropy library
814 header file for static linking (only)
815 Copyright (C) 2013-2015, Yann Collet
817 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
819 Redistribution and use in source and binary forms, with or without
820 modification, are permitted provided that the following conditions are
823 * Redistributions of source code must retain the above copyright
824 notice, this list of conditions and the following disclaimer.
825 * Redistributions in binary form must reproduce the above
826 copyright notice, this list of conditions and the following disclaimer
827 in the documentation and/or other materials provided with the
830 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
831 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
832 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
833 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
834 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
835 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
836 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
837 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
838 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
839 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
840 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
842 You can contact the author at :
843 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
844 - Public forum : https://groups.google.com/forum/#!forum/lz4c
845 ****************************************************************** */
847 #if defined (__cplusplus)
851 /******************************************
852 * Static allocation macros
853 ******************************************/
854 /* Huff0 buffer bounds */
855 #define HUF_CTABLEBOUND 129
856 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
857 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
859 /* static allocation of Huff0's DTable */
860 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
861 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
862 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
863 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
864 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
865 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
866 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
869 /******************************************
871 ******************************************/
872 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
873 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
874 static size_t HUF_decompress4X6 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* quad-symbols decoder */
877 #if defined (__cplusplus)
882 zstd - standard compression library
884 Copyright (C) 2014-2015, Yann Collet.
886 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
888 Redistribution and use in source and binary forms, with or without
889 modification, are permitted provided that the following conditions are
891 * Redistributions of source code must retain the above copyright
892 notice, this list of conditions and the following disclaimer.
893 * Redistributions in binary form must reproduce the above
894 copyright notice, this list of conditions and the following disclaimer
895 in the documentation and/or other materials provided with the
897 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
898 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
899 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
900 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
901 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
902 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
903 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
904 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
905 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
906 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
907 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
909 You can contact the author at :
910 - zstd source repository : https://github.com/Cyan4973/zstd
911 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
914 #if defined (__cplusplus)
918 /* *************************************
920 ***************************************/
921 #include <stddef.h> /* size_t */
924 /* *************************************
926 ***************************************/
927 #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
928 #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
929 #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
930 #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
933 /* *************************************
935 ***************************************/
936 typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */
938 #if defined (__cplusplus)
942 zstd - standard compression library
943 Header File for static linking only
944 Copyright (C) 2014-2015, Yann Collet.
946 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
948 Redistribution and use in source and binary forms, with or without
949 modification, are permitted provided that the following conditions are
951 * Redistributions of source code must retain the above copyright
952 notice, this list of conditions and the following disclaimer.
953 * Redistributions in binary form must reproduce the above
954 copyright notice, this list of conditions and the following disclaimer
955 in the documentation and/or other materials provided with the
957 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
958 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
959 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
960 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
961 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
962 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
963 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
964 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
965 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
966 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
967 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
969 You can contact the author at :
970 - zstd source repository : https://github.com/Cyan4973/zstd
971 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
974 /* The objects defined into this file should be considered experimental.
975 * They are not labelled stable, as their prototype may change in the future.
976 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
979 #if defined (__cplusplus)
983 /* *************************************
984 * Streaming functions
985 ***************************************/
987 typedef struct ZSTD_DCtx_s ZSTD_DCtx;
990 Use above functions alternatively.
991 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
992 ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
993 Result is the number of bytes regenerated within 'dst'.
994 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
997 /* *************************************
998 * Prefix - version detection
999 ***************************************/
1000 #define ZSTD_magicNumber 0xFD2FB522 /* v0.2 (current)*/
1003 #if defined (__cplusplus)
1006 /* ******************************************************************
1007 FSE : Finite State Entropy coder
1008 Copyright (C) 2013-2015, Yann Collet.
1010 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1012 Redistribution and use in source and binary forms, with or without
1013 modification, are permitted provided that the following conditions are
1016 * Redistributions of source code must retain the above copyright
1017 notice, this list of conditions and the following disclaimer.
1018 * Redistributions in binary form must reproduce the above
1019 copyright notice, this list of conditions and the following disclaimer
1020 in the documentation and/or other materials provided with the
1023 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1024 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1025 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1026 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1027 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1028 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1029 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1030 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1031 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1032 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1033 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1035 You can contact the author at :
1036 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1037 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1038 ****************************************************************** */
1040 #ifndef FSE_COMMONDEFS_ONLY
1042 /****************************************************************
1044 ****************************************************************/
1046 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1047 * Increasing memory usage improves compression ratio
1048 * Reduced memory usage can improve speed, due to cache effect
1049 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1050 #define FSE_MAX_MEMORY_USAGE 14
1051 #define FSE_DEFAULT_MEMORY_USAGE 13
1053 /* FSE_MAX_SYMBOL_VALUE :
1054 * Maximum symbol value authorized.
1055 * Required for proper stack allocation */
1056 #define FSE_MAX_SYMBOL_VALUE 255
1059 /****************************************************************
1060 * template functions type & suffix
1061 ****************************************************************/
1062 #define FSE_FUNCTION_TYPE BYTE
1063 #define FSE_FUNCTION_EXTENSION
1066 /****************************************************************
1068 ****************************************************************/
1069 #endif /* !FSE_COMMONDEFS_ONLY */
1072 /****************************************************************
1073 * Compiler specifics
1074 ****************************************************************/
1075 #ifdef _MSC_VER /* Visual Studio */
1076 # define FORCE_INLINE static __forceinline
1077 # include <intrin.h> /* For Visual 2005 */
1078 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1079 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1081 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1083 # define FORCE_INLINE static inline __attribute__((always_inline))
1085 # define FORCE_INLINE static inline
1088 # define FORCE_INLINE static
1089 # endif /* __STDC_VERSION__ */
1093 /****************************************************************
1095 ****************************************************************/
1096 #include <stdlib.h> /* malloc, free, qsort */
1097 #include <string.h> /* memcpy, memset */
1098 #include <stdio.h> /* printf (debug) */
1100 /****************************************************************
1102 *****************************************************************/
1103 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
1104 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
1105 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
1106 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
1107 #define FSE_MIN_TABLELOG 5
1109 #define FSE_TABLELOG_ABSOLUTE_MAX 15
1110 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1111 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1115 /****************************************************************
1117 ****************************************************************/
1118 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1121 /****************************************************************
1123 ****************************************************************/
1124 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1127 /****************************************************************
1129 ****************************************************************/
1131 designed to be included
1132 for type-specific functions (template emulation in C)
1133 Objective is to write these functions only once, for improved maintenance
1137 #ifndef FSE_FUNCTION_EXTENSION
1138 # error "FSE_FUNCTION_EXTENSION must be defined"
1140 #ifndef FSE_FUNCTION_TYPE
1141 # error "FSE_FUNCTION_TYPE must be defined"
1144 /* Function names */
1145 #define FSE_CAT(X,Y) X##Y
1146 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1147 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1150 /* Function templates */
1152 #define FSE_DECODE_TYPE FSE_decode_t
1154 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1156 static size_t FSE_buildDTable
1157 (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1160 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1161 FSE_DTableHeader DTableH;
1162 const U32 tableSize = 1 << tableLog;
1163 const U32 tableMask = tableSize-1;
1164 const U32 step = FSE_tableStep(tableSize);
1165 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1167 U32 highThreshold = tableSize-1;
1168 const S16 largeLimit= (S16)(1 << (tableLog-1));
1173 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1174 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1176 /* Init, lay down lowprob symbols */
1177 DTableH.tableLog = (U16)tableLog;
1178 for (s=0; s<=maxSymbolValue; s++)
1180 if (normalizedCounter[s]==-1)
1182 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1187 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1188 symbolNext[s] = normalizedCounter[s];
1192 /* Spread symbols */
1193 for (s=0; s<=maxSymbolValue; s++)
1196 for (i=0; i<normalizedCounter[s]; i++)
1198 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1199 position = (position + step) & tableMask;
1200 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1204 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1206 /* Build Decoding table */
1209 for (i=0; i<tableSize; i++)
1211 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1212 U16 nextState = symbolNext[symbol]++;
1213 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1214 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1218 DTableH.fastMode = (U16)noLarge;
1219 memcpy(dt, &DTableH, sizeof(DTableH)); /* memcpy(), to avoid strict aliasing warnings */
1224 #ifndef FSE_COMMONDEFS_ONLY
1225 /******************************************
1226 * FSE helper functions
1227 ******************************************/
1228 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1231 /****************************************************************
1232 * FSE NCount encoding-decoding
1233 ****************************************************************/
1234 static short FSE_abs(short a)
1236 return (short)(a<0 ? -a : a);
1239 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1240 const void* headerBuffer, size_t hbSize)
1242 const BYTE* const istart = (const BYTE*) headerBuffer;
1243 const BYTE* const iend = istart + hbSize;
1244 const BYTE* ip = istart;
1250 unsigned charnum = 0;
1253 if (hbSize < 4) return ERROR(srcSize_wrong);
1254 bitStream = MEM_readLE32(ip);
1255 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1256 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1259 *tableLogPtr = nbBits;
1260 remaining = (1<<nbBits)+1;
1261 threshold = 1<<nbBits;
1264 while ((remaining>1) && (charnum<=*maxSVPtr))
1268 unsigned n0 = charnum;
1269 while ((bitStream & 0xFFFF) == 0xFFFF)
1275 bitStream = MEM_readLE32(ip) >> bitCount;
1283 while ((bitStream & 3) == 3)
1289 n0 += bitStream & 3;
1291 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1292 while (charnum < n0) normalizedCounter[charnum++] = 0;
1293 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1297 bitStream = MEM_readLE32(ip) >> bitCount;
1303 const short max = (short)((2*threshold-1)-remaining);
1306 if ((bitStream & (threshold-1)) < (U32)max)
1308 count = (short)(bitStream & (threshold-1));
1309 bitCount += nbBits-1;
1313 count = (short)(bitStream & (2*threshold-1));
1314 if (count >= threshold) count -= max;
1318 count--; /* extra accuracy */
1319 remaining -= FSE_abs(count);
1320 normalizedCounter[charnum++] = count;
1322 while (remaining < threshold)
1329 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1336 bitCount -= (int)(8 * (iend - 4 - ip));
1339 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1343 if (remaining != 1) return ERROR(GENERIC);
1344 *maxSVPtr = charnum-1;
1346 ip += (bitCount+7)>>3;
1347 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1352 /*********************************************************
1353 * Decompression (Byte symbols)
1354 *********************************************************/
1355 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1358 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1359 FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */
1361 DTableH->tableLog = 0;
1362 DTableH->fastMode = 0;
1365 cell->symbol = symbolValue;
1372 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1375 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1376 FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1; /* because dt is unsigned */
1377 const unsigned tableSize = 1 << nbBits;
1378 const unsigned tableMask = tableSize - 1;
1379 const unsigned maxSymbolValue = tableMask;
1383 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1385 /* Build Decoding Table */
1386 DTableH->tableLog = (U16)nbBits;
1387 DTableH->fastMode = 1;
1388 for (s=0; s<=maxSymbolValue; s++)
1390 dinfo[s].newState = 0;
1391 dinfo[s].symbol = (BYTE)s;
1392 dinfo[s].nbBits = (BYTE)nbBits;
1398 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1399 void* dst, size_t maxDstSize,
1400 const void* cSrc, size_t cSrcSize,
1401 const FSE_DTable* dt, const unsigned fast)
1403 BYTE* const ostart = (BYTE*) dst;
1405 BYTE* const omax = op + maxDstSize;
1406 BYTE* const olimit = omax-3;
1409 FSE_DState_t state1;
1410 FSE_DState_t state2;
1414 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1415 if (FSE_isError(errorCode)) return errorCode;
1417 FSE_initDState(&state1, &bitD, dt);
1418 FSE_initDState(&state2, &bitD, dt);
1420 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1422 /* 4 symbols per loop */
1423 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1425 op[0] = FSE_GETSYMBOL(&state1);
1427 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1428 BIT_reloadDStream(&bitD);
1430 op[1] = FSE_GETSYMBOL(&state2);
1432 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1433 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1435 op[2] = FSE_GETSYMBOL(&state1);
1437 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1438 BIT_reloadDStream(&bitD);
1440 op[3] = FSE_GETSYMBOL(&state2);
1444 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1447 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1450 *op++ = FSE_GETSYMBOL(&state1);
1452 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1455 *op++ = FSE_GETSYMBOL(&state2);
1459 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1462 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1464 return ERROR(corruption_detected);
1468 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1469 const void* cSrc, size_t cSrcSize,
1470 const FSE_DTable* dt)
1472 FSE_DTableHeader DTableH;
1473 memcpy(&DTableH, dt, sizeof(DTableH));
1475 /* select fast mode (static) */
1476 if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1477 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1481 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1483 const BYTE* const istart = (const BYTE*)cSrc;
1484 const BYTE* ip = istart;
1485 short counting[FSE_MAX_SYMBOL_VALUE+1];
1486 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1488 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1491 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1493 /* normal FSE decoding mode */
1494 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1495 if (FSE_isError(errorCode)) return errorCode;
1496 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1498 cSrcSize -= errorCode;
1500 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1501 if (FSE_isError(errorCode)) return errorCode;
1503 /* always return, even if it is an error code */
1504 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1509 #endif /* FSE_COMMONDEFS_ONLY */
1510 /* ******************************************************************
1511 Huff0 : Huffman coder, part of New Generation Entropy library
1512 Copyright (C) 2013-2015, Yann Collet.
1514 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1516 Redistribution and use in source and binary forms, with or without
1517 modification, are permitted provided that the following conditions are
1520 * Redistributions of source code must retain the above copyright
1521 notice, this list of conditions and the following disclaimer.
1522 * Redistributions in binary form must reproduce the above
1523 copyright notice, this list of conditions and the following disclaimer
1524 in the documentation and/or other materials provided with the
1527 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1528 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1529 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1530 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1531 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1532 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1533 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1534 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1535 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1536 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1537 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1539 You can contact the author at :
1540 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1541 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1542 ****************************************************************** */
1544 /****************************************************************
1545 * Compiler specifics
1546 ****************************************************************/
1547 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1548 /* inline is defined */
1549 #elif defined(_MSC_VER)
1550 # define inline __inline
1552 # define inline /* disable inline */
1556 #ifdef _MSC_VER /* Visual Studio */
1557 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1561 /****************************************************************
1563 ****************************************************************/
1564 #include <stdlib.h> /* malloc, free, qsort */
1565 #include <string.h> /* memcpy, memset */
1566 #include <stdio.h> /* printf (debug) */
1568 /****************************************************************
1570 ****************************************************************/
1571 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1574 /******************************************
1576 ******************************************/
1577 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1579 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1580 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1581 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1582 #define HUF_MAX_SYMBOL_VALUE 255
1583 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1584 # error "HUF_MAX_TABLELOG is too large !"
1589 /*********************************************************
1590 * Huff0 : Huffman block decompression
1591 *********************************************************/
1592 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1594 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1596 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1599 Read compact Huffman tree, saved by HUF_writeCTable
1600 @huffWeight : destination buffer
1601 @return : size read from `src`
1603 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1604 U32* nbSymbolsPtr, U32* tableLogPtr,
1605 const void* src, size_t srcSize)
1609 const BYTE* ip = (const BYTE*) src;
1614 if (!srcSize) return ERROR(srcSize_wrong);
1616 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1618 if (iSize >= 128) /* special header */
1620 if (iSize >= (242)) /* RLE */
1622 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1623 oSize = l[iSize-242];
1624 memset(huffWeight, 1, hwSize);
1627 else /* Incompressible */
1629 oSize = iSize - 127;
1630 iSize = ((oSize+1)/2);
1631 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1632 if (oSize >= hwSize) return ERROR(corruption_detected);
1634 for (n=0; n<oSize; n+=2)
1636 huffWeight[n] = ip[n/2] >> 4;
1637 huffWeight[n+1] = ip[n/2] & 15;
1641 else /* header compressed with FSE (normal case) */
1643 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1644 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1645 if (FSE_isError(oSize)) return oSize;
1648 /* collect weight stats */
1649 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1651 for (n=0; n<oSize; n++)
1653 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1654 rankStats[huffWeight[n]]++;
1655 weightTotal += (1 << huffWeight[n]) >> 1;
1657 if (weightTotal == 0) return ERROR(corruption_detected);
1659 /* get last non-null symbol weight (implied, total must be 2^n) */
1660 tableLog = BIT_highbit32(weightTotal) + 1;
1661 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1663 U32 total = 1 << tableLog;
1664 U32 rest = total - weightTotal;
1665 U32 verif = 1 << BIT_highbit32(rest);
1666 U32 lastWeight = BIT_highbit32(rest) + 1;
1667 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1668 huffWeight[oSize] = (BYTE)lastWeight;
1669 rankStats[lastWeight]++;
1672 /* check tree construction validity */
1673 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1676 *nbSymbolsPtr = (U32)(oSize+1);
1677 *tableLogPtr = tableLog;
1682 /**************************/
1683 /* single-symbol decoding */
1684 /**************************/
1686 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1688 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1689 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1691 const BYTE* ip = (const BYTE*) src;
1692 size_t iSize = ip[0];
1696 void* ptr = DTable+1;
1697 HUF_DEltX2* const dt = (HUF_DEltX2*)ptr;
1699 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1700 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1702 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1703 if (HUF_isError(iSize)) return iSize;
1706 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1707 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1711 for (n=1; n<=tableLog; n++)
1713 U32 current = nextRankStart;
1714 nextRankStart += (rankVal[n] << (n-1));
1715 rankVal[n] = current;
1719 for (n=0; n<nbSymbols; n++)
1721 const U32 w = huffWeight[n];
1722 const U32 length = (1 << w) >> 1;
1725 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1726 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1728 rankVal[w] += length;
1734 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1736 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1737 const BYTE c = dt[val].byte;
1738 BIT_skipBits(Dstream, dt[val].nbBits);
1742 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1743 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1745 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1746 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1747 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1749 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1751 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1753 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1755 BYTE* const pStart = p;
1757 /* up to 4 symbols at a time */
1758 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1760 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1761 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1762 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1763 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1766 /* closer to the end */
1767 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1768 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1770 /* no more data to retrieve from bitstream, hence no need to reload */
1772 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1778 static size_t HUF_decompress4X2_usingDTable(
1779 void* dst, size_t dstSize,
1780 const void* cSrc, size_t cSrcSize,
1783 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1786 const BYTE* const istart = (const BYTE*) cSrc;
1787 BYTE* const ostart = (BYTE*) dst;
1788 BYTE* const oend = ostart + dstSize;
1790 const void* ptr = DTable;
1791 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1792 const U32 dtLog = DTable[0];
1796 BIT_DStream_t bitD1;
1797 BIT_DStream_t bitD2;
1798 BIT_DStream_t bitD3;
1799 BIT_DStream_t bitD4;
1800 const size_t length1 = MEM_readLE16(istart);
1801 const size_t length2 = MEM_readLE16(istart+2);
1802 const size_t length3 = MEM_readLE16(istart+4);
1804 const BYTE* const istart1 = istart + 6; /* jumpTable */
1805 const BYTE* const istart2 = istart1 + length1;
1806 const BYTE* const istart3 = istart2 + length2;
1807 const BYTE* const istart4 = istart3 + length3;
1808 const size_t segmentSize = (dstSize+3) / 4;
1809 BYTE* const opStart2 = ostart + segmentSize;
1810 BYTE* const opStart3 = opStart2 + segmentSize;
1811 BYTE* const opStart4 = opStart3 + segmentSize;
1813 BYTE* op2 = opStart2;
1814 BYTE* op3 = opStart3;
1815 BYTE* op4 = opStart4;
1818 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1819 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1820 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1821 if (HUF_isError(errorCode)) return errorCode;
1822 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1823 if (HUF_isError(errorCode)) return errorCode;
1824 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1825 if (HUF_isError(errorCode)) return errorCode;
1826 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1827 if (HUF_isError(errorCode)) return errorCode;
1829 /* 16-32 symbols per loop (4-8 symbols per stream) */
1830 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1831 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1833 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1834 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1835 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1836 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1837 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1838 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1839 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1840 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1841 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1842 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1843 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1844 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1845 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1846 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1847 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1848 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1850 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1853 /* check corruption */
1854 if (op1 > opStart2) return ERROR(corruption_detected);
1855 if (op2 > opStart3) return ERROR(corruption_detected);
1856 if (op3 > opStart4) return ERROR(corruption_detected);
1857 /* note : op4 supposed already verified within main loop */
1859 /* finish bitStreams one by one */
1860 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1861 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1862 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1863 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1866 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1867 if (!endSignal) return ERROR(corruption_detected);
1875 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1877 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1878 const BYTE* ip = (const BYTE*) cSrc;
1881 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1882 if (HUF_isError(errorCode)) return errorCode;
1883 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1885 cSrcSize -= errorCode;
1887 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1891 /***************************/
1892 /* double-symbols decoding */
1893 /***************************/
1895 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1896 const U32* rankValOrigin, const int minWeight,
1897 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1898 U32 nbBitsBaseline, U16 baseSeq)
1901 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1904 /* get pre-calculated rankVal */
1905 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1907 /* fill skipped values */
1910 U32 i, skipSize = rankVal[minWeight];
1911 MEM_writeLE16(&(DElt.sequence), baseSeq);
1912 DElt.nbBits = (BYTE)(consumed);
1914 for (i = 0; i < skipSize; i++)
1919 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1921 const U32 symbol = sortedSymbols[s].symbol;
1922 const U32 weight = sortedSymbols[s].weight;
1923 const U32 nbBits = nbBitsBaseline - weight;
1924 const U32 length = 1 << (sizeLog-nbBits);
1925 const U32 start = rankVal[weight];
1927 const U32 end = start + length;
1929 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1930 DElt.nbBits = (BYTE)(nbBits + consumed);
1932 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1934 rankVal[weight] += length;
1938 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1940 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1941 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1942 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1943 const U32 nbBitsBaseline)
1945 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1946 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1947 const U32 minBits = nbBitsBaseline - maxWeight;
1950 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1953 for (s=0; s<sortedListSize; s++)
1955 const U16 symbol = sortedList[s].symbol;
1956 const U32 weight = sortedList[s].weight;
1957 const U32 nbBits = nbBitsBaseline - weight;
1958 const U32 start = rankVal[weight];
1959 const U32 length = 1 << (targetLog-nbBits);
1961 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1964 int minWeight = nbBits + scaleLog;
1965 if (minWeight < 1) minWeight = 1;
1966 sortedRank = rankStart[minWeight];
1967 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1968 rankValOrigin[nbBits], minWeight,
1969 sortedList+sortedRank, sortedListSize-sortedRank,
1970 nbBitsBaseline, symbol);
1975 const U32 end = start + length;
1978 MEM_writeLE16(&(DElt.sequence), symbol);
1979 DElt.nbBits = (BYTE)(nbBits);
1981 for (i = start; i < end; i++)
1984 rankVal[weight] += length;
1988 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1990 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1991 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1992 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1993 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1994 U32* const rankStart = rankStart0+1;
1996 U32 tableLog, maxW, sizeOfSort, nbSymbols;
1997 const U32 memLog = DTable[0];
1998 const BYTE* ip = (const BYTE*) src;
1999 size_t iSize = ip[0];
2001 HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
2003 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
2004 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2005 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2007 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2008 if (HUF_isError(iSize)) return iSize;
2011 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2013 /* find maxWeight */
2014 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2015 {if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
2017 /* Get start index of each weight */
2019 U32 w, nextRankStart = 0;
2020 for (w=1; w<=maxW; w++)
2022 U32 current = nextRankStart;
2023 nextRankStart += rankStats[w];
2024 rankStart[w] = current;
2026 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2027 sizeOfSort = nextRankStart;
2030 /* sort symbols by weight */
2033 for (s=0; s<nbSymbols; s++)
2035 U32 w = weightList[s];
2036 U32 r = rankStart[w]++;
2037 sortedSymbol[r].symbol = (BYTE)s;
2038 sortedSymbol[r].weight = (BYTE)w;
2040 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2045 const U32 minBits = tableLog+1 - maxW;
2046 U32 nextRankVal = 0;
2048 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2049 U32* rankVal0 = rankVal[0];
2050 for (w=1; w<=maxW; w++)
2052 U32 current = nextRankVal;
2053 nextRankVal += rankStats[w] << (w+rescale);
2054 rankVal0[w] = current;
2056 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2058 U32* rankValPtr = rankVal[consumed];
2059 for (w = 1; w <= maxW; w++)
2061 rankValPtr[w] = rankVal0[w] >> consumed;
2066 HUF_fillDTableX4(dt, memLog,
2067 sortedSymbol, sizeOfSort,
2068 rankStart0, rankVal, maxW,
2075 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2077 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2078 memcpy(op, dt+val, 2);
2079 BIT_skipBits(DStream, dt[val].nbBits);
2080 return dt[val].length;
2083 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2085 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2086 memcpy(op, dt+val, 1);
2087 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2090 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2092 BIT_skipBits(DStream, dt[val].nbBits);
2093 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2094 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 */
2101 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2102 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2104 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2105 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2106 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2108 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2110 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2112 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2114 BYTE* const pStart = p;
2116 /* up to 8 symbols at a time */
2117 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2119 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2120 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2121 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2122 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2125 /* closer to the end */
2126 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2127 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2130 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2133 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2140 static size_t HUF_decompress4X4_usingDTable(
2141 void* dst, size_t dstSize,
2142 const void* cSrc, size_t cSrcSize,
2145 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2148 const BYTE* const istart = (const BYTE*) cSrc;
2149 BYTE* const ostart = (BYTE*) dst;
2150 BYTE* const oend = ostart + dstSize;
2152 const void* ptr = DTable;
2153 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2154 const U32 dtLog = DTable[0];
2158 BIT_DStream_t bitD1;
2159 BIT_DStream_t bitD2;
2160 BIT_DStream_t bitD3;
2161 BIT_DStream_t bitD4;
2162 const size_t length1 = MEM_readLE16(istart);
2163 const size_t length2 = MEM_readLE16(istart+2);
2164 const size_t length3 = MEM_readLE16(istart+4);
2166 const BYTE* const istart1 = istart + 6; /* jumpTable */
2167 const BYTE* const istart2 = istart1 + length1;
2168 const BYTE* const istart3 = istart2 + length2;
2169 const BYTE* const istart4 = istart3 + length3;
2170 const size_t segmentSize = (dstSize+3) / 4;
2171 BYTE* const opStart2 = ostart + segmentSize;
2172 BYTE* const opStart3 = opStart2 + segmentSize;
2173 BYTE* const opStart4 = opStart3 + segmentSize;
2175 BYTE* op2 = opStart2;
2176 BYTE* op3 = opStart3;
2177 BYTE* op4 = opStart4;
2180 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2181 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2182 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2183 if (HUF_isError(errorCode)) return errorCode;
2184 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2185 if (HUF_isError(errorCode)) return errorCode;
2186 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2187 if (HUF_isError(errorCode)) return errorCode;
2188 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2189 if (HUF_isError(errorCode)) return errorCode;
2191 /* 16-32 symbols per loop (4-8 symbols per stream) */
2192 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2193 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2195 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2196 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2197 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2198 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2199 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2200 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2201 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2202 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2203 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2204 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2205 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2206 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2207 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2208 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2209 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2210 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2212 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2215 /* check corruption */
2216 if (op1 > opStart2) return ERROR(corruption_detected);
2217 if (op2 > opStart3) return ERROR(corruption_detected);
2218 if (op3 > opStart4) return ERROR(corruption_detected);
2219 /* note : op4 supposed already verified within main loop */
2221 /* finish bitStreams one by one */
2222 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2223 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2224 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2225 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2228 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2229 if (!endSignal) return ERROR(corruption_detected);
2237 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2239 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2240 const BYTE* ip = (const BYTE*) cSrc;
2242 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2243 if (HUF_isError(hSize)) return hSize;
2244 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2248 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2252 /**********************************/
2253 /* quad-symbol decoding */
2254 /**********************************/
2255 typedef struct { BYTE nbBits; BYTE nbBytes; } HUF_DDescX6;
2256 typedef union { BYTE byte[4]; U32 sequence; } HUF_DSeqX6;
2258 /* recursive, up to level 3; may benefit from <template>-like strategy to nest each level inline */
2259 static void HUF_fillDTableX6LevelN(HUF_DDescX6* DDescription, HUF_DSeqX6* DSequence, int sizeLog,
2260 const rankVal_t rankValOrigin, const U32 consumed, const int minWeight, const U32 maxWeight,
2261 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize, const U32* rankStart,
2262 const U32 nbBitsBaseline, HUF_DSeqX6 baseSeq, HUF_DDescX6 DDesc)
2264 const int scaleLog = nbBitsBaseline - sizeLog; /* note : targetLog >= (nbBitsBaseline-1), hence scaleLog <= 1 */
2265 const int minBits = nbBitsBaseline - maxWeight;
2266 const U32 level = DDesc.nbBytes;
2267 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
2268 U32 symbolStartPos, s;
2270 /* local rankVal, will be modified */
2271 memcpy(rankVal, rankValOrigin[consumed], sizeof(rankVal));
2273 /* fill skipped values */
2277 const U32 skipSize = rankVal[minWeight];
2278 for (i = 0; i < skipSize; i++)
2280 DSequence[i] = baseSeq;
2281 DDescription[i] = DDesc;
2287 symbolStartPos = rankStart[minWeight];
2288 for (s=symbolStartPos; s<sortedListSize; s++)
2290 const BYTE symbol = sortedSymbols[s].symbol;
2291 const U32 weight = sortedSymbols[s].weight; /* >= 1 (sorted) */
2292 const int nbBits = nbBitsBaseline - weight; /* >= 1 (by construction) */
2293 const int totalBits = consumed+nbBits;
2294 const U32 start = rankVal[weight];
2295 const U32 length = 1 << (sizeLog-nbBits);
2296 baseSeq.byte[level] = symbol;
2297 DDesc.nbBits = (BYTE)totalBits;
2299 if ((level<3) && (sizeLog-totalBits >= minBits)) /* enough room for another symbol */
2301 int nextMinWeight = totalBits + scaleLog;
2302 if (nextMinWeight < 1) nextMinWeight = 1;
2303 HUF_fillDTableX6LevelN(DDescription+start, DSequence+start, sizeLog-nbBits,
2304 rankValOrigin, totalBits, nextMinWeight, maxWeight,
2305 sortedSymbols, sortedListSize, rankStart,
2306 nbBitsBaseline, baseSeq, DDesc); /* recursive (max : level 3) */
2311 const U32 end = start + length;
2312 for (i = start; i < end; i++)
2314 DDescription[i] = DDesc;
2315 DSequence[i] = baseSeq;
2318 rankVal[weight] += length;
2323 /* note : same preparation as X4 */
2324 static size_t HUF_readDTableX6 (U32* DTable, const void* src, size_t srcSize)
2326 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
2327 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
2328 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2329 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2330 U32* const rankStart = rankStart0+1;
2331 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2333 const U32 memLog = DTable[0];
2334 const BYTE* ip = (const BYTE*) src;
2335 size_t iSize = ip[0];
2337 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2338 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2340 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2341 if (HUF_isError(iSize)) return iSize;
2344 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable is too small */
2346 /* find maxWeight */
2347 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2348 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
2351 /* Get start index of each weight */
2353 U32 w, nextRankStart = 0;
2354 for (w=1; w<=maxW; w++)
2356 U32 current = nextRankStart;
2357 nextRankStart += rankStats[w];
2358 rankStart[w] = current;
2360 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2361 sizeOfSort = nextRankStart;
2364 /* sort symbols by weight */
2367 for (s=0; s<nbSymbols; s++)
2369 U32 w = weightList[s];
2370 U32 r = rankStart[w]++;
2371 sortedSymbol[r].symbol = (BYTE)s;
2372 sortedSymbol[r].weight = (BYTE)w;
2374 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2379 const U32 minBits = tableLog+1 - maxW;
2380 U32 nextRankVal = 0;
2382 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2383 U32* rankVal0 = rankVal[0];
2384 for (w=1; w<=maxW; w++)
2386 U32 current = nextRankVal;
2387 nextRankVal += rankStats[w] << (w+rescale);
2388 rankVal0[w] = current;
2390 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2392 U32* rankValPtr = rankVal[consumed];
2393 for (w = 1; w <= maxW; w++)
2395 rankValPtr[w] = rankVal0[w] >> consumed;
2403 void* ptr = DTable+1;
2404 HUF_DDescX6* DDescription = (HUF_DDescX6*)(ptr);
2405 void* dSeqStart = DTable + 1 + ((size_t)1<<(memLog-1));
2406 HUF_DSeqX6* DSequence = (HUF_DSeqX6*)(dSeqStart);
2412 HUF_fillDTableX6LevelN(DDescription, DSequence, memLog,
2413 (const U32 (*)[HUF_ABSOLUTEMAX_TABLELOG + 1])rankVal, 0, 1, maxW,
2414 sortedSymbol, sizeOfSort, rankStart0,
2415 tableLog+1, DSeq, DDesc);
2422 static U32 HUF_decodeSymbolX6(void* op, BIT_DStream_t* DStream, const HUF_DDescX6* dd, const HUF_DSeqX6* ds, const U32 dtLog)
2424 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2425 memcpy(op, ds+val, sizeof(HUF_DSeqX6));
2426 BIT_skipBits(DStream, dd[val].nbBits);
2427 return dd[val].nbBytes;
2430 static U32 HUF_decodeLastSymbolsX6(void* op, const U32 maxL, BIT_DStream_t* DStream,
2431 const HUF_DDescX6* dd, const HUF_DSeqX6* ds, const U32 dtLog)
2433 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2434 U32 length = dd[val].nbBytes;
2437 memcpy(op, ds+val, length);
2438 BIT_skipBits(DStream, dd[val].nbBits);
2441 memcpy(op, ds+val, maxL);
2442 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2444 BIT_skipBits(DStream, dd[val].nbBits);
2445 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2446 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 */
2452 #define HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr) \
2453 ptr += HUF_decodeSymbolX6(ptr, DStreamPtr, dd, ds, dtLog)
2455 #define HUF_DECODE_SYMBOLX6_1(ptr, DStreamPtr) \
2456 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2457 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2459 #define HUF_DECODE_SYMBOLX6_2(ptr, DStreamPtr) \
2461 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2463 static inline size_t HUF_decodeStreamX6(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const U32* DTable, const U32 dtLog)
2465 const void* ddPtr = DTable+1;
2466 const HUF_DDescX6* dd = (const HUF_DDescX6*)(ddPtr);
2467 const void* dsPtr = DTable + 1 + ((size_t)1<<(dtLog-1));
2468 const HUF_DSeqX6* ds = (const HUF_DSeqX6*)(dsPtr);
2469 BYTE* const pStart = p;
2471 /* up to 16 symbols at a time */
2472 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-16))
2474 HUF_DECODE_SYMBOLX6_2(p, bitDPtr);
2475 HUF_DECODE_SYMBOLX6_1(p, bitDPtr);
2476 HUF_DECODE_SYMBOLX6_2(p, bitDPtr);
2477 HUF_DECODE_SYMBOLX6_0(p, bitDPtr);
2480 /* closer to the end, up to 4 symbols at a time */
2481 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
2482 HUF_DECODE_SYMBOLX6_0(p, bitDPtr);
2485 HUF_DECODE_SYMBOLX6_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2488 p += HUF_decodeLastSymbolsX6(p, (U32)(pEnd-p), bitDPtr, dd, ds, dtLog);
2495 static size_t HUF_decompress4X6_usingDTable(
2496 void* dst, size_t dstSize,
2497 const void* cSrc, size_t cSrcSize,
2500 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2503 const BYTE* const istart = (const BYTE*) cSrc;
2504 BYTE* const ostart = (BYTE*) dst;
2505 BYTE* const oend = ostart + dstSize;
2507 const U32 dtLog = DTable[0];
2508 const void* ddPtr = DTable+1;
2509 const HUF_DDescX6* dd = (const HUF_DDescX6*)(ddPtr);
2510 const void* dsPtr = DTable + 1 + ((size_t)1<<(dtLog-1));
2511 const HUF_DSeqX6* ds = (const HUF_DSeqX6*)(dsPtr);
2515 BIT_DStream_t bitD1;
2516 BIT_DStream_t bitD2;
2517 BIT_DStream_t bitD3;
2518 BIT_DStream_t bitD4;
2519 const size_t length1 = MEM_readLE16(istart);
2520 const size_t length2 = MEM_readLE16(istart+2);
2521 const size_t length3 = MEM_readLE16(istart+4);
2523 const BYTE* const istart1 = istart + 6; /* jumpTable */
2524 const BYTE* const istart2 = istart1 + length1;
2525 const BYTE* const istart3 = istart2 + length2;
2526 const BYTE* const istart4 = istart3 + length3;
2527 const size_t segmentSize = (dstSize+3) / 4;
2528 BYTE* const opStart2 = ostart + segmentSize;
2529 BYTE* const opStart3 = opStart2 + segmentSize;
2530 BYTE* const opStart4 = opStart3 + segmentSize;
2532 BYTE* op2 = opStart2;
2533 BYTE* op3 = opStart3;
2534 BYTE* op4 = opStart4;
2537 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2538 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2539 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2540 if (HUF_isError(errorCode)) return errorCode;
2541 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2542 if (HUF_isError(errorCode)) return errorCode;
2543 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2544 if (HUF_isError(errorCode)) return errorCode;
2545 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2546 if (HUF_isError(errorCode)) return errorCode;
2548 /* 16-64 symbols per loop (4-16 symbols per stream) */
2549 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2550 for ( ; (op3 <= opStart4) && (endSignal==BIT_DStream_unfinished) && (op4<=(oend-16)) ; )
2552 HUF_DECODE_SYMBOLX6_2(op1, &bitD1);
2553 HUF_DECODE_SYMBOLX6_2(op2, &bitD2);
2554 HUF_DECODE_SYMBOLX6_2(op3, &bitD3);
2555 HUF_DECODE_SYMBOLX6_2(op4, &bitD4);
2556 HUF_DECODE_SYMBOLX6_1(op1, &bitD1);
2557 HUF_DECODE_SYMBOLX6_1(op2, &bitD2);
2558 HUF_DECODE_SYMBOLX6_1(op3, &bitD3);
2559 HUF_DECODE_SYMBOLX6_1(op4, &bitD4);
2560 HUF_DECODE_SYMBOLX6_2(op1, &bitD1);
2561 HUF_DECODE_SYMBOLX6_2(op2, &bitD2);
2562 HUF_DECODE_SYMBOLX6_2(op3, &bitD3);
2563 HUF_DECODE_SYMBOLX6_2(op4, &bitD4);
2564 HUF_DECODE_SYMBOLX6_0(op1, &bitD1);
2565 HUF_DECODE_SYMBOLX6_0(op2, &bitD2);
2566 HUF_DECODE_SYMBOLX6_0(op3, &bitD3);
2567 HUF_DECODE_SYMBOLX6_0(op4, &bitD4);
2569 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2572 /* check corruption */
2573 if (op1 > opStart2) return ERROR(corruption_detected);
2574 if (op2 > opStart3) return ERROR(corruption_detected);
2575 if (op3 > opStart4) return ERROR(corruption_detected);
2576 /* note : op4 supposed already verified within main loop */
2578 /* finish bitStreams one by one */
2579 HUF_decodeStreamX6(op1, &bitD1, opStart2, DTable, dtLog);
2580 HUF_decodeStreamX6(op2, &bitD2, opStart3, DTable, dtLog);
2581 HUF_decodeStreamX6(op3, &bitD3, opStart4, DTable, dtLog);
2582 HUF_decodeStreamX6(op4, &bitD4, oend, DTable, dtLog);
2585 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2586 if (!endSignal) return ERROR(corruption_detected);
2594 static size_t HUF_decompress4X6 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2596 HUF_CREATE_STATIC_DTABLEX6(DTable, HUF_MAX_TABLELOG);
2597 const BYTE* ip = (const BYTE*) cSrc;
2599 size_t hSize = HUF_readDTableX6 (DTable, cSrc, cSrcSize);
2600 if (HUF_isError(hSize)) return hSize;
2601 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2605 return HUF_decompress4X6_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2609 /**********************************/
2610 /* Generic decompression selector */
2611 /**********************************/
2613 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2614 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2616 /* single, double, quad */
2617 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2618 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2619 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2620 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2621 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2622 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2623 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2624 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2625 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2626 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2627 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2628 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2629 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2630 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2631 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2632 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2635 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2637 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2639 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, HUF_decompress4X6 };
2640 /* estimate decompression time */
2642 const U32 D256 = (U32)(dstSize >> 8);
2647 /* validation checks */
2648 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2649 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2650 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2651 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2653 /* decoder timing evaluation */
2654 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2656 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2658 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2660 if (Dtime[1] < Dtime[0]) algoNb = 1;
2661 if (Dtime[2] < Dtime[algoNb]) algoNb = 2;
2663 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2665 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2666 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2667 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2670 zstd - standard compression library
2671 Copyright (C) 2014-2015, Yann Collet.
2673 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2675 Redistribution and use in source and binary forms, with or without
2676 modification, are permitted provided that the following conditions are
2678 * Redistributions of source code must retain the above copyright
2679 notice, this list of conditions and the following disclaimer.
2680 * Redistributions in binary form must reproduce the above
2681 copyright notice, this list of conditions and the following disclaimer
2682 in the documentation and/or other materials provided with the
2684 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2685 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2686 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2687 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2688 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2689 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2690 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2691 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2692 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2693 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2694 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2696 You can contact the author at :
2697 - zstd source repository : https://github.com/Cyan4973/zstd
2698 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2701 /* ***************************************************************
2703 *****************************************************************/
2706 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2707 * Increasing memory usage improves compression ratio
2708 * Reduced memory usage can improve speed, due to cache effect
2710 #define ZSTD_MEMORY_USAGE 17
2714 * Select how default compression functions will allocate memory for their hash table,
2715 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2716 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2718 #ifndef ZSTD_HEAPMODE
2719 # define ZSTD_HEAPMODE 1
2720 #endif /* ZSTD_HEAPMODE */
2724 * decompressor can decode older formats (starting from Zstd 0.1+)
2726 #ifndef ZSTD_LEGACY_SUPPORT
2727 # define ZSTD_LEGACY_SUPPORT 1
2731 /* *******************************************************
2733 *********************************************************/
2734 #include <stdlib.h> /* calloc */
2735 #include <string.h> /* memcpy, memmove */
2736 #include <stdio.h> /* debug : printf */
2739 /* *******************************************************
2740 * Compiler specifics
2741 *********************************************************/
2743 # include <immintrin.h> /* AVX2 intrinsics */
2746 #ifdef _MSC_VER /* Visual Studio */
2747 # include <intrin.h> /* For Visual 2005 */
2748 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2749 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2753 /* *******************************************************
2755 *********************************************************/
2756 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2757 #define HASH_TABLESIZE (1 << HASH_LOG)
2758 #define HASH_MASK (HASH_TABLESIZE - 1)
2760 #define KNUTH 2654435761
2769 #define KB *(1 <<10)
2770 #define MB *(1 <<20)
2771 #define GB *(1U<<30)
2773 #define BLOCKSIZE (128 KB) /* define, for static allocation */
2774 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2775 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2779 #define WORKPLACESIZE (BLOCKSIZE*3)
2784 #define MaxML ((1<<MLbits )-1)
2785 #define MaxLL ((1<<LLbits )-1)
2787 #define LitFSELog 11
2791 #define MAX(a,b) ((a)<(b)?(b):(a))
2792 #define MaxSeq MAX(MaxLL, MaxML)
2794 #define LITERAL_NOENTROPY 63
2795 #define COMMAND_NOENTROPY 7 /* to remove */
2797 static const size_t ZSTD_blockHeaderSize = 3;
2798 static const size_t ZSTD_frameHeaderSize = 4;
2801 /* *******************************************************
2803 **********************************************************/
2804 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2806 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2808 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2810 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2811 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2813 const BYTE* ip = (const BYTE*)src;
2814 BYTE* op = (BYTE*)dst;
2815 BYTE* const oend = op + length;
2816 do COPY8(op, ip) while (op < oend);
2820 /* **************************************
2822 ****************************************/
2823 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2827 blockType_t blockType;
2829 } blockProperties_t;
2839 BYTE* litLengthStart;
2841 BYTE* matchLengthStart;
2848 /* *************************************
2850 ***************************************/
2852 * tells if a return value is an error code */
2853 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2857 /* *************************************************************
2858 * Decompression section
2859 ***************************************************************/
2862 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2863 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2864 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2865 void* previousDstEnd;
2872 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2873 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2876 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2878 const BYTE* const in = (const BYTE* const)src;
2882 if (srcSize < 3) return ERROR(srcSize_wrong);
2885 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2887 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2888 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2890 if (bpPtr->blockType == bt_end) return 0;
2891 if (bpPtr->blockType == bt_rle) return 1;
2895 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2897 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2898 memcpy(dst, src, srcSize);
2903 /** ZSTD_decompressLiterals
2904 @return : nb of bytes read from src, or an error code*/
2905 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2906 const void* src, size_t srcSize)
2908 const BYTE* ip = (const BYTE*)src;
2910 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2911 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2913 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2914 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2916 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2918 *maxDstSizePtr = litSize;
2919 return litCSize + 5;
2923 /** ZSTD_decodeLiteralsBlock
2924 @return : nb of bytes read from src (< srcSize )*/
2925 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2926 const void* src, size_t srcSize)
2928 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2929 const BYTE* const istart = (const BYTE* const)src;
2931 /* any compressed block with literals segment must be at least this size */
2932 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2939 size_t litSize = BLOCKSIZE;
2940 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2941 dctx->litPtr = dctx->litBuffer;
2942 dctx->litSize = litSize;
2943 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2944 return readSize; /* works if it's an error too */
2948 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2949 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2951 if (litSize > srcSize-3) return ERROR(corruption_detected);
2952 memcpy(dctx->litBuffer, istart, litSize);
2953 dctx->litPtr = dctx->litBuffer;
2954 dctx->litSize = litSize;
2955 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2958 /* direct reference into compressed stream */
2959 dctx->litPtr = istart+3;
2960 dctx->litSize = litSize;
2965 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2966 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2967 memset(dctx->litBuffer, istart[3], litSize + 8);
2968 dctx->litPtr = dctx->litBuffer;
2969 dctx->litSize = litSize;
2976 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2977 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2978 const void* src, size_t srcSize)
2980 const BYTE* const istart = (const BYTE* const)src;
2981 const BYTE* ip = istart;
2982 const BYTE* const iend = istart + srcSize;
2983 U32 LLtype, Offtype, MLtype;
2984 U32 LLlog, Offlog, MLlog;
2988 if (srcSize < 5) return ERROR(srcSize_wrong);
2991 *nbSeq = MEM_readLE16(ip); ip+=2;
2993 Offtype = (*ip >> 4) & 3;
2994 MLtype = (*ip >> 2) & 3;
2997 dumpsLength = ip[2];
2998 dumpsLength += ip[1] << 8;
3003 dumpsLength = ip[1];
3004 dumpsLength += (ip[0] & 1) << 8;
3009 *dumpsLengthPtr = dumpsLength;
3012 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3016 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
3024 FSE_buildDTable_rle(DTableLL, *ip++); break;
3027 FSE_buildDTable_raw(DTableLL, LLbits); break;
3030 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
3031 if (FSE_isError(headerSize)) return ERROR(GENERIC);
3032 if (LLlog > LLFSELog) return ERROR(corruption_detected);
3034 FSE_buildDTable(DTableLL, norm, max, LLlog);
3041 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3042 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
3046 FSE_buildDTable_raw(DTableOffb, Offbits); break;
3049 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
3050 if (FSE_isError(headerSize)) return ERROR(GENERIC);
3051 if (Offlog > OffFSELog) return ERROR(corruption_detected);
3053 FSE_buildDTable(DTableOffb, norm, max, Offlog);
3060 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3061 FSE_buildDTable_rle(DTableML, *ip++); break;
3064 FSE_buildDTable_raw(DTableML, MLbits); break;
3067 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
3068 if (FSE_isError(headerSize)) return ERROR(GENERIC);
3069 if (MLlog > MLFSELog) return ERROR(corruption_detected);
3071 FSE_buildDTable(DTableML, norm, max, MLlog);
3085 BIT_DStream_t DStream;
3086 FSE_DState_t stateLL;
3087 FSE_DState_t stateOffb;
3088 FSE_DState_t stateML;
3091 const BYTE* dumpsEnd;
3095 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
3101 const BYTE* dumps = seqState->dumps;
3102 const BYTE* const de = seqState->dumpsEnd;
3104 /* Literal length */
3105 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
3106 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3107 seqState->prevOffset = seq->offset;
3108 if (litLength == MaxLL)
3111 if (add < 255) litLength += add;
3114 litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3117 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3122 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
3123 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3124 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3125 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3126 U32 offsetCode, nbBits;
3127 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
3128 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3129 nbBits = offsetCode - 1;
3130 if (offsetCode==0) nbBits = 0; /* cmove */
3131 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
3132 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3133 if (offsetCode==0) offset = prevOffset; /* cmove */
3137 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3138 if (matchLength == MaxML)
3141 if (add < 255) matchLength += add;
3144 matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3147 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3149 matchLength += MINMATCH;
3152 seq->litLength = litLength;
3153 seq->offset = offset;
3154 seq->matchLength = matchLength;
3155 seqState->dumps = dumps;
3159 static size_t ZSTD_execSequence(BYTE* op,
3161 const BYTE** litPtr, const BYTE* const litLimit,
3162 BYTE* const base, BYTE* const oend)
3164 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
3165 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* substracted */
3166 const BYTE* const ostart = op;
3167 BYTE* const oLitEnd = op + sequence.litLength;
3168 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
3169 BYTE* const oend_8 = oend-8;
3170 const BYTE* const litEnd = *litPtr + sequence.litLength;
3173 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
3174 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3175 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
3178 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3180 *litPtr = litEnd; /* update for next sequence */
3184 const BYTE* match = op - sequence.offset;
3187 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
3188 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
3189 if (match < base) return ERROR(corruption_detected);
3191 /* close range match, overlap */
3192 if (sequence.offset < 8)
3194 const int dec64 = dec64table[sequence.offset];
3199 match += dec32table[sequence.offset];
3200 ZSTD_copy4(op+4, match);
3205 ZSTD_copy8(op, match);
3207 op += 8; match += 8;
3209 if (oMatchEnd > oend-(16-MINMATCH))
3213 ZSTD_wildcopy(op, match, oend_8 - op);
3214 match += oend_8 - op;
3217 while (op < oMatchEnd) *op++ = *match++;
3221 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3225 return oMatchEnd - ostart;
3228 static size_t ZSTD_decompressSequences(
3230 void* dst, size_t maxDstSize,
3231 const void* seqStart, size_t seqSize)
3233 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
3234 const BYTE* ip = (const BYTE*)seqStart;
3235 const BYTE* const iend = ip + seqSize;
3236 BYTE* const ostart = (BYTE* const)dst;
3238 BYTE* const oend = ostart + maxDstSize;
3239 size_t errorCode, dumpsLength;
3240 const BYTE* litPtr = dctx->litPtr;
3241 const BYTE* const litEnd = litPtr + dctx->litSize;
3244 U32* DTableLL = dctx->LLTable;
3245 U32* DTableML = dctx->MLTable;
3246 U32* DTableOffb = dctx->OffTable;
3247 BYTE* const base = (BYTE*) (dctx->base);
3249 /* Build Decoding Tables */
3250 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3251 DTableLL, DTableML, DTableOffb,
3253 if (ZSTD_isError(errorCode)) return errorCode;
3256 /* Regen sequences */
3259 seqState_t seqState;
3261 memset(&sequence, 0, sizeof(sequence));
3262 seqState.dumps = dumps;
3263 seqState.dumpsEnd = dumps + dumpsLength;
3264 seqState.prevOffset = 1;
3265 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
3266 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3267 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3268 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3269 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3271 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
3275 ZSTD_decodeSequence(&sequence, &seqState);
3276 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
3277 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
3281 /* check if reached exact end */
3282 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
3283 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
3285 /* last literal segment */
3287 size_t lastLLSize = litEnd - litPtr;
3288 if (litPtr > litEnd) return ERROR(corruption_detected);
3289 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3290 if (op != litPtr) memmove(op, litPtr, lastLLSize);
3299 static size_t ZSTD_decompressBlock(
3301 void* dst, size_t maxDstSize,
3302 const void* src, size_t srcSize)
3304 /* blockType == blockCompressed */
3305 const BYTE* ip = (const BYTE*)src;
3307 /* Decode literals sub-block */
3308 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
3309 if (ZSTD_isError(litCSize)) return litCSize;
3311 srcSize -= litCSize;
3313 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
3317 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3319 const BYTE* ip = (const BYTE*)src;
3320 const BYTE* iend = ip + srcSize;
3321 BYTE* const ostart = (BYTE* const)dst;
3323 BYTE* const oend = ostart + maxDstSize;
3324 size_t remainingSize = srcSize;
3326 blockProperties_t blockProperties;
3329 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3330 magicNumber = MEM_readLE32(src);
3331 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3332 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
3334 /* Loop on each block */
3337 size_t decodedSize=0;
3338 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
3339 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3341 ip += ZSTD_blockHeaderSize;
3342 remainingSize -= ZSTD_blockHeaderSize;
3343 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3345 switch(blockProperties.blockType)
3348 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
3351 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
3354 return ERROR(GENERIC); /* not yet supported */
3358 if (remainingSize) return ERROR(srcSize_wrong);
3361 return ERROR(GENERIC); /* impossible */
3363 if (cBlockSize == 0) break; /* bt_end */
3365 if (ZSTD_isError(decodedSize)) return decodedSize;
3368 remainingSize -= cBlockSize;
3374 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3378 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
3381 static size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
3384 const BYTE* ip = (const BYTE*)src;
3385 size_t remainingSize = srcSize;
3387 blockProperties_t blockProperties;
3390 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3391 magicNumber = MEM_readLE32(src);
3392 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3393 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
3395 /* Loop on each block */
3398 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
3399 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3401 ip += ZSTD_blockHeaderSize;
3402 remainingSize -= ZSTD_blockHeaderSize;
3403 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3405 if (cBlockSize == 0) break; /* bt_end */
3408 remainingSize -= cBlockSize;
3411 return ip - (const BYTE*)src;
3414 /*******************************
3415 * Streaming Decompression API
3416 *******************************/
3418 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
3420 dctx->expected = ZSTD_frameHeaderSize;
3422 dctx->previousDstEnd = NULL;
3427 static ZSTD_DCtx* ZSTD_createDCtx(void)
3429 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
3430 if (dctx==NULL) return NULL;
3431 ZSTD_resetDCtx(dctx);
3435 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3441 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3443 return dctx->expected;
3446 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3449 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3450 if (dst != ctx->previousDstEnd) /* not contiguous */
3453 /* Decompress : frame header */
3454 if (ctx->phase == 0)
3456 /* Check frame magic header */
3457 U32 magicNumber = MEM_readLE32(src);
3458 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3460 ctx->expected = ZSTD_blockHeaderSize;
3464 /* Decompress : block header */
3465 if (ctx->phase == 1)
3467 blockProperties_t bp;
3468 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3469 if (ZSTD_isError(blockSize)) return blockSize;
3470 if (bp.blockType == bt_end)
3477 ctx->expected = blockSize;
3478 ctx->bType = bp.blockType;
3485 /* Decompress : block content */
3491 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3494 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3497 return ERROR(GENERIC); /* not yet handled */
3499 case bt_end : /* should never happen (filtered at phase 1) */
3503 return ERROR(GENERIC);
3506 ctx->expected = ZSTD_blockHeaderSize;
3507 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3516 unsigned ZSTDv02_isError(size_t code)
3518 return ZSTD_isError(code);
3521 size_t ZSTDv02_decompress( void* dst, size_t maxOriginalSize,
3522 const void* src, size_t compressedSize)
3524 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3527 size_t ZSTDv02_findFrameCompressedSize(const void *src, size_t compressedSize)
3529 return ZSTD_findFrameCompressedSize(src, compressedSize);
3532 ZSTDv02_Dctx* ZSTDv02_createDCtx(void)
3534 return (ZSTDv02_Dctx*)ZSTD_createDCtx();
3537 size_t ZSTDv02_freeDCtx(ZSTDv02_Dctx* dctx)
3539 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3542 size_t ZSTDv02_resetDCtx(ZSTDv02_Dctx* dctx)
3544 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3547 size_t ZSTDv02_nextSrcSizeToDecompress(ZSTDv02_Dctx* dctx)
3549 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3552 size_t ZSTDv02_decompressContinue(ZSTDv02_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3554 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);