2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of this source tree. An additional grant
7 * of patent rights can be found in the PATENTS file in the same directory.
13 #include "error_private.h"
16 /* ******************************************************************
18 low-level memory access routines
19 Copyright (C) 2013-2015, Yann Collet.
21 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
23 Redistribution and use in source and binary forms, with or without
24 modification, are permitted provided that the following conditions are
27 * Redistributions of source code must retain the above copyright
28 notice, this list of conditions and the following disclaimer.
29 * Redistributions in binary form must reproduce the above
30 copyright notice, this list of conditions and the following disclaimer
31 in the documentation and/or other materials provided with the
34 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
35 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
36 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
37 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
38 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
39 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
40 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
41 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
42 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
43 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
44 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46 You can contact the author at :
47 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
48 - Public forum : https://groups.google.com/forum/#!forum/lz4c
49 ****************************************************************** */
53 #if defined (__cplusplus)
57 /******************************************
59 ******************************************/
60 #include <stddef.h> /* size_t, ptrdiff_t */
61 #include <string.h> /* memcpy */
64 /******************************************
66 ******************************************/
67 #if defined(_MSC_VER) /* Visual Studio */
68 # include <stdlib.h> /* _byteswap_ulong */
69 # include <intrin.h> /* _byteswap_* */
72 # define MEM_STATIC static __attribute__((unused))
73 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
74 # define MEM_STATIC static inline
75 #elif defined(_MSC_VER)
76 # define MEM_STATIC static __inline
78 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
82 /****************************************************************
84 *****************************************************************/
85 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
95 typedef unsigned char BYTE;
96 typedef unsigned short U16;
97 typedef signed short S16;
98 typedef unsigned int U32;
99 typedef signed int S32;
100 typedef unsigned long long U64;
101 typedef signed long long S64;
105 /****************************************************************
107 *****************************************************************/
108 /* MEM_FORCE_MEMORY_ACCESS
109 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
110 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
111 * The below switch allow to select different access method for improved performance.
112 * Method 0 (default) : use `memcpy()`. Safe and portable.
113 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
114 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
115 * Method 2 : direct access. This method is portable but violate C standard.
116 * It can generate buggy code on targets generating assembly depending on alignment.
117 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
118 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
119 * Prefer these methods in priority order (0 > 1 > 2)
121 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
122 # 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__) )
123 # define MEM_FORCE_MEMORY_ACCESS 2
124 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
125 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
126 # define MEM_FORCE_MEMORY_ACCESS 1
130 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
131 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
133 MEM_STATIC unsigned MEM_isLittleEndian(void)
135 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
139 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
141 /* violates C standard on structure alignment.
142 Only use if no other choice to achieve best performance on target platform */
143 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
144 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
145 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
147 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
149 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
151 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
152 /* currently only defined for gcc and icc */
153 typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;
155 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
156 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
157 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
159 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
163 /* default method, safe and standard.
164 can sometimes prove slower */
166 MEM_STATIC U16 MEM_read16(const void* memPtr)
168 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
171 MEM_STATIC U32 MEM_read32(const void* memPtr)
173 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
176 MEM_STATIC U64 MEM_read64(const void* memPtr)
178 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
181 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
183 memcpy(memPtr, &value, sizeof(value));
186 #endif // MEM_FORCE_MEMORY_ACCESS
189 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
191 if (MEM_isLittleEndian())
192 return MEM_read16(memPtr);
195 const BYTE* p = (const BYTE*)memPtr;
196 return (U16)(p[0] + (p[1]<<8));
200 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
202 if (MEM_isLittleEndian())
204 MEM_write16(memPtr, val);
208 BYTE* p = (BYTE*)memPtr;
210 p[1] = (BYTE)(val>>8);
214 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
216 if (MEM_isLittleEndian())
217 return MEM_read32(memPtr);
220 const BYTE* p = (const BYTE*)memPtr;
221 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
226 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
228 if (MEM_isLittleEndian())
229 return MEM_read64(memPtr);
232 const BYTE* p = (const BYTE*)memPtr;
233 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
234 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
239 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
242 return (size_t)MEM_readLE32(memPtr);
244 return (size_t)MEM_readLE64(memPtr);
248 #if defined (__cplusplus)
252 #endif /* MEM_H_MODULE */
255 zstd - standard compression library
256 Header File for static linking only
257 Copyright (C) 2014-2015, Yann Collet.
259 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
261 Redistribution and use in source and binary forms, with or without
262 modification, are permitted provided that the following conditions are
264 * Redistributions of source code must retain the above copyright
265 notice, this list of conditions and the following disclaimer.
266 * Redistributions in binary form must reproduce the above
267 copyright notice, this list of conditions and the following disclaimer
268 in the documentation and/or other materials provided with the
270 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
271 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
272 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
273 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
274 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
275 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
276 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
277 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
278 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
279 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
280 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
282 You can contact the author at :
283 - zstd source repository : https://github.com/Cyan4973/zstd
284 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
286 #ifndef ZSTD_STATIC_H
287 #define ZSTD_STATIC_H
289 /* The objects defined into this file shall be considered experimental.
290 * They are not considered stable, as their prototype may change in the future.
291 * You can use them for tests, provide feedback, or if you can endure risks of future changes.
294 #if defined (__cplusplus)
298 /* *************************************
300 ***************************************/
301 #define ZSTD_WINDOWLOG_MAX 26
302 #define ZSTD_WINDOWLOG_MIN 18
303 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 11
304 #define ZSTD_CONTENTLOG_MAX (ZSTD_WINDOWLOG_MAX+1)
305 #define ZSTD_CONTENTLOG_MIN 4
306 #define ZSTD_HASHLOG_MAX 28
307 #define ZSTD_HASHLOG_MIN 4
308 #define ZSTD_SEARCHLOG_MAX (ZSTD_CONTENTLOG_MAX-1)
309 #define ZSTD_SEARCHLOG_MIN 1
310 #define ZSTD_SEARCHLENGTH_MAX 7
311 #define ZSTD_SEARCHLENGTH_MIN 4
313 /** from faster to stronger */
314 typedef enum { ZSTD_fast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2 } ZSTD_strategy;
318 U64 srcSize; /* optional : tells how much bytes are present in the frame. Use 0 if not known. */
319 U32 windowLog; /* largest match distance : larger == more compression, more memory needed during decompression */
320 U32 contentLog; /* full search segment : larger == more compression, slower, more memory (useless for fast) */
321 U32 hashLog; /* dispatch table : larger == more memory, faster */
322 U32 searchLog; /* nb of searches : larger == more compression, slower */
323 U32 searchLength; /* size of matches : larger == faster decompression, sometimes less compression */
324 ZSTD_strategy strategy;
327 typedef ZSTDv04_Dctx ZSTD_DCtx;
329 /* *************************************
331 ***************************************/
332 /** ZSTD_decompress_usingDict
333 * Same as ZSTD_decompressDCtx, using a Dictionary content as prefix
334 * Note : dict can be NULL, in which case, it's equivalent to ZSTD_decompressDCtx() */
335 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
336 void* dst, size_t maxDstSize,
337 const void* src, size_t srcSize,
338 const void* dict,size_t dictSize);
341 /* **************************************
342 * Streaming functions (direct mode)
343 ****************************************/
344 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx);
345 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize);
346 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* src, size_t srcSize);
348 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx);
349 static size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize);
352 Streaming decompression, bufferless mode
354 A ZSTD_DCtx object is required to track streaming operations.
355 Use ZSTD_createDCtx() / ZSTD_freeDCtx() to manage it.
356 A ZSTD_DCtx object can be re-used multiple times. Use ZSTD_resetDCtx() to return to fresh status.
358 First operation is to retrieve frame parameters, using ZSTD_getFrameParams().
359 This function doesn't consume its input. It needs enough input data to properly decode the frame header.
360 Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.
361 Result : 0 when successful, it means the ZSTD_parameters structure has been filled.
362 >0 : means there is not enough data into src. Provides the expected size to successfully decode header.
363 errorCode, which can be tested using ZSTD_isError() (For example, if it's not a ZSTD header)
365 Then, you can optionally insert a dictionary.
366 This operation must mimic the compressor behavior, otherwise decompression will fail or be corrupted.
368 Then it's possible to start decompression.
369 Use ZSTD_nextSrcSizeToDecompress() and ZSTD_decompressContinue() alternatively.
370 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
371 ZSTD_decompressContinue() requires this exact amount of bytes, or it will fail.
372 ZSTD_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
373 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
375 @result of ZSTD_decompressContinue() is the number of bytes regenerated within 'dst'.
376 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
378 A frame is fully decoded when ZSTD_nextSrcSizeToDecompress() returns zero.
379 Context can then be reset to start a new decompression.
383 #if defined (__cplusplus)
388 #endif /* ZSTD_STATIC_H */
392 zstd_internal - common functions to include
393 Header File for include
394 Copyright (C) 2014-2015, Yann Collet.
396 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
398 Redistribution and use in source and binary forms, with or without
399 modification, are permitted provided that the following conditions are
401 * Redistributions of source code must retain the above copyright
402 notice, this list of conditions and the following disclaimer.
403 * Redistributions in binary form must reproduce the above
404 copyright notice, this list of conditions and the following disclaimer
405 in the documentation and/or other materials provided with the
407 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
408 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
409 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
410 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
411 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
412 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
413 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
414 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
415 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
416 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
417 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
419 You can contact the author at :
420 - zstd source repository : https://github.com/Cyan4973/zstd
421 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
423 #ifndef ZSTD_CCOMMON_H_MODULE
424 #define ZSTD_CCOMMON_H_MODULE
426 #if defined (__cplusplus)
430 /* *************************************
432 ***************************************/
433 #define MIN(a,b) ((a)<(b) ? (a) : (b))
434 #define MAX(a,b) ((a)>(b) ? (a) : (b))
437 /* *************************************
439 ***************************************/
440 #define ZSTD_MAGICNUMBER 0xFD2FB524 /* v0.4 */
446 #define BLOCKSIZE (128 KB) /* define, for static allocation */
448 static const size_t ZSTD_blockHeaderSize = 3;
449 static const size_t ZSTD_frameHeaderSize_min = 5;
450 #define ZSTD_frameHeaderSize_max 5 /* define, for static allocation */
463 #define REPCODE_STARTVALUE 4
468 #define MaxML ((1<<MLbits) - 1)
469 #define MaxLL ((1<<LLbits) - 1)
470 #define MaxOff ((1<<Offbits)- 1)
474 #define MaxSeq MAX(MaxLL, MaxML)
476 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
477 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
479 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
482 /* ******************************************
483 * Shared functions to include for inlining
484 ********************************************/
485 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
487 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
489 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
490 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
492 const BYTE* ip = (const BYTE*)src;
493 BYTE* op = (BYTE*)dst;
494 BYTE* const oend = op + length;
501 #if defined (__cplusplus)
506 /* ******************************************************************
507 FSE : Finite State Entropy coder
509 Copyright (C) 2013-2015, Yann Collet.
511 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
513 Redistribution and use in source and binary forms, with or without
514 modification, are permitted provided that the following conditions are
517 * Redistributions of source code must retain the above copyright
518 notice, this list of conditions and the following disclaimer.
519 * Redistributions in binary form must reproduce the above
520 copyright notice, this list of conditions and the following disclaimer
521 in the documentation and/or other materials provided with the
524 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
525 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
526 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
527 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
528 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
529 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
530 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
531 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
532 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
533 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
534 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
536 You can contact the author at :
537 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
538 - Public forum : https://groups.google.com/forum/#!forum/lz4c
539 ****************************************************************** */
543 #if defined (__cplusplus)
548 /* *****************************************
550 ******************************************/
551 #include <stddef.h> /* size_t, ptrdiff_t */
554 /* *****************************************
555 * FSE simple functions
556 ******************************************/
557 static size_t FSE_decompress(void* dst, size_t maxDstSize,
558 const void* cSrc, size_t cSrcSize);
561 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
562 into already allocated destination buffer 'dst', of size 'maxDstSize'.
563 return : size of regenerated data (<= maxDstSize)
564 or an error code, which can be tested using FSE_isError()
566 ** Important ** : FSE_decompress() doesn't decompress non-compressible nor RLE data !!!
567 Why ? : making this distinction requires a header.
568 Header management is intentionally delegated to the user layer, which can better manage special cases.
572 /* *****************************************
574 ******************************************/
575 /* Error Management */
576 static unsigned FSE_isError(size_t code); /* tells if a return value is an error code */
580 /* *****************************************
582 ******************************************/
584 FSE_compress() does the following:
585 1. count symbol occurrence from source[] into table count[]
586 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
587 3. save normalized counters to memory buffer using writeNCount()
588 4. build encoding table 'CTable' from normalized counters
589 5. encode the data stream using encoding table 'CTable'
591 FSE_decompress() does the following:
592 1. read normalized counters with readNCount()
593 2. build decoding table 'DTable' from normalized counters
594 3. decode the data stream using decoding table 'DTable'
596 The following API allows targeting specific sub-functions for advanced tasks.
597 For example, it's possible to compress several blocks using the same 'CTable',
598 or to save and provide normalized distribution using external method.
602 /* *** DECOMPRESSION *** */
606 Read compactly saved 'normalizedCounter' from 'rBuffer'.
607 return : size read from 'rBuffer'
608 or an errorCode, which can be tested using FSE_isError()
609 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
610 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
613 Constructor and Destructor of type FSE_DTable
614 Note that its size depends on 'tableLog' */
615 typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
619 Builds 'dt', which must be already allocated, using FSE_createDTable()
621 or an errorCode, which can be tested using FSE_isError() */
622 static size_t FSE_buildDTable ( FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
625 FSE_decompress_usingDTable():
626 Decompress compressed source 'cSrc' of size 'cSrcSize' using 'dt'
627 into 'dst' which must be already allocated.
628 return : size of regenerated data (necessarily <= maxDstSize)
629 or an errorCode, which can be tested using FSE_isError() */
630 static size_t FSE_decompress_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt);
635 (Note : these functions only decompress FSE-compressed blocks.
636 If block is uncompressed, use memcpy() instead
637 If block is a single repeated byte, use memset() instead )
639 The first step is to obtain the normalized frequencies of symbols.
640 This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount().
641 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
642 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
643 or size the table to handle worst case situations (typically 256).
644 FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
645 The result of FSE_readNCount() is the number of bytes read from 'rBuffer'.
646 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
647 If there is an error, the function will return an error code, which can be tested using FSE_isError().
649 The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'.
650 This is performed by the function FSE_buildDTable().
651 The space required by 'FSE_DTable' must be already allocated using FSE_createDTable().
652 If there is an error, the function will return an error code, which can be tested using FSE_isError().
654 'FSE_DTable' can then be used to decompress 'cSrc', with FSE_decompress_usingDTable().
655 'cSrcSize' must be strictly correct, otherwise decompression will fail.
656 FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=maxDstSize).
657 If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small)
661 #if defined (__cplusplus)
668 /* ******************************************************************
670 Part of NewGen Entropy library
671 header file (to include)
672 Copyright (C) 2013-2015, Yann Collet.
674 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
676 Redistribution and use in source and binary forms, with or without
677 modification, are permitted provided that the following conditions are
680 * Redistributions of source code must retain the above copyright
681 notice, this list of conditions and the following disclaimer.
682 * Redistributions in binary form must reproduce the above
683 copyright notice, this list of conditions and the following disclaimer
684 in the documentation and/or other materials provided with the
687 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
688 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
689 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
690 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
691 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
692 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
693 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
694 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
695 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
696 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
697 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
699 You can contact the author at :
700 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
701 - Public forum : https://groups.google.com/forum/#!forum/lz4c
702 ****************************************************************** */
703 #ifndef BITSTREAM_H_MODULE
704 #define BITSTREAM_H_MODULE
706 #if defined (__cplusplus)
712 * This API consists of small unitary functions, which highly benefit from being inlined.
713 * Since link-time-optimization is not available for all compilers,
714 * these functions are defined into a .h to be included.
717 /**********************************************
718 * bitStream decompression API (read backward)
719 **********************************************/
723 unsigned bitsConsumed;
728 typedef enum { BIT_DStream_unfinished = 0,
729 BIT_DStream_endOfBuffer = 1,
730 BIT_DStream_completed = 2,
731 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
732 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
734 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
735 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
736 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
737 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
741 * Start by invoking BIT_initDStream().
742 * A chunk of the bitStream is then stored into a local register.
743 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
744 * You can then retrieve bitFields stored into the local register, **in reverse order**.
745 * Local register is manually filled from memory by the BIT_reloadDStream() method.
746 * A reload guarantee a minimum of ((8*sizeof(size_t))-7) bits when its result is BIT_DStream_unfinished.
747 * Otherwise, it can be less than that, so proceed accordingly.
748 * Checking if DStream has reached its end can be performed with BIT_endOfDStream()
752 /******************************************
754 ******************************************/
755 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
756 /* faster, but works only if nbBits >= 1 */
760 /****************************************************************
762 ****************************************************************/
763 MEM_STATIC unsigned BIT_highbit32 (register U32 val)
765 # if defined(_MSC_VER) /* Visual */
767 _BitScanReverse ( &r, val );
769 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
770 return 31 - __builtin_clz (val);
771 # else /* Software version */
772 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 };
780 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
786 /**********************************************************
788 **********************************************************/
791 * Initialize a BIT_DStream_t.
792 * @bitD : a pointer to an already allocated BIT_DStream_t structure
793 * @srcBuffer must point at the beginning of a bitStream
794 * @srcSize must be the exact size of the bitStream
795 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
797 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
799 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
801 if (srcSize >= sizeof(size_t)) /* normal case */
804 bitD->start = (const char*)srcBuffer;
805 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
806 bitD->bitContainer = MEM_readLEST(bitD->ptr);
807 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
808 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
809 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
814 bitD->start = (const char*)srcBuffer;
815 bitD->ptr = bitD->start;
816 bitD->bitContainer = *(const BYTE*)(bitD->start);
819 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
820 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
821 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
822 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
823 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
824 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */
827 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
828 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
829 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
830 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
837 * Provides next n bits from local register
838 * local register is not modified (bits are still present for next read/look)
839 * On 32-bits, maxNbBits==25
840 * On 64-bits, maxNbBits==57
841 * @return : value extracted
843 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
845 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
846 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
849 /*! BIT_lookBitsFast :
850 * unsafe version; only works only if nbBits >= 1 */
851 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
853 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
854 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
857 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
859 bitD->bitsConsumed += nbBits;
863 * Read next n bits from local register.
864 * pay attention to not read more than nbBits contained into local register.
865 * @return : extracted value.
867 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
869 size_t value = BIT_lookBits(bitD, nbBits);
870 BIT_skipBits(bitD, nbBits);
874 /*!BIT_readBitsFast :
875 * unsafe version; only works only if nbBits >= 1 */
876 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
878 size_t value = BIT_lookBitsFast(bitD, nbBits);
879 BIT_skipBits(bitD, nbBits);
883 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
885 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
886 return BIT_DStream_overflow;
888 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
890 bitD->ptr -= bitD->bitsConsumed >> 3;
891 bitD->bitsConsumed &= 7;
892 bitD->bitContainer = MEM_readLEST(bitD->ptr);
893 return BIT_DStream_unfinished;
895 if (bitD->ptr == bitD->start)
897 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
898 return BIT_DStream_completed;
901 U32 nbBytes = bitD->bitsConsumed >> 3;
902 BIT_DStream_status result = BIT_DStream_unfinished;
903 if (bitD->ptr - nbBytes < bitD->start)
905 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
906 result = BIT_DStream_endOfBuffer;
908 bitD->ptr -= nbBytes;
909 bitD->bitsConsumed -= nbBytes*8;
910 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
916 * @return Tells if DStream has reached its exact end
918 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
920 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
923 #if defined (__cplusplus)
927 #endif /* BITSTREAM_H_MODULE */
931 /* ******************************************************************
932 FSE : Finite State Entropy coder
933 header file for static linking (only)
934 Copyright (C) 2013-2015, Yann Collet
936 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
938 Redistribution and use in source and binary forms, with or without
939 modification, are permitted provided that the following conditions are
942 * Redistributions of source code must retain the above copyright
943 notice, this list of conditions and the following disclaimer.
944 * Redistributions in binary form must reproduce the above
945 copyright notice, this list of conditions and the following disclaimer
946 in the documentation and/or other materials provided with the
949 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
950 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
951 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
952 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
953 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
954 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
955 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
956 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
957 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
958 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
959 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
961 You can contact the author at :
962 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
963 - Public forum : https://groups.google.com/forum/#!forum/lz4c
964 ****************************************************************** */
968 #if defined (__cplusplus)
973 /* *****************************************
975 *******************************************/
976 /* FSE buffer bounds */
977 #define FSE_NCOUNTBOUND 512
978 #define FSE_BLOCKBOUND(size) (size + (size>>7))
979 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
981 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
982 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
983 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
986 /* *****************************************
988 *******************************************/
989 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
990 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
992 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
993 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
997 /* *****************************************
998 * FSE symbol decompression API
999 *******************************************/
1003 const void* table; /* precise table may vary, depending on U16 */
1007 static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
1009 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
1011 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
1014 Let's now decompose FSE_decompress_usingDTable() into its unitary components.
1015 You will decode FSE-encoded symbols from the bitStream,
1016 and also any other bitFields you put in, **in reverse order**.
1018 You will need a few variables to track your bitStream. They are :
1020 BIT_DStream_t DStream; // Stream context
1021 FSE_DState_t DState; // State context. Multiple ones are possible
1022 FSE_DTable* DTablePtr; // Decoding table, provided by FSE_buildDTable()
1024 The first thing to do is to init the bitStream.
1025 errorCode = BIT_initDStream(&DStream, srcBuffer, srcSize);
1027 You should then retrieve your initial state(s)
1028 (in reverse flushing order if you have several ones) :
1029 errorCode = FSE_initDState(&DState, &DStream, DTablePtr);
1031 You can then decode your data, symbol after symbol.
1032 For information the maximum number of bits read by FSE_decodeSymbol() is 'tableLog'.
1033 Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
1034 unsigned char symbol = FSE_decodeSymbol(&DState, &DStream);
1036 You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
1037 Note : maximum allowed nbBits is 25, for 32-bits compatibility
1038 size_t bitField = BIT_readBits(&DStream, nbBits);
1040 All above operations only read from local register (which size depends on size_t).
1041 Refueling the register from memory is manually performed by the reload method.
1042 endSignal = FSE_reloadDStream(&DStream);
1044 BIT_reloadDStream() result tells if there is still some more data to read from DStream.
1045 BIT_DStream_unfinished : there is still some data left into the DStream.
1046 BIT_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
1047 BIT_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
1048 BIT_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
1050 When reaching end of buffer (BIT_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
1051 to properly detect the exact end of stream.
1052 After each decoded symbol, check if DStream is fully consumed using this simple test :
1053 BIT_reloadDStream(&DStream) >= BIT_DStream_completed
1055 When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
1056 Checking if DStream has reached its end is performed by :
1057 BIT_endOfDStream(&DStream);
1058 Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
1059 FSE_endOfDState(&DState);
1063 /* *****************************************
1065 *******************************************/
1066 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
1067 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
1070 /* *****************************************
1071 * Implementation of inlined functions
1072 *******************************************/
1078 } FSE_DTableHeader; /* sizeof U32 */
1082 unsigned short newState;
1083 unsigned char symbol;
1084 unsigned char nbBits;
1085 } FSE_decode_t; /* size == U32 */
1087 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
1089 FSE_DTableHeader DTableH;
1090 memcpy(&DTableH, dt, sizeof(DTableH));
1091 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
1092 BIT_reloadDStream(bitD);
1093 DStatePtr->table = dt + 1;
1096 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
1098 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
1099 const U32 nbBits = DInfo.nbBits;
1100 BYTE symbol = DInfo.symbol;
1101 size_t lowBits = BIT_readBits(bitD, nbBits);
1103 DStatePtr->state = DInfo.newState + lowBits;
1107 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
1109 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
1110 const U32 nbBits = DInfo.nbBits;
1111 BYTE symbol = DInfo.symbol;
1112 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
1114 DStatePtr->state = DInfo.newState + lowBits;
1118 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
1120 return DStatePtr->state == 0;
1124 #if defined (__cplusplus)
1128 #endif /* FSE_STATIC_H */
1130 /* ******************************************************************
1131 FSE : Finite State Entropy coder
1132 Copyright (C) 2013-2015, Yann Collet.
1134 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1136 Redistribution and use in source and binary forms, with or without
1137 modification, are permitted provided that the following conditions are
1140 * Redistributions of source code must retain the above copyright
1141 notice, this list of conditions and the following disclaimer.
1142 * Redistributions in binary form must reproduce the above
1143 copyright notice, this list of conditions and the following disclaimer
1144 in the documentation and/or other materials provided with the
1147 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1148 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1149 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1150 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1151 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1152 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1153 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1154 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1155 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1156 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1157 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1159 You can contact the author at :
1160 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1161 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1162 ****************************************************************** */
1164 #ifndef FSE_COMMONDEFS_ONLY
1166 /* **************************************************************
1168 ****************************************************************/
1170 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1171 * Increasing memory usage improves compression ratio
1172 * Reduced memory usage can improve speed, due to cache effect
1173 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1174 #define FSE_MAX_MEMORY_USAGE 14
1175 #define FSE_DEFAULT_MEMORY_USAGE 13
1177 /*!FSE_MAX_SYMBOL_VALUE :
1178 * Maximum symbol value authorized.
1179 * Required for proper stack allocation */
1180 #define FSE_MAX_SYMBOL_VALUE 255
1183 /* **************************************************************
1184 * template functions type & suffix
1185 ****************************************************************/
1186 #define FSE_FUNCTION_TYPE BYTE
1187 #define FSE_FUNCTION_EXTENSION
1188 #define FSE_DECODE_TYPE FSE_decode_t
1191 #endif /* !FSE_COMMONDEFS_ONLY */
1193 /* **************************************************************
1194 * Compiler specifics
1195 ****************************************************************/
1196 #ifdef _MSC_VER /* Visual Studio */
1197 # define FORCE_INLINE static __forceinline
1198 # include <intrin.h> /* For Visual 2005 */
1199 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1200 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1202 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1204 # define FORCE_INLINE static inline __attribute__((always_inline))
1206 # define FORCE_INLINE static inline
1209 # define FORCE_INLINE static
1210 # endif /* __STDC_VERSION__ */
1214 /* **************************************************************
1216 ****************************************************************/
1217 #include <stdlib.h> /* malloc, free, qsort */
1218 #include <string.h> /* memcpy, memset */
1219 #include <stdio.h> /* printf (debug) */
1222 /* ***************************************************************
1224 *****************************************************************/
1225 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
1226 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
1227 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
1228 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
1229 #define FSE_MIN_TABLELOG 5
1231 #define FSE_TABLELOG_ABSOLUTE_MAX 15
1232 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1233 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1237 /* **************************************************************
1239 ****************************************************************/
1240 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1243 /* **************************************************************
1245 ****************************************************************/
1246 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1249 /*-**************************************************************
1251 ****************************************************************/
1253 designed to be included
1254 for type-specific functions (template emulation in C)
1255 Objective is to write these functions only once, for improved maintenance
1259 #ifndef FSE_FUNCTION_EXTENSION
1260 # error "FSE_FUNCTION_EXTENSION must be defined"
1262 #ifndef FSE_FUNCTION_TYPE
1263 # error "FSE_FUNCTION_TYPE must be defined"
1266 /* Function names */
1267 #define FSE_CAT(X,Y) X##Y
1268 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1269 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1271 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1274 static size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1276 FSE_DTableHeader DTableH;
1277 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */
1278 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
1279 const U32 tableSize = 1 << tableLog;
1280 const U32 tableMask = tableSize-1;
1281 const U32 step = FSE_tableStep(tableSize);
1282 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1284 U32 highThreshold = tableSize-1;
1285 const S16 largeLimit= (S16)(1 << (tableLog-1));
1290 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1291 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1293 /* Init, lay down lowprob symbols */
1294 DTableH.tableLog = (U16)tableLog;
1295 for (s=0; s<=maxSymbolValue; s++)
1297 if (normalizedCounter[s]==-1)
1299 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1304 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1305 symbolNext[s] = normalizedCounter[s];
1309 /* Spread symbols */
1310 for (s=0; s<=maxSymbolValue; s++)
1313 for (i=0; i<normalizedCounter[s]; i++)
1315 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1316 position = (position + step) & tableMask;
1317 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1321 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1323 /* Build Decoding table */
1326 for (i=0; i<tableSize; i++)
1328 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1329 U16 nextState = symbolNext[symbol]++;
1330 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1331 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1335 DTableH.fastMode = (U16)noLarge;
1336 memcpy(dt, &DTableH, sizeof(DTableH));
1341 #ifndef FSE_COMMONDEFS_ONLY
1342 /******************************************
1343 * FSE helper functions
1344 ******************************************/
1345 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1348 /****************************************************************
1349 * FSE NCount encoding-decoding
1350 ****************************************************************/
1351 static short FSE_abs(short a)
1353 return a<0 ? -a : a;
1356 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1357 const void* headerBuffer, size_t hbSize)
1359 const BYTE* const istart = (const BYTE*) headerBuffer;
1360 const BYTE* const iend = istart + hbSize;
1361 const BYTE* ip = istart;
1367 unsigned charnum = 0;
1370 if (hbSize < 4) return ERROR(srcSize_wrong);
1371 bitStream = MEM_readLE32(ip);
1372 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1373 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1376 *tableLogPtr = nbBits;
1377 remaining = (1<<nbBits)+1;
1378 threshold = 1<<nbBits;
1381 while ((remaining>1) && (charnum<=*maxSVPtr))
1385 unsigned n0 = charnum;
1386 while ((bitStream & 0xFFFF) == 0xFFFF)
1392 bitStream = MEM_readLE32(ip) >> bitCount;
1400 while ((bitStream & 3) == 3)
1406 n0 += bitStream & 3;
1408 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1409 while (charnum < n0) normalizedCounter[charnum++] = 0;
1410 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1414 bitStream = MEM_readLE32(ip) >> bitCount;
1420 const short max = (short)((2*threshold-1)-remaining);
1423 if ((bitStream & (threshold-1)) < (U32)max)
1425 count = (short)(bitStream & (threshold-1));
1426 bitCount += nbBits-1;
1430 count = (short)(bitStream & (2*threshold-1));
1431 if (count >= threshold) count -= max;
1435 count--; /* extra accuracy */
1436 remaining -= FSE_abs(count);
1437 normalizedCounter[charnum++] = count;
1439 while (remaining < threshold)
1446 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1453 bitCount -= (int)(8 * (iend - 4 - ip));
1456 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1460 if (remaining != 1) return ERROR(GENERIC);
1461 *maxSVPtr = charnum-1;
1463 ip += (bitCount+7)>>3;
1464 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1469 /*********************************************************
1470 * Decompression (Byte symbols)
1471 *********************************************************/
1472 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1475 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1476 void* dPtr = dt + 1;
1477 FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
1479 DTableH->tableLog = 0;
1480 DTableH->fastMode = 0;
1483 cell->symbol = symbolValue;
1490 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1493 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1494 void* dPtr = dt + 1;
1495 FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
1496 const unsigned tableSize = 1 << nbBits;
1497 const unsigned tableMask = tableSize - 1;
1498 const unsigned maxSymbolValue = tableMask;
1502 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1504 /* Build Decoding Table */
1505 DTableH->tableLog = (U16)nbBits;
1506 DTableH->fastMode = 1;
1507 for (s=0; s<=maxSymbolValue; s++)
1509 dinfo[s].newState = 0;
1510 dinfo[s].symbol = (BYTE)s;
1511 dinfo[s].nbBits = (BYTE)nbBits;
1517 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1518 void* dst, size_t maxDstSize,
1519 const void* cSrc, size_t cSrcSize,
1520 const FSE_DTable* dt, const unsigned fast)
1522 BYTE* const ostart = (BYTE*) dst;
1524 BYTE* const omax = op + maxDstSize;
1525 BYTE* const olimit = omax-3;
1528 FSE_DState_t state1;
1529 FSE_DState_t state2;
1533 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1534 if (FSE_isError(errorCode)) return errorCode;
1536 FSE_initDState(&state1, &bitD, dt);
1537 FSE_initDState(&state2, &bitD, dt);
1539 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1541 /* 4 symbols per loop */
1542 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1544 op[0] = FSE_GETSYMBOL(&state1);
1546 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1547 BIT_reloadDStream(&bitD);
1549 op[1] = FSE_GETSYMBOL(&state2);
1551 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1552 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1554 op[2] = FSE_GETSYMBOL(&state1);
1556 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1557 BIT_reloadDStream(&bitD);
1559 op[3] = FSE_GETSYMBOL(&state2);
1563 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1566 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1569 *op++ = FSE_GETSYMBOL(&state1);
1571 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1574 *op++ = FSE_GETSYMBOL(&state2);
1578 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1581 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1583 return ERROR(corruption_detected);
1587 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1588 const void* cSrc, size_t cSrcSize,
1589 const FSE_DTable* dt)
1591 FSE_DTableHeader DTableH;
1594 memcpy(&DTableH, dt, sizeof(DTableH));
1595 fastMode = DTableH.fastMode;
1597 /* select fast mode (static) */
1598 if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1599 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1603 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1605 const BYTE* const istart = (const BYTE*)cSrc;
1606 const BYTE* ip = istart;
1607 short counting[FSE_MAX_SYMBOL_VALUE+1];
1608 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1610 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1613 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1615 /* normal FSE decoding mode */
1616 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1617 if (FSE_isError(errorCode)) return errorCode;
1618 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1620 cSrcSize -= errorCode;
1622 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1623 if (FSE_isError(errorCode)) return errorCode;
1625 /* always return, even if it is an error code */
1626 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1631 #endif /* FSE_COMMONDEFS_ONLY */
1634 /* ******************************************************************
1635 Huff0 : Huffman coder, part of New Generation Entropy library
1637 Copyright (C) 2013-2015, Yann Collet.
1639 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1641 Redistribution and use in source and binary forms, with or without
1642 modification, are permitted provided that the following conditions are
1645 * Redistributions of source code must retain the above copyright
1646 notice, this list of conditions and the following disclaimer.
1647 * Redistributions in binary form must reproduce the above
1648 copyright notice, this list of conditions and the following disclaimer
1649 in the documentation and/or other materials provided with the
1652 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1653 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1654 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1655 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1656 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1657 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1658 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1659 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1660 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1661 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1662 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1664 You can contact the author at :
1665 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1666 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1667 ****************************************************************** */
1671 #if defined (__cplusplus)
1676 /* ****************************************
1678 ******************************************/
1679 #include <stddef.h> /* size_t */
1682 /* ****************************************
1683 * Huff0 simple functions
1684 ******************************************/
1685 static size_t HUF_decompress(void* dst, size_t dstSize,
1686 const void* cSrc, size_t cSrcSize);
1689 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1690 into already allocated destination buffer 'dst', of size 'dstSize'.
1691 'dstSize' must be the exact size of original (uncompressed) data.
1692 Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate.
1693 @return : size of regenerated data (== dstSize)
1694 or an error code, which can be tested using HUF_isError()
1698 /* ****************************************
1700 ******************************************/
1701 /* Error Management */
1702 static unsigned HUF_isError(size_t code); /* tells if a return value is an error code */
1705 #if defined (__cplusplus)
1709 #endif /* HUFF0_H */
1712 /* ******************************************************************
1713 Huff0 : Huffman coder, part of New Generation Entropy library
1714 header file for static linking (only)
1715 Copyright (C) 2013-2015, Yann Collet
1717 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1719 Redistribution and use in source and binary forms, with or without
1720 modification, are permitted provided that the following conditions are
1723 * Redistributions of source code must retain the above copyright
1724 notice, this list of conditions and the following disclaimer.
1725 * Redistributions in binary form must reproduce the above
1726 copyright notice, this list of conditions and the following disclaimer
1727 in the documentation and/or other materials provided with the
1730 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1731 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1732 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1733 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1734 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1735 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1736 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1737 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1738 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1739 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1740 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1742 You can contact the author at :
1743 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1744 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1745 ****************************************************************** */
1746 #ifndef HUFF0_STATIC_H
1747 #define HUFF0_STATIC_H
1749 #if defined (__cplusplus)
1755 /* ****************************************
1756 * Static allocation macros
1757 ******************************************/
1758 /* static allocation of Huff0's DTable */
1759 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
1760 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1761 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1762 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1763 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1764 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1765 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1768 /* ****************************************
1769 * Advanced decompression functions
1770 ******************************************/
1771 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1772 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1775 /* ****************************************
1776 * Huff0 detailed API
1777 ******************************************/
1779 HUF_decompress() does the following:
1780 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1781 2. build Huffman table from save, using HUF_readDTableXn()
1782 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable
1785 static size_t HUF_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1786 static size_t HUF_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1788 static size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1789 static size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1792 #if defined (__cplusplus)
1796 #endif /* HUFF0_STATIC_H */
1800 /* ******************************************************************
1801 Huff0 : Huffman coder, part of New Generation Entropy library
1802 Copyright (C) 2013-2015, Yann Collet.
1804 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1806 Redistribution and use in source and binary forms, with or without
1807 modification, are permitted provided that the following conditions are
1810 * Redistributions of source code must retain the above copyright
1811 notice, this list of conditions and the following disclaimer.
1812 * Redistributions in binary form must reproduce the above
1813 copyright notice, this list of conditions and the following disclaimer
1814 in the documentation and/or other materials provided with the
1817 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1818 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1819 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1820 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1821 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1822 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1823 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1824 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1825 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1826 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1827 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1829 You can contact the author at :
1830 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1831 ****************************************************************** */
1833 /* **************************************************************
1834 * Compiler specifics
1835 ****************************************************************/
1836 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1837 /* inline is defined */
1838 #elif defined(_MSC_VER)
1839 # define inline __inline
1841 # define inline /* disable inline */
1845 #ifdef _MSC_VER /* Visual Studio */
1846 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1850 /* **************************************************************
1852 ****************************************************************/
1853 #include <stdlib.h> /* malloc, free, qsort */
1854 #include <string.h> /* memcpy, memset */
1855 #include <stdio.h> /* printf (debug) */
1858 /* **************************************************************
1860 ****************************************************************/
1861 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1862 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1863 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1864 #define HUF_MAX_SYMBOL_VALUE 255
1865 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1866 # error "HUF_MAX_TABLELOG is too large !"
1870 /* **************************************************************
1872 ****************************************************************/
1873 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1874 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1878 /*-*******************************************************
1879 * Huff0 : Huffman block decompression
1880 *********************************************************/
1881 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1883 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1885 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1888 Read compact Huffman tree, saved by HUF_writeCTable
1889 @huffWeight : destination buffer
1890 @return : size read from `src`
1892 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1893 U32* nbSymbolsPtr, U32* tableLogPtr,
1894 const void* src, size_t srcSize)
1898 const BYTE* ip = (const BYTE*) src;
1903 if (!srcSize) return ERROR(srcSize_wrong);
1905 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1907 if (iSize >= 128) /* special header */
1909 if (iSize >= (242)) /* RLE */
1911 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1912 oSize = l[iSize-242];
1913 memset(huffWeight, 1, hwSize);
1916 else /* Incompressible */
1918 oSize = iSize - 127;
1919 iSize = ((oSize+1)/2);
1920 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1921 if (oSize >= hwSize) return ERROR(corruption_detected);
1923 for (n=0; n<oSize; n+=2)
1925 huffWeight[n] = ip[n/2] >> 4;
1926 huffWeight[n+1] = ip[n/2] & 15;
1930 else /* header compressed with FSE (normal case) */
1932 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1933 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1934 if (FSE_isError(oSize)) return oSize;
1937 /* collect weight stats */
1938 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1940 for (n=0; n<oSize; n++)
1942 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1943 rankStats[huffWeight[n]]++;
1944 weightTotal += (1 << huffWeight[n]) >> 1;
1946 if (weightTotal == 0) return ERROR(corruption_detected);
1948 /* get last non-null symbol weight (implied, total must be 2^n) */
1949 tableLog = BIT_highbit32(weightTotal) + 1;
1950 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1952 U32 total = 1 << tableLog;
1953 U32 rest = total - weightTotal;
1954 U32 verif = 1 << BIT_highbit32(rest);
1955 U32 lastWeight = BIT_highbit32(rest) + 1;
1956 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1957 huffWeight[oSize] = (BYTE)lastWeight;
1958 rankStats[lastWeight]++;
1961 /* check tree construction validity */
1962 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1965 *nbSymbolsPtr = (U32)(oSize+1);
1966 *tableLogPtr = tableLog;
1971 /**************************/
1972 /* single-symbol decoding */
1973 /**************************/
1975 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1977 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1978 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1984 void* const dtPtr = DTable + 1;
1985 HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;
1987 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1988 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1990 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1991 if (HUF_isError(iSize)) return iSize;
1994 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1995 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1999 for (n=1; n<=tableLog; n++)
2001 U32 current = nextRankStart;
2002 nextRankStart += (rankVal[n] << (n-1));
2003 rankVal[n] = current;
2007 for (n=0; n<nbSymbols; n++)
2009 const U32 w = huffWeight[n];
2010 const U32 length = (1 << w) >> 1;
2013 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
2014 for (i = rankVal[w]; i < rankVal[w] + length; i++)
2016 rankVal[w] += length;
2022 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
2024 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
2025 const BYTE c = dt[val].byte;
2026 BIT_skipBits(Dstream, dt[val].nbBits);
2030 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
2031 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
2033 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
2034 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2035 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2037 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
2039 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2041 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
2043 BYTE* const pStart = p;
2045 /* up to 4 symbols at a time */
2046 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
2048 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
2049 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
2050 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
2051 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
2054 /* closer to the end */
2055 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
2056 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
2058 /* no more data to retrieve from bitstream, hence no need to reload */
2060 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
2066 static size_t HUF_decompress4X2_usingDTable(
2067 void* dst, size_t dstSize,
2068 const void* cSrc, size_t cSrcSize,
2071 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2074 const BYTE* const istart = (const BYTE*) cSrc;
2075 BYTE* const ostart = (BYTE*) dst;
2076 BYTE* const oend = ostart + dstSize;
2077 const void* const dtPtr = DTable;
2078 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)dtPtr) +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_SYMBOLX2_2(op1, &bitD1);
2121 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
2122 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
2123 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
2124 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
2125 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
2126 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
2127 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
2128 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
2129 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
2130 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
2131 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
2132 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
2133 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
2134 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
2135 HUF_DECODE_SYMBOLX2_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_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2148 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2149 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2150 HUF_decodeStreamX2(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_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2164 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
2165 const BYTE* ip = (const BYTE*) cSrc;
2168 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
2169 if (HUF_isError(errorCode)) return errorCode;
2170 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2172 cSrcSize -= errorCode;
2174 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2178 /***************************/
2179 /* double-symbols decoding */
2180 /***************************/
2182 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2183 const U32* rankValOrigin, const int minWeight,
2184 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2185 U32 nbBitsBaseline, U16 baseSeq)
2188 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
2191 /* get pre-calculated rankVal */
2192 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2194 /* fill skipped values */
2197 U32 i, skipSize = rankVal[minWeight];
2198 MEM_writeLE16(&(DElt.sequence), baseSeq);
2199 DElt.nbBits = (BYTE)(consumed);
2201 for (i = 0; i < skipSize; i++)
2206 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
2208 const U32 symbol = sortedSymbols[s].symbol;
2209 const U32 weight = sortedSymbols[s].weight;
2210 const U32 nbBits = nbBitsBaseline - weight;
2211 const U32 length = 1 << (sizeLog-nbBits);
2212 const U32 start = rankVal[weight];
2214 const U32 end = start + length;
2216 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2217 DElt.nbBits = (BYTE)(nbBits + consumed);
2219 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2221 rankVal[weight] += length;
2225 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
2227 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
2228 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2229 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2230 const U32 nbBitsBaseline)
2232 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
2233 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2234 const U32 minBits = nbBitsBaseline - maxWeight;
2237 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2240 for (s=0; s<sortedListSize; s++)
2242 const U16 symbol = sortedList[s].symbol;
2243 const U32 weight = sortedList[s].weight;
2244 const U32 nbBits = nbBitsBaseline - weight;
2245 const U32 start = rankVal[weight];
2246 const U32 length = 1 << (targetLog-nbBits);
2248 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
2251 int minWeight = nbBits + scaleLog;
2252 if (minWeight < 1) minWeight = 1;
2253 sortedRank = rankStart[minWeight];
2254 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2255 rankValOrigin[nbBits], minWeight,
2256 sortedList+sortedRank, sortedListSize-sortedRank,
2257 nbBitsBaseline, symbol);
2262 const U32 end = start + length;
2265 MEM_writeLE16(&(DElt.sequence), symbol);
2266 DElt.nbBits = (BYTE)(nbBits);
2268 for (i = start; i < end; i++)
2271 rankVal[weight] += length;
2275 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2277 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
2278 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
2279 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2280 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2281 U32* const rankStart = rankStart0+1;
2283 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2284 const U32 memLog = DTable[0];
2286 void* dtPtr = DTable;
2287 HUF_DEltX4* const dt = ((HUF_DEltX4*)dtPtr) + 1;
2289 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
2290 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2291 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2293 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2294 if (HUF_isError(iSize)) return iSize;
2297 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2299 /* find maxWeight */
2300 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2301 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
2303 /* Get start index of each weight */
2305 U32 w, nextRankStart = 0;
2306 for (w=1; w<=maxW; w++)
2308 U32 current = nextRankStart;
2309 nextRankStart += rankStats[w];
2310 rankStart[w] = current;
2312 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2313 sizeOfSort = nextRankStart;
2316 /* sort symbols by weight */
2319 for (s=0; s<nbSymbols; s++)
2321 U32 w = weightList[s];
2322 U32 r = rankStart[w]++;
2323 sortedSymbol[r].symbol = (BYTE)s;
2324 sortedSymbol[r].weight = (BYTE)w;
2326 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2331 const U32 minBits = tableLog+1 - maxW;
2332 U32 nextRankVal = 0;
2334 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2335 U32* rankVal0 = rankVal[0];
2336 for (w=1; w<=maxW; w++)
2338 U32 current = nextRankVal;
2339 nextRankVal += rankStats[w] << (w+rescale);
2340 rankVal0[w] = current;
2342 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2344 U32* rankValPtr = rankVal[consumed];
2345 for (w = 1; w <= maxW; w++)
2347 rankValPtr[w] = rankVal0[w] >> consumed;
2352 HUF_fillDTableX4(dt, memLog,
2353 sortedSymbol, sizeOfSort,
2354 rankStart0, rankVal, maxW,
2361 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2363 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2364 memcpy(op, dt+val, 2);
2365 BIT_skipBits(DStream, dt[val].nbBits);
2366 return dt[val].length;
2369 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2371 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2372 memcpy(op, dt+val, 1);
2373 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2376 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2378 BIT_skipBits(DStream, dt[val].nbBits);
2379 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2380 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 */
2387 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2388 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2390 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2391 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2392 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2394 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2396 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2398 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2400 BYTE* const pStart = p;
2402 /* up to 8 symbols at a time */
2403 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2405 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2406 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2407 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2408 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2411 /* closer to the end */
2412 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2413 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2416 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2419 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2424 static size_t HUF_decompress4X4_usingDTable(
2425 void* dst, size_t dstSize,
2426 const void* cSrc, size_t cSrcSize,
2429 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2432 const BYTE* const istart = (const BYTE*) cSrc;
2433 BYTE* const ostart = (BYTE*) dst;
2434 BYTE* const oend = ostart + dstSize;
2435 const void* const dtPtr = DTable;
2436 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)dtPtr) +1;
2437 const U32 dtLog = DTable[0];
2441 BIT_DStream_t bitD1;
2442 BIT_DStream_t bitD2;
2443 BIT_DStream_t bitD3;
2444 BIT_DStream_t bitD4;
2445 const size_t length1 = MEM_readLE16(istart);
2446 const size_t length2 = MEM_readLE16(istart+2);
2447 const size_t length3 = MEM_readLE16(istart+4);
2449 const BYTE* const istart1 = istart + 6; /* jumpTable */
2450 const BYTE* const istart2 = istart1 + length1;
2451 const BYTE* const istart3 = istart2 + length2;
2452 const BYTE* const istart4 = istart3 + length3;
2453 const size_t segmentSize = (dstSize+3) / 4;
2454 BYTE* const opStart2 = ostart + segmentSize;
2455 BYTE* const opStart3 = opStart2 + segmentSize;
2456 BYTE* const opStart4 = opStart3 + segmentSize;
2458 BYTE* op2 = opStart2;
2459 BYTE* op3 = opStart3;
2460 BYTE* op4 = opStart4;
2463 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2464 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2465 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2466 if (HUF_isError(errorCode)) return errorCode;
2467 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2468 if (HUF_isError(errorCode)) return errorCode;
2469 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2470 if (HUF_isError(errorCode)) return errorCode;
2471 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2472 if (HUF_isError(errorCode)) return errorCode;
2474 /* 16-32 symbols per loop (4-8 symbols per stream) */
2475 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2476 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2478 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2479 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2480 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2481 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2482 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2483 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2484 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2485 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2486 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2487 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2488 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2489 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2490 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2491 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2492 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2493 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2495 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2498 /* check corruption */
2499 if (op1 > opStart2) return ERROR(corruption_detected);
2500 if (op2 > opStart3) return ERROR(corruption_detected);
2501 if (op3 > opStart4) return ERROR(corruption_detected);
2502 /* note : op4 supposed already verified within main loop */
2504 /* finish bitStreams one by one */
2505 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2506 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2507 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2508 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2511 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2512 if (!endSignal) return ERROR(corruption_detected);
2520 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2522 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2523 const BYTE* ip = (const BYTE*) cSrc;
2525 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2526 if (HUF_isError(hSize)) return hSize;
2527 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2531 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2535 /**********************************/
2536 /* Generic decompression selector */
2537 /**********************************/
2539 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2540 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2542 /* single, double, quad */
2543 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2544 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2545 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2546 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2547 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2548 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2549 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2550 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2551 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2552 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2553 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2554 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2555 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2556 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2557 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2558 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2561 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2563 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2565 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2566 /* estimate decompression time */
2568 const U32 D256 = (U32)(dstSize >> 8);
2573 /* validation checks */
2574 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2575 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2576 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2577 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2579 /* decoder timing evaluation */
2580 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2582 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2584 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2586 if (Dtime[1] < Dtime[0]) algoNb = 1;
2588 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2590 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2591 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2592 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2597 #endif /* ZSTD_CCOMMON_H_MODULE */
2601 zstd - decompression module fo v0.4 legacy format
2602 Copyright (C) 2015-2016, Yann Collet.
2604 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2606 Redistribution and use in source and binary forms, with or without
2607 modification, are permitted provided that the following conditions are
2609 * Redistributions of source code must retain the above copyright
2610 notice, this list of conditions and the following disclaimer.
2611 * Redistributions in binary form must reproduce the above
2612 copyright notice, this list of conditions and the following disclaimer
2613 in the documentation and/or other materials provided with the
2615 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2616 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2617 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2618 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2619 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2620 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2621 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2622 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2623 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2624 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2625 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2627 You can contact the author at :
2628 - zstd source repository : https://github.com/Cyan4973/zstd
2629 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2632 /* ***************************************************************
2634 *****************************************************************/
2637 * Select how default decompression function ZSTD_decompress() will allocate memory,
2638 * in memory stack (0), or in memory heap (1, requires malloc())
2640 #ifndef ZSTD_HEAPMODE
2641 # define ZSTD_HEAPMODE 1
2645 /* *******************************************************
2647 *********************************************************/
2648 #include <stdlib.h> /* calloc */
2649 #include <string.h> /* memcpy, memmove */
2650 #include <stdio.h> /* debug : printf */
2653 /* *******************************************************
2654 * Compiler specifics
2655 *********************************************************/
2656 #ifdef _MSC_VER /* Visual Studio */
2657 # include <intrin.h> /* For Visual 2005 */
2658 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2659 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2663 /* *************************************
2665 ***************************************/
2668 blockType_t blockType;
2670 } blockProperties_t;
2673 /* *******************************************************
2675 **********************************************************/
2676 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2679 /* *************************************
2681 ***************************************/
2684 * tells if a return value is an error code */
2685 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2688 /* *************************************************************
2689 * Context management
2690 ***************************************************************/
2691 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2692 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTD_dStage;
2694 struct ZSTDv04_Dctx_s
2696 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2697 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2698 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2699 const void* previousDstEnd;
2702 const void* dictEnd;
2705 ZSTD_parameters params;
2710 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2711 BYTE headerBuffer[ZSTD_frameHeaderSize_max];
2712 }; /* typedef'd to ZSTD_DCtx within "zstd_static.h" */
2714 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2716 dctx->expected = ZSTD_frameHeaderSize_min;
2717 dctx->stage = ZSTDds_getFrameHeaderSize;
2718 dctx->previousDstEnd = NULL;
2721 dctx->dictEnd = NULL;
2725 static ZSTD_DCtx* ZSTD_createDCtx(void)
2727 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2728 if (dctx==NULL) return NULL;
2729 ZSTD_resetDCtx(dctx);
2733 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
2740 /* *************************************************************
2741 * Decompression section
2742 ***************************************************************/
2743 /** ZSTD_decodeFrameHeader_Part1
2744 * decode the 1st part of the Frame Header, which tells Frame Header size.
2745 * srcSize must be == ZSTD_frameHeaderSize_min
2746 * @return : the full size of the Frame Header */
2747 static size_t ZSTD_decodeFrameHeader_Part1(ZSTD_DCtx* zc, const void* src, size_t srcSize)
2750 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);
2751 magicNumber = MEM_readLE32(src);
2752 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
2753 zc->headerSize = ZSTD_frameHeaderSize_min;
2754 return zc->headerSize;
2758 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize)
2761 if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_max;
2762 magicNumber = MEM_readLE32(src);
2763 if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
2764 memset(params, 0, sizeof(*params));
2765 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
2766 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */
2770 /** ZSTD_decodeFrameHeader_Part2
2771 * decode the full Frame Header
2772 * srcSize must be the size provided by ZSTD_decodeFrameHeader_Part1
2773 * @return : 0, or an error code, which can be tested using ZSTD_isError() */
2774 static size_t ZSTD_decodeFrameHeader_Part2(ZSTD_DCtx* zc, const void* src, size_t srcSize)
2777 if (srcSize != zc->headerSize) return ERROR(srcSize_wrong);
2778 result = ZSTD_getFrameParams(&(zc->params), src, srcSize);
2779 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupportedBy32bits);
2784 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2786 const BYTE* const in = (const BYTE* const)src;
2790 if (srcSize < 3) return ERROR(srcSize_wrong);
2793 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2795 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2796 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2798 if (bpPtr->blockType == bt_end) return 0;
2799 if (bpPtr->blockType == bt_rle) return 1;
2803 static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2805 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2806 memcpy(dst, src, srcSize);
2811 /** ZSTD_decompressLiterals
2812 @return : nb of bytes read from src, or an error code*/
2813 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2814 const void* src, size_t srcSize)
2816 const BYTE* ip = (const BYTE*)src;
2818 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2819 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2821 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2822 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2824 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2826 *maxDstSizePtr = litSize;
2827 return litCSize + 5;
2831 /** ZSTD_decodeLiteralsBlock
2832 @return : nb of bytes read from src (< srcSize ) */
2833 static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
2834 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
2836 const BYTE* const istart = (const BYTE*) src;
2838 /* any compressed block with literals segment must be at least this size */
2839 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2846 size_t litSize = BLOCKSIZE;
2847 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2848 dctx->litPtr = dctx->litBuffer;
2849 dctx->litSize = litSize;
2850 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2851 return readSize; /* works if it's an error too */
2855 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2856 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2858 if (litSize > srcSize-3) return ERROR(corruption_detected);
2859 memcpy(dctx->litBuffer, istart, litSize);
2860 dctx->litPtr = dctx->litBuffer;
2861 dctx->litSize = litSize;
2862 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2865 /* direct reference into compressed stream */
2866 dctx->litPtr = istart+3;
2867 dctx->litSize = litSize;
2871 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2872 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2873 memset(dctx->litBuffer, istart[3], litSize + 8);
2874 dctx->litPtr = dctx->litBuffer;
2875 dctx->litSize = litSize;
2879 return ERROR(corruption_detected); /* forbidden nominal case */
2884 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2885 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2886 const void* src, size_t srcSize)
2888 const BYTE* const istart = (const BYTE* const)src;
2889 const BYTE* ip = istart;
2890 const BYTE* const iend = istart + srcSize;
2891 U32 LLtype, Offtype, MLtype;
2892 U32 LLlog, Offlog, MLlog;
2896 if (srcSize < 5) return ERROR(srcSize_wrong);
2899 *nbSeq = MEM_readLE16(ip); ip+=2;
2901 Offtype = (*ip >> 4) & 3;
2902 MLtype = (*ip >> 2) & 3;
2905 dumpsLength = ip[2];
2906 dumpsLength += ip[1] << 8;
2911 dumpsLength = ip[1];
2912 dumpsLength += (ip[0] & 1) << 8;
2917 *dumpsLengthPtr = dumpsLength;
2920 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2924 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */
2932 FSE_buildDTable_rle(DTableLL, *ip++); break;
2935 FSE_buildDTable_raw(DTableLL, LLbits); break;
2938 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2939 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2940 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2942 FSE_buildDTable(DTableLL, norm, max, LLlog);
2949 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2950 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2954 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2957 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2958 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2959 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2961 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2968 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2969 FSE_buildDTable_rle(DTableML, *ip++); break;
2972 FSE_buildDTable_raw(DTableML, MLbits); break;
2975 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2976 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2977 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2979 FSE_buildDTable(DTableML, norm, max, MLlog);
2993 BIT_DStream_t DStream;
2994 FSE_DState_t stateLL;
2995 FSE_DState_t stateOffb;
2996 FSE_DState_t stateML;
2999 const BYTE* dumpsEnd;
3003 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
3009 const BYTE* dumps = seqState->dumps;
3010 const BYTE* const de = seqState->dumpsEnd;
3012 /* Literal length */
3013 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
3014 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3015 if (litLength == MaxLL) {
3017 if (add < 255) litLength += add;
3019 litLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16);
3022 if (dumps > de) { litLength = MaxLL+255; } /* late correction, to avoid using uninitialized memory */
3023 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3027 { static const U32 offsetPrefix[MaxOff+1] = {
3028 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3029 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3030 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3031 U32 offsetCode, nbBits;
3032 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
3033 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3034 nbBits = offsetCode - 1;
3035 if (offsetCode==0) nbBits = 0; /* cmove */
3036 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
3037 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
3038 if (offsetCode==0) offset = prevOffset; /* cmove */
3039 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */
3043 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3044 if (matchLength == MaxML) {
3046 if (add < 255) matchLength += add;
3048 matchLength = dumps[0] + (dumps[1]<<8) + (dumps[2]<<16);
3051 if (dumps > de) { matchLength = MaxML+255; } /* late correction, to avoid using uninitialized memory */
3052 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3054 matchLength += MINMATCH;
3057 seq->litLength = litLength;
3058 seq->offset = offset;
3059 seq->matchLength = matchLength;
3060 seqState->dumps = dumps;
3064 static size_t ZSTD_execSequence(BYTE* op,
3065 BYTE* const oend, seq_t sequence,
3066 const BYTE** litPtr, const BYTE* const litLimit,
3067 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3069 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3070 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3071 BYTE* const oLitEnd = op + sequence.litLength;
3072 const size_t sequenceLength = sequence.litLength + sequence.matchLength;
3073 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3074 BYTE* const oend_8 = oend-8;
3075 const BYTE* const litEnd = *litPtr + sequence.litLength;
3076 const BYTE* match = oLitEnd - sequence.offset;
3079 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
3080 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3081 if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */
3084 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3086 *litPtr = litEnd; /* update for next sequence */
3089 if (sequence.offset > (size_t)(oLitEnd - base))
3091 /* offset beyond prefix */
3092 if (sequence.offset > (size_t)(oLitEnd - vBase))
3093 return ERROR(corruption_detected);
3094 match = dictEnd - (base-match);
3095 if (match + sequence.matchLength <= dictEnd)
3097 memmove(oLitEnd, match, sequence.matchLength);
3098 return sequenceLength;
3100 /* span extDict & currentPrefixSegment */
3102 size_t length1 = dictEnd - match;
3103 memmove(oLitEnd, match, length1);
3104 op = oLitEnd + length1;
3105 sequence.matchLength -= length1;
3107 if (op > oend_8 || sequence.matchLength < MINMATCH) {
3108 while (op < oMatchEnd) *op++ = *match++;
3109 return sequenceLength;
3113 /* Requirement: op <= oend_8 */
3115 /* match within prefix */
3116 if (sequence.offset < 8) {
3117 /* close range match, overlap */
3118 const int sub2 = dec64table[sequence.offset];
3123 match += dec32table[sequence.offset];
3124 ZSTD_copy4(op+4, match);
3127 ZSTD_copy8(op, match);
3129 op += 8; match += 8;
3131 if (oMatchEnd > oend-(16-MINMATCH))
3135 ZSTD_wildcopy(op, match, oend_8 - op);
3136 match += oend_8 - op;
3139 while (op < oMatchEnd) *op++ = *match++;
3143 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3145 return sequenceLength;
3149 static size_t ZSTD_decompressSequences(
3151 void* dst, size_t maxDstSize,
3152 const void* seqStart, size_t seqSize)
3154 const BYTE* ip = (const BYTE*)seqStart;
3155 const BYTE* const iend = ip + seqSize;
3156 BYTE* const ostart = (BYTE* const)dst;
3158 BYTE* const oend = ostart + maxDstSize;
3159 size_t errorCode, dumpsLength;
3160 const BYTE* litPtr = dctx->litPtr;
3161 const BYTE* const litEnd = litPtr + dctx->litSize;
3164 U32* DTableLL = dctx->LLTable;
3165 U32* DTableML = dctx->MLTable;
3166 U32* DTableOffb = dctx->OffTable;
3167 const BYTE* const base = (const BYTE*) (dctx->base);
3168 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3169 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3171 /* Build Decoding Tables */
3172 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3173 DTableLL, DTableML, DTableOffb,
3175 if (ZSTD_isError(errorCode)) return errorCode;
3178 /* Regen sequences */
3181 seqState_t seqState;
3183 memset(&sequence, 0, sizeof(sequence));
3184 sequence.offset = 4;
3185 seqState.dumps = dumps;
3186 seqState.dumpsEnd = dumps + dumpsLength;
3187 seqState.prevOffset = 4;
3188 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
3189 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3190 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3191 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3192 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3194 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; )
3198 ZSTD_decodeSequence(&sequence, &seqState);
3199 oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3200 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
3204 /* check if reached exact end */
3205 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* DStream should be entirely and exactly consumed; otherwise data is corrupted */
3207 /* last literal segment */
3209 size_t lastLLSize = litEnd - litPtr;
3210 if (litPtr > litEnd) return ERROR(corruption_detected);
3211 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3212 if (op != litPtr) memcpy(op, litPtr, lastLLSize);
3221 static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
3223 if (dst != dctx->previousDstEnd) /* not contiguous */
3225 dctx->dictEnd = dctx->previousDstEnd;
3226 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3228 dctx->previousDstEnd = dst;
3233 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
3234 void* dst, size_t maxDstSize,
3235 const void* src, size_t srcSize)
3237 /* blockType == blockCompressed */
3238 const BYTE* ip = (const BYTE*)src;
3240 /* Decode literals sub-block */
3241 size_t litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
3242 if (ZSTD_isError(litCSize)) return litCSize;
3244 srcSize -= litCSize;
3246 return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize);
3250 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
3251 void* dst, size_t maxDstSize,
3252 const void* src, size_t srcSize,
3253 const void* dict, size_t dictSize)
3255 const BYTE* ip = (const BYTE*)src;
3256 const BYTE* iend = ip + srcSize;
3257 BYTE* const ostart = (BYTE* const)dst;
3259 BYTE* const oend = ostart + maxDstSize;
3260 size_t remainingSize = srcSize;
3261 blockProperties_t blockProperties;
3264 ZSTD_resetDCtx(ctx);
3267 ZSTD_decompress_insertDictionary(ctx, dict, dictSize);
3268 ctx->dictEnd = ctx->previousDstEnd;
3269 ctx->vBase = (const char*)dst - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
3274 ctx->vBase = ctx->base = ctx->dictEnd = dst;
3279 size_t frameHeaderSize;
3280 if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3281 frameHeaderSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
3282 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
3283 if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3284 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3285 frameHeaderSize = ZSTD_decodeFrameHeader_Part2(ctx, src, frameHeaderSize);
3286 if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
3289 /* Loop on each block */
3292 size_t decodedSize=0;
3293 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
3294 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3296 ip += ZSTD_blockHeaderSize;
3297 remainingSize -= ZSTD_blockHeaderSize;
3298 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3300 switch(blockProperties.blockType)
3303 decodedSize = ZSTD_decompressBlock_internal(ctx, op, oend-op, ip, cBlockSize);
3306 decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
3309 return ERROR(GENERIC); /* not yet supported */
3313 if (remainingSize) return ERROR(srcSize_wrong);
3316 return ERROR(GENERIC); /* impossible */
3318 if (cBlockSize == 0) break; /* bt_end */
3320 if (ZSTD_isError(decodedSize)) return decodedSize;
3323 remainingSize -= cBlockSize;
3329 static size_t ZSTD_findFrameCompressedSize(const void* src, size_t srcSize)
3331 const BYTE* ip = (const BYTE*)src;
3332 size_t remainingSize = srcSize;
3333 blockProperties_t blockProperties;
3336 if (srcSize < ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);
3337 if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
3338 ip += ZSTD_frameHeaderSize_min; remainingSize -= ZSTD_frameHeaderSize_min;
3340 /* Loop on each block */
3343 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
3344 if (ZSTD_isError(cBlockSize)) return cBlockSize;
3346 ip += ZSTD_blockHeaderSize;
3347 remainingSize -= ZSTD_blockHeaderSize;
3348 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3350 if (cBlockSize == 0) break; /* bt_end */
3353 remainingSize -= cBlockSize;
3356 return ip - (const BYTE*)src;
3359 /* ******************************
3360 * Streaming Decompression API
3361 ********************************/
3362 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3364 return dctx->expected;
3367 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3370 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3371 ZSTD_checkContinuity(ctx, dst);
3373 /* Decompress : frame header; part 1 */
3376 case ZSTDds_getFrameHeaderSize :
3377 /* get frame header size */
3378 if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3379 ctx->headerSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
3380 if (ZSTD_isError(ctx->headerSize)) return ctx->headerSize;
3381 memcpy(ctx->headerBuffer, src, ZSTD_frameHeaderSize_min);
3382 if (ctx->headerSize > ZSTD_frameHeaderSize_min) return ERROR(GENERIC); /* impossible */
3383 ctx->expected = 0; /* not necessary to copy more */
3385 case ZSTDds_decodeFrameHeader:
3386 /* get frame header */
3387 { size_t const result = ZSTD_decodeFrameHeader_Part2(ctx, ctx->headerBuffer, ctx->headerSize);
3388 if (ZSTD_isError(result)) return result;
3389 ctx->expected = ZSTD_blockHeaderSize;
3390 ctx->stage = ZSTDds_decodeBlockHeader;
3393 case ZSTDds_decodeBlockHeader:
3394 /* Decode block header */
3395 { blockProperties_t bp;
3396 size_t const blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3397 if (ZSTD_isError(blockSize)) return blockSize;
3398 if (bp.blockType == bt_end)
3401 ctx->stage = ZSTDds_getFrameHeaderSize;
3405 ctx->expected = blockSize;
3406 ctx->bType = bp.blockType;
3407 ctx->stage = ZSTDds_decompressBlock;
3411 case ZSTDds_decompressBlock:
3413 /* Decompress : block content */
3418 rSize = ZSTD_decompressBlock_internal(ctx, dst, maxDstSize, src, srcSize);
3421 rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize);
3424 return ERROR(GENERIC); /* not yet handled */
3426 case bt_end : /* should never happen (filtered at phase 1) */
3430 return ERROR(GENERIC);
3432 ctx->stage = ZSTDds_decodeBlockHeader;
3433 ctx->expected = ZSTD_blockHeaderSize;
3434 ctx->previousDstEnd = (char*)dst + rSize;
3438 return ERROR(GENERIC); /* impossible */
3443 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* dict, size_t dictSize)
3445 ctx->dictEnd = ctx->previousDstEnd;
3446 ctx->vBase = (const char*)dict - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
3448 ctx->previousDstEnd = (const char*)dict + dictSize;
3454 Buffered version of Zstd compression library
3455 Copyright (C) 2015, Yann Collet.
3457 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
3459 Redistribution and use in source and binary forms, with or without
3460 modification, are permitted provided that the following conditions are
3462 * Redistributions of source code must retain the above copyright
3463 notice, this list of conditions and the following disclaimer.
3464 * Redistributions in binary form must reproduce the above
3465 copyright notice, this list of conditions and the following disclaimer
3466 in the documentation and/or other materials provided with the
3468 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3469 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3470 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3471 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3472 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3473 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3474 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3475 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3476 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3477 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3478 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3480 You can contact the author at :
3481 - zstd source repository : https://github.com/Cyan4973/zstd
3482 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3485 /* The objects defined into this file should be considered experimental.
3486 * They are not labelled stable, as their prototype may change in the future.
3487 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3490 /* *************************************
3492 ***************************************/
3496 /** ************************************************
3497 * Streaming decompression
3499 * A ZBUFF_DCtx object is required to track streaming operation.
3500 * Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources.
3501 * Use ZBUFF_decompressInit() to start a new decompression operation.
3502 * ZBUFF_DCtx objects can be reused multiple times.
3504 * Use ZBUFF_decompressContinue() repetitively to consume your input.
3505 * *srcSizePtr and *maxDstSizePtr can be any size.
3506 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3507 * Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input.
3508 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3509 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3510 * or 0 when a frame is completely decoded
3511 * or an error code, which can be tested using ZBUFF_isError().
3513 * Hint : recommended buffer sizes (not compulsory)
3514 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3515 * input : just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3516 * **************************************************/
3518 typedef enum { ZBUFFds_init, ZBUFFds_readHeader, ZBUFFds_loadHeader, ZBUFFds_decodeHeader,
3519 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage;
3521 /* *** Resource management *** */
3523 #define ZSTD_frameHeaderSize_max 5 /* too magical, should come from reference */
3524 struct ZBUFFv04_DCtx_s {
3526 ZSTD_parameters params;
3538 unsigned char headerBuffer[ZSTD_frameHeaderSize_max];
3539 }; /* typedef'd to ZBUFF_DCtx within "zstd_buffered.h" */
3541 typedef ZBUFFv04_DCtx ZBUFF_DCtx;
3544 static ZBUFF_DCtx* ZBUFF_createDCtx(void)
3546 ZBUFF_DCtx* zbc = (ZBUFF_DCtx*)malloc(sizeof(ZBUFF_DCtx));
3547 if (zbc==NULL) return NULL;
3548 memset(zbc, 0, sizeof(*zbc));
3549 zbc->zc = ZSTD_createDCtx();
3550 zbc->stage = ZBUFFds_init;
3554 static size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbc)
3556 if (zbc==NULL) return 0; /* support free on null */
3557 ZSTD_freeDCtx(zbc->zc);
3565 /* *** Initialization *** */
3567 static size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbc)
3569 zbc->stage = ZBUFFds_readHeader;
3570 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = zbc->dictSize = 0;
3571 return ZSTD_resetDCtx(zbc->zc);
3575 static size_t ZBUFF_decompressWithDictionary(ZBUFF_DCtx* zbc, const void* src, size_t srcSize)
3577 zbc->dict = (const char*)src;
3578 zbc->dictSize = srcSize;
3582 static size_t ZBUFF_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3584 size_t length = MIN(maxDstSize, srcSize);
3585 memcpy(dst, src, length);
3589 /* *** Decompression *** */
3591 static size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3593 const char* const istart = (const char*)src;
3594 const char* ip = istart;
3595 const char* const iend = istart + *srcSizePtr;
3596 char* const ostart = (char*)dst;
3598 char* const oend = ostart + *maxDstSizePtr;
3607 return ERROR(init_missing);
3609 case ZBUFFds_readHeader :
3610 /* read header from src */
3611 { size_t const headerSize = ZSTD_getFrameParams(&(zbc->params), src, *srcSizePtr);
3612 if (ZSTD_isError(headerSize)) return headerSize;
3614 /* not enough input to decode header : tell how many bytes would be necessary */
3615 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
3616 zbc->hPos += *srcSizePtr;
3618 zbc->stage = ZBUFFds_loadHeader;
3619 return headerSize - zbc->hPos;
3621 zbc->stage = ZBUFFds_decodeHeader;
3625 case ZBUFFds_loadHeader:
3626 /* complete header from src */
3627 { size_t headerSize = ZBUFF_limitCopy(
3628 zbc->headerBuffer + zbc->hPos, ZSTD_frameHeaderSize_max - zbc->hPos,
3630 zbc->hPos += headerSize;
3632 headerSize = ZSTD_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
3633 if (ZSTD_isError(headerSize)) return headerSize;
3635 /* not enough input to decode header : tell how many bytes would be necessary */
3637 return headerSize - zbc->hPos;
3639 /* intentional fallthrough */
3641 case ZBUFFds_decodeHeader:
3642 /* apply header to create / resize buffers */
3643 { size_t const neededOutSize = (size_t)1 << zbc->params.windowLog;
3644 size_t const neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */
3645 if (zbc->inBuffSize < neededInSize) {
3647 zbc->inBuffSize = neededInSize;
3648 zbc->inBuff = (char*)malloc(neededInSize);
3649 if (zbc->inBuff == NULL) return ERROR(memory_allocation);
3651 if (zbc->outBuffSize < neededOutSize) {
3653 zbc->outBuffSize = neededOutSize;
3654 zbc->outBuff = (char*)malloc(neededOutSize);
3655 if (zbc->outBuff == NULL) return ERROR(memory_allocation);
3658 ZSTD_decompress_insertDictionary(zbc->zc, zbc->dict, zbc->dictSize);
3660 /* some data already loaded into headerBuffer : transfer into inBuff */
3661 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
3662 zbc->inPos = zbc->hPos;
3664 zbc->stage = ZBUFFds_load;
3667 zbc->stage = ZBUFFds_read;
3671 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3672 if (neededInSize==0) /* end of frame */
3674 zbc->stage = ZBUFFds_init;
3678 if ((size_t)(iend-ip) >= neededInSize)
3680 /* directly decode from src */
3681 size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
3682 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3684 if (ZSTD_isError(decodedSize)) return decodedSize;
3686 if (!decodedSize) break; /* this was just a header */
3687 zbc->outEnd = zbc->outStart + decodedSize;
3688 zbc->stage = ZBUFFds_flush;
3691 if (ip==iend) { notDone = 0; break; } /* no more input */
3692 zbc->stage = ZBUFFds_load;
3697 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3698 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */
3700 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */
3701 loadedSize = ZBUFF_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
3703 zbc->inPos += loadedSize;
3704 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
3706 size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
3707 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3708 zbc->inBuff, neededInSize);
3709 if (ZSTD_isError(decodedSize)) return decodedSize;
3710 zbc->inPos = 0; /* input is consumed */
3711 if (!decodedSize) { zbc->stage = ZBUFFds_read; break; } /* this was just a header */
3712 zbc->outEnd = zbc->outStart + decodedSize;
3713 zbc->stage = ZBUFFds_flush;
3714 /* ZBUFFds_flush follows */
3720 size_t toFlushSize = zbc->outEnd - zbc->outStart;
3721 size_t flushedSize = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
3723 zbc->outStart += flushedSize;
3724 if (flushedSize == toFlushSize)
3726 zbc->stage = ZBUFFds_read;
3727 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
3728 zbc->outStart = zbc->outEnd = 0;
3731 /* cannot flush everything */
3735 default: return ERROR(GENERIC); /* impossible */
3739 *srcSizePtr = ip-istart;
3740 *maxDstSizePtr = op-ostart;
3743 size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3744 if (nextSrcSizeHint > 3) nextSrcSizeHint+= 3; /* get the next block header while at it */
3745 nextSrcSizeHint -= zbc->inPos; /* already loaded*/
3746 return nextSrcSizeHint;
3751 /* *************************************
3753 ***************************************/
3754 unsigned ZBUFFv04_isError(size_t errorCode) { return ERR_isError(errorCode); }
3755 const char* ZBUFFv04_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
3757 size_t ZBUFFv04_recommendedDInSize() { return BLOCKSIZE + 3; }
3758 size_t ZBUFFv04_recommendedDOutSize() { return BLOCKSIZE; }
3762 /*- ========================================================================= -*/
3764 /* final wrapping stage */
3766 size_t ZSTDv04_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3768 return ZSTD_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
3771 size_t ZSTDv04_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3773 #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1)
3775 ZSTD_DCtx* dctx = ZSTD_createDCtx();
3776 if (dctx==NULL) return ERROR(memory_allocation);
3777 regenSize = ZSTDv04_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
3778 ZSTD_freeDCtx(dctx);
3782 return ZSTDv04_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
3786 size_t ZSTDv04_findFrameCompressedSize(const void* src, size_t srcSize)
3788 return ZSTD_findFrameCompressedSize(src, srcSize);
3791 size_t ZSTDv04_resetDCtx(ZSTDv04_Dctx* dctx) { return ZSTD_resetDCtx(dctx); }
3793 size_t ZSTDv04_nextSrcSizeToDecompress(ZSTDv04_Dctx* dctx)
3795 return ZSTD_nextSrcSizeToDecompress(dctx);
3798 size_t ZSTDv04_decompressContinue(ZSTDv04_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3800 return ZSTD_decompressContinue(dctx, dst, maxDstSize, src, srcSize);
3805 ZBUFFv04_DCtx* ZBUFFv04_createDCtx(void) { return ZBUFF_createDCtx(); }
3806 size_t ZBUFFv04_freeDCtx(ZBUFFv04_DCtx* dctx) { return ZBUFF_freeDCtx(dctx); }
3808 size_t ZBUFFv04_decompressInit(ZBUFFv04_DCtx* dctx) { return ZBUFF_decompressInit(dctx); }
3809 size_t ZBUFFv04_decompressWithDictionary(ZBUFFv04_DCtx* dctx, const void* src, size_t srcSize)
3810 { return ZBUFF_decompressWithDictionary(dctx, src, srcSize); }
3812 size_t ZBUFFv04_decompressContinue(ZBUFFv04_DCtx* dctx, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3814 return ZBUFF_decompressContinue(dctx, dst, maxDstSizePtr, src, srcSizePtr);
3817 ZSTD_DCtx* ZSTDv04_createDCtx(void) { return ZSTD_createDCtx(); }
3818 size_t ZSTDv04_freeDCtx(ZSTD_DCtx* dctx) { return ZSTD_freeDCtx(dctx); }
3820 size_t ZSTDv04_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize)
3822 return ZSTD_getFrameParams(params, src, srcSize);