2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
12 #include <stddef.h> /* size_t, ptrdiff_t */
14 #include "error_private.h"
17 /******************************************
19 ******************************************/
20 #if defined(_MSC_VER) /* Visual Studio */
21 # include <stdlib.h> /* _byteswap_ulong */
22 # include <intrin.h> /* _byteswap_* */
27 /* ******************************************************************
29 low-level memory access routines
30 Copyright (C) 2013-2015, Yann Collet.
32 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
34 Redistribution and use in source and binary forms, with or without
35 modification, are permitted provided that the following conditions are
38 * Redistributions of source code must retain the above copyright
39 notice, this list of conditions and the following disclaimer.
40 * Redistributions in binary form must reproduce the above
41 copyright notice, this list of conditions and the following disclaimer
42 in the documentation and/or other materials provided with the
45 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
46 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
47 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
48 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
49 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
50 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
51 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
52 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
53 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
54 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
55 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
57 You can contact the author at :
58 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
59 - Public forum : https://groups.google.com/forum/#!forum/lz4c
60 ****************************************************************** */
64 #if defined (__cplusplus)
68 /******************************************
70 ******************************************/
71 #include <stddef.h> /* size_t, ptrdiff_t */
72 #include <string.h> /* memcpy */
75 /******************************************
77 ******************************************/
79 # define MEM_STATIC static __attribute__((unused))
80 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
81 # define MEM_STATIC static inline
82 #elif defined(_MSC_VER)
83 # define MEM_STATIC static __inline
85 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
89 /****************************************************************
91 *****************************************************************/
92 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
102 typedef unsigned char BYTE;
103 typedef unsigned short U16;
104 typedef signed short S16;
105 typedef unsigned int U32;
106 typedef signed int S32;
107 typedef unsigned long long U64;
108 typedef signed long long S64;
112 /****************************************************************
114 *****************************************************************/
115 /* MEM_FORCE_MEMORY_ACCESS
116 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
117 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
118 * The below switch allow to select different access method for improved performance.
119 * Method 0 (default) : use `memcpy()`. Safe and portable.
120 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
121 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
122 * Method 2 : direct access. This method is portable but violate C standard.
123 * It can generate buggy code on targets generating assembly depending on alignment.
124 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
125 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
126 * Prefer these methods in priority order (0 > 1 > 2)
128 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
129 # 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__) )
130 # define MEM_FORCE_MEMORY_ACCESS 2
131 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
132 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
133 # define MEM_FORCE_MEMORY_ACCESS 1
137 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
138 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
140 MEM_STATIC unsigned MEM_isLittleEndian(void)
142 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
146 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
148 /* violates C standard on structure alignment.
149 Only use if no other choice to achieve best performance on target platform */
150 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
151 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
152 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
154 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
156 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
158 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
159 /* currently only defined for gcc and icc */
160 typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;
162 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
163 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
164 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
166 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
170 /* default method, safe and standard.
171 can sometimes prove slower */
173 MEM_STATIC U16 MEM_read16(const void* memPtr)
175 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
178 MEM_STATIC U32 MEM_read32(const void* memPtr)
180 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
183 MEM_STATIC U64 MEM_read64(const void* memPtr)
185 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
188 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
190 memcpy(memPtr, &value, sizeof(value));
194 #endif // MEM_FORCE_MEMORY_ACCESS
197 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
199 if (MEM_isLittleEndian())
200 return MEM_read16(memPtr);
203 const BYTE* p = (const BYTE*)memPtr;
204 return (U16)(p[0] + (p[1]<<8));
208 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
210 if (MEM_isLittleEndian())
212 MEM_write16(memPtr, val);
216 BYTE* p = (BYTE*)memPtr;
218 p[1] = (BYTE)(val>>8);
222 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
224 if (MEM_isLittleEndian())
225 return MEM_read32(memPtr);
228 const BYTE* p = (const BYTE*)memPtr;
229 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
233 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
235 if (MEM_isLittleEndian())
236 return MEM_read64(memPtr);
239 const BYTE* p = (const BYTE*)memPtr;
240 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
241 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
246 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
249 return (size_t)MEM_readLE32(memPtr);
251 return (size_t)MEM_readLE64(memPtr);
255 #if defined (__cplusplus)
259 #endif /* MEM_H_MODULE */
262 /* ******************************************************************
264 Part of NewGen Entropy library
265 header file (to include)
266 Copyright (C) 2013-2015, Yann Collet.
268 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
270 Redistribution and use in source and binary forms, with or without
271 modification, are permitted provided that the following conditions are
274 * Redistributions of source code must retain the above copyright
275 notice, this list of conditions and the following disclaimer.
276 * Redistributions in binary form must reproduce the above
277 copyright notice, this list of conditions and the following disclaimer
278 in the documentation and/or other materials provided with the
281 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
282 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
283 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
284 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
285 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
286 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
287 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
288 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
289 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
290 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
291 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
293 You can contact the author at :
294 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
295 - Public forum : https://groups.google.com/forum/#!forum/lz4c
296 ****************************************************************** */
297 #ifndef BITSTREAM_H_MODULE
298 #define BITSTREAM_H_MODULE
300 #if defined (__cplusplus)
306 * This API consists of small unitary functions, which highly benefit from being inlined.
307 * Since link-time-optimization is not available for all compilers,
308 * these functions are defined into a .h to be included.
312 /**********************************************
313 * bitStream decompression API (read backward)
314 **********************************************/
318 unsigned bitsConsumed;
323 typedef enum { BIT_DStream_unfinished = 0,
324 BIT_DStream_endOfBuffer = 1,
325 BIT_DStream_completed = 2,
326 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
327 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
329 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
330 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
331 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
332 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
336 /******************************************
338 ******************************************/
339 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
340 /* faster, but works only if nbBits >= 1 */
344 /****************************************************************
346 ****************************************************************/
347 MEM_STATIC unsigned BIT_highbit32 (U32 val)
349 # if defined(_MSC_VER) /* Visual */
351 _BitScanReverse ( &r, val );
353 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
354 return 31 - __builtin_clz (val);
355 # else /* Software version */
356 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 };
364 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
371 /**********************************************************
373 **********************************************************/
376 * Initialize a BIT_DStream_t.
377 * @bitD : a pointer to an already allocated BIT_DStream_t structure
378 * @srcBuffer must point at the beginning of a bitStream
379 * @srcSize must be the exact size of the bitStream
380 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
382 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
384 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
386 if (srcSize >= sizeof(size_t)) /* normal case */
389 bitD->start = (const char*)srcBuffer;
390 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
391 bitD->bitContainer = MEM_readLEST(bitD->ptr);
392 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
393 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
394 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
399 bitD->start = (const char*)srcBuffer;
400 bitD->ptr = bitD->start;
401 bitD->bitContainer = *(const BYTE*)(bitD->start);
404 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
405 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
406 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
407 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
408 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
409 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
412 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
413 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
414 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
415 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
420 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
422 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
423 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
426 /*! BIT_lookBitsFast :
427 * unsafe version; only works only if nbBits >= 1 */
428 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
430 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
431 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
434 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
436 bitD->bitsConsumed += nbBits;
439 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
441 size_t value = BIT_lookBits(bitD, nbBits);
442 BIT_skipBits(bitD, nbBits);
446 /*!BIT_readBitsFast :
447 * unsafe version; only works only if nbBits >= 1 */
448 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
450 size_t value = BIT_lookBitsFast(bitD, nbBits);
451 BIT_skipBits(bitD, nbBits);
455 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
457 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
458 return BIT_DStream_overflow;
460 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
462 bitD->ptr -= bitD->bitsConsumed >> 3;
463 bitD->bitsConsumed &= 7;
464 bitD->bitContainer = MEM_readLEST(bitD->ptr);
465 return BIT_DStream_unfinished;
467 if (bitD->ptr == bitD->start)
469 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
470 return BIT_DStream_completed;
473 U32 nbBytes = bitD->bitsConsumed >> 3;
474 BIT_DStream_status result = BIT_DStream_unfinished;
475 if (bitD->ptr - nbBytes < bitD->start)
477 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
478 result = BIT_DStream_endOfBuffer;
480 bitD->ptr -= nbBytes;
481 bitD->bitsConsumed -= nbBytes*8;
482 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
488 * @return Tells if DStream has reached its exact end
490 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
492 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
495 #if defined (__cplusplus)
499 #endif /* BITSTREAM_H_MODULE */
500 /* ******************************************************************
501 Error codes and messages
502 Copyright (C) 2013-2015, Yann Collet
504 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
506 Redistribution and use in source and binary forms, with or without
507 modification, are permitted provided that the following conditions are
510 * Redistributions of source code must retain the above copyright
511 notice, this list of conditions and the following disclaimer.
512 * Redistributions in binary form must reproduce the above
513 copyright notice, this list of conditions and the following disclaimer
514 in the documentation and/or other materials provided with the
517 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
518 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
519 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
520 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
521 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
522 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
523 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
524 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
525 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
526 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
527 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
529 You can contact the author at :
530 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
531 - Public forum : https://groups.google.com/forum/#!forum/lz4c
532 ****************************************************************** */
533 #ifndef ERROR_H_MODULE
534 #define ERROR_H_MODULE
536 #if defined (__cplusplus)
541 /******************************************
543 ******************************************/
544 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
545 # define ERR_STATIC static inline
546 #elif defined(_MSC_VER)
547 # define ERR_STATIC static __inline
548 #elif defined(__GNUC__)
549 # define ERR_STATIC static __attribute__((unused))
551 # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
555 /******************************************
557 ******************************************/
558 #define PREFIX(name) ZSTD_error_##name
560 #define ERROR(name) (size_t)-PREFIX(name)
562 #define ERROR_LIST(ITEM) \
563 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
564 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
565 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
566 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
567 ITEM(PREFIX(maxCode))
569 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
570 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
572 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
573 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
574 static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
576 ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
578 ERR_STATIC const char* ERR_getErrorName(size_t code)
580 static const char* codeError = "Unspecified error code";
581 if (ERR_isError(code)) return ERR_strings[-(int)(code)];
586 #if defined (__cplusplus)
590 #endif /* ERROR_H_MODULE */
592 Constructor and Destructor of type FSE_CTable
593 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
594 typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
595 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
598 /* ******************************************************************
599 FSE : Finite State Entropy coder
600 header file for static linking (only)
601 Copyright (C) 2013-2015, Yann Collet
603 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
605 Redistribution and use in source and binary forms, with or without
606 modification, are permitted provided that the following conditions are
609 * Redistributions of source code must retain the above copyright
610 notice, this list of conditions and the following disclaimer.
611 * Redistributions in binary form must reproduce the above
612 copyright notice, this list of conditions and the following disclaimer
613 in the documentation and/or other materials provided with the
616 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
617 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
618 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
619 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
620 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
621 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
622 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
623 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
624 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
625 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
626 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
628 You can contact the author at :
629 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
630 - Public forum : https://groups.google.com/forum/#!forum/lz4c
631 ****************************************************************** */
632 #if defined (__cplusplus)
637 /******************************************
639 ******************************************/
640 /* FSE buffer bounds */
641 #define FSE_NCOUNTBOUND 512
642 #define FSE_BLOCKBOUND(size) (size + (size>>7))
643 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
645 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
646 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
647 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
650 /******************************************
652 ******************************************/
653 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
654 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
656 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
657 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
660 /******************************************
661 * FSE symbol decompression API
662 ******************************************/
666 const void* table; /* precise table may vary, depending on U16 */
670 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
672 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
674 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
677 /******************************************
679 ******************************************/
680 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
681 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
684 /******************************************
685 * Implementation of inline functions
686 ******************************************/
693 } FSE_DTableHeader; /* sizeof U32 */
697 unsigned short newState;
698 unsigned char symbol;
699 unsigned char nbBits;
700 } FSE_decode_t; /* size == U32 */
702 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
704 FSE_DTableHeader DTableH;
705 memcpy(&DTableH, dt, sizeof(DTableH));
706 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
707 BIT_reloadDStream(bitD);
708 DStatePtr->table = dt + 1;
711 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
713 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
714 const U32 nbBits = DInfo.nbBits;
715 BYTE symbol = DInfo.symbol;
716 size_t lowBits = BIT_readBits(bitD, nbBits);
718 DStatePtr->state = DInfo.newState + lowBits;
722 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
724 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
725 const U32 nbBits = DInfo.nbBits;
726 BYTE symbol = DInfo.symbol;
727 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
729 DStatePtr->state = DInfo.newState + lowBits;
733 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
735 return DStatePtr->state == 0;
739 #if defined (__cplusplus)
742 /* ******************************************************************
743 Huff0 : Huffman coder, part of New Generation Entropy library
744 header file for static linking (only)
745 Copyright (C) 2013-2015, Yann Collet
747 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
749 Redistribution and use in source and binary forms, with or without
750 modification, are permitted provided that the following conditions are
753 * Redistributions of source code must retain the above copyright
754 notice, this list of conditions and the following disclaimer.
755 * Redistributions in binary form must reproduce the above
756 copyright notice, this list of conditions and the following disclaimer
757 in the documentation and/or other materials provided with the
760 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
761 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
762 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
763 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
764 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
765 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
766 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
767 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
768 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
769 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
770 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
772 You can contact the author at :
773 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
774 - Public forum : https://groups.google.com/forum/#!forum/lz4c
775 ****************************************************************** */
777 #if defined (__cplusplus)
781 /******************************************
782 * Static allocation macros
783 ******************************************/
784 /* Huff0 buffer bounds */
785 #define HUF_CTABLEBOUND 129
786 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
787 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
789 /* static allocation of Huff0's DTable */
790 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
791 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
792 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
793 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
794 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
795 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
796 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
799 /******************************************
801 ******************************************/
802 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
803 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
806 #if defined (__cplusplus)
811 zstd - standard compression library
813 Copyright (C) 2014-2015, Yann Collet.
815 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
817 Redistribution and use in source and binary forms, with or without
818 modification, are permitted provided that the following conditions are
820 * Redistributions of source code must retain the above copyright
821 notice, this list of conditions and the following disclaimer.
822 * Redistributions in binary form must reproduce the above
823 copyright notice, this list of conditions and the following disclaimer
824 in the documentation and/or other materials provided with the
826 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
827 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
828 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
829 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
830 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
831 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
832 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
833 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
834 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
835 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
836 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
838 You can contact the author at :
839 - zstd source repository : https://github.com/Cyan4973/zstd
840 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
843 #if defined (__cplusplus)
847 /* *************************************
849 ***************************************/
850 #include <stddef.h> /* size_t */
853 /* *************************************
855 ***************************************/
856 #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
857 #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
858 #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
859 #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
862 /* *************************************
864 ***************************************/
865 typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */
867 #if defined (__cplusplus)
871 zstd - standard compression library
872 Header File for static linking only
873 Copyright (C) 2014-2015, Yann Collet.
875 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
877 Redistribution and use in source and binary forms, with or without
878 modification, are permitted provided that the following conditions are
880 * Redistributions of source code must retain the above copyright
881 notice, this list of conditions and the following disclaimer.
882 * Redistributions in binary form must reproduce the above
883 copyright notice, this list of conditions and the following disclaimer
884 in the documentation and/or other materials provided with the
886 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
887 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
888 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
889 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
890 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
891 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
892 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
893 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
894 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
895 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
896 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
898 You can contact the author at :
899 - zstd source repository : https://github.com/Cyan4973/zstd
900 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
903 /* The objects defined into this file should be considered experimental.
904 * They are not labelled stable, as their prototype may change in the future.
905 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
908 #if defined (__cplusplus)
912 /* *************************************
913 * Streaming functions
914 ***************************************/
916 typedef struct ZSTD_DCtx_s ZSTD_DCtx;
919 Use above functions alternatively.
920 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
921 ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
922 Result is the number of bytes regenerated within 'dst'.
923 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
926 /* *************************************
927 * Prefix - version detection
928 ***************************************/
929 #define ZSTD_magicNumber 0xFD2FB523 /* v0.3 */
932 #if defined (__cplusplus)
935 /* ******************************************************************
936 FSE : Finite State Entropy coder
937 Copyright (C) 2013-2015, Yann Collet.
939 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
941 Redistribution and use in source and binary forms, with or without
942 modification, are permitted provided that the following conditions are
945 * Redistributions of source code must retain the above copyright
946 notice, this list of conditions and the following disclaimer.
947 * Redistributions in binary form must reproduce the above
948 copyright notice, this list of conditions and the following disclaimer
949 in the documentation and/or other materials provided with the
952 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
953 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
954 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
955 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
956 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
957 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
958 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
959 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
960 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
961 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
962 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
964 You can contact the author at :
965 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
966 - Public forum : https://groups.google.com/forum/#!forum/lz4c
967 ****************************************************************** */
969 #ifndef FSE_COMMONDEFS_ONLY
971 /****************************************************************
973 ****************************************************************/
975 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
976 * Increasing memory usage improves compression ratio
977 * Reduced memory usage can improve speed, due to cache effect
978 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
979 #define FSE_MAX_MEMORY_USAGE 14
980 #define FSE_DEFAULT_MEMORY_USAGE 13
982 /* FSE_MAX_SYMBOL_VALUE :
983 * Maximum symbol value authorized.
984 * Required for proper stack allocation */
985 #define FSE_MAX_SYMBOL_VALUE 255
988 /****************************************************************
989 * template functions type & suffix
990 ****************************************************************/
991 #define FSE_FUNCTION_TYPE BYTE
992 #define FSE_FUNCTION_EXTENSION
995 /****************************************************************
997 ****************************************************************/
998 #endif /* !FSE_COMMONDEFS_ONLY */
1001 /****************************************************************
1002 * Compiler specifics
1003 ****************************************************************/
1004 #ifdef _MSC_VER /* Visual Studio */
1005 # define FORCE_INLINE static __forceinline
1006 # include <intrin.h> /* For Visual 2005 */
1007 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1008 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1010 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1012 # define FORCE_INLINE static inline __attribute__((always_inline))
1014 # define FORCE_INLINE static inline
1017 # define FORCE_INLINE static
1018 # endif /* __STDC_VERSION__ */
1022 /****************************************************************
1024 ****************************************************************/
1025 #include <stdlib.h> /* malloc, free, qsort */
1026 #include <string.h> /* memcpy, memset */
1027 #include <stdio.h> /* printf (debug) */
1029 /****************************************************************
1031 *****************************************************************/
1032 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
1033 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
1034 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
1035 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
1036 #define FSE_MIN_TABLELOG 5
1038 #define FSE_TABLELOG_ABSOLUTE_MAX 15
1039 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1040 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1044 /****************************************************************
1046 ****************************************************************/
1047 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1050 /****************************************************************
1052 ****************************************************************/
1053 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1056 /****************************************************************
1058 ****************************************************************/
1060 designed to be included
1061 for type-specific functions (template emulation in C)
1062 Objective is to write these functions only once, for improved maintenance
1066 #ifndef FSE_FUNCTION_EXTENSION
1067 # error "FSE_FUNCTION_EXTENSION must be defined"
1069 #ifndef FSE_FUNCTION_TYPE
1070 # error "FSE_FUNCTION_TYPE must be defined"
1073 /* Function names */
1074 #define FSE_CAT(X,Y) X##Y
1075 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1076 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1079 /* Function templates */
1081 #define FSE_DECODE_TYPE FSE_decode_t
1083 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1085 static size_t FSE_buildDTable
1086 (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1089 FSE_DTableHeader DTableH;
1090 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1091 const U32 tableSize = 1 << tableLog;
1092 const U32 tableMask = tableSize-1;
1093 const U32 step = FSE_tableStep(tableSize);
1094 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1096 U32 highThreshold = tableSize-1;
1097 const S16 largeLimit= (S16)(1 << (tableLog-1));
1102 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1103 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1105 /* Init, lay down lowprob symbols */
1106 DTableH.tableLog = (U16)tableLog;
1107 for (s=0; s<=maxSymbolValue; s++)
1109 if (normalizedCounter[s]==-1)
1111 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1116 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1117 symbolNext[s] = normalizedCounter[s];
1121 /* Spread symbols */
1122 for (s=0; s<=maxSymbolValue; s++)
1125 for (i=0; i<normalizedCounter[s]; i++)
1127 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1128 position = (position + step) & tableMask;
1129 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1133 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1135 /* Build Decoding table */
1138 for (i=0; i<tableSize; i++)
1140 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1141 U16 nextState = symbolNext[symbol]++;
1142 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1143 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1147 DTableH.fastMode = (U16)noLarge;
1148 memcpy(dt, &DTableH, sizeof(DTableH));
1153 #ifndef FSE_COMMONDEFS_ONLY
1154 /******************************************
1155 * FSE helper functions
1156 ******************************************/
1157 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1160 /****************************************************************
1161 * FSE NCount encoding-decoding
1162 ****************************************************************/
1163 static short FSE_abs(short a)
1165 return a<0 ? -a : a;
1168 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1169 const void* headerBuffer, size_t hbSize)
1171 const BYTE* const istart = (const BYTE*) headerBuffer;
1172 const BYTE* const iend = istart + hbSize;
1173 const BYTE* ip = istart;
1179 unsigned charnum = 0;
1182 if (hbSize < 4) return ERROR(srcSize_wrong);
1183 bitStream = MEM_readLE32(ip);
1184 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1185 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1188 *tableLogPtr = nbBits;
1189 remaining = (1<<nbBits)+1;
1190 threshold = 1<<nbBits;
1193 while ((remaining>1) && (charnum<=*maxSVPtr))
1197 unsigned n0 = charnum;
1198 while ((bitStream & 0xFFFF) == 0xFFFF)
1204 bitStream = MEM_readLE32(ip) >> bitCount;
1212 while ((bitStream & 3) == 3)
1218 n0 += bitStream & 3;
1220 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1221 while (charnum < n0) normalizedCounter[charnum++] = 0;
1222 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1226 bitStream = MEM_readLE32(ip) >> bitCount;
1232 const short max = (short)((2*threshold-1)-remaining);
1235 if ((bitStream & (threshold-1)) < (U32)max)
1237 count = (short)(bitStream & (threshold-1));
1238 bitCount += nbBits-1;
1242 count = (short)(bitStream & (2*threshold-1));
1243 if (count >= threshold) count -= max;
1247 count--; /* extra accuracy */
1248 remaining -= FSE_abs(count);
1249 normalizedCounter[charnum++] = count;
1251 while (remaining < threshold)
1258 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1265 bitCount -= (int)(8 * (iend - 4 - ip));
1268 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1272 if (remaining != 1) return ERROR(GENERIC);
1273 *maxSVPtr = charnum-1;
1275 ip += (bitCount+7)>>3;
1276 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1281 /*********************************************************
1282 * Decompression (Byte symbols)
1283 *********************************************************/
1284 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1287 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1288 FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1;
1290 DTableH->tableLog = 0;
1291 DTableH->fastMode = 0;
1294 cell->symbol = symbolValue;
1301 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1304 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1305 FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1;
1306 const unsigned tableSize = 1 << nbBits;
1307 const unsigned tableMask = tableSize - 1;
1308 const unsigned maxSymbolValue = tableMask;
1312 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1314 /* Build Decoding Table */
1315 DTableH->tableLog = (U16)nbBits;
1316 DTableH->fastMode = 1;
1317 for (s=0; s<=maxSymbolValue; s++)
1319 dinfo[s].newState = 0;
1320 dinfo[s].symbol = (BYTE)s;
1321 dinfo[s].nbBits = (BYTE)nbBits;
1327 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1328 void* dst, size_t maxDstSize,
1329 const void* cSrc, size_t cSrcSize,
1330 const FSE_DTable* dt, const unsigned fast)
1332 BYTE* const ostart = (BYTE*) dst;
1334 BYTE* const omax = op + maxDstSize;
1335 BYTE* const olimit = omax-3;
1338 FSE_DState_t state1;
1339 FSE_DState_t state2;
1343 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1344 if (FSE_isError(errorCode)) return errorCode;
1346 FSE_initDState(&state1, &bitD, dt);
1347 FSE_initDState(&state2, &bitD, dt);
1349 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1351 /* 4 symbols per loop */
1352 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1354 op[0] = FSE_GETSYMBOL(&state1);
1356 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1357 BIT_reloadDStream(&bitD);
1359 op[1] = FSE_GETSYMBOL(&state2);
1361 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1362 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1364 op[2] = FSE_GETSYMBOL(&state1);
1366 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1367 BIT_reloadDStream(&bitD);
1369 op[3] = FSE_GETSYMBOL(&state2);
1373 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1376 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1379 *op++ = FSE_GETSYMBOL(&state1);
1381 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1384 *op++ = FSE_GETSYMBOL(&state2);
1388 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1391 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1393 return ERROR(corruption_detected);
1397 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1398 const void* cSrc, size_t cSrcSize,
1399 const FSE_DTable* dt)
1401 FSE_DTableHeader DTableH;
1402 memcpy(&DTableH, dt, sizeof(DTableH));
1404 /* select fast mode (static) */
1405 if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1406 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1410 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1412 const BYTE* const istart = (const BYTE*)cSrc;
1413 const BYTE* ip = istart;
1414 short counting[FSE_MAX_SYMBOL_VALUE+1];
1415 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1417 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1420 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1422 /* normal FSE decoding mode */
1423 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1424 if (FSE_isError(errorCode)) return errorCode;
1425 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1427 cSrcSize -= errorCode;
1429 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1430 if (FSE_isError(errorCode)) return errorCode;
1432 /* always return, even if it is an error code */
1433 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1438 #endif /* FSE_COMMONDEFS_ONLY */
1439 /* ******************************************************************
1440 Huff0 : Huffman coder, part of New Generation Entropy library
1441 Copyright (C) 2013-2015, Yann Collet.
1443 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1445 Redistribution and use in source and binary forms, with or without
1446 modification, are permitted provided that the following conditions are
1449 * Redistributions of source code must retain the above copyright
1450 notice, this list of conditions and the following disclaimer.
1451 * Redistributions in binary form must reproduce the above
1452 copyright notice, this list of conditions and the following disclaimer
1453 in the documentation and/or other materials provided with the
1456 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1457 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1458 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1459 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1460 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1461 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1462 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1463 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1464 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1465 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1466 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1468 You can contact the author at :
1469 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1470 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1471 ****************************************************************** */
1473 /****************************************************************
1474 * Compiler specifics
1475 ****************************************************************/
1476 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1477 /* inline is defined */
1478 #elif defined(_MSC_VER)
1479 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1480 # define inline __inline
1482 # define inline /* disable inline */
1486 /****************************************************************
1488 ****************************************************************/
1489 #include <stdlib.h> /* malloc, free, qsort */
1490 #include <string.h> /* memcpy, memset */
1491 #include <stdio.h> /* printf (debug) */
1493 /****************************************************************
1495 ****************************************************************/
1496 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1499 /******************************************
1501 ******************************************/
1502 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1504 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1505 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1506 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1507 #define HUF_MAX_SYMBOL_VALUE 255
1508 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1509 # error "HUF_MAX_TABLELOG is too large !"
1514 /*********************************************************
1515 * Huff0 : Huffman block decompression
1516 *********************************************************/
1517 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1519 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1521 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1524 Read compact Huffman tree, saved by HUF_writeCTable
1525 @huffWeight : destination buffer
1526 @return : size read from `src`
1528 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1529 U32* nbSymbolsPtr, U32* tableLogPtr,
1530 const void* src, size_t srcSize)
1534 const BYTE* ip = (const BYTE*) src;
1539 if (!srcSize) return ERROR(srcSize_wrong);
1541 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1543 if (iSize >= 128) /* special header */
1545 if (iSize >= (242)) /* RLE */
1547 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1548 oSize = l[iSize-242];
1549 memset(huffWeight, 1, hwSize);
1552 else /* Incompressible */
1554 oSize = iSize - 127;
1555 iSize = ((oSize+1)/2);
1556 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1557 if (oSize >= hwSize) return ERROR(corruption_detected);
1559 for (n=0; n<oSize; n+=2)
1561 huffWeight[n] = ip[n/2] >> 4;
1562 huffWeight[n+1] = ip[n/2] & 15;
1566 else /* header compressed with FSE (normal case) */
1568 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1569 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1570 if (FSE_isError(oSize)) return oSize;
1573 /* collect weight stats */
1574 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1576 for (n=0; n<oSize; n++)
1578 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1579 rankStats[huffWeight[n]]++;
1580 weightTotal += (1 << huffWeight[n]) >> 1;
1582 if (weightTotal == 0) return ERROR(corruption_detected);
1584 /* get last non-null symbol weight (implied, total must be 2^n) */
1585 tableLog = BIT_highbit32(weightTotal) + 1;
1586 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1588 U32 total = 1 << tableLog;
1589 U32 rest = total - weightTotal;
1590 U32 verif = 1 << BIT_highbit32(rest);
1591 U32 lastWeight = BIT_highbit32(rest) + 1;
1592 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1593 huffWeight[oSize] = (BYTE)lastWeight;
1594 rankStats[lastWeight]++;
1597 /* check tree construction validity */
1598 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1601 *nbSymbolsPtr = (U32)(oSize+1);
1602 *tableLogPtr = tableLog;
1607 /**************************/
1608 /* single-symbol decoding */
1609 /**************************/
1611 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1613 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1614 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1616 const BYTE* ip = (const BYTE*) src;
1617 size_t iSize = ip[0];
1621 void* ptr = DTable+1;
1622 HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr);
1624 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1625 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1627 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1628 if (HUF_isError(iSize)) return iSize;
1631 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1632 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1636 for (n=1; n<=tableLog; n++)
1638 U32 current = nextRankStart;
1639 nextRankStart += (rankVal[n] << (n-1));
1640 rankVal[n] = current;
1644 for (n=0; n<nbSymbols; n++)
1646 const U32 w = huffWeight[n];
1647 const U32 length = (1 << w) >> 1;
1650 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1651 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1653 rankVal[w] += length;
1659 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1661 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1662 const BYTE c = dt[val].byte;
1663 BIT_skipBits(Dstream, dt[val].nbBits);
1667 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1668 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1670 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1671 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1672 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1674 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1676 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1678 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1680 BYTE* const pStart = p;
1682 /* up to 4 symbols at a time */
1683 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1685 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1686 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1687 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1688 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1691 /* closer to the end */
1692 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1693 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1695 /* no more data to retrieve from bitstream, hence no need to reload */
1697 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1703 static size_t HUF_decompress4X2_usingDTable(
1704 void* dst, size_t dstSize,
1705 const void* cSrc, size_t cSrcSize,
1708 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1711 const BYTE* const istart = (const BYTE*) cSrc;
1712 BYTE* const ostart = (BYTE*) dst;
1713 BYTE* const oend = ostart + dstSize;
1715 const void* ptr = DTable;
1716 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1717 const U32 dtLog = DTable[0];
1721 BIT_DStream_t bitD1;
1722 BIT_DStream_t bitD2;
1723 BIT_DStream_t bitD3;
1724 BIT_DStream_t bitD4;
1725 const size_t length1 = MEM_readLE16(istart);
1726 const size_t length2 = MEM_readLE16(istart+2);
1727 const size_t length3 = MEM_readLE16(istart+4);
1729 const BYTE* const istart1 = istart + 6; /* jumpTable */
1730 const BYTE* const istart2 = istart1 + length1;
1731 const BYTE* const istart3 = istart2 + length2;
1732 const BYTE* const istart4 = istart3 + length3;
1733 const size_t segmentSize = (dstSize+3) / 4;
1734 BYTE* const opStart2 = ostart + segmentSize;
1735 BYTE* const opStart3 = opStart2 + segmentSize;
1736 BYTE* const opStart4 = opStart3 + segmentSize;
1738 BYTE* op2 = opStart2;
1739 BYTE* op3 = opStart3;
1740 BYTE* op4 = opStart4;
1743 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1744 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1745 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1746 if (HUF_isError(errorCode)) return errorCode;
1747 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1748 if (HUF_isError(errorCode)) return errorCode;
1749 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1750 if (HUF_isError(errorCode)) return errorCode;
1751 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1752 if (HUF_isError(errorCode)) return errorCode;
1754 /* 16-32 symbols per loop (4-8 symbols per stream) */
1755 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1756 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1758 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1759 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1760 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1761 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1762 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1763 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1764 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1765 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1766 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1767 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1768 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1769 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1770 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1771 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1772 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1773 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1775 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1778 /* check corruption */
1779 if (op1 > opStart2) return ERROR(corruption_detected);
1780 if (op2 > opStart3) return ERROR(corruption_detected);
1781 if (op3 > opStart4) return ERROR(corruption_detected);
1782 /* note : op4 supposed already verified within main loop */
1784 /* finish bitStreams one by one */
1785 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1786 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1787 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1788 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1791 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1792 if (!endSignal) return ERROR(corruption_detected);
1800 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1802 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1803 const BYTE* ip = (const BYTE*) cSrc;
1806 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1807 if (HUF_isError(errorCode)) return errorCode;
1808 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1810 cSrcSize -= errorCode;
1812 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1816 /***************************/
1817 /* double-symbols decoding */
1818 /***************************/
1820 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1821 const U32* rankValOrigin, const int minWeight,
1822 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1823 U32 nbBitsBaseline, U16 baseSeq)
1826 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1829 /* get pre-calculated rankVal */
1830 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1832 /* fill skipped values */
1835 U32 i, skipSize = rankVal[minWeight];
1836 MEM_writeLE16(&(DElt.sequence), baseSeq);
1837 DElt.nbBits = (BYTE)(consumed);
1839 for (i = 0; i < skipSize; i++)
1844 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1846 const U32 symbol = sortedSymbols[s].symbol;
1847 const U32 weight = sortedSymbols[s].weight;
1848 const U32 nbBits = nbBitsBaseline - weight;
1849 const U32 length = 1 << (sizeLog-nbBits);
1850 const U32 start = rankVal[weight];
1852 const U32 end = start + length;
1854 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1855 DElt.nbBits = (BYTE)(nbBits + consumed);
1857 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1859 rankVal[weight] += length;
1863 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1865 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1866 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1867 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1868 const U32 nbBitsBaseline)
1870 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1871 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1872 const U32 minBits = nbBitsBaseline - maxWeight;
1875 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1878 for (s=0; s<sortedListSize; s++)
1880 const U16 symbol = sortedList[s].symbol;
1881 const U32 weight = sortedList[s].weight;
1882 const U32 nbBits = nbBitsBaseline - weight;
1883 const U32 start = rankVal[weight];
1884 const U32 length = 1 << (targetLog-nbBits);
1886 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1889 int minWeight = nbBits + scaleLog;
1890 if (minWeight < 1) minWeight = 1;
1891 sortedRank = rankStart[minWeight];
1892 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1893 rankValOrigin[nbBits], minWeight,
1894 sortedList+sortedRank, sortedListSize-sortedRank,
1895 nbBitsBaseline, symbol);
1900 const U32 end = start + length;
1903 MEM_writeLE16(&(DElt.sequence), symbol);
1904 DElt.nbBits = (BYTE)(nbBits);
1906 for (i = start; i < end; i++)
1909 rankVal[weight] += length;
1913 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1915 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1916 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1917 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1918 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1919 U32* const rankStart = rankStart0+1;
1921 U32 tableLog, maxW, sizeOfSort, nbSymbols;
1922 const U32 memLog = DTable[0];
1923 const BYTE* ip = (const BYTE*) src;
1924 size_t iSize = ip[0];
1926 HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1928 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
1929 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1930 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1932 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1933 if (HUF_isError(iSize)) return iSize;
1936 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
1938 /* find maxWeight */
1939 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1940 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
1942 /* Get start index of each weight */
1944 U32 w, nextRankStart = 0;
1945 for (w=1; w<=maxW; w++)
1947 U32 current = nextRankStart;
1948 nextRankStart += rankStats[w];
1949 rankStart[w] = current;
1951 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
1952 sizeOfSort = nextRankStart;
1955 /* sort symbols by weight */
1958 for (s=0; s<nbSymbols; s++)
1960 U32 w = weightList[s];
1961 U32 r = rankStart[w]++;
1962 sortedSymbol[r].symbol = (BYTE)s;
1963 sortedSymbol[r].weight = (BYTE)w;
1965 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1970 const U32 minBits = tableLog+1 - maxW;
1971 U32 nextRankVal = 0;
1973 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
1974 U32* rankVal0 = rankVal[0];
1975 for (w=1; w<=maxW; w++)
1977 U32 current = nextRankVal;
1978 nextRankVal += rankStats[w] << (w+rescale);
1979 rankVal0[w] = current;
1981 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1983 U32* rankValPtr = rankVal[consumed];
1984 for (w = 1; w <= maxW; w++)
1986 rankValPtr[w] = rankVal0[w] >> consumed;
1991 HUF_fillDTableX4(dt, memLog,
1992 sortedSymbol, sizeOfSort,
1993 rankStart0, rankVal, maxW,
2000 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2002 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2003 memcpy(op, dt+val, 2);
2004 BIT_skipBits(DStream, dt[val].nbBits);
2005 return dt[val].length;
2008 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2010 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2011 memcpy(op, dt+val, 1);
2012 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2015 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2017 BIT_skipBits(DStream, dt[val].nbBits);
2018 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2019 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 */
2026 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2027 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2029 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2030 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2031 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2033 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2035 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2037 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2039 BYTE* const pStart = p;
2041 /* up to 8 symbols at a time */
2042 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2044 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2045 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2046 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2047 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2050 /* closer to the end */
2051 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2052 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2055 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2058 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2065 static size_t HUF_decompress4X4_usingDTable(
2066 void* dst, size_t dstSize,
2067 const void* cSrc, size_t cSrcSize,
2070 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2073 const BYTE* const istart = (const BYTE*) cSrc;
2074 BYTE* const ostart = (BYTE*) dst;
2075 BYTE* const oend = ostart + dstSize;
2077 const void* ptr = DTable;
2078 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2079 const U32 dtLog = DTable[0];
2083 BIT_DStream_t bitD1;
2084 BIT_DStream_t bitD2;
2085 BIT_DStream_t bitD3;
2086 BIT_DStream_t bitD4;
2087 const size_t length1 = MEM_readLE16(istart);
2088 const size_t length2 = MEM_readLE16(istart+2);
2089 const size_t length3 = MEM_readLE16(istart+4);
2091 const BYTE* const istart1 = istart + 6; /* jumpTable */
2092 const BYTE* const istart2 = istart1 + length1;
2093 const BYTE* const istart3 = istart2 + length2;
2094 const BYTE* const istart4 = istart3 + length3;
2095 const size_t segmentSize = (dstSize+3) / 4;
2096 BYTE* const opStart2 = ostart + segmentSize;
2097 BYTE* const opStart3 = opStart2 + segmentSize;
2098 BYTE* const opStart4 = opStart3 + segmentSize;
2100 BYTE* op2 = opStart2;
2101 BYTE* op3 = opStart3;
2102 BYTE* op4 = opStart4;
2105 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2106 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2107 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2108 if (HUF_isError(errorCode)) return errorCode;
2109 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2110 if (HUF_isError(errorCode)) return errorCode;
2111 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2112 if (HUF_isError(errorCode)) return errorCode;
2113 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2114 if (HUF_isError(errorCode)) return errorCode;
2116 /* 16-32 symbols per loop (4-8 symbols per stream) */
2117 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2118 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2120 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2121 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2122 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2123 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2124 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2125 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2126 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2127 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2128 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2129 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2130 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2131 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2132 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2133 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2134 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2135 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2137 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2140 /* check corruption */
2141 if (op1 > opStart2) return ERROR(corruption_detected);
2142 if (op2 > opStart3) return ERROR(corruption_detected);
2143 if (op3 > opStart4) return ERROR(corruption_detected);
2144 /* note : op4 supposed already verified within main loop */
2146 /* finish bitStreams one by one */
2147 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2148 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2149 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2150 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2153 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2154 if (!endSignal) return ERROR(corruption_detected);
2162 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2164 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2165 const BYTE* ip = (const BYTE*) cSrc;
2167 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2168 if (HUF_isError(hSize)) return hSize;
2169 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2173 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2177 /**********************************/
2178 /* Generic decompression selector */
2179 /**********************************/
2181 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2182 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2184 /* single, double, quad */
2185 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2186 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2187 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2188 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2189 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2190 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2191 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2192 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2193 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2194 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2195 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2196 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2197 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2198 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2199 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2200 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2203 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2205 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2207 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2208 /* estimate decompression time */
2210 const U32 D256 = (U32)(dstSize >> 8);
2215 /* validation checks */
2216 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2217 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2218 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2219 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2221 /* decoder timing evaluation */
2222 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2224 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2226 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2228 if (Dtime[1] < Dtime[0]) algoNb = 1;
2230 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2232 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2233 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2234 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2237 zstd - standard compression library
2238 Copyright (C) 2014-2015, Yann Collet.
2240 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2242 Redistribution and use in source and binary forms, with or without
2243 modification, are permitted provided that the following conditions are
2245 * Redistributions of source code must retain the above copyright
2246 notice, this list of conditions and the following disclaimer.
2247 * Redistributions in binary form must reproduce the above
2248 copyright notice, this list of conditions and the following disclaimer
2249 in the documentation and/or other materials provided with the
2251 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2252 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2253 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2254 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2255 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2256 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2257 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2258 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2259 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2260 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2261 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2263 You can contact the author at :
2264 - zstd source repository : https://github.com/Cyan4973/zstd
2265 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2268 /* ***************************************************************
2270 *****************************************************************/
2273 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2274 * Increasing memory usage improves compression ratio
2275 * Reduced memory usage can improve speed, due to cache effect
2277 #define ZSTD_MEMORY_USAGE 17
2281 * Select how default compression functions will allocate memory for their hash table,
2282 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2283 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2285 #ifndef ZSTD_HEAPMODE
2286 # define ZSTD_HEAPMODE 1
2287 #endif /* ZSTD_HEAPMODE */
2291 * decompressor can decode older formats (starting from Zstd 0.1+)
2293 #ifndef ZSTD_LEGACY_SUPPORT
2294 # define ZSTD_LEGACY_SUPPORT 1
2298 /* *******************************************************
2300 *********************************************************/
2301 #include <stdlib.h> /* calloc */
2302 #include <string.h> /* memcpy, memmove */
2303 #include <stdio.h> /* debug : printf */
2306 /* *******************************************************
2307 * Compiler specifics
2308 *********************************************************/
2310 # include <immintrin.h> /* AVX2 intrinsics */
2313 #ifdef _MSC_VER /* Visual Studio */
2314 # include <intrin.h> /* For Visual 2005 */
2315 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2316 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2318 # define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
2322 /* *******************************************************
2324 *********************************************************/
2325 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2326 #define HASH_TABLESIZE (1 << HASH_LOG)
2327 #define HASH_MASK (HASH_TABLESIZE - 1)
2329 #define KNUTH 2654435761
2338 #define KB *(1 <<10)
2339 #define MB *(1 <<20)
2340 #define GB *(1U<<30)
2342 #define BLOCKSIZE (128 KB) /* define, for static allocation */
2343 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2344 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2348 #define WORKPLACESIZE (BLOCKSIZE*3)
2353 #define MaxML ((1<<MLbits )-1)
2354 #define MaxLL ((1<<LLbits )-1)
2356 #define LitFSELog 11
2360 #define MAX(a,b) ((a)<(b)?(b):(a))
2361 #define MaxSeq MAX(MaxLL, MaxML)
2363 #define LITERAL_NOENTROPY 63
2364 #define COMMAND_NOENTROPY 7 /* to remove */
2366 static const size_t ZSTD_blockHeaderSize = 3;
2367 static const size_t ZSTD_frameHeaderSize = 4;
2370 /* *******************************************************
2372 **********************************************************/
2373 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2375 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2377 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2379 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2380 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2382 const BYTE* ip = (const BYTE*)src;
2383 BYTE* op = (BYTE*)dst;
2384 BYTE* const oend = op + length;
2385 do COPY8(op, ip) while (op < oend);
2389 /* **************************************
2391 ****************************************/
2392 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2396 blockType_t blockType;
2398 } blockProperties_t;
2408 BYTE* litLengthStart;
2410 BYTE* matchLengthStart;
2417 /* *************************************
2419 ***************************************/
2421 * tells if a return value is an error code */
2422 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2426 /* *************************************************************
2427 * Decompression section
2428 ***************************************************************/
2431 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2432 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2433 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2434 void* previousDstEnd;
2441 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2442 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2445 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2447 const BYTE* const in = (const BYTE* const)src;
2451 if (srcSize < 3) return ERROR(srcSize_wrong);
2454 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2456 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2457 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2459 if (bpPtr->blockType == bt_end) return 0;
2460 if (bpPtr->blockType == bt_rle) return 1;
2464 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2466 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2467 memcpy(dst, src, srcSize);
2472 /** ZSTD_decompressLiterals
2473 @return : nb of bytes read from src, or an error code*/
2474 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2475 const void* src, size_t srcSize)
2477 const BYTE* ip = (const BYTE*)src;
2479 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2480 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2482 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2483 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2485 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2487 *maxDstSizePtr = litSize;
2488 return litCSize + 5;
2492 /** ZSTD_decodeLiteralsBlock
2493 @return : nb of bytes read from src (< srcSize )*/
2494 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2495 const void* src, size_t srcSize)
2497 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2498 const BYTE* const istart = (const BYTE* const)src;
2500 /* any compressed block with literals segment must be at least this size */
2501 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2508 size_t litSize = BLOCKSIZE;
2509 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2510 dctx->litPtr = dctx->litBuffer;
2511 dctx->litSize = litSize;
2512 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2513 return readSize; /* works if it's an error too */
2517 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2518 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2520 if (litSize > srcSize-3) return ERROR(corruption_detected);
2521 memcpy(dctx->litBuffer, istart, litSize);
2522 dctx->litPtr = dctx->litBuffer;
2523 dctx->litSize = litSize;
2524 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2527 /* direct reference into compressed stream */
2528 dctx->litPtr = istart+3;
2529 dctx->litSize = litSize;
2534 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2535 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2536 memset(dctx->litBuffer, istart[3], litSize + 8);
2537 dctx->litPtr = dctx->litBuffer;
2538 dctx->litSize = litSize;
2545 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2546 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2547 const void* src, size_t srcSize)
2549 const BYTE* const istart = (const BYTE* const)src;
2550 const BYTE* ip = istart;
2551 const BYTE* const iend = istart + srcSize;
2552 U32 LLtype, Offtype, MLtype;
2553 U32 LLlog, Offlog, MLlog;
2557 if (srcSize < 5) return ERROR(srcSize_wrong);
2560 *nbSeq = MEM_readLE16(ip); ip+=2;
2562 Offtype = (*ip >> 4) & 3;
2563 MLtype = (*ip >> 2) & 3;
2566 dumpsLength = ip[2];
2567 dumpsLength += ip[1] << 8;
2572 dumpsLength = ip[1];
2573 dumpsLength += (ip[0] & 1) << 8;
2578 *dumpsLengthPtr = dumpsLength;
2581 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2585 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2593 FSE_buildDTable_rle(DTableLL, *ip++); break;
2596 FSE_buildDTable_raw(DTableLL, LLbits); break;
2599 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2600 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2601 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2603 FSE_buildDTable(DTableLL, norm, max, LLlog);
2610 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2611 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2615 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2618 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2619 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2620 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2622 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2629 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2630 FSE_buildDTable_rle(DTableML, *ip++); break;
2633 FSE_buildDTable_raw(DTableML, MLbits); break;
2636 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2637 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2638 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2640 FSE_buildDTable(DTableML, norm, max, MLlog);
2654 BIT_DStream_t DStream;
2655 FSE_DState_t stateLL;
2656 FSE_DState_t stateOffb;
2657 FSE_DState_t stateML;
2660 const BYTE* dumpsEnd;
2664 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2670 const BYTE* dumps = seqState->dumps;
2671 const BYTE* const de = seqState->dumpsEnd;
2673 /* Literal length */
2674 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2675 prevOffset = litLength ? seq->offset : seqState->prevOffset;
2676 seqState->prevOffset = seq->offset;
2677 if (litLength == MaxLL)
2680 if (add < 255) litLength += add;
2683 litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
2686 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2691 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
2692 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2693 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2694 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2695 U32 offsetCode, nbBits;
2696 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
2697 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2698 nbBits = offsetCode - 1;
2699 if (offsetCode==0) nbBits = 0; /* cmove */
2700 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2701 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2702 if (offsetCode==0) offset = prevOffset; /* cmove */
2706 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2707 if (matchLength == MaxML)
2710 if (add < 255) matchLength += add;
2713 matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
2716 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2718 matchLength += MINMATCH;
2721 seq->litLength = litLength;
2722 seq->offset = offset;
2723 seq->matchLength = matchLength;
2724 seqState->dumps = dumps;
2728 static size_t ZSTD_execSequence(BYTE* op,
2730 const BYTE** litPtr, const BYTE* const litLimit,
2731 BYTE* const base, BYTE* const oend)
2733 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
2734 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* substracted */
2735 const BYTE* const ostart = op;
2736 BYTE* const oLitEnd = op + sequence.litLength;
2737 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
2738 BYTE* const oend_8 = oend-8;
2739 const BYTE* const litEnd = *litPtr + sequence.litLength;
2742 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
2743 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
2744 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
2747 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2749 *litPtr = litEnd; /* update for next sequence */
2753 const BYTE* match = op - sequence.offset;
2756 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
2757 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
2758 if (match < base) return ERROR(corruption_detected);
2760 /* close range match, overlap */
2761 if (sequence.offset < 8)
2763 const int dec64 = dec64table[sequence.offset];
2768 match += dec32table[sequence.offset];
2769 ZSTD_copy4(op+4, match);
2774 ZSTD_copy8(op, match);
2776 op += 8; match += 8;
2778 if (oMatchEnd > oend-(16-MINMATCH))
2782 ZSTD_wildcopy(op, match, oend_8 - op);
2783 match += oend_8 - op;
2786 while (op < oMatchEnd) *op++ = *match++;
2790 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
2794 return oMatchEnd - ostart;
2797 static size_t ZSTD_decompressSequences(
2799 void* dst, size_t maxDstSize,
2800 const void* seqStart, size_t seqSize)
2802 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2803 const BYTE* ip = (const BYTE*)seqStart;
2804 const BYTE* const iend = ip + seqSize;
2805 BYTE* const ostart = (BYTE* const)dst;
2807 BYTE* const oend = ostart + maxDstSize;
2808 size_t errorCode, dumpsLength;
2809 const BYTE* litPtr = dctx->litPtr;
2810 const BYTE* const litEnd = litPtr + dctx->litSize;
2813 U32* DTableLL = dctx->LLTable;
2814 U32* DTableML = dctx->MLTable;
2815 U32* DTableOffb = dctx->OffTable;
2816 BYTE* const base = (BYTE*) (dctx->base);
2818 /* Build Decoding Tables */
2819 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2820 DTableLL, DTableML, DTableOffb,
2822 if (ZSTD_isError(errorCode)) return errorCode;
2825 /* Regen sequences */
2828 seqState_t seqState;
2830 memset(&sequence, 0, sizeof(sequence));
2831 seqState.dumps = dumps;
2832 seqState.dumpsEnd = dumps + dumpsLength;
2833 seqState.prevOffset = sequence.offset = 4;
2834 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2835 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2836 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2837 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2838 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2840 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
2844 ZSTD_decodeSequence(&sequence, &seqState);
2845 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
2846 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2850 /* check if reached exact end */
2851 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
2852 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
2854 /* last literal segment */
2856 size_t lastLLSize = litEnd - litPtr;
2857 if (litPtr > litEnd) return ERROR(corruption_detected);
2858 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2859 if (op != litPtr) memmove(op, litPtr, lastLLSize);
2868 static size_t ZSTD_decompressBlock(
2870 void* dst, size_t maxDstSize,
2871 const void* src, size_t srcSize)
2873 /* blockType == blockCompressed */
2874 const BYTE* ip = (const BYTE*)src;
2876 /* Decode literals sub-block */
2877 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
2878 if (ZSTD_isError(litCSize)) return litCSize;
2880 srcSize -= litCSize;
2882 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
2886 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2888 const BYTE* ip = (const BYTE*)src;
2889 const BYTE* iend = ip + srcSize;
2890 BYTE* const ostart = (BYTE* const)dst;
2892 BYTE* const oend = ostart + maxDstSize;
2893 size_t remainingSize = srcSize;
2895 blockProperties_t blockProperties;
2898 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2899 magicNumber = MEM_readLE32(src);
2900 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2901 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2903 /* Loop on each block */
2906 size_t decodedSize=0;
2907 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
2908 if (ZSTD_isError(cBlockSize)) return cBlockSize;
2910 ip += ZSTD_blockHeaderSize;
2911 remainingSize -= ZSTD_blockHeaderSize;
2912 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2914 switch(blockProperties.blockType)
2917 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
2920 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
2923 return ERROR(GENERIC); /* not yet supported */
2927 if (remainingSize) return ERROR(srcSize_wrong);
2930 return ERROR(GENERIC); /* impossible */
2932 if (cBlockSize == 0) break; /* bt_end */
2934 if (ZSTD_isError(decodedSize)) return decodedSize;
2937 remainingSize -= cBlockSize;
2943 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2947 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
2950 static size_t ZSTD_findFrameCompressedSize(const void* src, size_t srcSize)
2952 const BYTE* ip = (const BYTE*)src;
2953 size_t remainingSize = srcSize;
2955 blockProperties_t blockProperties;
2958 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2959 magicNumber = MEM_readLE32(src);
2960 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2961 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2963 /* Loop on each block */
2966 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
2967 if (ZSTD_isError(cBlockSize)) return cBlockSize;
2969 ip += ZSTD_blockHeaderSize;
2970 remainingSize -= ZSTD_blockHeaderSize;
2971 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2973 if (cBlockSize == 0) break; /* bt_end */
2976 remainingSize -= cBlockSize;
2979 return ip - (const BYTE*)src;
2983 /*******************************
2984 * Streaming Decompression API
2985 *******************************/
2987 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2989 dctx->expected = ZSTD_frameHeaderSize;
2991 dctx->previousDstEnd = NULL;
2996 static ZSTD_DCtx* ZSTD_createDCtx(void)
2998 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2999 if (dctx==NULL) return NULL;
3000 ZSTD_resetDCtx(dctx);
3004 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3010 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3012 return dctx->expected;
3015 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3018 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3019 if (dst != ctx->previousDstEnd) /* not contiguous */
3022 /* Decompress : frame header */
3023 if (ctx->phase == 0)
3025 /* Check frame magic header */
3026 U32 magicNumber = MEM_readLE32(src);
3027 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3029 ctx->expected = ZSTD_blockHeaderSize;
3033 /* Decompress : block header */
3034 if (ctx->phase == 1)
3036 blockProperties_t bp;
3037 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3038 if (ZSTD_isError(blockSize)) return blockSize;
3039 if (bp.blockType == bt_end)
3046 ctx->expected = blockSize;
3047 ctx->bType = bp.blockType;
3054 /* Decompress : block content */
3060 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3063 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3066 return ERROR(GENERIC); /* not yet handled */
3068 case bt_end : /* should never happen (filtered at phase 1) */
3072 return ERROR(GENERIC);
3075 ctx->expected = ZSTD_blockHeaderSize;
3076 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3085 unsigned ZSTDv03_isError(size_t code)
3087 return ZSTD_isError(code);
3090 size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3091 const void* src, size_t compressedSize)
3093 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3096 size_t ZSTDv03_findFrameCompressedSize(const void* src, size_t srcSize)
3098 return ZSTD_findFrameCompressedSize(src, srcSize);
3101 ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3103 return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3106 size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3108 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3111 size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3113 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3116 size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3118 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3121 size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3123 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);