2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
14 #include "error_private.h"
17 /* ******************************************************************
19 low-level memory access routines
20 Copyright (C) 2013-2015, Yann Collet.
22 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
24 Redistribution and use in source and binary forms, with or without
25 modification, are permitted provided that the following conditions are
28 * Redistributions of source code must retain the above copyright
29 notice, this list of conditions and the following disclaimer.
30 * Redistributions in binary form must reproduce the above
31 copyright notice, this list of conditions and the following disclaimer
32 in the documentation and/or other materials provided with the
35 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
38 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
39 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
42 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
43 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
44 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
45 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
47 You can contact the author at :
48 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
49 - Public forum : https://groups.google.com/forum/#!forum/lz4c
50 ****************************************************************** */
54 #if defined (__cplusplus)
58 /*-****************************************
60 ******************************************/
61 #include <stddef.h> /* size_t, ptrdiff_t */
62 #include <string.h> /* memcpy */
65 /*-****************************************
67 ******************************************/
69 # define MEM_STATIC static __attribute__((unused))
70 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
71 # define MEM_STATIC static inline
72 #elif defined(_MSC_VER)
73 # define MEM_STATIC static __inline
75 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
79 /*-**************************************************************
81 *****************************************************************/
82 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
92 typedef unsigned char BYTE;
93 typedef unsigned short U16;
94 typedef signed short S16;
95 typedef unsigned int U32;
96 typedef signed int S32;
97 typedef unsigned long long U64;
98 typedef signed long long S64;
102 /*-**************************************************************
104 *****************************************************************/
105 /* MEM_FORCE_MEMORY_ACCESS :
106 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
107 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
108 * The below switch allow to select different access method for improved performance.
109 * Method 0 (default) : use `memcpy()`. Safe and portable.
110 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
111 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
112 * Method 2 : direct access. This method is portable but violate C standard.
113 * It can generate buggy code on targets depending on alignment.
114 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
115 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
116 * Prefer these methods in priority order (0 > 1 > 2)
118 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
119 # 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__) )
120 # define MEM_FORCE_MEMORY_ACCESS 2
121 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
122 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
123 # define MEM_FORCE_MEMORY_ACCESS 1
127 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
128 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
130 MEM_STATIC unsigned MEM_isLittleEndian(void)
132 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
136 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
138 /* violates C standard, by lying on structure alignment.
139 Only use if no other choice to achieve best performance on target platform */
140 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
141 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
142 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
144 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
145 MEM_STATIC void MEM_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
146 MEM_STATIC void MEM_write64(void* memPtr, U64 value) { *(U64*)memPtr = value; }
148 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
150 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
151 /* currently only defined for gcc and icc */
152 typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign;
154 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
155 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
156 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
158 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
159 MEM_STATIC void MEM_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }
160 MEM_STATIC void MEM_write64(void* memPtr, U64 value) { ((unalign*)memPtr)->u64 = value; }
164 /* default method, safe and standard.
165 can sometimes prove slower */
167 MEM_STATIC U16 MEM_read16(const void* memPtr)
169 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
172 MEM_STATIC U32 MEM_read32(const void* memPtr)
174 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
177 MEM_STATIC U64 MEM_read64(const void* memPtr)
179 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
182 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
184 memcpy(memPtr, &value, sizeof(value));
187 MEM_STATIC void MEM_write32(void* memPtr, U32 value)
189 memcpy(memPtr, &value, sizeof(value));
192 MEM_STATIC void MEM_write64(void* memPtr, U64 value)
194 memcpy(memPtr, &value, sizeof(value));
197 #endif /* MEM_FORCE_MEMORY_ACCESS */
200 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
202 if (MEM_isLittleEndian())
203 return MEM_read16(memPtr);
205 const BYTE* p = (const BYTE*)memPtr;
206 return (U16)(p[0] + (p[1]<<8));
210 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
212 if (MEM_isLittleEndian()) {
213 MEM_write16(memPtr, val);
215 BYTE* p = (BYTE*)memPtr;
217 p[1] = (BYTE)(val>>8);
221 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
223 if (MEM_isLittleEndian())
224 return MEM_read32(memPtr);
226 const BYTE* p = (const BYTE*)memPtr;
227 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
232 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
234 if (MEM_isLittleEndian())
235 return MEM_read64(memPtr);
237 const BYTE* p = (const BYTE*)memPtr;
238 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
239 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
244 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
247 return (size_t)MEM_readLE32(memPtr);
249 return (size_t)MEM_readLE64(memPtr);
253 #if defined (__cplusplus)
257 #endif /* MEM_H_MODULE */
260 zstd - standard compression library
261 Header File for static linking only
262 Copyright (C) 2014-2016, Yann Collet.
264 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
266 Redistribution and use in source and binary forms, with or without
267 modification, are permitted provided that the following conditions are
269 * Redistributions of source code must retain the above copyright
270 notice, this list of conditions and the following disclaimer.
271 * Redistributions in binary form must reproduce the above
272 copyright notice, this list of conditions and the following disclaimer
273 in the documentation and/or other materials provided with the
275 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
276 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
277 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
278 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
279 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
280 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
281 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
282 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
283 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
284 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
285 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
287 You can contact the author at :
288 - zstd homepage : http://www.zstd.net
290 #ifndef ZSTD_STATIC_H
291 #define ZSTD_STATIC_H
293 /* The prototypes defined within this file are considered experimental.
294 * They should not be used in the context DLL as they may change in the future.
295 * Prefer static linking if you need them, to control breaking version changes issues.
298 #if defined (__cplusplus)
304 /*-*************************************
306 ***************************************/
307 #define ZSTDv05_WINDOWLOG_ABSOLUTEMIN 11
310 /*-*************************************
312 ***************************************/
313 /*- Advanced Decompression functions -*/
315 /*! ZSTDv05_decompress_usingPreparedDCtx() :
316 * Same as ZSTDv05_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
317 * It avoids reloading the dictionary each time.
318 * `preparedDCtx` must have been properly initialized using ZSTDv05_decompressBegin_usingDict().
319 * Requires 2 contexts : 1 for reference, which will not be modified, and 1 to run the decompression operation */
320 size_t ZSTDv05_decompress_usingPreparedDCtx(
321 ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* preparedDCtx,
322 void* dst, size_t dstCapacity,
323 const void* src, size_t srcSize);
326 /* **************************************
327 * Streaming functions (direct mode)
328 ****************************************/
329 size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx);
332 Streaming decompression, direct mode (bufferless)
334 A ZSTDv05_DCtx object is required to track streaming operations.
335 Use ZSTDv05_createDCtx() / ZSTDv05_freeDCtx() to manage it.
336 A ZSTDv05_DCtx object can be re-used multiple times.
338 First typical operation is to retrieve frame parameters, using ZSTDv05_getFrameParams().
339 This operation is independent, and just needs enough input data to properly decode the frame header.
340 Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.
341 Result : 0 when successful, it means the ZSTDv05_parameters structure has been filled.
342 >0 : means there is not enough data into src. Provides the expected size to successfully decode header.
343 errorCode, which can be tested using ZSTDv05_isError()
345 Start decompression, with ZSTDv05_decompressBegin() or ZSTDv05_decompressBegin_usingDict()
346 Alternatively, you can copy a prepared context, using ZSTDv05_copyDCtx()
348 Then use ZSTDv05_nextSrcSizeToDecompress() and ZSTDv05_decompressContinue() alternatively.
349 ZSTDv05_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv05_decompressContinue().
350 ZSTDv05_decompressContinue() requires this exact amount of bytes, or it will fail.
351 ZSTDv05_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
352 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
354 @result of ZSTDv05_decompressContinue() is the number of bytes regenerated within 'dst'.
355 It can be zero, which is not an error; it just means ZSTDv05_decompressContinue() has decoded some header.
357 A frame is fully decoded when ZSTDv05_nextSrcSizeToDecompress() returns zero.
358 Context can then be reset to start a new decompression.
362 /* **************************************
364 ****************************************/
365 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
366 User will have to take in charge required information to regenerate data, such as block sizes.
368 A few rules to respect :
369 - Uncompressed block size must be <= 128 KB
370 - Compressing or decompressing requires a context structure
371 + Use ZSTDv05_createCCtx() and ZSTDv05_createDCtx()
372 - It is necessary to init context before starting
373 + compression : ZSTDv05_compressBegin()
374 + decompression : ZSTDv05_decompressBegin()
375 + variants _usingDict() are also allowed
376 + copyCCtx() and copyDCtx() work too
377 - When a block is considered not compressible enough, ZSTDv05_compressBlock() result will be zero.
378 In which case, nothing is produced into `dst`.
379 + User must test for such outcome and deal directly with uncompressed data
380 + ZSTDv05_decompressBlock() doesn't accept uncompressed data as input !!
383 size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
388 #if defined (__cplusplus)
392 #endif /* ZSTDv05_STATIC_H */
396 zstd_internal - common functions to include
397 Header File for include
398 Copyright (C) 2014-2016, Yann Collet.
400 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
402 Redistribution and use in source and binary forms, with or without
403 modification, are permitted provided that the following conditions are
405 * Redistributions of source code must retain the above copyright
406 notice, this list of conditions and the following disclaimer.
407 * Redistributions in binary form must reproduce the above
408 copyright notice, this list of conditions and the following disclaimer
409 in the documentation and/or other materials provided with the
411 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
412 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
413 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
414 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
415 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
416 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
417 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
418 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
419 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
420 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
421 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
423 You can contact the author at :
424 - zstd source repository : https://github.com/Cyan4973/zstd
426 #ifndef ZSTD_CCOMMON_H_MODULE
427 #define ZSTD_CCOMMON_H_MODULE
431 /*-*************************************
433 ***************************************/
434 #define MIN(a,b) ((a)<(b) ? (a) : (b))
435 #define MAX(a,b) ((a)>(b) ? (a) : (b))
438 /*-*************************************
440 ***************************************/
441 #define ZSTDv05_DICT_MAGIC 0xEC30A435
447 #define BLOCKSIZE (128 KB) /* define, for static allocation */
449 static const size_t ZSTDv05_blockHeaderSize = 3;
450 static const size_t ZSTDv05_frameHeaderSize_min = 5;
451 #define ZSTDv05_frameHeaderSize_max 5 /* define, for static allocation */
466 #define REPCODE_STARTVALUE 1
472 #define MaxLit ((1<<Litbits) - 1)
473 #define MaxML ((1<<MLbits) - 1)
474 #define MaxLL ((1<<LLbits) - 1)
475 #define MaxOff ((1<<Offbits)- 1)
476 #define MLFSEv05Log 10
477 #define LLFSEv05Log 10
478 #define OffFSEv05Log 9
479 #define MaxSeq MAX(MaxLL, MaxML)
481 #define FSEv05_ENCODING_RAW 0
482 #define FSEv05_ENCODING_RLE 1
483 #define FSEv05_ENCODING_STATIC 2
484 #define FSEv05_ENCODING_DYNAMIC 3
489 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
490 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
492 #define WILDCOPY_OVERLENGTH 8
494 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
496 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
499 /*-*******************************************
500 * Shared functions to include for inlining
501 *********************************************/
502 static void ZSTDv05_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
504 #define COPY8(d,s) { ZSTDv05_copy8(d,s); d+=8; s+=8; }
506 /*! ZSTDv05_wildcopy() :
507 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
508 MEM_STATIC void ZSTDv05_wildcopy(void* dst, const void* src, ptrdiff_t length)
510 const BYTE* ip = (const BYTE*)src;
511 BYTE* op = (BYTE*)dst;
512 BYTE* const oend = op + length;
519 /*-*******************************************
521 *********************************************/
530 BYTE* litLengthStart;
532 BYTE* matchLengthStart;
537 U32* matchLengthFreq;
549 #endif /* ZSTDv05_CCOMMON_H_MODULE */
550 /* ******************************************************************
551 FSEv05 : Finite State Entropy coder
553 Copyright (C) 2013-2015, Yann Collet.
555 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
557 Redistribution and use in source and binary forms, with or without
558 modification, are permitted provided that the following conditions are
561 * Redistributions of source code must retain the above copyright
562 notice, this list of conditions and the following disclaimer.
563 * Redistributions in binary form must reproduce the above
564 copyright notice, this list of conditions and the following disclaimer
565 in the documentation and/or other materials provided with the
568 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
569 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
570 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
571 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
572 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
573 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
574 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
575 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
576 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
577 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
578 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
580 You can contact the author at :
581 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
582 - Public forum : https://groups.google.com/forum/#!forum/lz4c
583 ****************************************************************** */
587 #if defined (__cplusplus)
592 /* *****************************************
594 ******************************************/
595 #include <stddef.h> /* size_t, ptrdiff_t */
598 /*-****************************************
599 * FSEv05 simple functions
600 ******************************************/
601 size_t FSEv05_decompress(void* dst, size_t maxDstSize,
602 const void* cSrc, size_t cSrcSize);
605 Decompress FSEv05 data from buffer 'cSrc', of size 'cSrcSize',
606 into already allocated destination buffer 'dst', of size 'maxDstSize'.
607 return : size of regenerated data (<= maxDstSize)
608 or an error code, which can be tested using FSEv05_isError()
610 ** Important ** : FSEv05_decompress() doesn't decompress non-compressible nor RLE data !!!
611 Why ? : making this distinction requires a header.
612 Header management is intentionally delegated to the user layer, which can better manage special cases.
616 /* *****************************************
618 ******************************************/
619 /* Error Management */
620 unsigned FSEv05_isError(size_t code); /* tells if a return value is an error code */
621 const char* FSEv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
626 /* *****************************************
627 * FSEv05 detailed API
628 ******************************************/
629 /* *** DECOMPRESSION *** */
633 Read compactly saved 'normalizedCounter' from 'rBuffer'.
634 return : size read from 'rBuffer'
635 or an errorCode, which can be tested using FSEv05_isError()
636 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
637 size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
640 Constructor and Destructor of type FSEv05_DTable
641 Note that its size depends on 'tableLog' */
642 typedef unsigned FSEv05_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
643 FSEv05_DTable* FSEv05_createDTable(unsigned tableLog);
644 void FSEv05_freeDTable(FSEv05_DTable* dt);
647 FSEv05_buildDTable():
648 Builds 'dt', which must be already allocated, using FSEv05_createDTable()
650 or an errorCode, which can be tested using FSEv05_isError() */
651 size_t FSEv05_buildDTable (FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
654 FSEv05_decompress_usingDTable():
655 Decompress compressed source @cSrc of size @cSrcSize using `dt`
656 into `dst` which must be already allocated.
657 @return : size of regenerated data (necessarily <= @dstCapacity)
658 or an errorCode, which can be tested using FSEv05_isError() */
659 size_t FSEv05_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv05_DTable* dt);
663 #if defined (__cplusplus)
667 #endif /* FSEv05_H */
668 /* ******************************************************************
670 Part of FSEv05 library
671 header file (to include)
672 Copyright (C) 2013-2016, 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 ****************************************************************** */
702 #ifndef BITv05STREAM_H_MODULE
703 #define BITv05STREAM_H_MODULE
705 #if defined (__cplusplus)
711 * This API consists of small unitary functions, which highly benefit from being inlined.
712 * Since link-time-optimization is not available for all compilers,
713 * these functions are defined into a .h to be included.
718 /*-********************************************
719 * bitStream decoding API (read backward)
720 **********************************************/
724 unsigned bitsConsumed;
729 typedef enum { BITv05_DStream_unfinished = 0,
730 BITv05_DStream_endOfBuffer = 1,
731 BITv05_DStream_completed = 2,
732 BITv05_DStream_overflow = 3 } BITv05_DStream_status; /* result of BITv05_reloadDStream() */
733 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
735 MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
736 MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits);
737 MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD);
738 MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* bitD);
741 /*-****************************************
743 ******************************************/
744 MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, unsigned nbBits);
745 /* faster, but works only if nbBits >= 1 */
749 /*-**************************************************************
751 ****************************************************************/
752 MEM_STATIC unsigned BITv05_highbit32 (U32 val)
754 # if defined(_MSC_VER) /* Visual */
756 _BitScanReverse ( &r, val );
758 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
759 return 31 - __builtin_clz (val);
760 # else /* Software version */
761 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 };
769 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
776 /*-********************************************************
778 **********************************************************/
779 /*!BITv05_initDStream
780 * Initialize a BITv05_DStream_t.
781 * @bitD : a pointer to an already allocated BITv05_DStream_t structure
782 * @srcBuffer must point at the beginning of a bitStream
783 * @srcSize must be the exact size of the bitStream
784 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
786 MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
788 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
790 if (srcSize >= sizeof(size_t)) { /* normal case */
792 bitD->start = (const char*)srcBuffer;
793 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
794 bitD->bitContainer = MEM_readLEST(bitD->ptr);
795 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
796 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
797 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
800 bitD->start = (const char*)srcBuffer;
801 bitD->ptr = bitD->start;
802 bitD->bitContainer = *(const BYTE*)(bitD->start);
805 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
806 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
807 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
808 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
809 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
810 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */
813 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
814 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
815 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
816 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
822 MEM_STATIC size_t BITv05_lookBits(BITv05_DStream_t* bitD, U32 nbBits)
824 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
825 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
828 /*! BITv05_lookBitsFast :
829 * unsafe version; only works only if nbBits >= 1 */
830 MEM_STATIC size_t BITv05_lookBitsFast(BITv05_DStream_t* bitD, U32 nbBits)
832 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
833 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
836 MEM_STATIC void BITv05_skipBits(BITv05_DStream_t* bitD, U32 nbBits)
838 bitD->bitsConsumed += nbBits;
841 MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits)
843 size_t value = BITv05_lookBits(bitD, nbBits);
844 BITv05_skipBits(bitD, nbBits);
848 /*!BITv05_readBitsFast :
849 * unsafe version; only works only if nbBits >= 1 */
850 MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, unsigned nbBits)
852 size_t value = BITv05_lookBitsFast(bitD, nbBits);
853 BITv05_skipBits(bitD, nbBits);
857 MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD)
859 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
860 return BITv05_DStream_overflow;
862 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
863 bitD->ptr -= bitD->bitsConsumed >> 3;
864 bitD->bitsConsumed &= 7;
865 bitD->bitContainer = MEM_readLEST(bitD->ptr);
866 return BITv05_DStream_unfinished;
868 if (bitD->ptr == bitD->start) {
869 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv05_DStream_endOfBuffer;
870 return BITv05_DStream_completed;
873 U32 nbBytes = bitD->bitsConsumed >> 3;
874 BITv05_DStream_status result = BITv05_DStream_unfinished;
875 if (bitD->ptr - nbBytes < bitD->start) {
876 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
877 result = BITv05_DStream_endOfBuffer;
879 bitD->ptr -= nbBytes;
880 bitD->bitsConsumed -= nbBytes*8;
881 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
886 /*! BITv05_endOfDStream
887 * @return Tells if DStream has reached its exact end
889 MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* DStream)
891 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
894 #if defined (__cplusplus)
898 #endif /* BITv05STREAM_H_MODULE */
899 /* ******************************************************************
900 FSEv05 : Finite State Entropy coder
901 header file for static linking (only)
902 Copyright (C) 2013-2015, Yann Collet
904 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
906 Redistribution and use in source and binary forms, with or without
907 modification, are permitted provided that the following conditions are
910 * Redistributions of source code must retain the above copyright
911 notice, this list of conditions and the following disclaimer.
912 * Redistributions in binary form must reproduce the above
913 copyright notice, this list of conditions and the following disclaimer
914 in the documentation and/or other materials provided with the
917 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
918 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
919 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
920 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
921 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
922 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
923 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
924 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
925 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
926 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
927 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
929 You can contact the author at :
930 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
931 - Public forum : https://groups.google.com/forum/#!forum/lz4c
932 ****************************************************************** */
933 #ifndef FSEv05_STATIC_H
934 #define FSEv05_STATIC_H
936 #if defined (__cplusplus)
942 /* *****************************************
944 *******************************************/
945 /* It is possible to statically allocate FSEv05 CTable/DTable as a table of unsigned using below macros */
946 #define FSEv05_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
949 /* *****************************************
950 * FSEv05 advanced API
951 *******************************************/
952 size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits);
953 /* build a fake FSEv05_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
955 size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, unsigned char symbolValue);
956 /* build a fake FSEv05_DTable, designed to always generate the same symbolValue */
960 /* *****************************************
961 * FSEv05 symbol decompression API
962 *******************************************/
966 const void* table; /* precise table may vary, depending on U16 */
970 static void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt);
972 static unsigned char FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
974 static unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr);
978 /* *****************************************
980 *******************************************/
981 static unsigned char FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
982 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
985 /* *****************************************
986 * Implementation of inlined functions
987 *******************************************/
993 } FSEv05_DTableHeader; /* sizeof U32 */
997 unsigned short newState;
998 unsigned char symbol;
999 unsigned char nbBits;
1000 } FSEv05_decode_t; /* size == U32 */
1002 MEM_STATIC void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt)
1004 const void* ptr = dt;
1005 const FSEv05_DTableHeader* const DTableH = (const FSEv05_DTableHeader*)ptr;
1006 DStatePtr->state = BITv05_readBits(bitD, DTableH->tableLog);
1007 BITv05_reloadDStream(bitD);
1008 DStatePtr->table = dt + 1;
1011 MEM_STATIC BYTE FSEv05_peakSymbol(FSEv05_DState_t* DStatePtr)
1013 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1014 return DInfo.symbol;
1017 MEM_STATIC BYTE FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
1019 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1020 const U32 nbBits = DInfo.nbBits;
1021 BYTE symbol = DInfo.symbol;
1022 size_t lowBits = BITv05_readBits(bitD, nbBits);
1024 DStatePtr->state = DInfo.newState + lowBits;
1028 MEM_STATIC BYTE FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
1030 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1031 const U32 nbBits = DInfo.nbBits;
1032 BYTE symbol = DInfo.symbol;
1033 size_t lowBits = BITv05_readBitsFast(bitD, nbBits);
1035 DStatePtr->state = DInfo.newState + lowBits;
1039 MEM_STATIC unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr)
1041 return DStatePtr->state == 0;
1045 #if defined (__cplusplus)
1049 #endif /* FSEv05_STATIC_H */
1050 /* ******************************************************************
1051 FSEv05 : Finite State Entropy coder
1052 Copyright (C) 2013-2015, Yann Collet.
1054 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1056 Redistribution and use in source and binary forms, with or without
1057 modification, are permitted provided that the following conditions are
1060 * Redistributions of source code must retain the above copyright
1061 notice, this list of conditions and the following disclaimer.
1062 * Redistributions in binary form must reproduce the above
1063 copyright notice, this list of conditions and the following disclaimer
1064 in the documentation and/or other materials provided with the
1067 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1068 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1069 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1070 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1071 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1072 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1073 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1074 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1075 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1076 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1077 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1079 You can contact the author at :
1080 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1081 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1082 ****************************************************************** */
1084 #ifndef FSEv05_COMMONDEFS_ONLY
1086 /* **************************************************************
1088 ****************************************************************/
1090 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1091 * Increasing memory usage improves compression ratio
1092 * Reduced memory usage can improve speed, due to cache effect
1093 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1094 #define FSEv05_MAX_MEMORY_USAGE 14
1095 #define FSEv05_DEFAULT_MEMORY_USAGE 13
1097 /*!FSEv05_MAX_SYMBOL_VALUE :
1098 * Maximum symbol value authorized.
1099 * Required for proper stack allocation */
1100 #define FSEv05_MAX_SYMBOL_VALUE 255
1103 /* **************************************************************
1104 * template functions type & suffix
1105 ****************************************************************/
1106 #define FSEv05_FUNCTION_TYPE BYTE
1107 #define FSEv05_FUNCTION_EXTENSION
1108 #define FSEv05_DECODE_TYPE FSEv05_decode_t
1111 #endif /* !FSEv05_COMMONDEFS_ONLY */
1113 /* **************************************************************
1114 * Compiler specifics
1115 ****************************************************************/
1116 #ifdef _MSC_VER /* Visual Studio */
1117 # define FORCE_INLINE static __forceinline
1118 # include <intrin.h> /* For Visual 2005 */
1119 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1120 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1122 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1124 # define FORCE_INLINE static inline __attribute__((always_inline))
1126 # define FORCE_INLINE static inline
1129 # define FORCE_INLINE static
1130 # endif /* __STDC_VERSION__ */
1134 /* **************************************************************
1136 ****************************************************************/
1137 #include <stdlib.h> /* malloc, free, qsort */
1138 #include <string.h> /* memcpy, memset */
1139 #include <stdio.h> /* printf (debug) */
1143 /* ***************************************************************
1145 *****************************************************************/
1146 #define FSEv05_MAX_TABLELOG (FSEv05_MAX_MEMORY_USAGE-2)
1147 #define FSEv05_MAX_TABLESIZE (1U<<FSEv05_MAX_TABLELOG)
1148 #define FSEv05_MAXTABLESIZE_MASK (FSEv05_MAX_TABLESIZE-1)
1149 #define FSEv05_DEFAULT_TABLELOG (FSEv05_DEFAULT_MEMORY_USAGE-2)
1150 #define FSEv05_MIN_TABLELOG 5
1152 #define FSEv05_TABLELOG_ABSOLUTE_MAX 15
1153 #if FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX
1154 #error "FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX is not supported"
1158 /* **************************************************************
1160 ****************************************************************/
1161 #define FSEv05_STATIC_ASSERT(c) { enum { FSEv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1164 /* **************************************************************
1166 ****************************************************************/
1167 typedef unsigned DTable_max_t[FSEv05_DTABLE_SIZE_U32(FSEv05_MAX_TABLELOG)];
1170 /* **************************************************************
1172 ****************************************************************/
1174 designed to be included
1175 for type-specific functions (template emulation in C)
1176 Objective is to write these functions only once, for improved maintenance
1180 #ifndef FSEv05_FUNCTION_EXTENSION
1181 # error "FSEv05_FUNCTION_EXTENSION must be defined"
1183 #ifndef FSEv05_FUNCTION_TYPE
1184 # error "FSEv05_FUNCTION_TYPE must be defined"
1187 /* Function names */
1188 #define FSEv05_CAT(X,Y) X##Y
1189 #define FSEv05_FUNCTION_NAME(X,Y) FSEv05_CAT(X,Y)
1190 #define FSEv05_TYPE_NAME(X,Y) FSEv05_CAT(X,Y)
1193 /* Function templates */
1194 static U32 FSEv05_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1198 FSEv05_DTable* FSEv05_createDTable (unsigned tableLog)
1200 if (tableLog > FSEv05_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv05_TABLELOG_ABSOLUTE_MAX;
1201 return (FSEv05_DTable*)malloc( FSEv05_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1204 void FSEv05_freeDTable (FSEv05_DTable* dt)
1209 size_t FSEv05_buildDTable(FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1211 FSEv05_DTableHeader DTableH;
1212 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */
1213 FSEv05_DECODE_TYPE* const tableDecode = (FSEv05_DECODE_TYPE*) (tdPtr);
1214 const U32 tableSize = 1 << tableLog;
1215 const U32 tableMask = tableSize-1;
1216 const U32 step = FSEv05_tableStep(tableSize);
1217 U16 symbolNext[FSEv05_MAX_SYMBOL_VALUE+1];
1219 U32 highThreshold = tableSize-1;
1220 const S16 largeLimit= (S16)(1 << (tableLog-1));
1225 if (maxSymbolValue > FSEv05_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1226 if (tableLog > FSEv05_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1228 /* Init, lay down lowprob symbols */
1229 memset(tableDecode, 0, sizeof(FSEv05_FUNCTION_TYPE) * (maxSymbolValue+1) ); /* useless init, but keep static analyzer happy, and we don't need to performance optimize legacy decoders */
1230 DTableH.tableLog = (U16)tableLog;
1231 for (s=0; s<=maxSymbolValue; s++) {
1232 if (normalizedCounter[s]==-1) {
1233 tableDecode[highThreshold--].symbol = (FSEv05_FUNCTION_TYPE)s;
1236 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1237 symbolNext[s] = normalizedCounter[s];
1240 /* Spread symbols */
1241 for (s=0; s<=maxSymbolValue; s++) {
1243 for (i=0; i<normalizedCounter[s]; i++) {
1244 tableDecode[position].symbol = (FSEv05_FUNCTION_TYPE)s;
1245 position = (position + step) & tableMask;
1246 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1249 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1251 /* Build Decoding table */
1254 for (i=0; i<tableSize; i++) {
1255 FSEv05_FUNCTION_TYPE symbol = (FSEv05_FUNCTION_TYPE)(tableDecode[i].symbol);
1256 U16 nextState = symbolNext[symbol]++;
1257 tableDecode[i].nbBits = (BYTE) (tableLog - BITv05_highbit32 ((U32)nextState) );
1258 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1261 DTableH.fastMode = (U16)noLarge;
1262 memcpy(dt, &DTableH, sizeof(DTableH));
1267 #ifndef FSEv05_COMMONDEFS_ONLY
1268 /*-****************************************
1269 * FSEv05 helper functions
1270 ******************************************/
1271 unsigned FSEv05_isError(size_t code) { return ERR_isError(code); }
1273 const char* FSEv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1276 /*-**************************************************************
1277 * FSEv05 NCount encoding-decoding
1278 ****************************************************************/
1279 static short FSEv05_abs(short a) { return a<0 ? -a : a; }
1282 size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1283 const void* headerBuffer, size_t hbSize)
1285 const BYTE* const istart = (const BYTE*) headerBuffer;
1286 const BYTE* const iend = istart + hbSize;
1287 const BYTE* ip = istart;
1293 unsigned charnum = 0;
1296 if (hbSize < 4) return ERROR(srcSize_wrong);
1297 bitStream = MEM_readLE32(ip);
1298 nbBits = (bitStream & 0xF) + FSEv05_MIN_TABLELOG; /* extract tableLog */
1299 if (nbBits > FSEv05_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1302 *tableLogPtr = nbBits;
1303 remaining = (1<<nbBits)+1;
1304 threshold = 1<<nbBits;
1307 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1309 unsigned n0 = charnum;
1310 while ((bitStream & 0xFFFF) == 0xFFFF) {
1314 bitStream = MEM_readLE32(ip) >> bitCount;
1319 while ((bitStream & 3) == 3) {
1324 n0 += bitStream & 3;
1326 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1327 while (charnum < n0) normalizedCounter[charnum++] = 0;
1328 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1331 bitStream = MEM_readLE32(ip) >> bitCount;
1337 const short max = (short)((2*threshold-1)-remaining);
1340 if ((bitStream & (threshold-1)) < (U32)max) {
1341 count = (short)(bitStream & (threshold-1));
1342 bitCount += nbBits-1;
1344 count = (short)(bitStream & (2*threshold-1));
1345 if (count >= threshold) count -= max;
1349 count--; /* extra accuracy */
1350 remaining -= FSEv05_abs(count);
1351 normalizedCounter[charnum++] = count;
1353 while (remaining < threshold) {
1358 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1362 bitCount -= (int)(8 * (iend - 4 - ip));
1365 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1367 if (remaining != 1) return ERROR(GENERIC);
1368 *maxSVPtr = charnum-1;
1370 ip += (bitCount+7)>>3;
1371 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1377 /*-*******************************************************
1378 * Decompression (Byte symbols)
1379 *********************************************************/
1380 size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, BYTE symbolValue)
1383 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1384 void* dPtr = dt + 1;
1385 FSEv05_decode_t* const cell = (FSEv05_decode_t*)dPtr;
1387 DTableH->tableLog = 0;
1388 DTableH->fastMode = 0;
1391 cell->symbol = symbolValue;
1398 size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits)
1401 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1402 void* dPtr = dt + 1;
1403 FSEv05_decode_t* const dinfo = (FSEv05_decode_t*)dPtr;
1404 const unsigned tableSize = 1 << nbBits;
1405 const unsigned tableMask = tableSize - 1;
1406 const unsigned maxSymbolValue = tableMask;
1410 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1412 /* Build Decoding Table */
1413 DTableH->tableLog = (U16)nbBits;
1414 DTableH->fastMode = 1;
1415 for (s=0; s<=maxSymbolValue; s++) {
1416 dinfo[s].newState = 0;
1417 dinfo[s].symbol = (BYTE)s;
1418 dinfo[s].nbBits = (BYTE)nbBits;
1424 FORCE_INLINE size_t FSEv05_decompress_usingDTable_generic(
1425 void* dst, size_t maxDstSize,
1426 const void* cSrc, size_t cSrcSize,
1427 const FSEv05_DTable* dt, const unsigned fast)
1429 BYTE* const ostart = (BYTE*) dst;
1431 BYTE* const omax = op + maxDstSize;
1432 BYTE* const olimit = omax-3;
1434 BITv05_DStream_t bitD;
1435 FSEv05_DState_t state1;
1436 FSEv05_DState_t state2;
1440 errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1441 if (FSEv05_isError(errorCode)) return errorCode;
1443 FSEv05_initDState(&state1, &bitD, dt);
1444 FSEv05_initDState(&state2, &bitD, dt);
1446 #define FSEv05_GETSYMBOL(statePtr) fast ? FSEv05_decodeSymbolFast(statePtr, &bitD) : FSEv05_decodeSymbol(statePtr, &bitD)
1448 /* 4 symbols per loop */
1449 for ( ; (BITv05_reloadDStream(&bitD)==BITv05_DStream_unfinished) && (op<olimit) ; op+=4) {
1450 op[0] = FSEv05_GETSYMBOL(&state1);
1452 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1453 BITv05_reloadDStream(&bitD);
1455 op[1] = FSEv05_GETSYMBOL(&state2);
1457 if (FSEv05_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1458 { if (BITv05_reloadDStream(&bitD) > BITv05_DStream_unfinished) { op+=2; break; } }
1460 op[2] = FSEv05_GETSYMBOL(&state1);
1462 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1463 BITv05_reloadDStream(&bitD);
1465 op[3] = FSEv05_GETSYMBOL(&state2);
1469 /* note : BITv05_reloadDStream(&bitD) >= FSEv05_DStream_partiallyFilled; Ends at exactly BITv05_DStream_completed */
1471 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state1))) )
1474 *op++ = FSEv05_GETSYMBOL(&state1);
1476 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state2))) )
1479 *op++ = FSEv05_GETSYMBOL(&state2);
1483 if (BITv05_endOfDStream(&bitD) && FSEv05_endOfDState(&state1) && FSEv05_endOfDState(&state2))
1486 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1488 return ERROR(corruption_detected);
1492 size_t FSEv05_decompress_usingDTable(void* dst, size_t originalSize,
1493 const void* cSrc, size_t cSrcSize,
1494 const FSEv05_DTable* dt)
1496 const void* ptr = dt;
1497 const FSEv05_DTableHeader* DTableH = (const FSEv05_DTableHeader*)ptr;
1498 const U32 fastMode = DTableH->fastMode;
1500 /* select fast mode (static) */
1501 if (fastMode) return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1502 return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1506 size_t FSEv05_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1508 const BYTE* const istart = (const BYTE*)cSrc;
1509 const BYTE* ip = istart;
1510 short counting[FSEv05_MAX_SYMBOL_VALUE+1];
1511 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1513 unsigned maxSymbolValue = FSEv05_MAX_SYMBOL_VALUE;
1516 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1518 /* normal FSEv05 decoding mode */
1519 errorCode = FSEv05_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1520 if (FSEv05_isError(errorCode)) return errorCode;
1521 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1523 cSrcSize -= errorCode;
1525 errorCode = FSEv05_buildDTable (dt, counting, maxSymbolValue, tableLog);
1526 if (FSEv05_isError(errorCode)) return errorCode;
1528 /* always return, even if it is an error code */
1529 return FSEv05_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1534 #endif /* FSEv05_COMMONDEFS_ONLY */
1535 /* ******************************************************************
1536 Huff0 : Huffman coder, part of New Generation Entropy library
1538 Copyright (C) 2013-2016, Yann Collet.
1540 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1542 Redistribution and use in source and binary forms, with or without
1543 modification, are permitted provided that the following conditions are
1546 * Redistributions of source code must retain the above copyright
1547 notice, this list of conditions and the following disclaimer.
1548 * Redistributions in binary form must reproduce the above
1549 copyright notice, this list of conditions and the following disclaimer
1550 in the documentation and/or other materials provided with the
1553 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1554 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1555 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1556 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1557 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1558 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1559 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1560 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1561 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1562 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1563 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1565 You can contact the author at :
1566 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1567 ****************************************************************** */
1571 #if defined (__cplusplus)
1577 /* ****************************************
1578 * Huff0 simple functions
1579 ******************************************/
1580 size_t HUFv05_decompress(void* dst, size_t dstSize,
1581 const void* cSrc, size_t cSrcSize);
1583 HUFv05_decompress():
1584 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1585 into already allocated destination buffer 'dst', of size 'dstSize'.
1586 @dstSize : must be the **exact** size of original (uncompressed) data.
1587 Note : in contrast with FSEv05, HUFv05_decompress can regenerate
1588 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1589 because it knows size to regenerate.
1590 @return : size of regenerated data (== dstSize)
1591 or an error code, which can be tested using HUFv05_isError()
1595 /* ****************************************
1597 ******************************************/
1598 /* Error Management */
1599 unsigned HUFv05_isError(size_t code); /* tells if a return value is an error code */
1600 const char* HUFv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
1603 #if defined (__cplusplus)
1608 /* ******************************************************************
1609 Huff0 : Huffman codec, part of New Generation Entropy library
1610 header file, for static linking only
1611 Copyright (C) 2013-2016, Yann Collet
1613 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1615 Redistribution and use in source and binary forms, with or without
1616 modification, are permitted provided that the following conditions are
1619 * Redistributions of source code must retain the above copyright
1620 notice, this list of conditions and the following disclaimer.
1621 * Redistributions in binary form must reproduce the above
1622 copyright notice, this list of conditions and the following disclaimer
1623 in the documentation and/or other materials provided with the
1626 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1627 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1628 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1629 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1630 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1631 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1632 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1633 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1634 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1635 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1636 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1638 You can contact the author at :
1639 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1640 ****************************************************************** */
1641 #ifndef HUF0_STATIC_H
1642 #define HUF0_STATIC_H
1644 #if defined (__cplusplus)
1650 /* ****************************************
1652 ******************************************/
1653 /* static allocation of Huff0's DTable */
1654 #define HUFv05_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1655 #define HUFv05_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1656 unsigned short DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1657 #define HUFv05_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1658 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1659 #define HUFv05_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1660 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1663 /* ****************************************
1664 * Advanced decompression functions
1665 ******************************************/
1666 size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1667 size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1670 /* ****************************************
1671 * Huff0 detailed API
1672 ******************************************/
1674 HUFv05_decompress() does the following:
1675 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1676 2. build Huffman table from save, using HUFv05_readDTableXn()
1677 3. decode 1 or 4 segments in parallel using HUFv05_decompressSXn_usingDTable
1679 size_t HUFv05_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1680 size_t HUFv05_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1682 size_t HUFv05_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1683 size_t HUFv05_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1686 /* single stream variants */
1688 size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1689 size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1691 size_t HUFv05_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1692 size_t HUFv05_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1696 #if defined (__cplusplus)
1700 #endif /* HUF0_STATIC_H */
1701 /* ******************************************************************
1702 Huff0 : Huffman coder, part of New Generation Entropy library
1703 Copyright (C) 2013-2015, Yann Collet.
1705 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1707 Redistribution and use in source and binary forms, with or without
1708 modification, are permitted provided that the following conditions are
1711 * Redistributions of source code must retain the above copyright
1712 notice, this list of conditions and the following disclaimer.
1713 * Redistributions in binary form must reproduce the above
1714 copyright notice, this list of conditions and the following disclaimer
1715 in the documentation and/or other materials provided with the
1718 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1719 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1720 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1721 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1722 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1723 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1724 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1725 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1726 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1727 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1728 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1730 You can contact the author at :
1731 - FSEv05+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1732 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1733 ****************************************************************** */
1735 /* **************************************************************
1736 * Compiler specifics
1737 ****************************************************************/
1738 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1739 /* inline is defined */
1740 #elif defined(_MSC_VER)
1741 # define inline __inline
1743 # define inline /* disable inline */
1747 #ifdef _MSC_VER /* Visual Studio */
1748 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1752 /* **************************************************************
1754 ****************************************************************/
1755 #include <stdlib.h> /* malloc, free, qsort */
1756 #include <string.h> /* memcpy, memset */
1757 #include <stdio.h> /* printf (debug) */
1760 /* **************************************************************
1762 ****************************************************************/
1763 #define HUFv05_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv05_MAX_TABLELOG. Beyond that value, code does not work */
1764 #define HUFv05_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv05_ABSOLUTEMAX_TABLELOG */
1765 #define HUFv05_DEFAULT_TABLELOG HUFv05_MAX_TABLELOG /* tableLog by default, when not specified */
1766 #define HUFv05_MAX_SYMBOL_VALUE 255
1767 #if (HUFv05_MAX_TABLELOG > HUFv05_ABSOLUTEMAX_TABLELOG)
1768 # error "HUFv05_MAX_TABLELOG is too large !"
1772 /* **************************************************************
1774 ****************************************************************/
1775 unsigned HUFv05_isError(size_t code) { return ERR_isError(code); }
1776 const char* HUFv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1777 #define HUFv05_STATIC_ASSERT(c) { enum { HUFv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1780 /* *******************************************************
1781 * Huff0 : Huffman block decompression
1782 *********************************************************/
1783 typedef struct { BYTE byte; BYTE nbBits; } HUFv05_DEltX2; /* single-symbol decoding */
1785 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv05_DEltX4; /* double-symbols decoding */
1787 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1789 /*! HUFv05_readStats
1790 Read compact Huffman tree, saved by HUFv05_writeCTable
1791 @huffWeight : destination buffer
1792 @return : size read from `src`
1794 static size_t HUFv05_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1795 U32* nbSymbolsPtr, U32* tableLogPtr,
1796 const void* src, size_t srcSize)
1800 const BYTE* ip = (const BYTE*) src;
1805 if (!srcSize) return ERROR(srcSize_wrong);
1807 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1809 if (iSize >= 128) { /* special header */
1810 if (iSize >= (242)) { /* RLE */
1811 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1812 oSize = l[iSize-242];
1813 memset(huffWeight, 1, hwSize);
1816 else { /* Incompressible */
1817 oSize = iSize - 127;
1818 iSize = ((oSize+1)/2);
1819 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1820 if (oSize >= hwSize) return ERROR(corruption_detected);
1822 for (n=0; n<oSize; n+=2) {
1823 huffWeight[n] = ip[n/2] >> 4;
1824 huffWeight[n+1] = ip[n/2] & 15;
1826 else { /* header compressed with FSEv05 (normal case) */
1827 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1828 oSize = FSEv05_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1829 if (FSEv05_isError(oSize)) return oSize;
1832 /* collect weight stats */
1833 memset(rankStats, 0, (HUFv05_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1835 for (n=0; n<oSize; n++) {
1836 if (huffWeight[n] >= HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1837 rankStats[huffWeight[n]]++;
1838 weightTotal += (1 << huffWeight[n]) >> 1;
1840 if (weightTotal == 0) return ERROR(corruption_detected);
1842 /* get last non-null symbol weight (implied, total must be 2^n) */
1843 tableLog = BITv05_highbit32(weightTotal) + 1;
1844 if (tableLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1845 { /* determine last weight */
1846 U32 total = 1 << tableLog;
1847 U32 rest = total - weightTotal;
1848 U32 verif = 1 << BITv05_highbit32(rest);
1849 U32 lastWeight = BITv05_highbit32(rest) + 1;
1850 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1851 huffWeight[oSize] = (BYTE)lastWeight;
1852 rankStats[lastWeight]++;
1855 /* check tree construction validity */
1856 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1859 *nbSymbolsPtr = (U32)(oSize+1);
1860 *tableLogPtr = tableLog;
1865 /*-***************************/
1866 /* single-symbol decoding */
1867 /*-***************************/
1869 size_t HUFv05_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1871 BYTE huffWeight[HUFv05_MAX_SYMBOL_VALUE + 1];
1872 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1878 void* const dtPtr = DTable + 1;
1879 HUFv05_DEltX2* const dt = (HUFv05_DEltX2*)dtPtr;
1881 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1882 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1884 iSize = HUFv05_readStats(huffWeight, HUFv05_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1885 if (HUFv05_isError(iSize)) return iSize;
1888 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1889 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
1893 for (n=1; n<=tableLog; n++) {
1894 U32 current = nextRankStart;
1895 nextRankStart += (rankVal[n] << (n-1));
1896 rankVal[n] = current;
1900 for (n=0; n<nbSymbols; n++) {
1901 const U32 w = huffWeight[n];
1902 const U32 length = (1 << w) >> 1;
1905 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1906 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1908 rankVal[w] += length;
1914 static BYTE HUFv05_decodeSymbolX2(BITv05_DStream_t* Dstream, const HUFv05_DEltX2* dt, const U32 dtLog)
1916 const size_t val = BITv05_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1917 const BYTE c = dt[val].byte;
1918 BITv05_skipBits(Dstream, dt[val].nbBits);
1922 #define HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1923 *ptr++ = HUFv05_decodeSymbolX2(DStreamPtr, dt, dtLog)
1925 #define HUFv05_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1926 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
1927 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1929 #define HUFv05_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1931 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1933 static inline size_t HUFv05_decodeStreamX2(BYTE* p, BITv05_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv05_DEltX2* const dt, const U32 dtLog)
1935 BYTE* const pStart = p;
1937 /* up to 4 symbols at a time */
1938 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-4)) {
1939 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1940 HUFv05_DECODE_SYMBOLX2_1(p, bitDPtr);
1941 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1942 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1945 /* closer to the end */
1946 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd))
1947 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1949 /* no more data to retrieve from bitstream, hence no need to reload */
1951 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1956 size_t HUFv05_decompress1X2_usingDTable(
1957 void* dst, size_t dstSize,
1958 const void* cSrc, size_t cSrcSize,
1961 BYTE* op = (BYTE*)dst;
1962 BYTE* const oend = op + dstSize;
1963 const U32 dtLog = DTable[0];
1964 const void* dtPtr = DTable;
1965 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr)+1;
1966 BITv05_DStream_t bitD;
1968 if (dstSize <= cSrcSize) return ERROR(dstSize_tooSmall);
1969 { size_t const errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize);
1970 if (HUFv05_isError(errorCode)) return errorCode; }
1972 HUFv05_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1975 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
1980 size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1982 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
1983 const BYTE* ip = (const BYTE*) cSrc;
1986 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
1987 if (HUFv05_isError(errorCode)) return errorCode;
1988 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1990 cSrcSize -= errorCode;
1992 return HUFv05_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1996 size_t HUFv05_decompress4X2_usingDTable(
1997 void* dst, size_t dstSize,
1998 const void* cSrc, size_t cSrcSize,
2002 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2004 const BYTE* const istart = (const BYTE*) cSrc;
2005 BYTE* const ostart = (BYTE*) dst;
2006 BYTE* const oend = ostart + dstSize;
2007 const void* const dtPtr = DTable;
2008 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr) +1;
2009 const U32 dtLog = DTable[0];
2013 BITv05_DStream_t bitD1;
2014 BITv05_DStream_t bitD2;
2015 BITv05_DStream_t bitD3;
2016 BITv05_DStream_t bitD4;
2017 const size_t length1 = MEM_readLE16(istart);
2018 const size_t length2 = MEM_readLE16(istart+2);
2019 const size_t length3 = MEM_readLE16(istart+4);
2021 const BYTE* const istart1 = istart + 6; /* jumpTable */
2022 const BYTE* const istart2 = istart1 + length1;
2023 const BYTE* const istart3 = istart2 + length2;
2024 const BYTE* const istart4 = istart3 + length3;
2025 const size_t segmentSize = (dstSize+3) / 4;
2026 BYTE* const opStart2 = ostart + segmentSize;
2027 BYTE* const opStart3 = opStart2 + segmentSize;
2028 BYTE* const opStart4 = opStart3 + segmentSize;
2030 BYTE* op2 = opStart2;
2031 BYTE* op3 = opStart3;
2032 BYTE* op4 = opStart4;
2035 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2036 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2037 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
2038 if (HUFv05_isError(errorCode)) return errorCode;
2039 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
2040 if (HUFv05_isError(errorCode)) return errorCode;
2041 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
2042 if (HUFv05_isError(errorCode)) return errorCode;
2043 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
2044 if (HUFv05_isError(errorCode)) return errorCode;
2046 /* 16-32 symbols per loop (4-8 symbols per stream) */
2047 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2048 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
2049 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
2050 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
2051 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2052 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2053 HUFv05_DECODE_SYMBOLX2_1(op1, &bitD1);
2054 HUFv05_DECODE_SYMBOLX2_1(op2, &bitD2);
2055 HUFv05_DECODE_SYMBOLX2_1(op3, &bitD3);
2056 HUFv05_DECODE_SYMBOLX2_1(op4, &bitD4);
2057 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
2058 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
2059 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2060 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2061 HUFv05_DECODE_SYMBOLX2_0(op1, &bitD1);
2062 HUFv05_DECODE_SYMBOLX2_0(op2, &bitD2);
2063 HUFv05_DECODE_SYMBOLX2_0(op3, &bitD3);
2064 HUFv05_DECODE_SYMBOLX2_0(op4, &bitD4);
2065 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2068 /* check corruption */
2069 if (op1 > opStart2) return ERROR(corruption_detected);
2070 if (op2 > opStart3) return ERROR(corruption_detected);
2071 if (op3 > opStart4) return ERROR(corruption_detected);
2072 /* note : op4 supposed already verified within main loop */
2074 /* finish bitStreams one by one */
2075 HUFv05_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2076 HUFv05_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2077 HUFv05_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2078 HUFv05_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2081 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2082 if (!endSignal) return ERROR(corruption_detected);
2090 size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2092 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
2093 const BYTE* ip = (const BYTE*) cSrc;
2096 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
2097 if (HUFv05_isError(errorCode)) return errorCode;
2098 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2100 cSrcSize -= errorCode;
2102 return HUFv05_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2106 /* *************************/
2107 /* double-symbols decoding */
2108 /* *************************/
2110 static void HUFv05_fillDTableX4Level2(HUFv05_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2111 const U32* rankValOrigin, const int minWeight,
2112 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2113 U32 nbBitsBaseline, U16 baseSeq)
2116 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2119 /* get pre-calculated rankVal */
2120 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2122 /* fill skipped values */
2124 U32 i, skipSize = rankVal[minWeight];
2125 MEM_writeLE16(&(DElt.sequence), baseSeq);
2126 DElt.nbBits = (BYTE)(consumed);
2128 for (i = 0; i < skipSize; i++)
2133 for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2134 const U32 symbol = sortedSymbols[s].symbol;
2135 const U32 weight = sortedSymbols[s].weight;
2136 const U32 nbBits = nbBitsBaseline - weight;
2137 const U32 length = 1 << (sizeLog-nbBits);
2138 const U32 start = rankVal[weight];
2140 const U32 end = start + length;
2142 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2143 DElt.nbBits = (BYTE)(nbBits + consumed);
2145 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2147 rankVal[weight] += length;
2151 typedef U32 rankVal_t[HUFv05_ABSOLUTEMAX_TABLELOG][HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2153 static void HUFv05_fillDTableX4(HUFv05_DEltX4* DTable, const U32 targetLog,
2154 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2155 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2156 const U32 nbBitsBaseline)
2158 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2159 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2160 const U32 minBits = nbBitsBaseline - maxWeight;
2163 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2166 for (s=0; s<sortedListSize; s++) {
2167 const U16 symbol = sortedList[s].symbol;
2168 const U32 weight = sortedList[s].weight;
2169 const U32 nbBits = nbBitsBaseline - weight;
2170 const U32 start = rankVal[weight];
2171 const U32 length = 1 << (targetLog-nbBits);
2173 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2175 int minWeight = nbBits + scaleLog;
2176 if (minWeight < 1) minWeight = 1;
2177 sortedRank = rankStart[minWeight];
2178 HUFv05_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2179 rankValOrigin[nbBits], minWeight,
2180 sortedList+sortedRank, sortedListSize-sortedRank,
2181 nbBitsBaseline, symbol);
2184 const U32 end = start + length;
2187 MEM_writeLE16(&(DElt.sequence), symbol);
2188 DElt.nbBits = (BYTE)(nbBits);
2190 for (i = start; i < end; i++)
2193 rankVal[weight] += length;
2197 size_t HUFv05_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize)
2199 BYTE weightList[HUFv05_MAX_SYMBOL_VALUE + 1];
2200 sortedSymbol_t sortedSymbol[HUFv05_MAX_SYMBOL_VALUE + 1];
2201 U32 rankStats[HUFv05_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2202 U32 rankStart0[HUFv05_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2203 U32* const rankStart = rankStart0+1;
2205 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2206 const U32 memLog = DTable[0];
2208 void* dtPtr = DTable;
2209 HUFv05_DEltX4* const dt = ((HUFv05_DEltX4*)dtPtr) + 1;
2211 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX4) == sizeof(unsigned)); /* if compilation fails here, assertion is false */
2212 if (memLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2213 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2215 iSize = HUFv05_readStats(weightList, HUFv05_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2216 if (HUFv05_isError(iSize)) return iSize;
2219 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2221 /* find maxWeight */
2222 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2224 /* Get start index of each weight */
2226 U32 w, nextRankStart = 0;
2227 for (w=1; w<=maxW; w++) {
2228 U32 current = nextRankStart;
2229 nextRankStart += rankStats[w];
2230 rankStart[w] = current;
2232 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2233 sizeOfSort = nextRankStart;
2236 /* sort symbols by weight */
2239 for (s=0; s<nbSymbols; s++) {
2240 U32 w = weightList[s];
2241 U32 r = rankStart[w]++;
2242 sortedSymbol[r].symbol = (BYTE)s;
2243 sortedSymbol[r].weight = (BYTE)w;
2245 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2250 const U32 minBits = tableLog+1 - maxW;
2251 U32 nextRankVal = 0;
2253 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2254 U32* rankVal0 = rankVal[0];
2255 for (w=1; w<=maxW; w++) {
2256 U32 current = nextRankVal;
2257 nextRankVal += rankStats[w] << (w+rescale);
2258 rankVal0[w] = current;
2260 for (consumed = minBits; consumed <= memLog - minBits; consumed++) {
2261 U32* rankValPtr = rankVal[consumed];
2262 for (w = 1; w <= maxW; w++) {
2263 rankValPtr[w] = rankVal0[w] >> consumed;
2266 HUFv05_fillDTableX4(dt, memLog,
2267 sortedSymbol, sizeOfSort,
2268 rankStart0, rankVal, maxW,
2275 static U32 HUFv05_decodeSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2277 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2278 memcpy(op, dt+val, 2);
2279 BITv05_skipBits(DStream, dt[val].nbBits);
2280 return dt[val].length;
2283 static U32 HUFv05_decodeLastSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2285 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2286 memcpy(op, dt+val, 1);
2287 if (dt[val].length==1) BITv05_skipBits(DStream, dt[val].nbBits);
2289 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2290 BITv05_skipBits(DStream, dt[val].nbBits);
2291 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2292 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 */
2298 #define HUFv05_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2299 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2301 #define HUFv05_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2302 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
2303 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2305 #define HUFv05_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2307 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2309 static inline size_t HUFv05_decodeStreamX4(BYTE* p, BITv05_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv05_DEltX4* const dt, const U32 dtLog)
2311 BYTE* const pStart = p;
2313 /* up to 8 symbols at a time */
2314 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd-7)) {
2315 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2316 HUFv05_DECODE_SYMBOLX4_1(p, bitDPtr);
2317 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2318 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2321 /* closer to the end */
2322 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-2))
2323 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2326 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2329 p += HUFv05_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2335 size_t HUFv05_decompress1X4_usingDTable(
2336 void* dst, size_t dstSize,
2337 const void* cSrc, size_t cSrcSize,
2338 const unsigned* DTable)
2340 const BYTE* const istart = (const BYTE*) cSrc;
2341 BYTE* const ostart = (BYTE*) dst;
2342 BYTE* const oend = ostart + dstSize;
2344 const U32 dtLog = DTable[0];
2345 const void* const dtPtr = DTable;
2346 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2350 BITv05_DStream_t bitD;
2351 errorCode = BITv05_initDStream(&bitD, istart, cSrcSize);
2352 if (HUFv05_isError(errorCode)) return errorCode;
2354 /* finish bitStreams one by one */
2355 HUFv05_decodeStreamX4(ostart, &bitD, oend, dt, dtLog);
2358 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
2364 size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2366 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2367 const BYTE* ip = (const BYTE*) cSrc;
2369 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2370 if (HUFv05_isError(hSize)) return hSize;
2371 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2375 return HUFv05_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2378 size_t HUFv05_decompress4X4_usingDTable(
2379 void* dst, size_t dstSize,
2380 const void* cSrc, size_t cSrcSize,
2381 const unsigned* DTable)
2383 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2386 const BYTE* const istart = (const BYTE*) cSrc;
2387 BYTE* const ostart = (BYTE*) dst;
2388 BYTE* const oend = ostart + dstSize;
2389 const void* const dtPtr = DTable;
2390 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2391 const U32 dtLog = DTable[0];
2395 BITv05_DStream_t bitD1;
2396 BITv05_DStream_t bitD2;
2397 BITv05_DStream_t bitD3;
2398 BITv05_DStream_t bitD4;
2399 const size_t length1 = MEM_readLE16(istart);
2400 const size_t length2 = MEM_readLE16(istart+2);
2401 const size_t length3 = MEM_readLE16(istart+4);
2403 const BYTE* const istart1 = istart + 6; /* jumpTable */
2404 const BYTE* const istart2 = istart1 + length1;
2405 const BYTE* const istart3 = istart2 + length2;
2406 const BYTE* const istart4 = istart3 + length3;
2407 const size_t segmentSize = (dstSize+3) / 4;
2408 BYTE* const opStart2 = ostart + segmentSize;
2409 BYTE* const opStart3 = opStart2 + segmentSize;
2410 BYTE* const opStart4 = opStart3 + segmentSize;
2412 BYTE* op2 = opStart2;
2413 BYTE* op3 = opStart3;
2414 BYTE* op4 = opStart4;
2417 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2418 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2419 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
2420 if (HUFv05_isError(errorCode)) return errorCode;
2421 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
2422 if (HUFv05_isError(errorCode)) return errorCode;
2423 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
2424 if (HUFv05_isError(errorCode)) return errorCode;
2425 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
2426 if (HUFv05_isError(errorCode)) return errorCode;
2428 /* 16-32 symbols per loop (4-8 symbols per stream) */
2429 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2430 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
2431 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2432 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2433 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2434 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2435 HUFv05_DECODE_SYMBOLX4_1(op1, &bitD1);
2436 HUFv05_DECODE_SYMBOLX4_1(op2, &bitD2);
2437 HUFv05_DECODE_SYMBOLX4_1(op3, &bitD3);
2438 HUFv05_DECODE_SYMBOLX4_1(op4, &bitD4);
2439 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2440 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2441 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2442 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2443 HUFv05_DECODE_SYMBOLX4_0(op1, &bitD1);
2444 HUFv05_DECODE_SYMBOLX4_0(op2, &bitD2);
2445 HUFv05_DECODE_SYMBOLX4_0(op3, &bitD3);
2446 HUFv05_DECODE_SYMBOLX4_0(op4, &bitD4);
2448 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2451 /* check corruption */
2452 if (op1 > opStart2) return ERROR(corruption_detected);
2453 if (op2 > opStart3) return ERROR(corruption_detected);
2454 if (op3 > opStart4) return ERROR(corruption_detected);
2455 /* note : op4 supposed already verified within main loop */
2457 /* finish bitStreams one by one */
2458 HUFv05_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2459 HUFv05_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2460 HUFv05_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2461 HUFv05_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2464 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2465 if (!endSignal) return ERROR(corruption_detected);
2473 size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2475 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2476 const BYTE* ip = (const BYTE*) cSrc;
2478 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2479 if (HUFv05_isError(hSize)) return hSize;
2480 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2484 return HUFv05_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2488 /* ********************************/
2489 /* Generic decompression selector */
2490 /* ********************************/
2492 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2493 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2495 /* single, double, quad */
2496 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2497 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2498 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2499 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2500 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2501 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2502 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2503 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2504 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2505 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2506 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2507 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2508 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2509 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2510 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2511 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2514 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2516 size_t HUFv05_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2518 static const decompressionAlgo decompress[3] = { HUFv05_decompress4X2, HUFv05_decompress4X4, NULL };
2519 /* estimate decompression time */
2521 const U32 D256 = (U32)(dstSize >> 8);
2526 /* validation checks */
2527 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2528 if (cSrcSize >= dstSize) return ERROR(corruption_detected); /* invalid, or not compressed, but not compressed already dealt with */
2529 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2531 /* decoder timing evaluation */
2532 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2534 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2536 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2538 if (Dtime[1] < Dtime[0]) algoNb = 1;
2540 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2542 //return HUFv05_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2543 //return HUFv05_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2544 //return HUFv05_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2547 zstd - standard compression library
2548 Copyright (C) 2014-2016, Yann Collet.
2550 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2552 Redistribution and use in source and binary forms, with or without
2553 modification, are permitted provided that the following conditions are
2555 * Redistributions of source code must retain the above copyright
2556 notice, this list of conditions and the following disclaimer.
2557 * Redistributions in binary form must reproduce the above
2558 copyright notice, this list of conditions and the following disclaimer
2559 in the documentation and/or other materials provided with the
2561 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2562 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2563 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2564 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2565 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2566 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2567 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2568 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2569 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2570 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2571 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2573 You can contact the author at :
2574 - zstd source repository : https://github.com/Cyan4973/zstd
2577 /* ***************************************************************
2579 *****************************************************************/
2582 * Select how default decompression function ZSTDv05_decompress() will allocate memory,
2583 * in memory stack (0), or in memory heap (1, requires malloc())
2585 #ifndef ZSTDv05_HEAPMODE
2586 # define ZSTDv05_HEAPMODE 1
2590 /*-*******************************************************
2592 *********************************************************/
2593 #include <stdlib.h> /* calloc */
2594 #include <string.h> /* memcpy, memmove */
2595 #include <stdio.h> /* debug only : printf */
2598 /*-*******************************************************
2599 * Compiler specifics
2600 *********************************************************/
2601 #ifdef _MSC_VER /* Visual Studio */
2602 # include <intrin.h> /* For Visual 2005 */
2603 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2604 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2608 /*-*************************************
2610 ***************************************/
2613 blockType_t blockType;
2615 } blockProperties_t;
2618 /* *******************************************************
2620 **********************************************************/
2621 static void ZSTDv05_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2624 /* *************************************
2626 ***************************************/
2627 /*! ZSTDv05_isError() :
2628 * tells if a return value is an error code */
2629 unsigned ZSTDv05_isError(size_t code) { return ERR_isError(code); }
2632 /*! ZSTDv05_getErrorName() :
2633 * provides error code string (useful for debugging) */
2634 const char* ZSTDv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
2637 /* *************************************************************
2638 * Context management
2639 ***************************************************************/
2640 typedef enum { ZSTDv05ds_getFrameHeaderSize, ZSTDv05ds_decodeFrameHeader,
2641 ZSTDv05ds_decodeBlockHeader, ZSTDv05ds_decompressBlock } ZSTDv05_dStage;
2643 struct ZSTDv05_DCtx_s
2645 FSEv05_DTable LLTable[FSEv05_DTABLE_SIZE_U32(LLFSEv05Log)];
2646 FSEv05_DTable OffTable[FSEv05_DTABLE_SIZE_U32(OffFSEv05Log)];
2647 FSEv05_DTable MLTable[FSEv05_DTABLE_SIZE_U32(MLFSEv05Log)];
2648 unsigned hufTableX4[HUFv05_DTABLE_SIZE(HufLog)];
2649 const void* previousDstEnd;
2652 const void* dictEnd;
2655 ZSTDv05_parameters params;
2656 blockType_t bType; /* used in ZSTDv05_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2657 ZSTDv05_dStage stage;
2658 U32 flagStaticTables;
2661 BYTE litBuffer[BLOCKSIZE + WILDCOPY_OVERLENGTH];
2662 BYTE headerBuffer[ZSTDv05_frameHeaderSize_max];
2663 }; /* typedef'd to ZSTDv05_DCtx within "zstd_static.h" */
2665 size_t ZSTDv05_sizeofDCtx (void); /* Hidden declaration */
2666 size_t ZSTDv05_sizeofDCtx (void) { return sizeof(ZSTDv05_DCtx); }
2668 size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx)
2670 dctx->expected = ZSTDv05_frameHeaderSize_min;
2671 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
2672 dctx->previousDstEnd = NULL;
2675 dctx->dictEnd = NULL;
2676 dctx->hufTableX4[0] = HufLog;
2677 dctx->flagStaticTables = 0;
2681 ZSTDv05_DCtx* ZSTDv05_createDCtx(void)
2683 ZSTDv05_DCtx* dctx = (ZSTDv05_DCtx*)malloc(sizeof(ZSTDv05_DCtx));
2684 if (dctx==NULL) return NULL;
2685 ZSTDv05_decompressBegin(dctx);
2689 size_t ZSTDv05_freeDCtx(ZSTDv05_DCtx* dctx)
2692 return 0; /* reserved as a potential error code in the future */
2695 void ZSTDv05_copyDCtx(ZSTDv05_DCtx* dstDCtx, const ZSTDv05_DCtx* srcDCtx)
2697 memcpy(dstDCtx, srcDCtx,
2698 sizeof(ZSTDv05_DCtx) - (BLOCKSIZE+WILDCOPY_OVERLENGTH + ZSTDv05_frameHeaderSize_max)); /* no need to copy workspace */
2702 /* *************************************************************
2703 * Decompression section
2704 ***************************************************************/
2706 /* Frame format description
2707 Frame Header - [ Block Header - Block ] - Frame End
2709 - 4 bytes - Magic Number : ZSTDv05_MAGICNUMBER (defined within zstd_internal.h)
2710 - 1 byte - Window Descriptor
2712 - 3 bytes, starting with a 2-bits descriptor
2713 Uncompressed, Compressed, Frame End, unused
2715 See Block Format Description
2717 - 3 bytes, compatible with Block Header
2720 /* Block format description
2722 Block = Literal Section - Sequences Section
2723 Prerequisite : size of (compressed) block, maximum size of regenerated data
2727 1.1) Header : 1-5 bytes
2729 00 compressed by Huff0
2731 10 is Raw (uncompressed)
2733 Note : using 01 => Huff0 with precomputed table ?
2734 Note : delta map ? => compressed ?
2736 1.1.1) Huff0-compressed literal block : 3-5 bytes
2737 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2738 srcSize < 1 KB => 3 bytes (2-2-10-10)
2739 srcSize < 16KB => 4 bytes (2-2-14-14)
2740 else => 5 bytes (2-2-18-18)
2741 big endian convention
2743 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2744 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2745 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2747 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2751 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2752 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
2753 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2755 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2759 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2760 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2761 srcSize < 1 KB => 3 bytes (2-2-10-10)
2762 srcSize < 16KB => 4 bytes (2-2-14-14)
2763 else => 5 bytes (2-2-18-18)
2764 big endian convention
2766 1- CTable available (stored into workspace ?)
2767 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2770 1.2) Literal block content
2772 1.2.1) Huff0 block, using sizes from header
2775 1.2.2) Huff0 block, using prepared table
2782 2) Sequences section
2787 /** ZSTDv05_decodeFrameHeader_Part1() :
2788 * decode the 1st part of the Frame Header, which tells Frame Header size.
2789 * srcSize must be == ZSTDv05_frameHeaderSize_min.
2790 * @return : the full size of the Frame Header */
2791 static size_t ZSTDv05_decodeFrameHeader_Part1(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2794 if (srcSize != ZSTDv05_frameHeaderSize_min)
2795 return ERROR(srcSize_wrong);
2796 magicNumber = MEM_readLE32(src);
2797 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2798 zc->headerSize = ZSTDv05_frameHeaderSize_min;
2799 return zc->headerSize;
2803 size_t ZSTDv05_getFrameParams(ZSTDv05_parameters* params, const void* src, size_t srcSize)
2806 if (srcSize < ZSTDv05_frameHeaderSize_min) return ZSTDv05_frameHeaderSize_max;
2807 magicNumber = MEM_readLE32(src);
2808 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2809 memset(params, 0, sizeof(*params));
2810 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTDv05_WINDOWLOG_ABSOLUTEMIN;
2811 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */
2815 /** ZSTDv05_decodeFrameHeader_Part2() :
2816 * decode the full Frame Header.
2817 * srcSize must be the size provided by ZSTDv05_decodeFrameHeader_Part1().
2818 * @return : 0, or an error code, which can be tested using ZSTDv05_isError() */
2819 static size_t ZSTDv05_decodeFrameHeader_Part2(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2822 if (srcSize != zc->headerSize)
2823 return ERROR(srcSize_wrong);
2824 result = ZSTDv05_getFrameParams(&(zc->params), src, srcSize);
2825 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported);
2830 static size_t ZSTDv05_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2832 const BYTE* const in = (const BYTE* const)src;
2837 return ERROR(srcSize_wrong);
2840 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2842 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2843 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2845 if (bpPtr->blockType == bt_end) return 0;
2846 if (bpPtr->blockType == bt_rle) return 1;
2851 static size_t ZSTDv05_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2853 if (dst==NULL) return ERROR(dstSize_tooSmall);
2854 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2855 memcpy(dst, src, srcSize);
2860 /*! ZSTDv05_decodeLiteralsBlock() :
2861 @return : nb of bytes read from src (< srcSize ) */
2862 static size_t ZSTDv05_decodeLiteralsBlock(ZSTDv05_DCtx* dctx,
2863 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
2865 const BYTE* const istart = (const BYTE*) src;
2867 /* any compressed block with literals segment must be at least this size */
2868 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2870 switch(istart[0]>> 6)
2874 size_t litSize, litCSize, singleStream=0;
2875 U32 lhSize = ((istart[0]) >> 4) & 3;
2876 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
2879 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2880 /* 2 - 2 - 10 - 10 */
2882 singleStream = istart[0] & 16;
2883 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2884 litCSize = ((istart[1] & 3) << 8) + istart[2];
2887 /* 2 - 2 - 14 - 14 */
2889 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
2890 litCSize = ((istart[2] & 63) << 8) + istart[3];
2893 /* 2 - 2 - 18 - 18 */
2895 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
2896 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
2899 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2900 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2902 if (HUFv05_isError(singleStream ?
2903 HUFv05_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) :
2904 HUFv05_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
2905 return ERROR(corruption_detected);
2907 dctx->litPtr = dctx->litBuffer;
2908 dctx->litSize = litSize;
2909 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2910 return litCSize + lhSize;
2915 size_t litSize, litCSize;
2916 U32 lhSize = ((istart[0]) >> 4) & 3;
2917 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
2918 return ERROR(corruption_detected);
2919 if (!dctx->flagStaticTables)
2920 return ERROR(dictionary_corrupted);
2922 /* 2 - 2 - 10 - 10 */
2924 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2925 litCSize = ((istart[1] & 3) << 8) + istart[2];
2926 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2928 errorCode = HUFv05_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4);
2929 if (HUFv05_isError(errorCode)) return ERROR(corruption_detected);
2931 dctx->litPtr = dctx->litBuffer;
2932 dctx->litSize = litSize;
2933 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2934 return litCSize + lhSize;
2939 U32 lhSize = ((istart[0]) >> 4) & 3;
2942 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2944 litSize = istart[0] & 31;
2947 litSize = ((istart[0] & 15) << 8) + istart[1];
2950 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2954 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
2955 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
2956 memcpy(dctx->litBuffer, istart+lhSize, litSize);
2957 dctx->litPtr = dctx->litBuffer;
2958 dctx->litSize = litSize;
2959 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2960 return lhSize+litSize;
2962 /* direct reference into compressed stream */
2963 dctx->litPtr = istart+lhSize;
2964 dctx->litSize = litSize;
2965 return lhSize+litSize;
2970 U32 lhSize = ((istart[0]) >> 4) & 3;
2973 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2975 litSize = istart[0] & 31;
2978 litSize = ((istart[0] & 15) << 8) + istart[1];
2981 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2982 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
2985 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2986 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
2987 dctx->litPtr = dctx->litBuffer;
2988 dctx->litSize = litSize;
2992 return ERROR(corruption_detected); /* impossible */
2997 static size_t ZSTDv05_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2998 FSEv05_DTable* DTableLL, FSEv05_DTable* DTableML, FSEv05_DTable* DTableOffb,
2999 const void* src, size_t srcSize, U32 flagStaticTable)
3001 const BYTE* const istart = (const BYTE* const)src;
3002 const BYTE* ip = istart;
3003 const BYTE* const iend = istart + srcSize;
3004 U32 LLtype, Offtype, MLtype;
3005 unsigned LLlog, Offlog, MLlog;
3009 if (srcSize < MIN_SEQUENCES_SIZE)
3010 return ERROR(srcSize_wrong);
3014 if (*nbSeq==0) return 1;
3015 if (*nbSeq >= 128) {
3016 if (ip >= iend) return ERROR(srcSize_wrong);
3017 *nbSeq = ((nbSeq[0]-128)<<8) + *ip++;
3020 if (ip >= iend) return ERROR(srcSize_wrong);
3022 Offtype = (*ip >> 4) & 3;
3023 MLtype = (*ip >> 2) & 3;
3025 if (ip+3 > iend) return ERROR(srcSize_wrong);
3026 dumpsLength = ip[2];
3027 dumpsLength += ip[1] << 8;
3030 if (ip+2 > iend) return ERROR(srcSize_wrong);
3031 dumpsLength = ip[1];
3032 dumpsLength += (ip[0] & 1) << 8;
3037 *dumpsLengthPtr = dumpsLength;
3040 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3044 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */
3050 case FSEv05_ENCODING_RLE :
3052 FSEv05_buildDTable_rle(DTableLL, *ip++);
3054 case FSEv05_ENCODING_RAW :
3056 FSEv05_buildDTable_raw(DTableLL, LLbits);
3058 case FSEv05_ENCODING_STATIC:
3059 if (!flagStaticTable) return ERROR(corruption_detected);
3061 case FSEv05_ENCODING_DYNAMIC :
3062 default : /* impossible */
3063 { unsigned max = MaxLL;
3064 headerSize = FSEv05_readNCount(norm, &max, &LLlog, ip, iend-ip);
3065 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3066 if (LLlog > LLFSEv05Log) return ERROR(corruption_detected);
3068 FSEv05_buildDTable(DTableLL, norm, max, LLlog);
3073 case FSEv05_ENCODING_RLE :
3075 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3076 FSEv05_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
3078 case FSEv05_ENCODING_RAW :
3080 FSEv05_buildDTable_raw(DTableOffb, Offbits);
3082 case FSEv05_ENCODING_STATIC:
3083 if (!flagStaticTable) return ERROR(corruption_detected);
3085 case FSEv05_ENCODING_DYNAMIC :
3086 default : /* impossible */
3087 { unsigned max = MaxOff;
3088 headerSize = FSEv05_readNCount(norm, &max, &Offlog, ip, iend-ip);
3089 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3090 if (Offlog > OffFSEv05Log) return ERROR(corruption_detected);
3092 FSEv05_buildDTable(DTableOffb, norm, max, Offlog);
3097 case FSEv05_ENCODING_RLE :
3099 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3100 FSEv05_buildDTable_rle(DTableML, *ip++);
3102 case FSEv05_ENCODING_RAW :
3104 FSEv05_buildDTable_raw(DTableML, MLbits);
3106 case FSEv05_ENCODING_STATIC:
3107 if (!flagStaticTable) return ERROR(corruption_detected);
3109 case FSEv05_ENCODING_DYNAMIC :
3110 default : /* impossible */
3111 { unsigned max = MaxML;
3112 headerSize = FSEv05_readNCount(norm, &max, &MLlog, ip, iend-ip);
3113 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3114 if (MLlog > MLFSEv05Log) return ERROR(corruption_detected);
3116 FSEv05_buildDTable(DTableML, norm, max, MLlog);
3130 BITv05_DStream_t DStream;
3131 FSEv05_DState_t stateLL;
3132 FSEv05_DState_t stateOffb;
3133 FSEv05_DState_t stateML;
3136 const BYTE* dumpsEnd;
3141 static void ZSTDv05_decodeSequence(seq_t* seq, seqState_t* seqState)
3147 const BYTE* dumps = seqState->dumps;
3148 const BYTE* const de = seqState->dumpsEnd;
3150 /* Literal length */
3151 litLength = FSEv05_peakSymbol(&(seqState->stateLL));
3152 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3153 if (litLength == MaxLL) {
3154 const U32 add = *dumps++;
3155 if (add < 255) litLength += add;
3156 else if (dumps + 2 <= de) {
3157 litLength = MEM_readLE16(dumps);
3159 if ((litLength & 1) && dumps < de) {
3160 litLength += *dumps << 16;
3165 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3170 static const U32 offsetPrefix[MaxOff+1] = {
3171 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3172 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3173 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3174 U32 offsetCode = FSEv05_peakSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3175 U32 nbBits = offsetCode - 1;
3176 if (offsetCode==0) nbBits = 0; /* cmove */
3177 offset = offsetPrefix[offsetCode] + BITv05_readBits(&(seqState->DStream), nbBits);
3178 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3179 if (offsetCode==0) offset = prevOffset; /* repcode, cmove */
3180 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */
3181 FSEv05_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* update */
3184 /* Literal length update */
3185 FSEv05_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); /* update */
3186 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3189 matchLength = FSEv05_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3190 if (matchLength == MaxML) {
3191 const U32 add = dumps<de ? *dumps++ : 0;
3192 if (add < 255) matchLength += add;
3193 else if (dumps + 2 <= de) {
3194 matchLength = MEM_readLE16(dumps);
3196 if ((matchLength & 1) && dumps < de) {
3197 matchLength += *dumps << 16;
3202 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3204 matchLength += MINMATCH;
3207 seq->litLength = litLength;
3208 seq->offset = offset;
3209 seq->matchLength = matchLength;
3210 seqState->dumps = dumps;
3214 static U64 totalDecoded = 0;
3215 printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n",
3216 (U32)(totalDecoded), (U32)litLength, (U32)matchLength, (U32)offset);
3217 totalDecoded += litLength + matchLength;
3223 static size_t ZSTDv05_execSequence(BYTE* op,
3224 BYTE* const oend, seq_t sequence,
3225 const BYTE** litPtr, const BYTE* const litLimit,
3226 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3228 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3229 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
3230 BYTE* const oLitEnd = op + sequence.litLength;
3231 const size_t sequenceLength = sequence.litLength + sequence.matchLength;
3232 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3233 BYTE* const oend_8 = oend-8;
3234 const BYTE* const litEnd = *litPtr + sequence.litLength;
3235 const BYTE* match = oLitEnd - sequence.offset;
3238 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
3239 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3240 if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */
3243 ZSTDv05_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3245 *litPtr = litEnd; /* update for next sequence */
3248 if (sequence.offset > (size_t)(oLitEnd - base)) {
3249 /* offset beyond prefix */
3250 if (sequence.offset > (size_t)(oLitEnd - vBase))
3251 return ERROR(corruption_detected);
3252 match = dictEnd - (base-match);
3253 if (match + sequence.matchLength <= dictEnd) {
3254 memmove(oLitEnd, match, sequence.matchLength);
3255 return sequenceLength;
3257 /* span extDict & currentPrefixSegment */
3259 size_t length1 = dictEnd - match;
3260 memmove(oLitEnd, match, length1);
3261 op = oLitEnd + length1;
3262 sequence.matchLength -= length1;
3264 if (op > oend_8 || sequence.matchLength < MINMATCH) {
3265 while (op < oMatchEnd) *op++ = *match++;
3266 return sequenceLength;
3269 /* Requirement: op <= oend_8 */
3271 /* match within prefix */
3272 if (sequence.offset < 8) {
3273 /* close range match, overlap */
3274 const int sub2 = dec64table[sequence.offset];
3279 match += dec32table[sequence.offset];
3280 ZSTDv05_copy4(op+4, match);
3283 ZSTDv05_copy8(op, match);
3285 op += 8; match += 8;
3287 if (oMatchEnd > oend-(16-MINMATCH)) {
3289 ZSTDv05_wildcopy(op, match, oend_8 - op);
3290 match += oend_8 - op;
3293 while (op < oMatchEnd)
3296 ZSTDv05_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3298 return sequenceLength;
3302 static size_t ZSTDv05_decompressSequences(
3304 void* dst, size_t maxDstSize,
3305 const void* seqStart, size_t seqSize)
3307 const BYTE* ip = (const BYTE*)seqStart;
3308 const BYTE* const iend = ip + seqSize;
3309 BYTE* const ostart = (BYTE* const)dst;
3311 BYTE* const oend = ostart + maxDstSize;
3312 size_t errorCode, dumpsLength=0;
3313 const BYTE* litPtr = dctx->litPtr;
3314 const BYTE* const litEnd = litPtr + dctx->litSize;
3316 const BYTE* dumps = NULL;
3317 unsigned* DTableLL = dctx->LLTable;
3318 unsigned* DTableML = dctx->MLTable;
3319 unsigned* DTableOffb = dctx->OffTable;
3320 const BYTE* const base = (const BYTE*) (dctx->base);
3321 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3322 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3324 /* Build Decoding Tables */
3325 errorCode = ZSTDv05_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3326 DTableLL, DTableML, DTableOffb,
3327 ip, seqSize, dctx->flagStaticTables);
3328 if (ZSTDv05_isError(errorCode)) return errorCode;
3331 /* Regen sequences */
3334 seqState_t seqState;
3336 memset(&sequence, 0, sizeof(sequence));
3337 sequence.offset = REPCODE_STARTVALUE;
3338 seqState.dumps = dumps;
3339 seqState.dumpsEnd = dumps + dumpsLength;
3340 seqState.prevOffset = REPCODE_STARTVALUE;
3341 errorCode = BITv05_initDStream(&(seqState.DStream), ip, iend-ip);
3342 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3343 FSEv05_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3344 FSEv05_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3345 FSEv05_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3347 for ( ; (BITv05_reloadDStream(&(seqState.DStream)) <= BITv05_DStream_completed) && nbSeq ; ) {
3350 ZSTDv05_decodeSequence(&sequence, &seqState);
3351 oneSeqSize = ZSTDv05_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3352 if (ZSTDv05_isError(oneSeqSize)) return oneSeqSize;
3356 /* check if reached exact end */
3357 if (nbSeq) return ERROR(corruption_detected);
3360 /* last literal segment */
3362 size_t lastLLSize = litEnd - litPtr;
3363 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3364 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3365 memcpy(op, litPtr, lastLLSize);
3373 static void ZSTDv05_checkContinuity(ZSTDv05_DCtx* dctx, const void* dst)
3375 if (dst != dctx->previousDstEnd) { /* not contiguous */
3376 dctx->dictEnd = dctx->previousDstEnd;
3377 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3379 dctx->previousDstEnd = dst;
3384 static size_t ZSTDv05_decompressBlock_internal(ZSTDv05_DCtx* dctx,
3385 void* dst, size_t dstCapacity,
3386 const void* src, size_t srcSize)
3387 { /* blockType == blockCompressed */
3388 const BYTE* ip = (const BYTE*)src;
3391 if (srcSize >= BLOCKSIZE) return ERROR(srcSize_wrong);
3393 /* Decode literals sub-block */
3394 litCSize = ZSTDv05_decodeLiteralsBlock(dctx, src, srcSize);
3395 if (ZSTDv05_isError(litCSize)) return litCSize;
3397 srcSize -= litCSize;
3399 return ZSTDv05_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3403 size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx,
3404 void* dst, size_t dstCapacity,
3405 const void* src, size_t srcSize)
3407 ZSTDv05_checkContinuity(dctx, dst);
3408 return ZSTDv05_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3412 /*! ZSTDv05_decompress_continueDCtx
3413 * dctx must have been properly initialized */
3414 static size_t ZSTDv05_decompress_continueDCtx(ZSTDv05_DCtx* dctx,
3415 void* dst, size_t maxDstSize,
3416 const void* src, size_t srcSize)
3418 const BYTE* ip = (const BYTE*)src;
3419 const BYTE* iend = ip + srcSize;
3420 BYTE* const ostart = (BYTE* const)dst;
3422 BYTE* const oend = ostart + maxDstSize;
3423 size_t remainingSize = srcSize;
3424 blockProperties_t blockProperties;
3425 memset(&blockProperties, 0, sizeof(blockProperties));
3428 { size_t frameHeaderSize;
3429 if (srcSize < ZSTDv05_frameHeaderSize_min+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3430 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3431 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3432 if (srcSize < frameHeaderSize+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3433 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3434 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part2(dctx, src, frameHeaderSize);
3435 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3438 /* Loop on each block */
3441 size_t decodedSize=0;
3442 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, iend-ip, &blockProperties);
3443 if (ZSTDv05_isError(cBlockSize)) return cBlockSize;
3445 ip += ZSTDv05_blockHeaderSize;
3446 remainingSize -= ZSTDv05_blockHeaderSize;
3447 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3449 switch(blockProperties.blockType)
3452 decodedSize = ZSTDv05_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3455 decodedSize = ZSTDv05_copyRawBlock(op, oend-op, ip, cBlockSize);
3458 return ERROR(GENERIC); /* not yet supported */
3462 if (remainingSize) return ERROR(srcSize_wrong);
3465 return ERROR(GENERIC); /* impossible */
3467 if (cBlockSize == 0) break; /* bt_end */
3469 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3472 remainingSize -= cBlockSize;
3479 size_t ZSTDv05_decompress_usingPreparedDCtx(ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* refDCtx,
3480 void* dst, size_t maxDstSize,
3481 const void* src, size_t srcSize)
3483 ZSTDv05_copyDCtx(dctx, refDCtx);
3484 ZSTDv05_checkContinuity(dctx, dst);
3485 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3489 size_t ZSTDv05_decompress_usingDict(ZSTDv05_DCtx* dctx,
3490 void* dst, size_t maxDstSize,
3491 const void* src, size_t srcSize,
3492 const void* dict, size_t dictSize)
3494 ZSTDv05_decompressBegin_usingDict(dctx, dict, dictSize);
3495 ZSTDv05_checkContinuity(dctx, dst);
3496 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3500 size_t ZSTDv05_decompressDCtx(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3502 return ZSTDv05_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
3505 size_t ZSTDv05_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3507 #if defined(ZSTDv05_HEAPMODE) && (ZSTDv05_HEAPMODE==1)
3509 ZSTDv05_DCtx* dctx = ZSTDv05_createDCtx();
3510 if (dctx==NULL) return ERROR(memory_allocation);
3511 regenSize = ZSTDv05_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
3512 ZSTDv05_freeDCtx(dctx);
3516 return ZSTDv05_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
3520 /* ZSTD_errorFrameSizeInfoLegacy() :
3521 assumes `cSize` and `dBound` are _not_ NULL */
3522 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3525 *dBound = ZSTD_CONTENTSIZE_ERROR;
3528 void ZSTDv05_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3530 const BYTE* ip = (const BYTE*)src;
3531 size_t remainingSize = srcSize;
3532 size_t nbBlocks = 0;
3533 blockProperties_t blockProperties;
3536 if (srcSize < ZSTDv05_frameHeaderSize_min) {
3537 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3540 if (MEM_readLE32(src) != ZSTDv05_MAGICNUMBER) {
3541 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3544 ip += ZSTDv05_frameHeaderSize_min; remainingSize -= ZSTDv05_frameHeaderSize_min;
3546 /* Loop on each block */
3549 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, remainingSize, &blockProperties);
3550 if (ZSTDv05_isError(cBlockSize)) {
3551 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3555 ip += ZSTDv05_blockHeaderSize;
3556 remainingSize -= ZSTDv05_blockHeaderSize;
3557 if (cBlockSize > remainingSize) {
3558 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3562 if (cBlockSize == 0) break; /* bt_end */
3565 remainingSize -= cBlockSize;
3569 *cSize = ip - (const BYTE*)src;
3570 *dBound = nbBlocks * BLOCKSIZE;
3573 /* ******************************
3574 * Streaming Decompression API
3575 ********************************/
3576 size_t ZSTDv05_nextSrcSizeToDecompress(ZSTDv05_DCtx* dctx)
3578 return dctx->expected;
3581 size_t ZSTDv05_decompressContinue(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3584 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3585 ZSTDv05_checkContinuity(dctx, dst);
3587 /* Decompress : frame header; part 1 */
3588 switch (dctx->stage)
3590 case ZSTDv05ds_getFrameHeaderSize :
3591 /* get frame header size */
3592 if (srcSize != ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3593 dctx->headerSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3594 if (ZSTDv05_isError(dctx->headerSize)) return dctx->headerSize;
3595 memcpy(dctx->headerBuffer, src, ZSTDv05_frameHeaderSize_min);
3596 if (dctx->headerSize > ZSTDv05_frameHeaderSize_min) return ERROR(GENERIC); /* should never happen */
3597 dctx->expected = 0; /* not necessary to copy more */
3599 case ZSTDv05ds_decodeFrameHeader:
3600 /* get frame header */
3601 { size_t const result = ZSTDv05_decodeFrameHeader_Part2(dctx, dctx->headerBuffer, dctx->headerSize);
3602 if (ZSTDv05_isError(result)) return result;
3603 dctx->expected = ZSTDv05_blockHeaderSize;
3604 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3607 case ZSTDv05ds_decodeBlockHeader:
3609 /* Decode block header */
3610 blockProperties_t bp;
3611 size_t blockSize = ZSTDv05_getcBlockSize(src, ZSTDv05_blockHeaderSize, &bp);
3612 if (ZSTDv05_isError(blockSize)) return blockSize;
3613 if (bp.blockType == bt_end) {
3615 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
3618 dctx->expected = blockSize;
3619 dctx->bType = bp.blockType;
3620 dctx->stage = ZSTDv05ds_decompressBlock;
3624 case ZSTDv05ds_decompressBlock:
3626 /* Decompress : block content */
3631 rSize = ZSTDv05_decompressBlock_internal(dctx, dst, maxDstSize, src, srcSize);
3634 rSize = ZSTDv05_copyRawBlock(dst, maxDstSize, src, srcSize);
3637 return ERROR(GENERIC); /* not yet handled */
3639 case bt_end : /* should never happen (filtered at phase 1) */
3643 return ERROR(GENERIC); /* impossible */
3645 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3646 dctx->expected = ZSTDv05_blockHeaderSize;
3647 dctx->previousDstEnd = (char*)dst + rSize;
3651 return ERROR(GENERIC); /* impossible */
3656 static void ZSTDv05_refDictContent(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3658 dctx->dictEnd = dctx->previousDstEnd;
3659 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3661 dctx->previousDstEnd = (const char*)dict + dictSize;
3664 static size_t ZSTDv05_loadEntropy(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3666 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, errorCode, litlengthHeaderSize;
3667 short offcodeNCount[MaxOff+1];
3668 unsigned offcodeMaxValue=MaxOff, offcodeLog;
3669 short matchlengthNCount[MaxML+1];
3670 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3671 short litlengthNCount[MaxLL+1];
3672 unsigned litlengthMaxValue = MaxLL, litlengthLog;
3674 hSize = HUFv05_readDTableX4(dctx->hufTableX4, dict, dictSize);
3675 if (HUFv05_isError(hSize)) return ERROR(dictionary_corrupted);
3676 dict = (const char*)dict + hSize;
3679 offcodeHeaderSize = FSEv05_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize);
3680 if (FSEv05_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3681 if (offcodeLog > OffFSEv05Log) return ERROR(dictionary_corrupted);
3682 errorCode = FSEv05_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
3683 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3684 dict = (const char*)dict + offcodeHeaderSize;
3685 dictSize -= offcodeHeaderSize;
3687 matchlengthHeaderSize = FSEv05_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize);
3688 if (FSEv05_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3689 if (matchlengthLog > MLFSEv05Log) return ERROR(dictionary_corrupted);
3690 errorCode = FSEv05_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
3691 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3692 dict = (const char*)dict + matchlengthHeaderSize;
3693 dictSize -= matchlengthHeaderSize;
3695 litlengthHeaderSize = FSEv05_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize);
3696 if (litlengthLog > LLFSEv05Log) return ERROR(dictionary_corrupted);
3697 if (FSEv05_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3698 errorCode = FSEv05_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
3699 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3701 dctx->flagStaticTables = 1;
3702 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize;
3705 static size_t ZSTDv05_decompress_insertDictionary(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3708 U32 magic = MEM_readLE32(dict);
3709 if (magic != ZSTDv05_DICT_MAGIC) {
3710 /* pure content mode */
3711 ZSTDv05_refDictContent(dctx, dict, dictSize);
3714 /* load entropy tables */
3715 dict = (const char*)dict + 4;
3717 eSize = ZSTDv05_loadEntropy(dctx, dict, dictSize);
3718 if (ZSTDv05_isError(eSize)) return ERROR(dictionary_corrupted);
3720 /* reference dictionary content */
3721 dict = (const char*)dict + eSize;
3723 ZSTDv05_refDictContent(dctx, dict, dictSize);
3729 size_t ZSTDv05_decompressBegin_usingDict(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3732 errorCode = ZSTDv05_decompressBegin(dctx);
3733 if (ZSTDv05_isError(errorCode)) return errorCode;
3735 if (dict && dictSize) {
3736 errorCode = ZSTDv05_decompress_insertDictionary(dctx, dict, dictSize);
3737 if (ZSTDv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3744 Buffered version of Zstd compression library
3745 Copyright (C) 2015-2016, Yann Collet.
3747 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
3749 Redistribution and use in source and binary forms, with or without
3750 modification, are permitted provided that the following conditions are
3752 * Redistributions of source code must retain the above copyright
3753 notice, this list of conditions and the following disclaimer.
3754 * Redistributions in binary form must reproduce the above
3755 copyright notice, this list of conditions and the following disclaimer
3756 in the documentation and/or other materials provided with the
3758 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3759 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3760 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3761 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3762 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3763 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3764 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3765 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3766 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3767 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3768 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3770 You can contact the author at :
3771 - zstd source repository : https://github.com/Cyan4973/zstd
3772 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3775 /* The objects defined into this file should be considered experimental.
3776 * They are not labelled stable, as their prototype may change in the future.
3777 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3782 /* *************************************
3784 ***************************************/
3785 static size_t ZBUFFv05_blockHeaderSize = 3;
3789 /* *** Compression *** */
3791 static size_t ZBUFFv05_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3793 size_t length = MIN(maxDstSize, srcSize);
3794 memcpy(dst, src, length);
3801 /** ************************************************
3802 * Streaming decompression
3804 * A ZBUFFv05_DCtx object is required to track streaming operation.
3805 * Use ZBUFFv05_createDCtx() and ZBUFFv05_freeDCtx() to create/release resources.
3806 * Use ZBUFFv05_decompressInit() to start a new decompression operation.
3807 * ZBUFFv05_DCtx objects can be reused multiple times.
3809 * Use ZBUFFv05_decompressContinue() repetitively to consume your input.
3810 * *srcSizePtr and *maxDstSizePtr can be any size.
3811 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3812 * 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.
3813 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3814 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3815 * or 0 when a frame is completely decoded
3816 * or an error code, which can be tested using ZBUFFv05_isError().
3818 * Hint : recommended buffer sizes (not compulsory)
3819 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3820 * input : just follow indications from ZBUFFv05_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3821 * **************************************************/
3823 typedef enum { ZBUFFv05ds_init, ZBUFFv05ds_readHeader, ZBUFFv05ds_loadHeader, ZBUFFv05ds_decodeHeader,
3824 ZBUFFv05ds_read, ZBUFFv05ds_load, ZBUFFv05ds_flush } ZBUFFv05_dStage;
3826 /* *** Resource management *** */
3828 #define ZSTDv05_frameHeaderSize_max 5 /* too magical, should come from reference */
3829 struct ZBUFFv05_DCtx_s {
3831 ZSTDv05_parameters params;
3840 ZBUFFv05_dStage stage;
3841 unsigned char headerBuffer[ZSTDv05_frameHeaderSize_max];
3842 }; /* typedef'd to ZBUFFv05_DCtx within "zstd_buffered.h" */
3845 ZBUFFv05_DCtx* ZBUFFv05_createDCtx(void)
3847 ZBUFFv05_DCtx* zbc = (ZBUFFv05_DCtx*)malloc(sizeof(ZBUFFv05_DCtx));
3848 if (zbc==NULL) return NULL;
3849 memset(zbc, 0, sizeof(*zbc));
3850 zbc->zc = ZSTDv05_createDCtx();
3851 zbc->stage = ZBUFFv05ds_init;
3855 size_t ZBUFFv05_freeDCtx(ZBUFFv05_DCtx* zbc)
3857 if (zbc==NULL) return 0; /* support free on null */
3858 ZSTDv05_freeDCtx(zbc->zc);
3866 /* *** Initialization *** */
3868 size_t ZBUFFv05_decompressInitDictionary(ZBUFFv05_DCtx* zbc, const void* dict, size_t dictSize)
3870 zbc->stage = ZBUFFv05ds_readHeader;
3871 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = 0;
3872 return ZSTDv05_decompressBegin_usingDict(zbc->zc, dict, dictSize);
3875 size_t ZBUFFv05_decompressInit(ZBUFFv05_DCtx* zbc)
3877 return ZBUFFv05_decompressInitDictionary(zbc, NULL, 0);
3881 /* *** Decompression *** */
3883 size_t ZBUFFv05_decompressContinue(ZBUFFv05_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3885 const char* const istart = (const char*)src;
3886 const char* ip = istart;
3887 const char* const iend = istart + *srcSizePtr;
3888 char* const ostart = (char*)dst;
3890 char* const oend = ostart + *maxDstSizePtr;
3896 case ZBUFFv05ds_init :
3897 return ERROR(init_missing);
3899 case ZBUFFv05ds_readHeader :
3900 /* read header from src */
3902 size_t headerSize = ZSTDv05_getFrameParams(&(zbc->params), src, *srcSizePtr);
3903 if (ZSTDv05_isError(headerSize)) return headerSize;
3905 /* not enough input to decode header : tell how many bytes would be necessary */
3906 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
3907 zbc->hPos += *srcSizePtr;
3909 zbc->stage = ZBUFFv05ds_loadHeader;
3910 return headerSize - zbc->hPos;
3912 zbc->stage = ZBUFFv05ds_decodeHeader;
3916 case ZBUFFv05ds_loadHeader:
3917 /* complete header from src */
3919 size_t headerSize = ZBUFFv05_limitCopy(
3920 zbc->headerBuffer + zbc->hPos, ZSTDv05_frameHeaderSize_max - zbc->hPos,
3922 zbc->hPos += headerSize;
3924 headerSize = ZSTDv05_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
3925 if (ZSTDv05_isError(headerSize)) return headerSize;
3927 /* not enough input to decode header : tell how many bytes would be necessary */
3929 return headerSize - zbc->hPos;
3931 // zbc->stage = ZBUFFv05ds_decodeHeader; break; /* useless : stage follows */
3934 case ZBUFFv05ds_decodeHeader:
3935 /* apply header to create / resize buffers */
3937 size_t neededOutSize = (size_t)1 << zbc->params.windowLog;
3938 size_t neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */
3939 if (zbc->inBuffSize < neededInSize) {
3941 zbc->inBuffSize = neededInSize;
3942 zbc->inBuff = (char*)malloc(neededInSize);
3943 if (zbc->inBuff == NULL) return ERROR(memory_allocation);
3945 if (zbc->outBuffSize < neededOutSize) {
3947 zbc->outBuffSize = neededOutSize;
3948 zbc->outBuff = (char*)malloc(neededOutSize);
3949 if (zbc->outBuff == NULL) return ERROR(memory_allocation);
3952 /* some data already loaded into headerBuffer : transfer into inBuff */
3953 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
3954 zbc->inPos = zbc->hPos;
3956 zbc->stage = ZBUFFv05ds_load;
3959 zbc->stage = ZBUFFv05ds_read;
3961 case ZBUFFv05ds_read:
3963 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3964 if (neededInSize==0) { /* end of frame */
3965 zbc->stage = ZBUFFv05ds_init;
3969 if ((size_t)(iend-ip) >= neededInSize) {
3970 /* directly decode from src */
3971 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3972 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3974 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3976 if (!decodedSize) break; /* this was just a header */
3977 zbc->outEnd = zbc->outStart + decodedSize;
3978 zbc->stage = ZBUFFv05ds_flush;
3981 if (ip==iend) { notDone = 0; break; } /* no more input */
3982 zbc->stage = ZBUFFv05ds_load;
3985 case ZBUFFv05ds_load:
3987 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3988 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */
3990 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */
3991 loadedSize = ZBUFFv05_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
3993 zbc->inPos += loadedSize;
3994 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
3996 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3997 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3998 zbc->inBuff, neededInSize);
3999 if (ZSTDv05_isError(decodedSize)) return decodedSize;
4000 zbc->inPos = 0; /* input is consumed */
4001 if (!decodedSize) { zbc->stage = ZBUFFv05ds_read; break; } /* this was just a header */
4002 zbc->outEnd = zbc->outStart + decodedSize;
4003 zbc->stage = ZBUFFv05ds_flush;
4004 // break; /* ZBUFFv05ds_flush follows */
4008 case ZBUFFv05ds_flush:
4010 size_t toFlushSize = zbc->outEnd - zbc->outStart;
4011 size_t flushedSize = ZBUFFv05_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
4013 zbc->outStart += flushedSize;
4014 if (flushedSize == toFlushSize) {
4015 zbc->stage = ZBUFFv05ds_read;
4016 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
4017 zbc->outStart = zbc->outEnd = 0;
4020 /* cannot flush everything */
4024 default: return ERROR(GENERIC); /* impossible */
4027 *srcSizePtr = ip-istart;
4028 *maxDstSizePtr = op-ostart;
4030 { size_t nextSrcSizeHint = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
4031 if (nextSrcSizeHint > ZBUFFv05_blockHeaderSize) nextSrcSizeHint+= ZBUFFv05_blockHeaderSize; /* get next block header too */
4032 nextSrcSizeHint -= zbc->inPos; /* already loaded*/
4033 return nextSrcSizeHint;
4039 /* *************************************
4041 ***************************************/
4042 unsigned ZBUFFv05_isError(size_t errorCode) { return ERR_isError(errorCode); }
4043 const char* ZBUFFv05_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
4045 size_t ZBUFFv05_recommendedDInSize(void) { return BLOCKSIZE + ZBUFFv05_blockHeaderSize /* block header size*/ ; }
4046 size_t ZBUFFv05_recommendedDOutSize(void) { return BLOCKSIZE; }