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 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
497 /*-*******************************************
498 * Shared functions to include for inlining
499 *********************************************/
500 static void ZSTDv05_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
502 #define COPY8(d,s) { ZSTDv05_copy8(d,s); d+=8; s+=8; }
504 /*! ZSTDv05_wildcopy() :
505 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
506 MEM_STATIC void ZSTDv05_wildcopy(void* dst, const void* src, ptrdiff_t length)
508 const BYTE* ip = (const BYTE*)src;
509 BYTE* op = (BYTE*)dst;
510 BYTE* const oend = op + length;
517 /*-*******************************************
519 *********************************************/
528 BYTE* litLengthStart;
530 BYTE* matchLengthStart;
535 U32* matchLengthFreq;
547 #endif /* ZSTDv05_CCOMMON_H_MODULE */
548 /* ******************************************************************
549 FSEv05 : Finite State Entropy coder
551 Copyright (C) 2013-2015, Yann Collet.
553 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
555 Redistribution and use in source and binary forms, with or without
556 modification, are permitted provided that the following conditions are
559 * Redistributions of source code must retain the above copyright
560 notice, this list of conditions and the following disclaimer.
561 * Redistributions in binary form must reproduce the above
562 copyright notice, this list of conditions and the following disclaimer
563 in the documentation and/or other materials provided with the
566 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
567 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
568 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
569 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
570 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
571 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
572 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
573 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
574 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
575 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
576 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
578 You can contact the author at :
579 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
580 - Public forum : https://groups.google.com/forum/#!forum/lz4c
581 ****************************************************************** */
585 #if defined (__cplusplus)
590 /* *****************************************
592 ******************************************/
593 #include <stddef.h> /* size_t, ptrdiff_t */
596 /*-****************************************
597 * FSEv05 simple functions
598 ******************************************/
599 size_t FSEv05_decompress(void* dst, size_t maxDstSize,
600 const void* cSrc, size_t cSrcSize);
603 Decompress FSEv05 data from buffer 'cSrc', of size 'cSrcSize',
604 into already allocated destination buffer 'dst', of size 'maxDstSize'.
605 return : size of regenerated data (<= maxDstSize)
606 or an error code, which can be tested using FSEv05_isError()
608 ** Important ** : FSEv05_decompress() doesn't decompress non-compressible nor RLE data !!!
609 Why ? : making this distinction requires a header.
610 Header management is intentionally delegated to the user layer, which can better manage special cases.
614 /* *****************************************
616 ******************************************/
617 /* Error Management */
618 unsigned FSEv05_isError(size_t code); /* tells if a return value is an error code */
619 const char* FSEv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
624 /* *****************************************
625 * FSEv05 detailed API
626 ******************************************/
627 /* *** DECOMPRESSION *** */
631 Read compactly saved 'normalizedCounter' from 'rBuffer'.
632 return : size read from 'rBuffer'
633 or an errorCode, which can be tested using FSEv05_isError()
634 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
635 size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
638 Constructor and Destructor of type FSEv05_DTable
639 Note that its size depends on 'tableLog' */
640 typedef unsigned FSEv05_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
641 FSEv05_DTable* FSEv05_createDTable(unsigned tableLog);
642 void FSEv05_freeDTable(FSEv05_DTable* dt);
645 FSEv05_buildDTable():
646 Builds 'dt', which must be already allocated, using FSEv05_createDTable()
648 or an errorCode, which can be tested using FSEv05_isError() */
649 size_t FSEv05_buildDTable (FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
652 FSEv05_decompress_usingDTable():
653 Decompress compressed source @cSrc of size @cSrcSize using `dt`
654 into `dst` which must be already allocated.
655 @return : size of regenerated data (necessarily <= @dstCapacity)
656 or an errorCode, which can be tested using FSEv05_isError() */
657 size_t FSEv05_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv05_DTable* dt);
661 #if defined (__cplusplus)
665 #endif /* FSEv05_H */
666 /* ******************************************************************
668 Part of FSEv05 library
669 header file (to include)
670 Copyright (C) 2013-2016, Yann Collet.
672 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
674 Redistribution and use in source and binary forms, with or without
675 modification, are permitted provided that the following conditions are
678 * Redistributions of source code must retain the above copyright
679 notice, this list of conditions and the following disclaimer.
680 * Redistributions in binary form must reproduce the above
681 copyright notice, this list of conditions and the following disclaimer
682 in the documentation and/or other materials provided with the
685 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
686 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
687 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
688 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
689 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
690 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
691 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
692 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
693 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
694 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
695 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
697 You can contact the author at :
698 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
699 ****************************************************************** */
700 #ifndef BITv05STREAM_H_MODULE
701 #define BITv05STREAM_H_MODULE
703 #if defined (__cplusplus)
709 * This API consists of small unitary functions, which highly benefit from being inlined.
710 * Since link-time-optimization is not available for all compilers,
711 * these functions are defined into a .h to be included.
716 /*-********************************************
717 * bitStream decoding API (read backward)
718 **********************************************/
722 unsigned bitsConsumed;
727 typedef enum { BITv05_DStream_unfinished = 0,
728 BITv05_DStream_endOfBuffer = 1,
729 BITv05_DStream_completed = 2,
730 BITv05_DStream_overflow = 3 } BITv05_DStream_status; /* result of BITv05_reloadDStream() */
731 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
733 MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
734 MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits);
735 MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD);
736 MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* bitD);
739 /*-****************************************
741 ******************************************/
742 MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, unsigned nbBits);
743 /* faster, but works only if nbBits >= 1 */
747 /*-**************************************************************
749 ****************************************************************/
750 MEM_STATIC unsigned BITv05_highbit32 (U32 val)
752 # if defined(_MSC_VER) /* Visual */
754 _BitScanReverse ( &r, val );
756 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
757 return 31 - __builtin_clz (val);
758 # else /* Software version */
759 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 };
767 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
774 /*-********************************************************
776 **********************************************************/
777 /*!BITv05_initDStream
778 * Initialize a BITv05_DStream_t.
779 * @bitD : a pointer to an already allocated BITv05_DStream_t structure
780 * @srcBuffer must point at the beginning of a bitStream
781 * @srcSize must be the exact size of the bitStream
782 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
784 MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
786 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
788 if (srcSize >= sizeof(size_t)) { /* normal case */
790 bitD->start = (const char*)srcBuffer;
791 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
792 bitD->bitContainer = MEM_readLEST(bitD->ptr);
793 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
794 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
795 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
798 bitD->start = (const char*)srcBuffer;
799 bitD->ptr = bitD->start;
800 bitD->bitContainer = *(const BYTE*)(bitD->start);
803 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
804 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
805 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
806 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
807 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
808 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */
811 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
812 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
813 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
814 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
820 MEM_STATIC size_t BITv05_lookBits(BITv05_DStream_t* bitD, U32 nbBits)
822 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
823 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
826 /*! BITv05_lookBitsFast :
827 * unsafe version; only works only if nbBits >= 1 */
828 MEM_STATIC size_t BITv05_lookBitsFast(BITv05_DStream_t* bitD, U32 nbBits)
830 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
831 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
834 MEM_STATIC void BITv05_skipBits(BITv05_DStream_t* bitD, U32 nbBits)
836 bitD->bitsConsumed += nbBits;
839 MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, U32 nbBits)
841 size_t value = BITv05_lookBits(bitD, nbBits);
842 BITv05_skipBits(bitD, nbBits);
846 /*!BITv05_readBitsFast :
847 * unsafe version; only works only if nbBits >= 1 */
848 MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, U32 nbBits)
850 size_t value = BITv05_lookBitsFast(bitD, nbBits);
851 BITv05_skipBits(bitD, nbBits);
855 MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD)
857 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
858 return BITv05_DStream_overflow;
860 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
861 bitD->ptr -= bitD->bitsConsumed >> 3;
862 bitD->bitsConsumed &= 7;
863 bitD->bitContainer = MEM_readLEST(bitD->ptr);
864 return BITv05_DStream_unfinished;
866 if (bitD->ptr == bitD->start) {
867 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv05_DStream_endOfBuffer;
868 return BITv05_DStream_completed;
871 U32 nbBytes = bitD->bitsConsumed >> 3;
872 BITv05_DStream_status result = BITv05_DStream_unfinished;
873 if (bitD->ptr - nbBytes < bitD->start) {
874 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
875 result = BITv05_DStream_endOfBuffer;
877 bitD->ptr -= nbBytes;
878 bitD->bitsConsumed -= nbBytes*8;
879 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
884 /*! BITv05_endOfDStream
885 * @return Tells if DStream has reached its exact end
887 MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* DStream)
889 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
892 #if defined (__cplusplus)
896 #endif /* BITv05STREAM_H_MODULE */
897 /* ******************************************************************
898 FSEv05 : Finite State Entropy coder
899 header file for static linking (only)
900 Copyright (C) 2013-2015, Yann Collet
902 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
904 Redistribution and use in source and binary forms, with or without
905 modification, are permitted provided that the following conditions are
908 * Redistributions of source code must retain the above copyright
909 notice, this list of conditions and the following disclaimer.
910 * Redistributions in binary form must reproduce the above
911 copyright notice, this list of conditions and the following disclaimer
912 in the documentation and/or other materials provided with the
915 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
916 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
917 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
918 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
919 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
920 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
921 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
922 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
923 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
924 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
925 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
927 You can contact the author at :
928 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
929 - Public forum : https://groups.google.com/forum/#!forum/lz4c
930 ****************************************************************** */
931 #ifndef FSEv05_STATIC_H
932 #define FSEv05_STATIC_H
934 #if defined (__cplusplus)
940 /* *****************************************
942 *******************************************/
943 /* It is possible to statically allocate FSEv05 CTable/DTable as a table of unsigned using below macros */
944 #define FSEv05_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
947 /* *****************************************
948 * FSEv05 advanced API
949 *******************************************/
950 size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits);
951 /* build a fake FSEv05_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
953 size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, unsigned char symbolValue);
954 /* build a fake FSEv05_DTable, designed to always generate the same symbolValue */
958 /* *****************************************
959 * FSEv05 symbol decompression API
960 *******************************************/
964 const void* table; /* precise table may vary, depending on U16 */
968 static void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt);
970 static unsigned char FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
972 static unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr);
976 /* *****************************************
978 *******************************************/
979 static unsigned char FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
980 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
983 /* *****************************************
984 * Implementation of inlined functions
985 *******************************************/
991 } FSEv05_DTableHeader; /* sizeof U32 */
995 unsigned short newState;
996 unsigned char symbol;
997 unsigned char nbBits;
998 } FSEv05_decode_t; /* size == U32 */
1000 MEM_STATIC void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt)
1002 const void* ptr = dt;
1003 const FSEv05_DTableHeader* const DTableH = (const FSEv05_DTableHeader*)ptr;
1004 DStatePtr->state = BITv05_readBits(bitD, DTableH->tableLog);
1005 BITv05_reloadDStream(bitD);
1006 DStatePtr->table = dt + 1;
1009 MEM_STATIC BYTE FSEv05_peakSymbol(FSEv05_DState_t* DStatePtr)
1011 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1012 return DInfo.symbol;
1015 MEM_STATIC BYTE FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
1017 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1018 const U32 nbBits = DInfo.nbBits;
1019 BYTE symbol = DInfo.symbol;
1020 size_t lowBits = BITv05_readBits(bitD, nbBits);
1022 DStatePtr->state = DInfo.newState + lowBits;
1026 MEM_STATIC BYTE FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
1028 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1029 const U32 nbBits = DInfo.nbBits;
1030 BYTE symbol = DInfo.symbol;
1031 size_t lowBits = BITv05_readBitsFast(bitD, nbBits);
1033 DStatePtr->state = DInfo.newState + lowBits;
1037 MEM_STATIC unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr)
1039 return DStatePtr->state == 0;
1043 #if defined (__cplusplus)
1047 #endif /* FSEv05_STATIC_H */
1048 /* ******************************************************************
1049 FSEv05 : Finite State Entropy coder
1050 Copyright (C) 2013-2015, Yann Collet.
1052 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1054 Redistribution and use in source and binary forms, with or without
1055 modification, are permitted provided that the following conditions are
1058 * Redistributions of source code must retain the above copyright
1059 notice, this list of conditions and the following disclaimer.
1060 * Redistributions in binary form must reproduce the above
1061 copyright notice, this list of conditions and the following disclaimer
1062 in the documentation and/or other materials provided with the
1065 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1066 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1067 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1068 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1069 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1070 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1071 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1072 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1073 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1074 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1075 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1077 You can contact the author at :
1078 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1079 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1080 ****************************************************************** */
1082 #ifndef FSEv05_COMMONDEFS_ONLY
1084 /* **************************************************************
1086 ****************************************************************/
1088 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1089 * Increasing memory usage improves compression ratio
1090 * Reduced memory usage can improve speed, due to cache effect
1091 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1092 #define FSEv05_MAX_MEMORY_USAGE 14
1093 #define FSEv05_DEFAULT_MEMORY_USAGE 13
1095 /*!FSEv05_MAX_SYMBOL_VALUE :
1096 * Maximum symbol value authorized.
1097 * Required for proper stack allocation */
1098 #define FSEv05_MAX_SYMBOL_VALUE 255
1101 /* **************************************************************
1102 * template functions type & suffix
1103 ****************************************************************/
1104 #define FSEv05_FUNCTION_TYPE BYTE
1105 #define FSEv05_FUNCTION_EXTENSION
1106 #define FSEv05_DECODE_TYPE FSEv05_decode_t
1109 #endif /* !FSEv05_COMMONDEFS_ONLY */
1111 /* **************************************************************
1112 * Compiler specifics
1113 ****************************************************************/
1114 #ifdef _MSC_VER /* Visual Studio */
1115 # define FORCE_INLINE static __forceinline
1116 # include <intrin.h> /* For Visual 2005 */
1117 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1118 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1120 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1122 # define FORCE_INLINE static inline __attribute__((always_inline))
1124 # define FORCE_INLINE static inline
1127 # define FORCE_INLINE static
1128 # endif /* __STDC_VERSION__ */
1132 /* **************************************************************
1134 ****************************************************************/
1135 #include <stdlib.h> /* malloc, free, qsort */
1136 #include <string.h> /* memcpy, memset */
1137 #include <stdio.h> /* printf (debug) */
1141 /* ***************************************************************
1143 *****************************************************************/
1144 #define FSEv05_MAX_TABLELOG (FSEv05_MAX_MEMORY_USAGE-2)
1145 #define FSEv05_MAX_TABLESIZE (1U<<FSEv05_MAX_TABLELOG)
1146 #define FSEv05_MAXTABLESIZE_MASK (FSEv05_MAX_TABLESIZE-1)
1147 #define FSEv05_DEFAULT_TABLELOG (FSEv05_DEFAULT_MEMORY_USAGE-2)
1148 #define FSEv05_MIN_TABLELOG 5
1150 #define FSEv05_TABLELOG_ABSOLUTE_MAX 15
1151 #if FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX
1152 #error "FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX is not supported"
1156 /* **************************************************************
1158 ****************************************************************/
1159 #define FSEv05_STATIC_ASSERT(c) { enum { FSEv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1162 /* **************************************************************
1164 ****************************************************************/
1165 typedef U32 DTable_max_t[FSEv05_DTABLE_SIZE_U32(FSEv05_MAX_TABLELOG)];
1168 /* **************************************************************
1170 ****************************************************************/
1172 designed to be included
1173 for type-specific functions (template emulation in C)
1174 Objective is to write these functions only once, for improved maintenance
1178 #ifndef FSEv05_FUNCTION_EXTENSION
1179 # error "FSEv05_FUNCTION_EXTENSION must be defined"
1181 #ifndef FSEv05_FUNCTION_TYPE
1182 # error "FSEv05_FUNCTION_TYPE must be defined"
1185 /* Function names */
1186 #define FSEv05_CAT(X,Y) X##Y
1187 #define FSEv05_FUNCTION_NAME(X,Y) FSEv05_CAT(X,Y)
1188 #define FSEv05_TYPE_NAME(X,Y) FSEv05_CAT(X,Y)
1191 /* Function templates */
1192 static U32 FSEv05_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1196 FSEv05_DTable* FSEv05_createDTable (unsigned tableLog)
1198 if (tableLog > FSEv05_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv05_TABLELOG_ABSOLUTE_MAX;
1199 return (FSEv05_DTable*)malloc( FSEv05_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1202 void FSEv05_freeDTable (FSEv05_DTable* dt)
1207 size_t FSEv05_buildDTable(FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1209 FSEv05_DTableHeader DTableH;
1210 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */
1211 FSEv05_DECODE_TYPE* const tableDecode = (FSEv05_DECODE_TYPE*) (tdPtr);
1212 const U32 tableSize = 1 << tableLog;
1213 const U32 tableMask = tableSize-1;
1214 const U32 step = FSEv05_tableStep(tableSize);
1215 U16 symbolNext[FSEv05_MAX_SYMBOL_VALUE+1];
1217 U32 highThreshold = tableSize-1;
1218 const S16 largeLimit= (S16)(1 << (tableLog-1));
1223 if (maxSymbolValue > FSEv05_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1224 if (tableLog > FSEv05_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1226 /* Init, lay down lowprob symbols */
1227 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 */
1228 DTableH.tableLog = (U16)tableLog;
1229 for (s=0; s<=maxSymbolValue; s++) {
1230 if (normalizedCounter[s]==-1) {
1231 tableDecode[highThreshold--].symbol = (FSEv05_FUNCTION_TYPE)s;
1234 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1235 symbolNext[s] = normalizedCounter[s];
1238 /* Spread symbols */
1239 for (s=0; s<=maxSymbolValue; s++) {
1241 for (i=0; i<normalizedCounter[s]; i++) {
1242 tableDecode[position].symbol = (FSEv05_FUNCTION_TYPE)s;
1243 position = (position + step) & tableMask;
1244 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1247 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1249 /* Build Decoding table */
1252 for (i=0; i<tableSize; i++) {
1253 FSEv05_FUNCTION_TYPE symbol = (FSEv05_FUNCTION_TYPE)(tableDecode[i].symbol);
1254 U16 nextState = symbolNext[symbol]++;
1255 tableDecode[i].nbBits = (BYTE) (tableLog - BITv05_highbit32 ((U32)nextState) );
1256 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1259 DTableH.fastMode = (U16)noLarge;
1260 memcpy(dt, &DTableH, sizeof(DTableH));
1265 #ifndef FSEv05_COMMONDEFS_ONLY
1266 /*-****************************************
1267 * FSEv05 helper functions
1268 ******************************************/
1269 unsigned FSEv05_isError(size_t code) { return ERR_isError(code); }
1271 const char* FSEv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1274 /*-**************************************************************
1275 * FSEv05 NCount encoding-decoding
1276 ****************************************************************/
1277 static short FSEv05_abs(short a) { return a<0 ? -a : a; }
1280 size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1281 const void* headerBuffer, size_t hbSize)
1283 const BYTE* const istart = (const BYTE*) headerBuffer;
1284 const BYTE* const iend = istart + hbSize;
1285 const BYTE* ip = istart;
1291 unsigned charnum = 0;
1294 if (hbSize < 4) return ERROR(srcSize_wrong);
1295 bitStream = MEM_readLE32(ip);
1296 nbBits = (bitStream & 0xF) + FSEv05_MIN_TABLELOG; /* extract tableLog */
1297 if (nbBits > FSEv05_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1300 *tableLogPtr = nbBits;
1301 remaining = (1<<nbBits)+1;
1302 threshold = 1<<nbBits;
1305 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1307 unsigned n0 = charnum;
1308 while ((bitStream & 0xFFFF) == 0xFFFF) {
1312 bitStream = MEM_readLE32(ip) >> bitCount;
1317 while ((bitStream & 3) == 3) {
1322 n0 += bitStream & 3;
1324 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1325 while (charnum < n0) normalizedCounter[charnum++] = 0;
1326 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1329 bitStream = MEM_readLE32(ip) >> bitCount;
1335 const short max = (short)((2*threshold-1)-remaining);
1338 if ((bitStream & (threshold-1)) < (U32)max) {
1339 count = (short)(bitStream & (threshold-1));
1340 bitCount += nbBits-1;
1342 count = (short)(bitStream & (2*threshold-1));
1343 if (count >= threshold) count -= max;
1347 count--; /* extra accuracy */
1348 remaining -= FSEv05_abs(count);
1349 normalizedCounter[charnum++] = count;
1351 while (remaining < threshold) {
1356 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1360 bitCount -= (int)(8 * (iend - 4 - ip));
1363 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1365 if (remaining != 1) return ERROR(GENERIC);
1366 *maxSVPtr = charnum-1;
1368 ip += (bitCount+7)>>3;
1369 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1375 /*-*******************************************************
1376 * Decompression (Byte symbols)
1377 *********************************************************/
1378 size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, BYTE symbolValue)
1381 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1382 void* dPtr = dt + 1;
1383 FSEv05_decode_t* const cell = (FSEv05_decode_t*)dPtr;
1385 DTableH->tableLog = 0;
1386 DTableH->fastMode = 0;
1389 cell->symbol = symbolValue;
1396 size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits)
1399 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1400 void* dPtr = dt + 1;
1401 FSEv05_decode_t* const dinfo = (FSEv05_decode_t*)dPtr;
1402 const unsigned tableSize = 1 << nbBits;
1403 const unsigned tableMask = tableSize - 1;
1404 const unsigned maxSymbolValue = tableMask;
1408 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1410 /* Build Decoding Table */
1411 DTableH->tableLog = (U16)nbBits;
1412 DTableH->fastMode = 1;
1413 for (s=0; s<=maxSymbolValue; s++) {
1414 dinfo[s].newState = 0;
1415 dinfo[s].symbol = (BYTE)s;
1416 dinfo[s].nbBits = (BYTE)nbBits;
1422 FORCE_INLINE size_t FSEv05_decompress_usingDTable_generic(
1423 void* dst, size_t maxDstSize,
1424 const void* cSrc, size_t cSrcSize,
1425 const FSEv05_DTable* dt, const unsigned fast)
1427 BYTE* const ostart = (BYTE*) dst;
1429 BYTE* const omax = op + maxDstSize;
1430 BYTE* const olimit = omax-3;
1432 BITv05_DStream_t bitD;
1433 FSEv05_DState_t state1;
1434 FSEv05_DState_t state2;
1438 errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1439 if (FSEv05_isError(errorCode)) return errorCode;
1441 FSEv05_initDState(&state1, &bitD, dt);
1442 FSEv05_initDState(&state2, &bitD, dt);
1444 #define FSEv05_GETSYMBOL(statePtr) fast ? FSEv05_decodeSymbolFast(statePtr, &bitD) : FSEv05_decodeSymbol(statePtr, &bitD)
1446 /* 4 symbols per loop */
1447 for ( ; (BITv05_reloadDStream(&bitD)==BITv05_DStream_unfinished) && (op<olimit) ; op+=4) {
1448 op[0] = FSEv05_GETSYMBOL(&state1);
1450 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1451 BITv05_reloadDStream(&bitD);
1453 op[1] = FSEv05_GETSYMBOL(&state2);
1455 if (FSEv05_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1456 { if (BITv05_reloadDStream(&bitD) > BITv05_DStream_unfinished) { op+=2; break; } }
1458 op[2] = FSEv05_GETSYMBOL(&state1);
1460 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1461 BITv05_reloadDStream(&bitD);
1463 op[3] = FSEv05_GETSYMBOL(&state2);
1467 /* note : BITv05_reloadDStream(&bitD) >= FSEv05_DStream_partiallyFilled; Ends at exactly BITv05_DStream_completed */
1469 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state1))) )
1472 *op++ = FSEv05_GETSYMBOL(&state1);
1474 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state2))) )
1477 *op++ = FSEv05_GETSYMBOL(&state2);
1481 if (BITv05_endOfDStream(&bitD) && FSEv05_endOfDState(&state1) && FSEv05_endOfDState(&state2))
1484 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1486 return ERROR(corruption_detected);
1490 size_t FSEv05_decompress_usingDTable(void* dst, size_t originalSize,
1491 const void* cSrc, size_t cSrcSize,
1492 const FSEv05_DTable* dt)
1494 const void* ptr = dt;
1495 const FSEv05_DTableHeader* DTableH = (const FSEv05_DTableHeader*)ptr;
1496 const U32 fastMode = DTableH->fastMode;
1498 /* select fast mode (static) */
1499 if (fastMode) return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1500 return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1504 size_t FSEv05_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1506 const BYTE* const istart = (const BYTE*)cSrc;
1507 const BYTE* ip = istart;
1508 short counting[FSEv05_MAX_SYMBOL_VALUE+1];
1509 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1511 unsigned maxSymbolValue = FSEv05_MAX_SYMBOL_VALUE;
1514 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1516 /* normal FSEv05 decoding mode */
1517 errorCode = FSEv05_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1518 if (FSEv05_isError(errorCode)) return errorCode;
1519 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1521 cSrcSize -= errorCode;
1523 errorCode = FSEv05_buildDTable (dt, counting, maxSymbolValue, tableLog);
1524 if (FSEv05_isError(errorCode)) return errorCode;
1526 /* always return, even if it is an error code */
1527 return FSEv05_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1532 #endif /* FSEv05_COMMONDEFS_ONLY */
1533 /* ******************************************************************
1534 Huff0 : Huffman coder, part of New Generation Entropy library
1536 Copyright (C) 2013-2016, Yann Collet.
1538 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1540 Redistribution and use in source and binary forms, with or without
1541 modification, are permitted provided that the following conditions are
1544 * Redistributions of source code must retain the above copyright
1545 notice, this list of conditions and the following disclaimer.
1546 * Redistributions in binary form must reproduce the above
1547 copyright notice, this list of conditions and the following disclaimer
1548 in the documentation and/or other materials provided with the
1551 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1552 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1553 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1554 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1555 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1556 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1557 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1558 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1559 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1560 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1561 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1563 You can contact the author at :
1564 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1565 ****************************************************************** */
1569 #if defined (__cplusplus)
1575 /* ****************************************
1576 * Huff0 simple functions
1577 ******************************************/
1578 size_t HUFv05_decompress(void* dst, size_t dstSize,
1579 const void* cSrc, size_t cSrcSize);
1581 HUFv05_decompress():
1582 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1583 into already allocated destination buffer 'dst', of size 'dstSize'.
1584 @dstSize : must be the **exact** size of original (uncompressed) data.
1585 Note : in contrast with FSEv05, HUFv05_decompress can regenerate
1586 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1587 because it knows size to regenerate.
1588 @return : size of regenerated data (== dstSize)
1589 or an error code, which can be tested using HUFv05_isError()
1593 /* ****************************************
1595 ******************************************/
1596 /* Error Management */
1597 unsigned HUFv05_isError(size_t code); /* tells if a return value is an error code */
1598 const char* HUFv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
1601 #if defined (__cplusplus)
1606 /* ******************************************************************
1607 Huff0 : Huffman codec, part of New Generation Entropy library
1608 header file, for static linking only
1609 Copyright (C) 2013-2016, Yann Collet
1611 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1613 Redistribution and use in source and binary forms, with or without
1614 modification, are permitted provided that the following conditions are
1617 * Redistributions of source code must retain the above copyright
1618 notice, this list of conditions and the following disclaimer.
1619 * Redistributions in binary form must reproduce the above
1620 copyright notice, this list of conditions and the following disclaimer
1621 in the documentation and/or other materials provided with the
1624 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1625 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1626 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1627 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1628 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1629 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1630 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1631 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1632 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1633 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1634 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1636 You can contact the author at :
1637 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1638 ****************************************************************** */
1639 #ifndef HUF0_STATIC_H
1640 #define HUF0_STATIC_H
1642 #if defined (__cplusplus)
1648 /* ****************************************
1650 ******************************************/
1651 /* static allocation of Huff0's DTable */
1652 #define HUFv05_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1653 #define HUFv05_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1654 unsigned short DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1655 #define HUFv05_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1656 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1657 #define HUFv05_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1658 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1661 /* ****************************************
1662 * Advanced decompression functions
1663 ******************************************/
1664 size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1665 size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1668 /* ****************************************
1669 * Huff0 detailed API
1670 ******************************************/
1672 HUFv05_decompress() does the following:
1673 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1674 2. build Huffman table from save, using HUFv05_readDTableXn()
1675 3. decode 1 or 4 segments in parallel using HUFv05_decompressSXn_usingDTable
1677 size_t HUFv05_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1678 size_t HUFv05_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1680 size_t HUFv05_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1681 size_t HUFv05_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1684 /* single stream variants */
1686 size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1687 size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1689 size_t HUFv05_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1690 size_t HUFv05_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1694 #if defined (__cplusplus)
1698 #endif /* HUF0_STATIC_H */
1699 /* ******************************************************************
1700 Huff0 : Huffman coder, part of New Generation Entropy library
1701 Copyright (C) 2013-2015, Yann Collet.
1703 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1705 Redistribution and use in source and binary forms, with or without
1706 modification, are permitted provided that the following conditions are
1709 * Redistributions of source code must retain the above copyright
1710 notice, this list of conditions and the following disclaimer.
1711 * Redistributions in binary form must reproduce the above
1712 copyright notice, this list of conditions and the following disclaimer
1713 in the documentation and/or other materials provided with the
1716 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1717 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1718 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1719 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1720 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1721 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1722 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1723 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1724 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1725 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1726 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1728 You can contact the author at :
1729 - FSEv05+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1730 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1731 ****************************************************************** */
1733 /* **************************************************************
1734 * Compiler specifics
1735 ****************************************************************/
1736 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1737 /* inline is defined */
1738 #elif defined(_MSC_VER)
1739 # define inline __inline
1741 # define inline /* disable inline */
1745 #ifdef _MSC_VER /* Visual Studio */
1746 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1750 /* **************************************************************
1752 ****************************************************************/
1753 #include <stdlib.h> /* malloc, free, qsort */
1754 #include <string.h> /* memcpy, memset */
1755 #include <stdio.h> /* printf (debug) */
1758 /* **************************************************************
1760 ****************************************************************/
1761 #define HUFv05_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv05_MAX_TABLELOG. Beyond that value, code does not work */
1762 #define HUFv05_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv05_ABSOLUTEMAX_TABLELOG */
1763 #define HUFv05_DEFAULT_TABLELOG HUFv05_MAX_TABLELOG /* tableLog by default, when not specified */
1764 #define HUFv05_MAX_SYMBOL_VALUE 255
1765 #if (HUFv05_MAX_TABLELOG > HUFv05_ABSOLUTEMAX_TABLELOG)
1766 # error "HUFv05_MAX_TABLELOG is too large !"
1770 /* **************************************************************
1772 ****************************************************************/
1773 unsigned HUFv05_isError(size_t code) { return ERR_isError(code); }
1774 const char* HUFv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1775 #define HUFv05_STATIC_ASSERT(c) { enum { HUFv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1778 /* *******************************************************
1779 * Huff0 : Huffman block decompression
1780 *********************************************************/
1781 typedef struct { BYTE byte; BYTE nbBits; } HUFv05_DEltX2; /* single-symbol decoding */
1783 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv05_DEltX4; /* double-symbols decoding */
1785 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1787 /*! HUFv05_readStats
1788 Read compact Huffman tree, saved by HUFv05_writeCTable
1789 @huffWeight : destination buffer
1790 @return : size read from `src`
1792 static size_t HUFv05_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1793 U32* nbSymbolsPtr, U32* tableLogPtr,
1794 const void* src, size_t srcSize)
1798 const BYTE* ip = (const BYTE*) src;
1803 if (!srcSize) return ERROR(srcSize_wrong);
1805 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1807 if (iSize >= 128) { /* special header */
1808 if (iSize >= (242)) { /* RLE */
1809 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1810 oSize = l[iSize-242];
1811 memset(huffWeight, 1, hwSize);
1814 else { /* Incompressible */
1815 oSize = iSize - 127;
1816 iSize = ((oSize+1)/2);
1817 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1818 if (oSize >= hwSize) return ERROR(corruption_detected);
1820 for (n=0; n<oSize; n+=2) {
1821 huffWeight[n] = ip[n/2] >> 4;
1822 huffWeight[n+1] = ip[n/2] & 15;
1824 else { /* header compressed with FSEv05 (normal case) */
1825 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1826 oSize = FSEv05_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1827 if (FSEv05_isError(oSize)) return oSize;
1830 /* collect weight stats */
1831 memset(rankStats, 0, (HUFv05_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1833 for (n=0; n<oSize; n++) {
1834 if (huffWeight[n] >= HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1835 rankStats[huffWeight[n]]++;
1836 weightTotal += (1 << huffWeight[n]) >> 1;
1838 if (weightTotal == 0) return ERROR(corruption_detected);
1840 /* get last non-null symbol weight (implied, total must be 2^n) */
1841 tableLog = BITv05_highbit32(weightTotal) + 1;
1842 if (tableLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1843 { /* determine last weight */
1844 U32 total = 1 << tableLog;
1845 U32 rest = total - weightTotal;
1846 U32 verif = 1 << BITv05_highbit32(rest);
1847 U32 lastWeight = BITv05_highbit32(rest) + 1;
1848 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1849 huffWeight[oSize] = (BYTE)lastWeight;
1850 rankStats[lastWeight]++;
1853 /* check tree construction validity */
1854 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1857 *nbSymbolsPtr = (U32)(oSize+1);
1858 *tableLogPtr = tableLog;
1863 /*-***************************/
1864 /* single-symbol decoding */
1865 /*-***************************/
1867 size_t HUFv05_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1869 BYTE huffWeight[HUFv05_MAX_SYMBOL_VALUE + 1];
1870 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1876 void* const dtPtr = DTable + 1;
1877 HUFv05_DEltX2* const dt = (HUFv05_DEltX2*)dtPtr;
1879 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1880 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1882 iSize = HUFv05_readStats(huffWeight, HUFv05_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1883 if (HUFv05_isError(iSize)) return iSize;
1886 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1887 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
1891 for (n=1; n<=tableLog; n++) {
1892 U32 current = nextRankStart;
1893 nextRankStart += (rankVal[n] << (n-1));
1894 rankVal[n] = current;
1898 for (n=0; n<nbSymbols; n++) {
1899 const U32 w = huffWeight[n];
1900 const U32 length = (1 << w) >> 1;
1903 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1904 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1906 rankVal[w] += length;
1912 static BYTE HUFv05_decodeSymbolX2(BITv05_DStream_t* Dstream, const HUFv05_DEltX2* dt, const U32 dtLog)
1914 const size_t val = BITv05_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1915 const BYTE c = dt[val].byte;
1916 BITv05_skipBits(Dstream, dt[val].nbBits);
1920 #define HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1921 *ptr++ = HUFv05_decodeSymbolX2(DStreamPtr, dt, dtLog)
1923 #define HUFv05_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1924 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
1925 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1927 #define HUFv05_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1929 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1931 static inline size_t HUFv05_decodeStreamX2(BYTE* p, BITv05_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv05_DEltX2* const dt, const U32 dtLog)
1933 BYTE* const pStart = p;
1935 /* up to 4 symbols at a time */
1936 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-4)) {
1937 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1938 HUFv05_DECODE_SYMBOLX2_1(p, bitDPtr);
1939 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1940 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1943 /* closer to the end */
1944 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd))
1945 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1947 /* no more data to retrieve from bitstream, hence no need to reload */
1949 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1954 size_t HUFv05_decompress1X2_usingDTable(
1955 void* dst, size_t dstSize,
1956 const void* cSrc, size_t cSrcSize,
1959 BYTE* op = (BYTE*)dst;
1960 BYTE* const oend = op + dstSize;
1961 const U32 dtLog = DTable[0];
1962 const void* dtPtr = DTable;
1963 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr)+1;
1964 BITv05_DStream_t bitD;
1966 if (dstSize <= cSrcSize) return ERROR(dstSize_tooSmall);
1967 { size_t const errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize);
1968 if (HUFv05_isError(errorCode)) return errorCode; }
1970 HUFv05_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1973 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
1978 size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1980 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
1981 const BYTE* ip = (const BYTE*) cSrc;
1984 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
1985 if (HUFv05_isError(errorCode)) return errorCode;
1986 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1988 cSrcSize -= errorCode;
1990 return HUFv05_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1994 size_t HUFv05_decompress4X2_usingDTable(
1995 void* dst, size_t dstSize,
1996 const void* cSrc, size_t cSrcSize,
1999 const BYTE* const istart = (const BYTE*) cSrc;
2000 BYTE* const ostart = (BYTE*) dst;
2001 BYTE* const oend = ostart + dstSize;
2002 const void* const dtPtr = DTable;
2003 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr) +1;
2004 const U32 dtLog = DTable[0];
2008 BITv05_DStream_t bitD1;
2009 BITv05_DStream_t bitD2;
2010 BITv05_DStream_t bitD3;
2011 BITv05_DStream_t bitD4;
2012 const size_t length1 = MEM_readLE16(istart);
2013 const size_t length2 = MEM_readLE16(istart+2);
2014 const size_t length3 = MEM_readLE16(istart+4);
2016 const BYTE* const istart1 = istart + 6; /* jumpTable */
2017 const BYTE* const istart2 = istart1 + length1;
2018 const BYTE* const istart3 = istart2 + length2;
2019 const BYTE* const istart4 = istart3 + length3;
2020 const size_t segmentSize = (dstSize+3) / 4;
2021 BYTE* const opStart2 = ostart + segmentSize;
2022 BYTE* const opStart3 = opStart2 + segmentSize;
2023 BYTE* const opStart4 = opStart3 + segmentSize;
2025 BYTE* op2 = opStart2;
2026 BYTE* op3 = opStart3;
2027 BYTE* op4 = opStart4;
2031 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2033 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2034 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2035 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
2036 if (HUFv05_isError(errorCode)) return errorCode;
2037 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
2038 if (HUFv05_isError(errorCode)) return errorCode;
2039 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
2040 if (HUFv05_isError(errorCode)) return errorCode;
2041 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
2042 if (HUFv05_isError(errorCode)) return errorCode;
2044 /* 16-32 symbols per loop (4-8 symbols per stream) */
2045 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2046 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
2047 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
2048 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
2049 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2050 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2051 HUFv05_DECODE_SYMBOLX2_1(op1, &bitD1);
2052 HUFv05_DECODE_SYMBOLX2_1(op2, &bitD2);
2053 HUFv05_DECODE_SYMBOLX2_1(op3, &bitD3);
2054 HUFv05_DECODE_SYMBOLX2_1(op4, &bitD4);
2055 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
2056 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
2057 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2058 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2059 HUFv05_DECODE_SYMBOLX2_0(op1, &bitD1);
2060 HUFv05_DECODE_SYMBOLX2_0(op2, &bitD2);
2061 HUFv05_DECODE_SYMBOLX2_0(op3, &bitD3);
2062 HUFv05_DECODE_SYMBOLX2_0(op4, &bitD4);
2063 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2066 /* check corruption */
2067 if (op1 > opStart2) return ERROR(corruption_detected);
2068 if (op2 > opStart3) return ERROR(corruption_detected);
2069 if (op3 > opStart4) return ERROR(corruption_detected);
2070 /* note : op4 supposed already verified within main loop */
2072 /* finish bitStreams one by one */
2073 HUFv05_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2074 HUFv05_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2075 HUFv05_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2076 HUFv05_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2079 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2080 if (!endSignal) return ERROR(corruption_detected);
2087 size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2089 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
2090 const BYTE* ip = (const BYTE*) cSrc;
2093 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
2094 if (HUFv05_isError(errorCode)) return errorCode;
2095 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2097 cSrcSize -= errorCode;
2099 return HUFv05_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2103 /* *************************/
2104 /* double-symbols decoding */
2105 /* *************************/
2107 static void HUFv05_fillDTableX4Level2(HUFv05_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2108 const U32* rankValOrigin, const int minWeight,
2109 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2110 U32 nbBitsBaseline, U16 baseSeq)
2113 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2116 /* get pre-calculated rankVal */
2117 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2119 /* fill skipped values */
2121 U32 i, skipSize = rankVal[minWeight];
2122 MEM_writeLE16(&(DElt.sequence), baseSeq);
2123 DElt.nbBits = (BYTE)(consumed);
2125 for (i = 0; i < skipSize; i++)
2130 for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2131 const U32 symbol = sortedSymbols[s].symbol;
2132 const U32 weight = sortedSymbols[s].weight;
2133 const U32 nbBits = nbBitsBaseline - weight;
2134 const U32 length = 1 << (sizeLog-nbBits);
2135 const U32 start = rankVal[weight];
2137 const U32 end = start + length;
2139 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2140 DElt.nbBits = (BYTE)(nbBits + consumed);
2142 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2144 rankVal[weight] += length;
2148 typedef U32 rankVal_t[HUFv05_ABSOLUTEMAX_TABLELOG][HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2150 static void HUFv05_fillDTableX4(HUFv05_DEltX4* DTable, const U32 targetLog,
2151 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2152 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2153 const U32 nbBitsBaseline)
2155 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2156 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2157 const U32 minBits = nbBitsBaseline - maxWeight;
2160 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2163 for (s=0; s<sortedListSize; s++) {
2164 const U16 symbol = sortedList[s].symbol;
2165 const U32 weight = sortedList[s].weight;
2166 const U32 nbBits = nbBitsBaseline - weight;
2167 const U32 start = rankVal[weight];
2168 const U32 length = 1 << (targetLog-nbBits);
2170 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2172 int minWeight = nbBits + scaleLog;
2173 if (minWeight < 1) minWeight = 1;
2174 sortedRank = rankStart[minWeight];
2175 HUFv05_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2176 rankValOrigin[nbBits], minWeight,
2177 sortedList+sortedRank, sortedListSize-sortedRank,
2178 nbBitsBaseline, symbol);
2181 const U32 end = start + length;
2184 MEM_writeLE16(&(DElt.sequence), symbol);
2185 DElt.nbBits = (BYTE)(nbBits);
2187 for (i = start; i < end; i++)
2190 rankVal[weight] += length;
2194 size_t HUFv05_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2196 BYTE weightList[HUFv05_MAX_SYMBOL_VALUE + 1];
2197 sortedSymbol_t sortedSymbol[HUFv05_MAX_SYMBOL_VALUE + 1];
2198 U32 rankStats[HUFv05_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2199 U32 rankStart0[HUFv05_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2200 U32* const rankStart = rankStart0+1;
2202 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2203 const U32 memLog = DTable[0];
2205 void* dtPtr = DTable;
2206 HUFv05_DEltX4* const dt = ((HUFv05_DEltX4*)dtPtr) + 1;
2208 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
2209 if (memLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2210 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2212 iSize = HUFv05_readStats(weightList, HUFv05_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2213 if (HUFv05_isError(iSize)) return iSize;
2216 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2218 /* find maxWeight */
2219 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2221 /* Get start index of each weight */
2223 U32 w, nextRankStart = 0;
2224 for (w=1; w<=maxW; w++) {
2225 U32 current = nextRankStart;
2226 nextRankStart += rankStats[w];
2227 rankStart[w] = current;
2229 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2230 sizeOfSort = nextRankStart;
2233 /* sort symbols by weight */
2236 for (s=0; s<nbSymbols; s++) {
2237 U32 w = weightList[s];
2238 U32 r = rankStart[w]++;
2239 sortedSymbol[r].symbol = (BYTE)s;
2240 sortedSymbol[r].weight = (BYTE)w;
2242 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2247 const U32 minBits = tableLog+1 - maxW;
2248 U32 nextRankVal = 0;
2250 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2251 U32* rankVal0 = rankVal[0];
2252 for (w=1; w<=maxW; w++) {
2253 U32 current = nextRankVal;
2254 nextRankVal += rankStats[w] << (w+rescale);
2255 rankVal0[w] = current;
2257 for (consumed = minBits; consumed <= memLog - minBits; consumed++) {
2258 U32* rankValPtr = rankVal[consumed];
2259 for (w = 1; w <= maxW; w++) {
2260 rankValPtr[w] = rankVal0[w] >> consumed;
2263 HUFv05_fillDTableX4(dt, memLog,
2264 sortedSymbol, sizeOfSort,
2265 rankStart0, rankVal, maxW,
2272 static U32 HUFv05_decodeSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2274 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2275 memcpy(op, dt+val, 2);
2276 BITv05_skipBits(DStream, dt[val].nbBits);
2277 return dt[val].length;
2280 static U32 HUFv05_decodeLastSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2282 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2283 memcpy(op, dt+val, 1);
2284 if (dt[val].length==1) BITv05_skipBits(DStream, dt[val].nbBits);
2286 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2287 BITv05_skipBits(DStream, dt[val].nbBits);
2288 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2289 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 */
2295 #define HUFv05_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2296 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2298 #define HUFv05_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2299 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
2300 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2302 #define HUFv05_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2304 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2306 static inline size_t HUFv05_decodeStreamX4(BYTE* p, BITv05_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv05_DEltX4* const dt, const U32 dtLog)
2308 BYTE* const pStart = p;
2310 /* up to 8 symbols at a time */
2311 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd-7)) {
2312 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2313 HUFv05_DECODE_SYMBOLX4_1(p, bitDPtr);
2314 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2315 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2318 /* closer to the end */
2319 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-2))
2320 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2323 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2326 p += HUFv05_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2332 size_t HUFv05_decompress1X4_usingDTable(
2333 void* dst, size_t dstSize,
2334 const void* cSrc, size_t cSrcSize,
2337 const BYTE* const istart = (const BYTE*) cSrc;
2338 BYTE* const ostart = (BYTE*) dst;
2339 BYTE* const oend = ostart + dstSize;
2341 const U32 dtLog = DTable[0];
2342 const void* const dtPtr = DTable;
2343 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2347 BITv05_DStream_t bitD;
2348 errorCode = BITv05_initDStream(&bitD, istart, cSrcSize);
2349 if (HUFv05_isError(errorCode)) return errorCode;
2351 /* finish bitStreams one by one */
2352 HUFv05_decodeStreamX4(ostart, &bitD, oend, dt, dtLog);
2355 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
2361 size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2363 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2364 const BYTE* ip = (const BYTE*) cSrc;
2366 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2367 if (HUFv05_isError(hSize)) return hSize;
2368 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2372 return HUFv05_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2375 size_t HUFv05_decompress4X4_usingDTable(
2376 void* dst, size_t dstSize,
2377 const void* cSrc, size_t cSrcSize,
2380 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2383 const BYTE* const istart = (const BYTE*) cSrc;
2384 BYTE* const ostart = (BYTE*) dst;
2385 BYTE* const oend = ostart + dstSize;
2386 const void* const dtPtr = DTable;
2387 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2388 const U32 dtLog = DTable[0];
2392 BITv05_DStream_t bitD1;
2393 BITv05_DStream_t bitD2;
2394 BITv05_DStream_t bitD3;
2395 BITv05_DStream_t bitD4;
2396 const size_t length1 = MEM_readLE16(istart);
2397 const size_t length2 = MEM_readLE16(istart+2);
2398 const size_t length3 = MEM_readLE16(istart+4);
2400 const BYTE* const istart1 = istart + 6; /* jumpTable */
2401 const BYTE* const istart2 = istart1 + length1;
2402 const BYTE* const istart3 = istart2 + length2;
2403 const BYTE* const istart4 = istart3 + length3;
2404 const size_t segmentSize = (dstSize+3) / 4;
2405 BYTE* const opStart2 = ostart + segmentSize;
2406 BYTE* const opStart3 = opStart2 + segmentSize;
2407 BYTE* const opStart4 = opStart3 + segmentSize;
2409 BYTE* op2 = opStart2;
2410 BYTE* op3 = opStart3;
2411 BYTE* op4 = opStart4;
2414 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2415 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2416 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
2417 if (HUFv05_isError(errorCode)) return errorCode;
2418 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
2419 if (HUFv05_isError(errorCode)) return errorCode;
2420 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
2421 if (HUFv05_isError(errorCode)) return errorCode;
2422 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
2423 if (HUFv05_isError(errorCode)) return errorCode;
2425 /* 16-32 symbols per loop (4-8 symbols per stream) */
2426 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2427 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
2428 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2429 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2430 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2431 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2432 HUFv05_DECODE_SYMBOLX4_1(op1, &bitD1);
2433 HUFv05_DECODE_SYMBOLX4_1(op2, &bitD2);
2434 HUFv05_DECODE_SYMBOLX4_1(op3, &bitD3);
2435 HUFv05_DECODE_SYMBOLX4_1(op4, &bitD4);
2436 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2437 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2438 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2439 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2440 HUFv05_DECODE_SYMBOLX4_0(op1, &bitD1);
2441 HUFv05_DECODE_SYMBOLX4_0(op2, &bitD2);
2442 HUFv05_DECODE_SYMBOLX4_0(op3, &bitD3);
2443 HUFv05_DECODE_SYMBOLX4_0(op4, &bitD4);
2445 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2448 /* check corruption */
2449 if (op1 > opStart2) return ERROR(corruption_detected);
2450 if (op2 > opStart3) return ERROR(corruption_detected);
2451 if (op3 > opStart4) return ERROR(corruption_detected);
2452 /* note : op4 supposed already verified within main loop */
2454 /* finish bitStreams one by one */
2455 HUFv05_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2456 HUFv05_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2457 HUFv05_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2458 HUFv05_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2461 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2462 if (!endSignal) return ERROR(corruption_detected);
2470 size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2472 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2473 const BYTE* ip = (const BYTE*) cSrc;
2475 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2476 if (HUFv05_isError(hSize)) return hSize;
2477 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2481 return HUFv05_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2485 /* ********************************/
2486 /* Generic decompression selector */
2487 /* ********************************/
2489 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2490 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2492 /* single, double, quad */
2493 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2494 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2495 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2496 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2497 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2498 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2499 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2500 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2501 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2502 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2503 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2504 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2505 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2506 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2507 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2508 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2511 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2513 size_t HUFv05_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2515 static const decompressionAlgo decompress[3] = { HUFv05_decompress4X2, HUFv05_decompress4X4, NULL };
2516 /* estimate decompression time */
2518 const U32 D256 = (U32)(dstSize >> 8);
2523 /* validation checks */
2524 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2525 if (cSrcSize >= dstSize) return ERROR(corruption_detected); /* invalid, or not compressed, but not compressed already dealt with */
2526 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2528 /* decoder timing evaluation */
2529 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2531 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2533 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2535 if (Dtime[1] < Dtime[0]) algoNb = 1;
2537 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2539 //return HUFv05_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2540 //return HUFv05_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2541 //return HUFv05_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2544 zstd - standard compression library
2545 Copyright (C) 2014-2016, Yann Collet.
2547 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2549 Redistribution and use in source and binary forms, with or without
2550 modification, are permitted provided that the following conditions are
2552 * Redistributions of source code must retain the above copyright
2553 notice, this list of conditions and the following disclaimer.
2554 * Redistributions in binary form must reproduce the above
2555 copyright notice, this list of conditions and the following disclaimer
2556 in the documentation and/or other materials provided with the
2558 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2559 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2560 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2561 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2562 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2563 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2564 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2565 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2566 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2567 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2568 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2570 You can contact the author at :
2571 - zstd source repository : https://github.com/Cyan4973/zstd
2574 /* ***************************************************************
2576 *****************************************************************/
2579 * Select how default decompression function ZSTDv05_decompress() will allocate memory,
2580 * in memory stack (0), or in memory heap (1, requires malloc())
2582 #ifndef ZSTDv05_HEAPMODE
2583 # define ZSTDv05_HEAPMODE 1
2587 /*-*******************************************************
2589 *********************************************************/
2590 #include <stdlib.h> /* calloc */
2591 #include <string.h> /* memcpy, memmove */
2592 #include <stdio.h> /* debug only : printf */
2595 /*-*******************************************************
2596 * Compiler specifics
2597 *********************************************************/
2598 #ifdef _MSC_VER /* Visual Studio */
2599 # include <intrin.h> /* For Visual 2005 */
2600 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2601 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2605 /*-*************************************
2607 ***************************************/
2610 blockType_t blockType;
2612 } blockProperties_t;
2615 /* *******************************************************
2617 **********************************************************/
2618 static void ZSTDv05_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2621 /* *************************************
2623 ***************************************/
2624 /*! ZSTDv05_isError() :
2625 * tells if a return value is an error code */
2626 unsigned ZSTDv05_isError(size_t code) { return ERR_isError(code); }
2629 /*! ZSTDv05_getErrorName() :
2630 * provides error code string (useful for debugging) */
2631 const char* ZSTDv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
2634 /* *************************************************************
2635 * Context management
2636 ***************************************************************/
2637 typedef enum { ZSTDv05ds_getFrameHeaderSize, ZSTDv05ds_decodeFrameHeader,
2638 ZSTDv05ds_decodeBlockHeader, ZSTDv05ds_decompressBlock } ZSTDv05_dStage;
2640 struct ZSTDv05_DCtx_s
2642 FSEv05_DTable LLTable[FSEv05_DTABLE_SIZE_U32(LLFSEv05Log)];
2643 FSEv05_DTable OffTable[FSEv05_DTABLE_SIZE_U32(OffFSEv05Log)];
2644 FSEv05_DTable MLTable[FSEv05_DTABLE_SIZE_U32(MLFSEv05Log)];
2645 unsigned hufTableX4[HUFv05_DTABLE_SIZE(HufLog)];
2646 const void* previousDstEnd;
2649 const void* dictEnd;
2652 ZSTDv05_parameters params;
2653 blockType_t bType; /* used in ZSTDv05_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2654 ZSTDv05_dStage stage;
2655 U32 flagStaticTables;
2658 BYTE litBuffer[BLOCKSIZE + WILDCOPY_OVERLENGTH];
2659 BYTE headerBuffer[ZSTDv05_frameHeaderSize_max];
2660 }; /* typedef'd to ZSTDv05_DCtx within "zstd_static.h" */
2662 size_t ZSTDv05_sizeofDCtx (void); /* Hidden declaration */
2663 size_t ZSTDv05_sizeofDCtx (void) { return sizeof(ZSTDv05_DCtx); }
2665 size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx)
2667 dctx->expected = ZSTDv05_frameHeaderSize_min;
2668 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
2669 dctx->previousDstEnd = NULL;
2672 dctx->dictEnd = NULL;
2673 dctx->hufTableX4[0] = HufLog;
2674 dctx->flagStaticTables = 0;
2678 ZSTDv05_DCtx* ZSTDv05_createDCtx(void)
2680 ZSTDv05_DCtx* dctx = (ZSTDv05_DCtx*)malloc(sizeof(ZSTDv05_DCtx));
2681 if (dctx==NULL) return NULL;
2682 ZSTDv05_decompressBegin(dctx);
2686 size_t ZSTDv05_freeDCtx(ZSTDv05_DCtx* dctx)
2689 return 0; /* reserved as a potential error code in the future */
2692 void ZSTDv05_copyDCtx(ZSTDv05_DCtx* dstDCtx, const ZSTDv05_DCtx* srcDCtx)
2694 memcpy(dstDCtx, srcDCtx,
2695 sizeof(ZSTDv05_DCtx) - (BLOCKSIZE+WILDCOPY_OVERLENGTH + ZSTDv05_frameHeaderSize_max)); /* no need to copy workspace */
2699 /* *************************************************************
2700 * Decompression section
2701 ***************************************************************/
2703 /* Frame format description
2704 Frame Header - [ Block Header - Block ] - Frame End
2706 - 4 bytes - Magic Number : ZSTDv05_MAGICNUMBER (defined within zstd_internal.h)
2707 - 1 byte - Window Descriptor
2709 - 3 bytes, starting with a 2-bits descriptor
2710 Uncompressed, Compressed, Frame End, unused
2712 See Block Format Description
2714 - 3 bytes, compatible with Block Header
2717 /* Block format description
2719 Block = Literal Section - Sequences Section
2720 Prerequisite : size of (compressed) block, maximum size of regenerated data
2724 1.1) Header : 1-5 bytes
2726 00 compressed by Huff0
2728 10 is Raw (uncompressed)
2730 Note : using 01 => Huff0 with precomputed table ?
2731 Note : delta map ? => compressed ?
2733 1.1.1) Huff0-compressed literal block : 3-5 bytes
2734 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2735 srcSize < 1 KB => 3 bytes (2-2-10-10)
2736 srcSize < 16KB => 4 bytes (2-2-14-14)
2737 else => 5 bytes (2-2-18-18)
2738 big endian convention
2740 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2741 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2742 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2744 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2748 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2749 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
2750 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2752 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2756 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2757 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2758 srcSize < 1 KB => 3 bytes (2-2-10-10)
2759 srcSize < 16KB => 4 bytes (2-2-14-14)
2760 else => 5 bytes (2-2-18-18)
2761 big endian convention
2763 1- CTable available (stored into workspace ?)
2764 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2767 1.2) Literal block content
2769 1.2.1) Huff0 block, using sizes from header
2772 1.2.2) Huff0 block, using prepared table
2779 2) Sequences section
2784 /** ZSTDv05_decodeFrameHeader_Part1() :
2785 * decode the 1st part of the Frame Header, which tells Frame Header size.
2786 * srcSize must be == ZSTDv05_frameHeaderSize_min.
2787 * @return : the full size of the Frame Header */
2788 static size_t ZSTDv05_decodeFrameHeader_Part1(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2791 if (srcSize != ZSTDv05_frameHeaderSize_min)
2792 return ERROR(srcSize_wrong);
2793 magicNumber = MEM_readLE32(src);
2794 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2795 zc->headerSize = ZSTDv05_frameHeaderSize_min;
2796 return zc->headerSize;
2800 size_t ZSTDv05_getFrameParams(ZSTDv05_parameters* params, const void* src, size_t srcSize)
2803 if (srcSize < ZSTDv05_frameHeaderSize_min) return ZSTDv05_frameHeaderSize_max;
2804 magicNumber = MEM_readLE32(src);
2805 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2806 memset(params, 0, sizeof(*params));
2807 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTDv05_WINDOWLOG_ABSOLUTEMIN;
2808 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */
2812 /** ZSTDv05_decodeFrameHeader_Part2() :
2813 * decode the full Frame Header.
2814 * srcSize must be the size provided by ZSTDv05_decodeFrameHeader_Part1().
2815 * @return : 0, or an error code, which can be tested using ZSTDv05_isError() */
2816 static size_t ZSTDv05_decodeFrameHeader_Part2(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2819 if (srcSize != zc->headerSize)
2820 return ERROR(srcSize_wrong);
2821 result = ZSTDv05_getFrameParams(&(zc->params), src, srcSize);
2822 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported);
2827 static size_t ZSTDv05_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2829 const BYTE* const in = (const BYTE* const)src;
2834 return ERROR(srcSize_wrong);
2837 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2839 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2840 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2842 if (bpPtr->blockType == bt_end) return 0;
2843 if (bpPtr->blockType == bt_rle) return 1;
2848 static size_t ZSTDv05_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2850 if (dst==NULL) return ERROR(dstSize_tooSmall);
2851 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2852 memcpy(dst, src, srcSize);
2857 /*! ZSTDv05_decodeLiteralsBlock() :
2858 @return : nb of bytes read from src (< srcSize ) */
2859 static size_t ZSTDv05_decodeLiteralsBlock(ZSTDv05_DCtx* dctx,
2860 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
2862 const BYTE* const istart = (const BYTE*) src;
2864 /* any compressed block with literals segment must be at least this size */
2865 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2867 switch(istart[0]>> 6)
2871 size_t litSize, litCSize, singleStream=0;
2872 U32 lhSize = ((istart[0]) >> 4) & 3;
2873 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
2876 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2877 /* 2 - 2 - 10 - 10 */
2879 singleStream = istart[0] & 16;
2880 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2881 litCSize = ((istart[1] & 3) << 8) + istart[2];
2884 /* 2 - 2 - 14 - 14 */
2886 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
2887 litCSize = ((istart[2] & 63) << 8) + istart[3];
2890 /* 2 - 2 - 18 - 18 */
2892 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
2893 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
2896 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2897 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2899 if (HUFv05_isError(singleStream ?
2900 HUFv05_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) :
2901 HUFv05_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
2902 return ERROR(corruption_detected);
2904 dctx->litPtr = dctx->litBuffer;
2905 dctx->litSize = litSize;
2906 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2907 return litCSize + lhSize;
2912 size_t litSize, litCSize;
2913 U32 lhSize = ((istart[0]) >> 4) & 3;
2914 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
2915 return ERROR(corruption_detected);
2916 if (!dctx->flagStaticTables)
2917 return ERROR(dictionary_corrupted);
2919 /* 2 - 2 - 10 - 10 */
2921 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2922 litCSize = ((istart[1] & 3) << 8) + istart[2];
2923 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2925 errorCode = HUFv05_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4);
2926 if (HUFv05_isError(errorCode)) return ERROR(corruption_detected);
2928 dctx->litPtr = dctx->litBuffer;
2929 dctx->litSize = litSize;
2930 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2931 return litCSize + lhSize;
2936 U32 lhSize = ((istart[0]) >> 4) & 3;
2939 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2941 litSize = istart[0] & 31;
2944 litSize = ((istart[0] & 15) << 8) + istart[1];
2947 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2951 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
2952 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
2953 memcpy(dctx->litBuffer, istart+lhSize, litSize);
2954 dctx->litPtr = dctx->litBuffer;
2955 dctx->litSize = litSize;
2956 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2957 return lhSize+litSize;
2959 /* direct reference into compressed stream */
2960 dctx->litPtr = istart+lhSize;
2961 dctx->litSize = litSize;
2962 return lhSize+litSize;
2967 U32 lhSize = ((istart[0]) >> 4) & 3;
2970 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2972 litSize = istart[0] & 31;
2975 litSize = ((istart[0] & 15) << 8) + istart[1];
2978 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2979 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
2982 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2983 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
2984 dctx->litPtr = dctx->litBuffer;
2985 dctx->litSize = litSize;
2989 return ERROR(corruption_detected); /* impossible */
2994 static size_t ZSTDv05_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2995 FSEv05_DTable* DTableLL, FSEv05_DTable* DTableML, FSEv05_DTable* DTableOffb,
2996 const void* src, size_t srcSize, U32 flagStaticTable)
2998 const BYTE* const istart = (const BYTE* const)src;
2999 const BYTE* ip = istart;
3000 const BYTE* const iend = istart + srcSize;
3001 U32 LLtype, Offtype, MLtype;
3002 U32 LLlog, Offlog, MLlog;
3006 if (srcSize < MIN_SEQUENCES_SIZE)
3007 return ERROR(srcSize_wrong);
3011 if (*nbSeq==0) return 1;
3012 if (*nbSeq >= 128) {
3013 if (ip >= iend) return ERROR(srcSize_wrong);
3014 *nbSeq = ((nbSeq[0]-128)<<8) + *ip++;
3017 if (ip >= iend) return ERROR(srcSize_wrong);
3019 Offtype = (*ip >> 4) & 3;
3020 MLtype = (*ip >> 2) & 3;
3022 if (ip+3 > iend) return ERROR(srcSize_wrong);
3023 dumpsLength = ip[2];
3024 dumpsLength += ip[1] << 8;
3027 if (ip+2 > iend) return ERROR(srcSize_wrong);
3028 dumpsLength = ip[1];
3029 dumpsLength += (ip[0] & 1) << 8;
3034 *dumpsLengthPtr = dumpsLength;
3037 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3041 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */
3047 case FSEv05_ENCODING_RLE :
3049 FSEv05_buildDTable_rle(DTableLL, *ip++);
3051 case FSEv05_ENCODING_RAW :
3053 FSEv05_buildDTable_raw(DTableLL, LLbits);
3055 case FSEv05_ENCODING_STATIC:
3056 if (!flagStaticTable) return ERROR(corruption_detected);
3058 case FSEv05_ENCODING_DYNAMIC :
3059 default : /* impossible */
3061 headerSize = FSEv05_readNCount(norm, &max, &LLlog, ip, iend-ip);
3062 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3063 if (LLlog > LLFSEv05Log) return ERROR(corruption_detected);
3065 FSEv05_buildDTable(DTableLL, norm, max, LLlog);
3070 case FSEv05_ENCODING_RLE :
3072 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3073 FSEv05_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
3075 case FSEv05_ENCODING_RAW :
3077 FSEv05_buildDTable_raw(DTableOffb, Offbits);
3079 case FSEv05_ENCODING_STATIC:
3080 if (!flagStaticTable) return ERROR(corruption_detected);
3082 case FSEv05_ENCODING_DYNAMIC :
3083 default : /* impossible */
3085 headerSize = FSEv05_readNCount(norm, &max, &Offlog, ip, iend-ip);
3086 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3087 if (Offlog > OffFSEv05Log) return ERROR(corruption_detected);
3089 FSEv05_buildDTable(DTableOffb, norm, max, Offlog);
3094 case FSEv05_ENCODING_RLE :
3096 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3097 FSEv05_buildDTable_rle(DTableML, *ip++);
3099 case FSEv05_ENCODING_RAW :
3101 FSEv05_buildDTable_raw(DTableML, MLbits);
3103 case FSEv05_ENCODING_STATIC:
3104 if (!flagStaticTable) return ERROR(corruption_detected);
3106 case FSEv05_ENCODING_DYNAMIC :
3107 default : /* impossible */
3109 headerSize = FSEv05_readNCount(norm, &max, &MLlog, ip, iend-ip);
3110 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3111 if (MLlog > MLFSEv05Log) return ERROR(corruption_detected);
3113 FSEv05_buildDTable(DTableML, norm, max, MLlog);
3127 BITv05_DStream_t DStream;
3128 FSEv05_DState_t stateLL;
3129 FSEv05_DState_t stateOffb;
3130 FSEv05_DState_t stateML;
3133 const BYTE* dumpsEnd;
3138 static void ZSTDv05_decodeSequence(seq_t* seq, seqState_t* seqState)
3144 const BYTE* dumps = seqState->dumps;
3145 const BYTE* const de = seqState->dumpsEnd;
3147 /* Literal length */
3148 litLength = FSEv05_peakSymbol(&(seqState->stateLL));
3149 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3150 if (litLength == MaxLL) {
3152 if (add < 255) litLength += add;
3154 litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no risk : dumps is always followed by seq tables > 1 byte */
3155 if (litLength&1) litLength>>=1, dumps += 3;
3156 else litLength = (U16)(litLength)>>1, dumps += 2;
3158 if (dumps > de) { litLength = MaxLL+255; } /* late correction, to avoid using uninitialized memory */
3159 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3164 static const U32 offsetPrefix[MaxOff+1] = {
3165 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3166 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3167 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3168 U32 offsetCode = FSEv05_peakSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3169 U32 nbBits = offsetCode - 1;
3170 if (offsetCode==0) nbBits = 0; /* cmove */
3171 offset = offsetPrefix[offsetCode] + BITv05_readBits(&(seqState->DStream), nbBits);
3172 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3173 if (offsetCode==0) offset = prevOffset; /* repcode, cmove */
3174 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */
3175 FSEv05_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* update */
3178 /* Literal length update */
3179 FSEv05_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); /* update */
3180 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3183 matchLength = FSEv05_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3184 if (matchLength == MaxML) {
3186 if (add < 255) matchLength += add;
3188 matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3189 if (matchLength&1) matchLength>>=1, dumps += 3;
3190 else matchLength = (U16)(matchLength)>>1, dumps += 2;
3192 if (dumps > de) { matchLength = MaxML+255; } /* late correction, to avoid using uninitialized memory */
3193 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3195 matchLength += MINMATCH;
3198 seq->litLength = litLength;
3199 seq->offset = offset;
3200 seq->matchLength = matchLength;
3201 seqState->dumps = dumps;
3205 static U64 totalDecoded = 0;
3206 printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n",
3207 (U32)(totalDecoded), (U32)litLength, (U32)matchLength, (U32)offset);
3208 totalDecoded += litLength + matchLength;
3214 static size_t ZSTDv05_execSequence(BYTE* op,
3215 BYTE* const oend, seq_t sequence,
3216 const BYTE** litPtr, const BYTE* const litLimit,
3217 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3219 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3220 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3221 BYTE* const oLitEnd = op + sequence.litLength;
3222 const size_t sequenceLength = sequence.litLength + sequence.matchLength;
3223 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3224 BYTE* const oend_8 = oend-8;
3225 const BYTE* const litEnd = *litPtr + sequence.litLength;
3226 const BYTE* match = oLitEnd - sequence.offset;
3229 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
3230 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3231 if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */
3234 ZSTDv05_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3236 *litPtr = litEnd; /* update for next sequence */
3239 if (sequence.offset > (size_t)(oLitEnd - base)) {
3240 /* offset beyond prefix */
3241 if (sequence.offset > (size_t)(oLitEnd - vBase))
3242 return ERROR(corruption_detected);
3243 match = dictEnd - (base-match);
3244 if (match + sequence.matchLength <= dictEnd) {
3245 memmove(oLitEnd, match, sequence.matchLength);
3246 return sequenceLength;
3248 /* span extDict & currentPrefixSegment */
3250 size_t length1 = dictEnd - match;
3251 memmove(oLitEnd, match, length1);
3252 op = oLitEnd + length1;
3253 sequence.matchLength -= length1;
3255 if (op > oend_8 || sequence.matchLength < MINMATCH) {
3256 while (op < oMatchEnd) *op++ = *match++;
3257 return sequenceLength;
3260 /* Requirement: op <= oend_8 */
3262 /* match within prefix */
3263 if (sequence.offset < 8) {
3264 /* close range match, overlap */
3265 const int sub2 = dec64table[sequence.offset];
3270 match += dec32table[sequence.offset];
3271 ZSTDv05_copy4(op+4, match);
3274 ZSTDv05_copy8(op, match);
3276 op += 8; match += 8;
3278 if (oMatchEnd > oend-(16-MINMATCH)) {
3280 ZSTDv05_wildcopy(op, match, oend_8 - op);
3281 match += oend_8 - op;
3284 while (op < oMatchEnd)
3287 ZSTDv05_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3289 return sequenceLength;
3293 static size_t ZSTDv05_decompressSequences(
3295 void* dst, size_t maxDstSize,
3296 const void* seqStart, size_t seqSize)
3298 const BYTE* ip = (const BYTE*)seqStart;
3299 const BYTE* const iend = ip + seqSize;
3300 BYTE* const ostart = (BYTE* const)dst;
3302 BYTE* const oend = ostart + maxDstSize;
3303 size_t errorCode, dumpsLength=0;
3304 const BYTE* litPtr = dctx->litPtr;
3305 const BYTE* const litEnd = litPtr + dctx->litSize;
3307 const BYTE* dumps = NULL;
3308 U32* DTableLL = dctx->LLTable;
3309 U32* DTableML = dctx->MLTable;
3310 U32* DTableOffb = dctx->OffTable;
3311 const BYTE* const base = (const BYTE*) (dctx->base);
3312 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3313 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3315 /* Build Decoding Tables */
3316 errorCode = ZSTDv05_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3317 DTableLL, DTableML, DTableOffb,
3318 ip, seqSize, dctx->flagStaticTables);
3319 if (ZSTDv05_isError(errorCode)) return errorCode;
3322 /* Regen sequences */
3325 seqState_t seqState;
3327 memset(&sequence, 0, sizeof(sequence));
3328 sequence.offset = REPCODE_STARTVALUE;
3329 seqState.dumps = dumps;
3330 seqState.dumpsEnd = dumps + dumpsLength;
3331 seqState.prevOffset = REPCODE_STARTVALUE;
3332 errorCode = BITv05_initDStream(&(seqState.DStream), ip, iend-ip);
3333 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3334 FSEv05_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3335 FSEv05_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3336 FSEv05_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3338 for ( ; (BITv05_reloadDStream(&(seqState.DStream)) <= BITv05_DStream_completed) && nbSeq ; ) {
3341 ZSTDv05_decodeSequence(&sequence, &seqState);
3342 oneSeqSize = ZSTDv05_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3343 if (ZSTDv05_isError(oneSeqSize)) return oneSeqSize;
3347 /* check if reached exact end */
3348 if (nbSeq) return ERROR(corruption_detected);
3351 /* last literal segment */
3353 size_t lastLLSize = litEnd - litPtr;
3354 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3355 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3356 memcpy(op, litPtr, lastLLSize);
3364 static void ZSTDv05_checkContinuity(ZSTDv05_DCtx* dctx, const void* dst)
3366 if (dst != dctx->previousDstEnd) { /* not contiguous */
3367 dctx->dictEnd = dctx->previousDstEnd;
3368 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3370 dctx->previousDstEnd = dst;
3375 static size_t ZSTDv05_decompressBlock_internal(ZSTDv05_DCtx* dctx,
3376 void* dst, size_t dstCapacity,
3377 const void* src, size_t srcSize)
3378 { /* blockType == blockCompressed */
3379 const BYTE* ip = (const BYTE*)src;
3382 if (srcSize >= BLOCKSIZE) return ERROR(srcSize_wrong);
3384 /* Decode literals sub-block */
3385 litCSize = ZSTDv05_decodeLiteralsBlock(dctx, src, srcSize);
3386 if (ZSTDv05_isError(litCSize)) return litCSize;
3388 srcSize -= litCSize;
3390 return ZSTDv05_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3394 size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx,
3395 void* dst, size_t dstCapacity,
3396 const void* src, size_t srcSize)
3398 ZSTDv05_checkContinuity(dctx, dst);
3399 return ZSTDv05_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3403 /*! ZSTDv05_decompress_continueDCtx
3404 * dctx must have been properly initialized */
3405 static size_t ZSTDv05_decompress_continueDCtx(ZSTDv05_DCtx* dctx,
3406 void* dst, size_t maxDstSize,
3407 const void* src, size_t srcSize)
3409 const BYTE* ip = (const BYTE*)src;
3410 const BYTE* iend = ip + srcSize;
3411 BYTE* const ostart = (BYTE* const)dst;
3413 BYTE* const oend = ostart + maxDstSize;
3414 size_t remainingSize = srcSize;
3415 blockProperties_t blockProperties;
3416 memset(&blockProperties, 0, sizeof(blockProperties));
3419 { size_t frameHeaderSize;
3420 if (srcSize < ZSTDv05_frameHeaderSize_min+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3421 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3422 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3423 if (srcSize < frameHeaderSize+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3424 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3425 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part2(dctx, src, frameHeaderSize);
3426 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3429 /* Loop on each block */
3432 size_t decodedSize=0;
3433 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, iend-ip, &blockProperties);
3434 if (ZSTDv05_isError(cBlockSize)) return cBlockSize;
3436 ip += ZSTDv05_blockHeaderSize;
3437 remainingSize -= ZSTDv05_blockHeaderSize;
3438 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3440 switch(blockProperties.blockType)
3443 decodedSize = ZSTDv05_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3446 decodedSize = ZSTDv05_copyRawBlock(op, oend-op, ip, cBlockSize);
3449 return ERROR(GENERIC); /* not yet supported */
3453 if (remainingSize) return ERROR(srcSize_wrong);
3456 return ERROR(GENERIC); /* impossible */
3458 if (cBlockSize == 0) break; /* bt_end */
3460 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3463 remainingSize -= cBlockSize;
3470 size_t ZSTDv05_decompress_usingPreparedDCtx(ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* refDCtx,
3471 void* dst, size_t maxDstSize,
3472 const void* src, size_t srcSize)
3474 ZSTDv05_copyDCtx(dctx, refDCtx);
3475 ZSTDv05_checkContinuity(dctx, dst);
3476 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3480 size_t ZSTDv05_decompress_usingDict(ZSTDv05_DCtx* dctx,
3481 void* dst, size_t maxDstSize,
3482 const void* src, size_t srcSize,
3483 const void* dict, size_t dictSize)
3485 ZSTDv05_decompressBegin_usingDict(dctx, dict, dictSize);
3486 ZSTDv05_checkContinuity(dctx, dst);
3487 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3491 size_t ZSTDv05_decompressDCtx(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3493 return ZSTDv05_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
3496 size_t ZSTDv05_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3498 #if defined(ZSTDv05_HEAPMODE) && (ZSTDv05_HEAPMODE==1)
3500 ZSTDv05_DCtx* dctx = ZSTDv05_createDCtx();
3501 if (dctx==NULL) return ERROR(memory_allocation);
3502 regenSize = ZSTDv05_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
3503 ZSTDv05_freeDCtx(dctx);
3507 return ZSTDv05_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
3511 size_t ZSTDv05_findFrameCompressedSize(const void *src, size_t srcSize)
3513 const BYTE* ip = (const BYTE*)src;
3514 size_t remainingSize = srcSize;
3515 blockProperties_t blockProperties;
3518 if (srcSize < ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong);
3519 if (MEM_readLE32(src) != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
3520 ip += ZSTDv05_frameHeaderSize_min; remainingSize -= ZSTDv05_frameHeaderSize_min;
3522 /* Loop on each block */
3525 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, remainingSize, &blockProperties);
3526 if (ZSTDv05_isError(cBlockSize)) return cBlockSize;
3528 ip += ZSTDv05_blockHeaderSize;
3529 remainingSize -= ZSTDv05_blockHeaderSize;
3530 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3532 if (cBlockSize == 0) break; /* bt_end */
3535 remainingSize -= cBlockSize;
3538 return ip - (const BYTE*)src;
3541 /* ******************************
3542 * Streaming Decompression API
3543 ********************************/
3544 size_t ZSTDv05_nextSrcSizeToDecompress(ZSTDv05_DCtx* dctx)
3546 return dctx->expected;
3549 size_t ZSTDv05_decompressContinue(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3552 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3553 ZSTDv05_checkContinuity(dctx, dst);
3555 /* Decompress : frame header; part 1 */
3556 switch (dctx->stage)
3558 case ZSTDv05ds_getFrameHeaderSize :
3559 /* get frame header size */
3560 if (srcSize != ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3561 dctx->headerSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3562 if (ZSTDv05_isError(dctx->headerSize)) return dctx->headerSize;
3563 memcpy(dctx->headerBuffer, src, ZSTDv05_frameHeaderSize_min);
3564 if (dctx->headerSize > ZSTDv05_frameHeaderSize_min) return ERROR(GENERIC); /* should never happen */
3565 dctx->expected = 0; /* not necessary to copy more */
3567 case ZSTDv05ds_decodeFrameHeader:
3568 /* get frame header */
3569 { size_t const result = ZSTDv05_decodeFrameHeader_Part2(dctx, dctx->headerBuffer, dctx->headerSize);
3570 if (ZSTDv05_isError(result)) return result;
3571 dctx->expected = ZSTDv05_blockHeaderSize;
3572 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3575 case ZSTDv05ds_decodeBlockHeader:
3577 /* Decode block header */
3578 blockProperties_t bp;
3579 size_t blockSize = ZSTDv05_getcBlockSize(src, ZSTDv05_blockHeaderSize, &bp);
3580 if (ZSTDv05_isError(blockSize)) return blockSize;
3581 if (bp.blockType == bt_end) {
3583 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
3586 dctx->expected = blockSize;
3587 dctx->bType = bp.blockType;
3588 dctx->stage = ZSTDv05ds_decompressBlock;
3592 case ZSTDv05ds_decompressBlock:
3594 /* Decompress : block content */
3599 rSize = ZSTDv05_decompressBlock_internal(dctx, dst, maxDstSize, src, srcSize);
3602 rSize = ZSTDv05_copyRawBlock(dst, maxDstSize, src, srcSize);
3605 return ERROR(GENERIC); /* not yet handled */
3607 case bt_end : /* should never happen (filtered at phase 1) */
3611 return ERROR(GENERIC); /* impossible */
3613 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3614 dctx->expected = ZSTDv05_blockHeaderSize;
3615 dctx->previousDstEnd = (char*)dst + rSize;
3619 return ERROR(GENERIC); /* impossible */
3624 static void ZSTDv05_refDictContent(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3626 dctx->dictEnd = dctx->previousDstEnd;
3627 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3629 dctx->previousDstEnd = (const char*)dict + dictSize;
3632 static size_t ZSTDv05_loadEntropy(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3634 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, errorCode, litlengthHeaderSize;
3635 short offcodeNCount[MaxOff+1];
3636 U32 offcodeMaxValue=MaxOff, offcodeLog;
3637 short matchlengthNCount[MaxML+1];
3638 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3639 short litlengthNCount[MaxLL+1];
3640 unsigned litlengthMaxValue = MaxLL, litlengthLog;
3642 hSize = HUFv05_readDTableX4(dctx->hufTableX4, dict, dictSize);
3643 if (HUFv05_isError(hSize)) return ERROR(dictionary_corrupted);
3644 dict = (const char*)dict + hSize;
3647 offcodeHeaderSize = FSEv05_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize);
3648 if (FSEv05_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3649 if (offcodeLog > OffFSEv05Log) return ERROR(dictionary_corrupted);
3650 errorCode = FSEv05_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
3651 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3652 dict = (const char*)dict + offcodeHeaderSize;
3653 dictSize -= offcodeHeaderSize;
3655 matchlengthHeaderSize = FSEv05_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize);
3656 if (FSEv05_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3657 if (matchlengthLog > MLFSEv05Log) return ERROR(dictionary_corrupted);
3658 errorCode = FSEv05_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
3659 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3660 dict = (const char*)dict + matchlengthHeaderSize;
3661 dictSize -= matchlengthHeaderSize;
3663 litlengthHeaderSize = FSEv05_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize);
3664 if (litlengthLog > LLFSEv05Log) return ERROR(dictionary_corrupted);
3665 if (FSEv05_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3666 errorCode = FSEv05_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
3667 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3669 dctx->flagStaticTables = 1;
3670 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize;
3673 static size_t ZSTDv05_decompress_insertDictionary(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3676 U32 magic = MEM_readLE32(dict);
3677 if (magic != ZSTDv05_DICT_MAGIC) {
3678 /* pure content mode */
3679 ZSTDv05_refDictContent(dctx, dict, dictSize);
3682 /* load entropy tables */
3683 dict = (const char*)dict + 4;
3685 eSize = ZSTDv05_loadEntropy(dctx, dict, dictSize);
3686 if (ZSTDv05_isError(eSize)) return ERROR(dictionary_corrupted);
3688 /* reference dictionary content */
3689 dict = (const char*)dict + eSize;
3691 ZSTDv05_refDictContent(dctx, dict, dictSize);
3697 size_t ZSTDv05_decompressBegin_usingDict(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3700 errorCode = ZSTDv05_decompressBegin(dctx);
3701 if (ZSTDv05_isError(errorCode)) return errorCode;
3703 if (dict && dictSize) {
3704 errorCode = ZSTDv05_decompress_insertDictionary(dctx, dict, dictSize);
3705 if (ZSTDv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3712 Buffered version of Zstd compression library
3713 Copyright (C) 2015-2016, Yann Collet.
3715 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
3717 Redistribution and use in source and binary forms, with or without
3718 modification, are permitted provided that the following conditions are
3720 * Redistributions of source code must retain the above copyright
3721 notice, this list of conditions and the following disclaimer.
3722 * Redistributions in binary form must reproduce the above
3723 copyright notice, this list of conditions and the following disclaimer
3724 in the documentation and/or other materials provided with the
3726 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3727 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3728 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3729 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3730 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3731 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3732 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3733 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3734 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3735 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3736 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3738 You can contact the author at :
3739 - zstd source repository : https://github.com/Cyan4973/zstd
3740 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3743 /* The objects defined into this file should be considered experimental.
3744 * They are not labelled stable, as their prototype may change in the future.
3745 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3750 /* *************************************
3752 ***************************************/
3753 static size_t ZBUFFv05_blockHeaderSize = 3;
3757 /* *** Compression *** */
3759 static size_t ZBUFFv05_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3761 size_t length = MIN(maxDstSize, srcSize);
3762 memcpy(dst, src, length);
3769 /** ************************************************
3770 * Streaming decompression
3772 * A ZBUFFv05_DCtx object is required to track streaming operation.
3773 * Use ZBUFFv05_createDCtx() and ZBUFFv05_freeDCtx() to create/release resources.
3774 * Use ZBUFFv05_decompressInit() to start a new decompression operation.
3775 * ZBUFFv05_DCtx objects can be reused multiple times.
3777 * Use ZBUFFv05_decompressContinue() repetitively to consume your input.
3778 * *srcSizePtr and *maxDstSizePtr can be any size.
3779 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3780 * 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.
3781 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3782 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3783 * or 0 when a frame is completely decoded
3784 * or an error code, which can be tested using ZBUFFv05_isError().
3786 * Hint : recommended buffer sizes (not compulsory)
3787 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3788 * input : just follow indications from ZBUFFv05_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3789 * **************************************************/
3791 typedef enum { ZBUFFv05ds_init, ZBUFFv05ds_readHeader, ZBUFFv05ds_loadHeader, ZBUFFv05ds_decodeHeader,
3792 ZBUFFv05ds_read, ZBUFFv05ds_load, ZBUFFv05ds_flush } ZBUFFv05_dStage;
3794 /* *** Resource management *** */
3796 #define ZSTDv05_frameHeaderSize_max 5 /* too magical, should come from reference */
3797 struct ZBUFFv05_DCtx_s {
3799 ZSTDv05_parameters params;
3808 ZBUFFv05_dStage stage;
3809 unsigned char headerBuffer[ZSTDv05_frameHeaderSize_max];
3810 }; /* typedef'd to ZBUFFv05_DCtx within "zstd_buffered.h" */
3813 ZBUFFv05_DCtx* ZBUFFv05_createDCtx(void)
3815 ZBUFFv05_DCtx* zbc = (ZBUFFv05_DCtx*)malloc(sizeof(ZBUFFv05_DCtx));
3816 if (zbc==NULL) return NULL;
3817 memset(zbc, 0, sizeof(*zbc));
3818 zbc->zc = ZSTDv05_createDCtx();
3819 zbc->stage = ZBUFFv05ds_init;
3823 size_t ZBUFFv05_freeDCtx(ZBUFFv05_DCtx* zbc)
3825 if (zbc==NULL) return 0; /* support free on null */
3826 ZSTDv05_freeDCtx(zbc->zc);
3834 /* *** Initialization *** */
3836 size_t ZBUFFv05_decompressInitDictionary(ZBUFFv05_DCtx* zbc, const void* dict, size_t dictSize)
3838 zbc->stage = ZBUFFv05ds_readHeader;
3839 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = 0;
3840 return ZSTDv05_decompressBegin_usingDict(zbc->zc, dict, dictSize);
3843 size_t ZBUFFv05_decompressInit(ZBUFFv05_DCtx* zbc)
3845 return ZBUFFv05_decompressInitDictionary(zbc, NULL, 0);
3849 /* *** Decompression *** */
3851 size_t ZBUFFv05_decompressContinue(ZBUFFv05_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3853 const char* const istart = (const char*)src;
3854 const char* ip = istart;
3855 const char* const iend = istart + *srcSizePtr;
3856 char* const ostart = (char*)dst;
3858 char* const oend = ostart + *maxDstSizePtr;
3864 case ZBUFFv05ds_init :
3865 return ERROR(init_missing);
3867 case ZBUFFv05ds_readHeader :
3868 /* read header from src */
3870 size_t headerSize = ZSTDv05_getFrameParams(&(zbc->params), src, *srcSizePtr);
3871 if (ZSTDv05_isError(headerSize)) return headerSize;
3873 /* not enough input to decode header : tell how many bytes would be necessary */
3874 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
3875 zbc->hPos += *srcSizePtr;
3877 zbc->stage = ZBUFFv05ds_loadHeader;
3878 return headerSize - zbc->hPos;
3880 zbc->stage = ZBUFFv05ds_decodeHeader;
3884 case ZBUFFv05ds_loadHeader:
3885 /* complete header from src */
3887 size_t headerSize = ZBUFFv05_limitCopy(
3888 zbc->headerBuffer + zbc->hPos, ZSTDv05_frameHeaderSize_max - zbc->hPos,
3890 zbc->hPos += headerSize;
3892 headerSize = ZSTDv05_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
3893 if (ZSTDv05_isError(headerSize)) return headerSize;
3895 /* not enough input to decode header : tell how many bytes would be necessary */
3897 return headerSize - zbc->hPos;
3899 // zbc->stage = ZBUFFv05ds_decodeHeader; break; /* useless : stage follows */
3902 case ZBUFFv05ds_decodeHeader:
3903 /* apply header to create / resize buffers */
3905 size_t neededOutSize = (size_t)1 << zbc->params.windowLog;
3906 size_t neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */
3907 if (zbc->inBuffSize < neededInSize) {
3909 zbc->inBuffSize = neededInSize;
3910 zbc->inBuff = (char*)malloc(neededInSize);
3911 if (zbc->inBuff == NULL) return ERROR(memory_allocation);
3913 if (zbc->outBuffSize < neededOutSize) {
3915 zbc->outBuffSize = neededOutSize;
3916 zbc->outBuff = (char*)malloc(neededOutSize);
3917 if (zbc->outBuff == NULL) return ERROR(memory_allocation);
3920 /* some data already loaded into headerBuffer : transfer into inBuff */
3921 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
3922 zbc->inPos = zbc->hPos;
3924 zbc->stage = ZBUFFv05ds_load;
3927 zbc->stage = ZBUFFv05ds_read;
3929 case ZBUFFv05ds_read:
3931 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3932 if (neededInSize==0) { /* end of frame */
3933 zbc->stage = ZBUFFv05ds_init;
3937 if ((size_t)(iend-ip) >= neededInSize) {
3938 /* directly decode from src */
3939 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3940 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3942 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3944 if (!decodedSize) break; /* this was just a header */
3945 zbc->outEnd = zbc->outStart + decodedSize;
3946 zbc->stage = ZBUFFv05ds_flush;
3949 if (ip==iend) { notDone = 0; break; } /* no more input */
3950 zbc->stage = ZBUFFv05ds_load;
3953 case ZBUFFv05ds_load:
3955 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3956 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */
3958 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */
3959 loadedSize = ZBUFFv05_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
3961 zbc->inPos += loadedSize;
3962 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
3964 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3965 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3966 zbc->inBuff, neededInSize);
3967 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3968 zbc->inPos = 0; /* input is consumed */
3969 if (!decodedSize) { zbc->stage = ZBUFFv05ds_read; break; } /* this was just a header */
3970 zbc->outEnd = zbc->outStart + decodedSize;
3971 zbc->stage = ZBUFFv05ds_flush;
3972 // break; /* ZBUFFv05ds_flush follows */
3976 case ZBUFFv05ds_flush:
3978 size_t toFlushSize = zbc->outEnd - zbc->outStart;
3979 size_t flushedSize = ZBUFFv05_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
3981 zbc->outStart += flushedSize;
3982 if (flushedSize == toFlushSize) {
3983 zbc->stage = ZBUFFv05ds_read;
3984 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
3985 zbc->outStart = zbc->outEnd = 0;
3988 /* cannot flush everything */
3992 default: return ERROR(GENERIC); /* impossible */
3995 *srcSizePtr = ip-istart;
3996 *maxDstSizePtr = op-ostart;
3998 { size_t nextSrcSizeHint = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3999 if (nextSrcSizeHint > ZBUFFv05_blockHeaderSize) nextSrcSizeHint+= ZBUFFv05_blockHeaderSize; /* get next block header too */
4000 nextSrcSizeHint -= zbc->inPos; /* already loaded*/
4001 return nextSrcSizeHint;
4007 /* *************************************
4009 ***************************************/
4010 unsigned ZBUFFv05_isError(size_t errorCode) { return ERR_isError(errorCode); }
4011 const char* ZBUFFv05_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
4013 size_t ZBUFFv05_recommendedDInSize(void) { return BLOCKSIZE + ZBUFFv05_blockHeaderSize /* block header size*/ ; }
4014 size_t ZBUFFv05_recommendedDOutSize(void) { return BLOCKSIZE; }