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
);
740 * Start by invoking BITv05_initDStream().
741 * A chunk of the bitStream is then stored into a local register.
742 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
743 * You can then retrieve bitFields stored into the local register, **in reverse order**.
744 * Local register is explicitly reloaded from memory by the BITv05_reloadDStream() method.
745 * A reload guarantee a minimum of ((8*sizeof(size_t))-7) bits when its result is BITv05_DStream_unfinished.
746 * Otherwise, it can be less than that, so proceed accordingly.
747 * Checking if DStream has reached its end can be performed with BITv05_endOfDStream()
751 /*-****************************************
753 ******************************************/
754 MEM_STATIC
size_t BITv05_readBitsFast(BITv05_DStream_t
* bitD
, unsigned nbBits
);
755 /* faster, but works only if nbBits >= 1 */
759 /*-**************************************************************
761 ****************************************************************/
762 MEM_STATIC
unsigned BITv05_highbit32 (register U32 val
)
764 # if defined(_MSC_VER) /* Visual */
766 _BitScanReverse ( &r
, val
);
768 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
769 return 31 - __builtin_clz (val
);
770 # else /* Software version */
771 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 };
779 r
= DeBruijnClz
[ (U32
) (v
* 0x07C4ACDDU
) >> 27];
786 /*-********************************************************
788 **********************************************************/
789 /*!BITv05_initDStream
790 * Initialize a BITv05_DStream_t.
791 * @bitD : a pointer to an already allocated BITv05_DStream_t structure
792 * @srcBuffer must point at the beginning of a bitStream
793 * @srcSize must be the exact size of the bitStream
794 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
796 MEM_STATIC
size_t BITv05_initDStream(BITv05_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
)
798 if (srcSize
< 1) { memset(bitD
, 0, sizeof(*bitD
)); return ERROR(srcSize_wrong
); }
800 if (srcSize
>= sizeof(size_t)) { /* normal case */
802 bitD
->start
= (const char*)srcBuffer
;
803 bitD
->ptr
= (const char*)srcBuffer
+ srcSize
- sizeof(size_t);
804 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
805 contain32
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
806 if (contain32
== 0) return ERROR(GENERIC
); /* endMark not present */
807 bitD
->bitsConsumed
= 8 - BITv05_highbit32(contain32
);
810 bitD
->start
= (const char*)srcBuffer
;
811 bitD
->ptr
= bitD
->start
;
812 bitD
->bitContainer
= *(const BYTE
*)(bitD
->start
);
815 case 7: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
816 case 6: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
817 case 5: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
818 case 4: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[3]) << 24; /* fall-through */
819 case 3: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[2]) << 16; /* fall-through */
820 case 2: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[1]) << 8; /* fall-through */
823 contain32
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
824 if (contain32
== 0) return ERROR(GENERIC
); /* endMark not present */
825 bitD
->bitsConsumed
= 8 - BITv05_highbit32(contain32
);
826 bitD
->bitsConsumed
+= (U32
)(sizeof(size_t) - srcSize
)*8;
833 * Provides next n bits from local register
834 * local register is not modified (bits are still present for next read/look)
835 * On 32-bits, maxNbBits==25
836 * On 64-bits, maxNbBits==57
837 * @return : value extracted
839 MEM_STATIC
size_t BITv05_lookBits(BITv05_DStream_t
* bitD
, U32 nbBits
)
841 const U32 bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
842 return ((bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> 1) >> ((bitMask
-nbBits
) & bitMask
);
845 /*! BITv05_lookBitsFast :
846 * unsafe version; only works only if nbBits >= 1 */
847 MEM_STATIC
size_t BITv05_lookBitsFast(BITv05_DStream_t
* bitD
, U32 nbBits
)
849 const U32 bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
850 return (bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> (((bitMask
+1)-nbBits
) & bitMask
);
853 MEM_STATIC
void BITv05_skipBits(BITv05_DStream_t
* bitD
, U32 nbBits
)
855 bitD
->bitsConsumed
+= nbBits
;
859 * Read next n bits from local register.
860 * pay attention to not read more than nbBits contained into local register.
861 * @return : extracted value.
863 MEM_STATIC
size_t BITv05_readBits(BITv05_DStream_t
* bitD
, U32 nbBits
)
865 size_t value
= BITv05_lookBits(bitD
, nbBits
);
866 BITv05_skipBits(bitD
, nbBits
);
870 /*!BITv05_readBitsFast :
871 * unsafe version; only works only if nbBits >= 1 */
872 MEM_STATIC
size_t BITv05_readBitsFast(BITv05_DStream_t
* bitD
, U32 nbBits
)
874 size_t value
= BITv05_lookBitsFast(bitD
, nbBits
);
875 BITv05_skipBits(bitD
, nbBits
);
879 MEM_STATIC BITv05_DStream_status
BITv05_reloadDStream(BITv05_DStream_t
* bitD
)
881 if (bitD
->bitsConsumed
> (sizeof(bitD
->bitContainer
)*8)) /* should never happen */
882 return BITv05_DStream_overflow
;
884 if (bitD
->ptr
>= bitD
->start
+ sizeof(bitD
->bitContainer
)) {
885 bitD
->ptr
-= bitD
->bitsConsumed
>> 3;
886 bitD
->bitsConsumed
&= 7;
887 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
888 return BITv05_DStream_unfinished
;
890 if (bitD
->ptr
== bitD
->start
) {
891 if (bitD
->bitsConsumed
< sizeof(bitD
->bitContainer
)*8) return BITv05_DStream_endOfBuffer
;
892 return BITv05_DStream_completed
;
895 U32 nbBytes
= bitD
->bitsConsumed
>> 3;
896 BITv05_DStream_status result
= BITv05_DStream_unfinished
;
897 if (bitD
->ptr
- nbBytes
< bitD
->start
) {
898 nbBytes
= (U32
)(bitD
->ptr
- bitD
->start
); /* ptr > start */
899 result
= BITv05_DStream_endOfBuffer
;
901 bitD
->ptr
-= nbBytes
;
902 bitD
->bitsConsumed
-= nbBytes
*8;
903 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
); /* reminder : srcSize > sizeof(bitD) */
908 /*! BITv05_endOfDStream
909 * @return Tells if DStream has reached its exact end
911 MEM_STATIC
unsigned BITv05_endOfDStream(const BITv05_DStream_t
* DStream
)
913 return ((DStream
->ptr
== DStream
->start
) && (DStream
->bitsConsumed
== sizeof(DStream
->bitContainer
)*8));
916 #if defined (__cplusplus)
920 #endif /* BITv05STREAM_H_MODULE */
921 /* ******************************************************************
922 FSEv05 : Finite State Entropy coder
923 header file for static linking (only)
924 Copyright (C) 2013-2015, Yann Collet
926 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
928 Redistribution and use in source and binary forms, with or without
929 modification, are permitted provided that the following conditions are
932 * Redistributions of source code must retain the above copyright
933 notice, this list of conditions and the following disclaimer.
934 * Redistributions in binary form must reproduce the above
935 copyright notice, this list of conditions and the following disclaimer
936 in the documentation and/or other materials provided with the
939 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
940 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
941 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
942 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
943 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
944 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
945 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
946 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
947 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
948 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
949 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
951 You can contact the author at :
952 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
953 - Public forum : https://groups.google.com/forum/#!forum/lz4c
954 ****************************************************************** */
955 #ifndef FSEv05_STATIC_H
956 #define FSEv05_STATIC_H
958 #if defined (__cplusplus)
964 /* *****************************************
966 *******************************************/
967 /* It is possible to statically allocate FSEv05 CTable/DTable as a table of unsigned using below macros */
968 #define FSEv05_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
971 /* *****************************************
972 * FSEv05 advanced API
973 *******************************************/
974 size_t FSEv05_buildDTable_raw (FSEv05_DTable
* dt
, unsigned nbBits
);
975 /* build a fake FSEv05_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
977 size_t FSEv05_buildDTable_rle (FSEv05_DTable
* dt
, unsigned char symbolValue
);
978 /* build a fake FSEv05_DTable, designed to always generate the same symbolValue */
982 /* *****************************************
983 * FSEv05 symbol decompression API
984 *******************************************/
988 const void* table
; /* precise table may vary, depending on U16 */
992 static void FSEv05_initDState(FSEv05_DState_t
* DStatePtr
, BITv05_DStream_t
* bitD
, const FSEv05_DTable
* dt
);
994 static unsigned char FSEv05_decodeSymbol(FSEv05_DState_t
* DStatePtr
, BITv05_DStream_t
* bitD
);
996 static unsigned FSEv05_endOfDState(const FSEv05_DState_t
* DStatePtr
);
999 Let's now decompose FSEv05_decompress_usingDTable() into its unitary components.
1000 You will decode FSEv05-encoded symbols from the bitStream,
1001 and also any other bitFields you put in, **in reverse order**.
1003 You will need a few variables to track your bitStream. They are :
1005 BITv05_DStream_t DStream; // Stream context
1006 FSEv05_DState_t DState; // State context. Multiple ones are possible
1007 FSEv05_DTable* DTablePtr; // Decoding table, provided by FSEv05_buildDTable()
1009 The first thing to do is to init the bitStream.
1010 errorCode = BITv05_initDStream(&DStream, srcBuffer, srcSize);
1012 You should then retrieve your initial state(s)
1013 (in reverse flushing order if you have several ones) :
1014 errorCode = FSEv05_initDState(&DState, &DStream, DTablePtr);
1016 You can then decode your data, symbol after symbol.
1017 For information the maximum number of bits read by FSEv05_decodeSymbol() is 'tableLog'.
1018 Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
1019 unsigned char symbol = FSEv05_decodeSymbol(&DState, &DStream);
1021 You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
1022 Note : maximum allowed nbBits is 25, for 32-bits compatibility
1023 size_t bitField = BITv05_readBits(&DStream, nbBits);
1025 All above operations only read from local register (which size depends on size_t).
1026 Refueling the register from memory is manually performed by the reload method.
1027 endSignal = FSEv05_reloadDStream(&DStream);
1029 BITv05_reloadDStream() result tells if there is still some more data to read from DStream.
1030 BITv05_DStream_unfinished : there is still some data left into the DStream.
1031 BITv05_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
1032 BITv05_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
1033 BITv05_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
1035 When reaching end of buffer (BITv05_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
1036 to properly detect the exact end of stream.
1037 After each decoded symbol, check if DStream is fully consumed using this simple test :
1038 BITv05_reloadDStream(&DStream) >= BITv05_DStream_completed
1040 When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
1041 Checking if DStream has reached its end is performed by :
1042 BITv05_endOfDStream(&DStream);
1043 Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
1044 FSEv05_endOfDState(&DState);
1048 /* *****************************************
1050 *******************************************/
1051 static unsigned char FSEv05_decodeSymbolFast(FSEv05_DState_t
* DStatePtr
, BITv05_DStream_t
* bitD
);
1052 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
1055 /* *****************************************
1056 * Implementation of inlined functions
1057 *******************************************/
1063 } FSEv05_DTableHeader
; /* sizeof U32 */
1067 unsigned short newState
;
1068 unsigned char symbol
;
1069 unsigned char nbBits
;
1070 } FSEv05_decode_t
; /* size == U32 */
1072 MEM_STATIC
void FSEv05_initDState(FSEv05_DState_t
* DStatePtr
, BITv05_DStream_t
* bitD
, const FSEv05_DTable
* dt
)
1074 const void* ptr
= dt
;
1075 const FSEv05_DTableHeader
* const DTableH
= (const FSEv05_DTableHeader
*)ptr
;
1076 DStatePtr
->state
= BITv05_readBits(bitD
, DTableH
->tableLog
);
1077 BITv05_reloadDStream(bitD
);
1078 DStatePtr
->table
= dt
+ 1;
1081 MEM_STATIC BYTE
FSEv05_peakSymbol(FSEv05_DState_t
* DStatePtr
)
1083 const FSEv05_decode_t DInfo
= ((const FSEv05_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
1084 return DInfo
.symbol
;
1087 MEM_STATIC BYTE
FSEv05_decodeSymbol(FSEv05_DState_t
* DStatePtr
, BITv05_DStream_t
* bitD
)
1089 const FSEv05_decode_t DInfo
= ((const FSEv05_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
1090 const U32 nbBits
= DInfo
.nbBits
;
1091 BYTE symbol
= DInfo
.symbol
;
1092 size_t lowBits
= BITv05_readBits(bitD
, nbBits
);
1094 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
1098 MEM_STATIC BYTE
FSEv05_decodeSymbolFast(FSEv05_DState_t
* DStatePtr
, BITv05_DStream_t
* bitD
)
1100 const FSEv05_decode_t DInfo
= ((const FSEv05_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
1101 const U32 nbBits
= DInfo
.nbBits
;
1102 BYTE symbol
= DInfo
.symbol
;
1103 size_t lowBits
= BITv05_readBitsFast(bitD
, nbBits
);
1105 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
1109 MEM_STATIC
unsigned FSEv05_endOfDState(const FSEv05_DState_t
* DStatePtr
)
1111 return DStatePtr
->state
== 0;
1115 #if defined (__cplusplus)
1119 #endif /* FSEv05_STATIC_H */
1120 /* ******************************************************************
1121 FSEv05 : Finite State Entropy coder
1122 Copyright (C) 2013-2015, Yann Collet.
1124 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1126 Redistribution and use in source and binary forms, with or without
1127 modification, are permitted provided that the following conditions are
1130 * Redistributions of source code must retain the above copyright
1131 notice, this list of conditions and the following disclaimer.
1132 * Redistributions in binary form must reproduce the above
1133 copyright notice, this list of conditions and the following disclaimer
1134 in the documentation and/or other materials provided with the
1137 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1138 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1139 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1140 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1141 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1142 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1143 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1144 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1145 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1146 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1147 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1149 You can contact the author at :
1150 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1151 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1152 ****************************************************************** */
1154 #ifndef FSEv05_COMMONDEFS_ONLY
1156 /* **************************************************************
1158 ****************************************************************/
1160 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1161 * Increasing memory usage improves compression ratio
1162 * Reduced memory usage can improve speed, due to cache effect
1163 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1164 #define FSEv05_MAX_MEMORY_USAGE 14
1165 #define FSEv05_DEFAULT_MEMORY_USAGE 13
1167 /*!FSEv05_MAX_SYMBOL_VALUE :
1168 * Maximum symbol value authorized.
1169 * Required for proper stack allocation */
1170 #define FSEv05_MAX_SYMBOL_VALUE 255
1173 /* **************************************************************
1174 * template functions type & suffix
1175 ****************************************************************/
1176 #define FSEv05_FUNCTION_TYPE BYTE
1177 #define FSEv05_FUNCTION_EXTENSION
1178 #define FSEv05_DECODE_TYPE FSEv05_decode_t
1181 #endif /* !FSEv05_COMMONDEFS_ONLY */
1183 /* **************************************************************
1184 * Compiler specifics
1185 ****************************************************************/
1186 #ifdef _MSC_VER /* Visual Studio */
1187 # define FORCE_INLINE static __forceinline
1188 # include <intrin.h> /* For Visual 2005 */
1189 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1190 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1192 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1194 # define FORCE_INLINE static inline __attribute__((always_inline))
1196 # define FORCE_INLINE static inline
1199 # define FORCE_INLINE static
1200 # endif /* __STDC_VERSION__ */
1204 /* **************************************************************
1206 ****************************************************************/
1207 #include <stdlib.h> /* malloc, free, qsort */
1208 #include <string.h> /* memcpy, memset */
1209 #include <stdio.h> /* printf (debug) */
1213 /* ***************************************************************
1215 *****************************************************************/
1216 #define FSEv05_MAX_TABLELOG (FSEv05_MAX_MEMORY_USAGE-2)
1217 #define FSEv05_MAX_TABLESIZE (1U<<FSEv05_MAX_TABLELOG)
1218 #define FSEv05_MAXTABLESIZE_MASK (FSEv05_MAX_TABLESIZE-1)
1219 #define FSEv05_DEFAULT_TABLELOG (FSEv05_DEFAULT_MEMORY_USAGE-2)
1220 #define FSEv05_MIN_TABLELOG 5
1222 #define FSEv05_TABLELOG_ABSOLUTE_MAX 15
1223 #if FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX
1224 #error "FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX is not supported"
1228 /* **************************************************************
1230 ****************************************************************/
1231 #define FSEv05_STATIC_ASSERT(c) { enum { FSEv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1234 /* **************************************************************
1236 ****************************************************************/
1237 typedef U32 DTable_max_t
[FSEv05_DTABLE_SIZE_U32(FSEv05_MAX_TABLELOG
)];
1240 /* **************************************************************
1242 ****************************************************************/
1244 designed to be included
1245 for type-specific functions (template emulation in C)
1246 Objective is to write these functions only once, for improved maintenance
1250 #ifndef FSEv05_FUNCTION_EXTENSION
1251 # error "FSEv05_FUNCTION_EXTENSION must be defined"
1253 #ifndef FSEv05_FUNCTION_TYPE
1254 # error "FSEv05_FUNCTION_TYPE must be defined"
1257 /* Function names */
1258 #define FSEv05_CAT(X,Y) X##Y
1259 #define FSEv05_FUNCTION_NAME(X,Y) FSEv05_CAT(X,Y)
1260 #define FSEv05_TYPE_NAME(X,Y) FSEv05_CAT(X,Y)
1263 /* Function templates */
1264 static U32
FSEv05_tableStep(U32 tableSize
) { return (tableSize
>>1) + (tableSize
>>3) + 3; }
1268 FSEv05_DTable
* FSEv05_createDTable (unsigned tableLog
)
1270 if (tableLog
> FSEv05_TABLELOG_ABSOLUTE_MAX
) tableLog
= FSEv05_TABLELOG_ABSOLUTE_MAX
;
1271 return (FSEv05_DTable
*)malloc( FSEv05_DTABLE_SIZE_U32(tableLog
) * sizeof (U32
) );
1274 void FSEv05_freeDTable (FSEv05_DTable
* dt
)
1279 size_t FSEv05_buildDTable(FSEv05_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
)
1281 FSEv05_DTableHeader DTableH
;
1282 void* const tdPtr
= dt
+1; /* because dt is unsigned, 32-bits aligned on 32-bits */
1283 FSEv05_DECODE_TYPE
* const tableDecode
= (FSEv05_DECODE_TYPE
*) (tdPtr
);
1284 const U32 tableSize
= 1 << tableLog
;
1285 const U32 tableMask
= tableSize
-1;
1286 const U32 step
= FSEv05_tableStep(tableSize
);
1287 U16 symbolNext
[FSEv05_MAX_SYMBOL_VALUE
+1];
1289 U32 highThreshold
= tableSize
-1;
1290 const S16 largeLimit
= (S16
)(1 << (tableLog
-1));
1295 if (maxSymbolValue
> FSEv05_MAX_SYMBOL_VALUE
) return ERROR(maxSymbolValue_tooLarge
);
1296 if (tableLog
> FSEv05_MAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
1298 /* Init, lay down lowprob symbols */
1299 DTableH
.tableLog
= (U16
)tableLog
;
1300 for (s
=0; s
<=maxSymbolValue
; s
++) {
1301 if (normalizedCounter
[s
]==-1) {
1302 tableDecode
[highThreshold
--].symbol
= (FSEv05_FUNCTION_TYPE
)s
;
1305 if (normalizedCounter
[s
] >= largeLimit
) noLarge
=0;
1306 symbolNext
[s
] = normalizedCounter
[s
];
1309 /* Spread symbols */
1310 for (s
=0; s
<=maxSymbolValue
; s
++) {
1312 for (i
=0; i
<normalizedCounter
[s
]; i
++) {
1313 tableDecode
[position
].symbol
= (FSEv05_FUNCTION_TYPE
)s
;
1314 position
= (position
+ step
) & tableMask
;
1315 while (position
> highThreshold
) position
= (position
+ step
) & tableMask
; /* lowprob area */
1318 if (position
!=0) return ERROR(GENERIC
); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1320 /* Build Decoding table */
1323 for (i
=0; i
<tableSize
; i
++) {
1324 FSEv05_FUNCTION_TYPE symbol
= (FSEv05_FUNCTION_TYPE
)(tableDecode
[i
].symbol
);
1325 U16 nextState
= symbolNext
[symbol
]++;
1326 tableDecode
[i
].nbBits
= (BYTE
) (tableLog
- BITv05_highbit32 ((U32
)nextState
) );
1327 tableDecode
[i
].newState
= (U16
) ( (nextState
<< tableDecode
[i
].nbBits
) - tableSize
);
1330 DTableH
.fastMode
= (U16
)noLarge
;
1331 memcpy(dt
, &DTableH
, sizeof(DTableH
));
1336 #ifndef FSEv05_COMMONDEFS_ONLY
1337 /*-****************************************
1338 * FSEv05 helper functions
1339 ******************************************/
1340 unsigned FSEv05_isError(size_t code
) { return ERR_isError(code
); }
1342 const char* FSEv05_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1345 /*-**************************************************************
1346 * FSEv05 NCount encoding-decoding
1347 ****************************************************************/
1348 static short FSEv05_abs(short a
) { return a
<0 ? -a
: a
; }
1351 size_t FSEv05_readNCount (short* normalizedCounter
, unsigned* maxSVPtr
, unsigned* tableLogPtr
,
1352 const void* headerBuffer
, size_t hbSize
)
1354 const BYTE
* const istart
= (const BYTE
*) headerBuffer
;
1355 const BYTE
* const iend
= istart
+ hbSize
;
1356 const BYTE
* ip
= istart
;
1362 unsigned charnum
= 0;
1365 if (hbSize
< 4) return ERROR(srcSize_wrong
);
1366 bitStream
= MEM_readLE32(ip
);
1367 nbBits
= (bitStream
& 0xF) + FSEv05_MIN_TABLELOG
; /* extract tableLog */
1368 if (nbBits
> FSEv05_TABLELOG_ABSOLUTE_MAX
) return ERROR(tableLog_tooLarge
);
1371 *tableLogPtr
= nbBits
;
1372 remaining
= (1<<nbBits
)+1;
1373 threshold
= 1<<nbBits
;
1376 while ((remaining
>1) && (charnum
<=*maxSVPtr
)) {
1378 unsigned n0
= charnum
;
1379 while ((bitStream
& 0xFFFF) == 0xFFFF) {
1383 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1388 while ((bitStream
& 3) == 3) {
1393 n0
+= bitStream
& 3;
1395 if (n0
> *maxSVPtr
) return ERROR(maxSymbolValue_tooSmall
);
1396 while (charnum
< n0
) normalizedCounter
[charnum
++] = 0;
1397 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1400 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1406 const short max
= (short)((2*threshold
-1)-remaining
);
1409 if ((bitStream
& (threshold
-1)) < (U32
)max
) {
1410 count
= (short)(bitStream
& (threshold
-1));
1411 bitCount
+= nbBits
-1;
1413 count
= (short)(bitStream
& (2*threshold
-1));
1414 if (count
>= threshold
) count
-= max
;
1418 count
--; /* extra accuracy */
1419 remaining
-= FSEv05_abs(count
);
1420 normalizedCounter
[charnum
++] = count
;
1422 while (remaining
< threshold
) {
1427 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1431 bitCount
-= (int)(8 * (iend
- 4 - ip
));
1434 bitStream
= MEM_readLE32(ip
) >> (bitCount
& 31);
1436 if (remaining
!= 1) return ERROR(GENERIC
);
1437 *maxSVPtr
= charnum
-1;
1439 ip
+= (bitCount
+7)>>3;
1440 if ((size_t)(ip
-istart
) > hbSize
) return ERROR(srcSize_wrong
);
1446 /*-*******************************************************
1447 * Decompression (Byte symbols)
1448 *********************************************************/
1449 size_t FSEv05_buildDTable_rle (FSEv05_DTable
* dt
, BYTE symbolValue
)
1452 FSEv05_DTableHeader
* const DTableH
= (FSEv05_DTableHeader
*)ptr
;
1453 void* dPtr
= dt
+ 1;
1454 FSEv05_decode_t
* const cell
= (FSEv05_decode_t
*)dPtr
;
1456 DTableH
->tableLog
= 0;
1457 DTableH
->fastMode
= 0;
1460 cell
->symbol
= symbolValue
;
1467 size_t FSEv05_buildDTable_raw (FSEv05_DTable
* dt
, unsigned nbBits
)
1470 FSEv05_DTableHeader
* const DTableH
= (FSEv05_DTableHeader
*)ptr
;
1471 void* dPtr
= dt
+ 1;
1472 FSEv05_decode_t
* const dinfo
= (FSEv05_decode_t
*)dPtr
;
1473 const unsigned tableSize
= 1 << nbBits
;
1474 const unsigned tableMask
= tableSize
- 1;
1475 const unsigned maxSymbolValue
= tableMask
;
1479 if (nbBits
< 1) return ERROR(GENERIC
); /* min size */
1481 /* Build Decoding Table */
1482 DTableH
->tableLog
= (U16
)nbBits
;
1483 DTableH
->fastMode
= 1;
1484 for (s
=0; s
<=maxSymbolValue
; s
++) {
1485 dinfo
[s
].newState
= 0;
1486 dinfo
[s
].symbol
= (BYTE
)s
;
1487 dinfo
[s
].nbBits
= (BYTE
)nbBits
;
1493 FORCE_INLINE
size_t FSEv05_decompress_usingDTable_generic(
1494 void* dst
, size_t maxDstSize
,
1495 const void* cSrc
, size_t cSrcSize
,
1496 const FSEv05_DTable
* dt
, const unsigned fast
)
1498 BYTE
* const ostart
= (BYTE
*) dst
;
1500 BYTE
* const omax
= op
+ maxDstSize
;
1501 BYTE
* const olimit
= omax
-3;
1503 BITv05_DStream_t bitD
;
1504 FSEv05_DState_t state1
;
1505 FSEv05_DState_t state2
;
1509 errorCode
= BITv05_initDStream(&bitD
, cSrc
, cSrcSize
); /* replaced last arg by maxCompressed Size */
1510 if (FSEv05_isError(errorCode
)) return errorCode
;
1512 FSEv05_initDState(&state1
, &bitD
, dt
);
1513 FSEv05_initDState(&state2
, &bitD
, dt
);
1515 #define FSEv05_GETSYMBOL(statePtr) fast ? FSEv05_decodeSymbolFast(statePtr, &bitD) : FSEv05_decodeSymbol(statePtr, &bitD)
1517 /* 4 symbols per loop */
1518 for ( ; (BITv05_reloadDStream(&bitD
)==BITv05_DStream_unfinished
) && (op
<olimit
) ; op
+=4) {
1519 op
[0] = FSEv05_GETSYMBOL(&state1
);
1521 if (FSEv05_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1522 BITv05_reloadDStream(&bitD
);
1524 op
[1] = FSEv05_GETSYMBOL(&state2
);
1526 if (FSEv05_MAX_TABLELOG
*4+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1527 { if (BITv05_reloadDStream(&bitD
) > BITv05_DStream_unfinished
) { op
+=2; break; } }
1529 op
[2] = FSEv05_GETSYMBOL(&state1
);
1531 if (FSEv05_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1532 BITv05_reloadDStream(&bitD
);
1534 op
[3] = FSEv05_GETSYMBOL(&state2
);
1538 /* note : BITv05_reloadDStream(&bitD) >= FSEv05_DStream_partiallyFilled; Ends at exactly BITv05_DStream_completed */
1540 if ( (BITv05_reloadDStream(&bitD
)>BITv05_DStream_completed
) || (op
==omax
) || (BITv05_endOfDStream(&bitD
) && (fast
|| FSEv05_endOfDState(&state1
))) )
1543 *op
++ = FSEv05_GETSYMBOL(&state1
);
1545 if ( (BITv05_reloadDStream(&bitD
)>BITv05_DStream_completed
) || (op
==omax
) || (BITv05_endOfDStream(&bitD
) && (fast
|| FSEv05_endOfDState(&state2
))) )
1548 *op
++ = FSEv05_GETSYMBOL(&state2
);
1552 if (BITv05_endOfDStream(&bitD
) && FSEv05_endOfDState(&state1
) && FSEv05_endOfDState(&state2
))
1555 if (op
==omax
) return ERROR(dstSize_tooSmall
); /* dst buffer is full, but cSrc unfinished */
1557 return ERROR(corruption_detected
);
1561 size_t FSEv05_decompress_usingDTable(void* dst
, size_t originalSize
,
1562 const void* cSrc
, size_t cSrcSize
,
1563 const FSEv05_DTable
* dt
)
1565 const void* ptr
= dt
;
1566 const FSEv05_DTableHeader
* DTableH
= (const FSEv05_DTableHeader
*)ptr
;
1567 const U32 fastMode
= DTableH
->fastMode
;
1569 /* select fast mode (static) */
1570 if (fastMode
) return FSEv05_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 1);
1571 return FSEv05_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 0);
1575 size_t FSEv05_decompress(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
)
1577 const BYTE
* const istart
= (const BYTE
*)cSrc
;
1578 const BYTE
* ip
= istart
;
1579 short counting
[FSEv05_MAX_SYMBOL_VALUE
+1];
1580 DTable_max_t dt
; /* Static analyzer seems unable to understand this table will be properly initialized later */
1582 unsigned maxSymbolValue
= FSEv05_MAX_SYMBOL_VALUE
;
1585 if (cSrcSize
<2) return ERROR(srcSize_wrong
); /* too small input size */
1587 /* normal FSEv05 decoding mode */
1588 errorCode
= FSEv05_readNCount (counting
, &maxSymbolValue
, &tableLog
, istart
, cSrcSize
);
1589 if (FSEv05_isError(errorCode
)) return errorCode
;
1590 if (errorCode
>= cSrcSize
) return ERROR(srcSize_wrong
); /* too small input size */
1592 cSrcSize
-= errorCode
;
1594 errorCode
= FSEv05_buildDTable (dt
, counting
, maxSymbolValue
, tableLog
);
1595 if (FSEv05_isError(errorCode
)) return errorCode
;
1597 /* always return, even if it is an error code */
1598 return FSEv05_decompress_usingDTable (dst
, maxDstSize
, ip
, cSrcSize
, dt
);
1603 #endif /* FSEv05_COMMONDEFS_ONLY */
1604 /* ******************************************************************
1605 Huff0 : Huffman coder, part of New Generation Entropy library
1607 Copyright (C) 2013-2016, Yann Collet.
1609 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1611 Redistribution and use in source and binary forms, with or without
1612 modification, are permitted provided that the following conditions are
1615 * Redistributions of source code must retain the above copyright
1616 notice, this list of conditions and the following disclaimer.
1617 * Redistributions in binary form must reproduce the above
1618 copyright notice, this list of conditions and the following disclaimer
1619 in the documentation and/or other materials provided with the
1622 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1623 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1624 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1625 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1626 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1627 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1628 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1629 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1630 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1631 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1632 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1634 You can contact the author at :
1635 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1636 ****************************************************************** */
1640 #if defined (__cplusplus)
1646 /* ****************************************
1647 * Huff0 simple functions
1648 ******************************************/
1649 size_t HUFv05_decompress(void* dst
, size_t dstSize
,
1650 const void* cSrc
, size_t cSrcSize
);
1652 HUFv05_decompress():
1653 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1654 into already allocated destination buffer 'dst', of size 'dstSize'.
1655 @dstSize : must be the **exact** size of original (uncompressed) data.
1656 Note : in contrast with FSEv05, HUFv05_decompress can regenerate
1657 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1658 because it knows size to regenerate.
1659 @return : size of regenerated data (== dstSize)
1660 or an error code, which can be tested using HUFv05_isError()
1664 /* ****************************************
1666 ******************************************/
1667 /* Error Management */
1668 unsigned HUFv05_isError(size_t code
); /* tells if a return value is an error code */
1669 const char* HUFv05_getErrorName(size_t code
); /* provides error code string (useful for debugging) */
1672 #if defined (__cplusplus)
1677 /* ******************************************************************
1678 Huff0 : Huffman codec, part of New Generation Entropy library
1679 header file, for static linking only
1680 Copyright (C) 2013-2016, Yann Collet
1682 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1684 Redistribution and use in source and binary forms, with or without
1685 modification, are permitted provided that the following conditions are
1688 * Redistributions of source code must retain the above copyright
1689 notice, this list of conditions and the following disclaimer.
1690 * Redistributions in binary form must reproduce the above
1691 copyright notice, this list of conditions and the following disclaimer
1692 in the documentation and/or other materials provided with the
1695 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1696 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1697 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1698 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1699 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1700 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1701 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1702 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1703 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1704 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1705 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1707 You can contact the author at :
1708 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1709 ****************************************************************** */
1710 #ifndef HUF0_STATIC_H
1711 #define HUF0_STATIC_H
1713 #if defined (__cplusplus)
1719 /* ****************************************
1721 ******************************************/
1722 /* static allocation of Huff0's DTable */
1723 #define HUFv05_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1724 #define HUFv05_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1725 unsigned short DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1726 #define HUFv05_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1727 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1728 #define HUFv05_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1729 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1732 /* ****************************************
1733 * Advanced decompression functions
1734 ******************************************/
1735 size_t HUFv05_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* single-symbol decoder */
1736 size_t HUFv05_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* double-symbols decoder */
1739 /* ****************************************
1740 * Huff0 detailed API
1741 ******************************************/
1743 HUFv05_decompress() does the following:
1744 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1745 2. build Huffman table from save, using HUFv05_readDTableXn()
1746 3. decode 1 or 4 segments in parallel using HUFv05_decompressSXn_usingDTable
1748 size_t HUFv05_readDTableX2 (unsigned short* DTable
, const void* src
, size_t srcSize
);
1749 size_t HUFv05_readDTableX4 (unsigned* DTable
, const void* src
, size_t srcSize
);
1751 size_t HUFv05_decompress4X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned short* DTable
);
1752 size_t HUFv05_decompress4X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned* DTable
);
1755 /* single stream variants */
1757 size_t HUFv05_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* single-symbol decoder */
1758 size_t HUFv05_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* double-symbol decoder */
1760 size_t HUFv05_decompress1X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned short* DTable
);
1761 size_t HUFv05_decompress1X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned* DTable
);
1765 #if defined (__cplusplus)
1769 #endif /* HUF0_STATIC_H */
1770 /* ******************************************************************
1771 Huff0 : Huffman coder, part of New Generation Entropy library
1772 Copyright (C) 2013-2015, Yann Collet.
1774 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1776 Redistribution and use in source and binary forms, with or without
1777 modification, are permitted provided that the following conditions are
1780 * Redistributions of source code must retain the above copyright
1781 notice, this list of conditions and the following disclaimer.
1782 * Redistributions in binary form must reproduce the above
1783 copyright notice, this list of conditions and the following disclaimer
1784 in the documentation and/or other materials provided with the
1787 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1788 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1789 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1790 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1791 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1792 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1793 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1794 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1795 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1796 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1797 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1799 You can contact the author at :
1800 - FSEv05+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1801 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1802 ****************************************************************** */
1804 /* **************************************************************
1805 * Compiler specifics
1806 ****************************************************************/
1807 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1808 /* inline is defined */
1809 #elif defined(_MSC_VER)
1810 # define inline __inline
1812 # define inline /* disable inline */
1816 #ifdef _MSC_VER /* Visual Studio */
1817 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1821 /* **************************************************************
1823 ****************************************************************/
1824 #include <stdlib.h> /* malloc, free, qsort */
1825 #include <string.h> /* memcpy, memset */
1826 #include <stdio.h> /* printf (debug) */
1829 /* **************************************************************
1831 ****************************************************************/
1832 #define HUFv05_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv05_MAX_TABLELOG. Beyond that value, code does not work */
1833 #define HUFv05_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv05_ABSOLUTEMAX_TABLELOG */
1834 #define HUFv05_DEFAULT_TABLELOG HUFv05_MAX_TABLELOG /* tableLog by default, when not specified */
1835 #define HUFv05_MAX_SYMBOL_VALUE 255
1836 #if (HUFv05_MAX_TABLELOG > HUFv05_ABSOLUTEMAX_TABLELOG)
1837 # error "HUFv05_MAX_TABLELOG is too large !"
1841 /* **************************************************************
1843 ****************************************************************/
1844 unsigned HUFv05_isError(size_t code
) { return ERR_isError(code
); }
1845 const char* HUFv05_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1846 #define HUFv05_STATIC_ASSERT(c) { enum { HUFv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1849 /* *******************************************************
1850 * Huff0 : Huffman block decompression
1851 *********************************************************/
1852 typedef struct { BYTE byte
; BYTE nbBits
; } HUFv05_DEltX2
; /* single-symbol decoding */
1854 typedef struct { U16 sequence
; BYTE nbBits
; BYTE length
; } HUFv05_DEltX4
; /* double-symbols decoding */
1856 typedef struct { BYTE symbol
; BYTE weight
; } sortedSymbol_t
;
1858 /*! HUFv05_readStats
1859 Read compact Huffman tree, saved by HUFv05_writeCTable
1860 @huffWeight : destination buffer
1861 @return : size read from `src`
1863 static size_t HUFv05_readStats(BYTE
* huffWeight
, size_t hwSize
, U32
* rankStats
,
1864 U32
* nbSymbolsPtr
, U32
* tableLogPtr
,
1865 const void* src
, size_t srcSize
)
1869 const BYTE
* ip
= (const BYTE
*) src
;
1874 if (!srcSize
) return ERROR(srcSize_wrong
);
1876 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1878 if (iSize
>= 128) { /* special header */
1879 if (iSize
>= (242)) { /* RLE */
1880 static int l
[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1881 oSize
= l
[iSize
-242];
1882 memset(huffWeight
, 1, hwSize
);
1885 else { /* Incompressible */
1886 oSize
= iSize
- 127;
1887 iSize
= ((oSize
+1)/2);
1888 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1889 if (oSize
>= hwSize
) return ERROR(corruption_detected
);
1891 for (n
=0; n
<oSize
; n
+=2) {
1892 huffWeight
[n
] = ip
[n
/2] >> 4;
1893 huffWeight
[n
+1] = ip
[n
/2] & 15;
1895 else { /* header compressed with FSEv05 (normal case) */
1896 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1897 oSize
= FSEv05_decompress(huffWeight
, hwSize
-1, ip
+1, iSize
); /* max (hwSize-1) values decoded, as last one is implied */
1898 if (FSEv05_isError(oSize
)) return oSize
;
1901 /* collect weight stats */
1902 memset(rankStats
, 0, (HUFv05_ABSOLUTEMAX_TABLELOG
+ 1) * sizeof(U32
));
1904 for (n
=0; n
<oSize
; n
++) {
1905 if (huffWeight
[n
] >= HUFv05_ABSOLUTEMAX_TABLELOG
) return ERROR(corruption_detected
);
1906 rankStats
[huffWeight
[n
]]++;
1907 weightTotal
+= (1 << huffWeight
[n
]) >> 1;
1909 if (weightTotal
== 0) return ERROR(corruption_detected
);
1911 /* get last non-null symbol weight (implied, total must be 2^n) */
1912 tableLog
= BITv05_highbit32(weightTotal
) + 1;
1913 if (tableLog
> HUFv05_ABSOLUTEMAX_TABLELOG
) return ERROR(corruption_detected
);
1914 { /* determine last weight */
1915 U32 total
= 1 << tableLog
;
1916 U32 rest
= total
- weightTotal
;
1917 U32 verif
= 1 << BITv05_highbit32(rest
);
1918 U32 lastWeight
= BITv05_highbit32(rest
) + 1;
1919 if (verif
!= rest
) return ERROR(corruption_detected
); /* last value must be a clean power of 2 */
1920 huffWeight
[oSize
] = (BYTE
)lastWeight
;
1921 rankStats
[lastWeight
]++;
1924 /* check tree construction validity */
1925 if ((rankStats
[1] < 2) || (rankStats
[1] & 1)) return ERROR(corruption_detected
); /* by construction : at least 2 elts of rank 1, must be even */
1928 *nbSymbolsPtr
= (U32
)(oSize
+1);
1929 *tableLogPtr
= tableLog
;
1934 /*-***************************/
1935 /* single-symbol decoding */
1936 /*-***************************/
1938 size_t HUFv05_readDTableX2 (U16
* DTable
, const void* src
, size_t srcSize
)
1940 BYTE huffWeight
[HUFv05_MAX_SYMBOL_VALUE
+ 1];
1941 U32 rankVal
[HUFv05_ABSOLUTEMAX_TABLELOG
+ 1]; /* large enough for values from 0 to 16 */
1947 void* const dtPtr
= DTable
+ 1;
1948 HUFv05_DEltX2
* const dt
= (HUFv05_DEltX2
*)dtPtr
;
1950 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX2
) == sizeof(U16
)); /* if compilation fails here, assertion is false */
1951 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1953 iSize
= HUFv05_readStats(huffWeight
, HUFv05_MAX_SYMBOL_VALUE
+ 1, rankVal
, &nbSymbols
, &tableLog
, src
, srcSize
);
1954 if (HUFv05_isError(iSize
)) return iSize
;
1957 if (tableLog
> DTable
[0]) return ERROR(tableLog_tooLarge
); /* DTable is too small */
1958 DTable
[0] = (U16
)tableLog
; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
1962 for (n
=1; n
<=tableLog
; n
++) {
1963 U32 current
= nextRankStart
;
1964 nextRankStart
+= (rankVal
[n
] << (n
-1));
1965 rankVal
[n
] = current
;
1969 for (n
=0; n
<nbSymbols
; n
++) {
1970 const U32 w
= huffWeight
[n
];
1971 const U32 length
= (1 << w
) >> 1;
1974 D
.byte
= (BYTE
)n
; D
.nbBits
= (BYTE
)(tableLog
+ 1 - w
);
1975 for (i
= rankVal
[w
]; i
< rankVal
[w
] + length
; i
++)
1977 rankVal
[w
] += length
;
1983 static BYTE
HUFv05_decodeSymbolX2(BITv05_DStream_t
* Dstream
, const HUFv05_DEltX2
* dt
, const U32 dtLog
)
1985 const size_t val
= BITv05_lookBitsFast(Dstream
, dtLog
); /* note : dtLog >= 1 */
1986 const BYTE c
= dt
[val
].byte
;
1987 BITv05_skipBits(Dstream
, dt
[val
].nbBits
);
1991 #define HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1992 *ptr++ = HUFv05_decodeSymbolX2(DStreamPtr, dt, dtLog)
1994 #define HUFv05_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1995 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
1996 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1998 #define HUFv05_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
2000 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2002 static inline size_t HUFv05_decodeStreamX2(BYTE
* p
, BITv05_DStream_t
* const bitDPtr
, BYTE
* const pEnd
, const HUFv05_DEltX2
* const dt
, const U32 dtLog
)
2004 BYTE
* const pStart
= p
;
2006 /* up to 4 symbols at a time */
2007 while ((BITv05_reloadDStream(bitDPtr
) == BITv05_DStream_unfinished
) && (p
<= pEnd
-4)) {
2008 HUFv05_DECODE_SYMBOLX2_2(p
, bitDPtr
);
2009 HUFv05_DECODE_SYMBOLX2_1(p
, bitDPtr
);
2010 HUFv05_DECODE_SYMBOLX2_2(p
, bitDPtr
);
2011 HUFv05_DECODE_SYMBOLX2_0(p
, bitDPtr
);
2014 /* closer to the end */
2015 while ((BITv05_reloadDStream(bitDPtr
) == BITv05_DStream_unfinished
) && (p
< pEnd
))
2016 HUFv05_DECODE_SYMBOLX2_0(p
, bitDPtr
);
2018 /* no more data to retrieve from bitstream, hence no need to reload */
2020 HUFv05_DECODE_SYMBOLX2_0(p
, bitDPtr
);
2025 size_t HUFv05_decompress1X2_usingDTable(
2026 void* dst
, size_t dstSize
,
2027 const void* cSrc
, size_t cSrcSize
,
2030 BYTE
* op
= (BYTE
*)dst
;
2031 BYTE
* const oend
= op
+ dstSize
;
2032 const U32 dtLog
= DTable
[0];
2033 const void* dtPtr
= DTable
;
2034 const HUFv05_DEltX2
* const dt
= ((const HUFv05_DEltX2
*)dtPtr
)+1;
2035 BITv05_DStream_t bitD
;
2037 if (dstSize
<= cSrcSize
) return ERROR(dstSize_tooSmall
);
2038 { size_t const errorCode
= BITv05_initDStream(&bitD
, cSrc
, cSrcSize
);
2039 if (HUFv05_isError(errorCode
)) return errorCode
; }
2041 HUFv05_decodeStreamX2(op
, &bitD
, oend
, dt
, dtLog
);
2044 if (!BITv05_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
2049 size_t HUFv05_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2051 HUFv05_CREATE_STATIC_DTABLEX2(DTable
, HUFv05_MAX_TABLELOG
);
2052 const BYTE
* ip
= (const BYTE
*) cSrc
;
2055 errorCode
= HUFv05_readDTableX2 (DTable
, cSrc
, cSrcSize
);
2056 if (HUFv05_isError(errorCode
)) return errorCode
;
2057 if (errorCode
>= cSrcSize
) return ERROR(srcSize_wrong
);
2059 cSrcSize
-= errorCode
;
2061 return HUFv05_decompress1X2_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2065 size_t HUFv05_decompress4X2_usingDTable(
2066 void* dst
, size_t dstSize
,
2067 const void* cSrc
, size_t cSrcSize
,
2070 const BYTE
* const istart
= (const BYTE
*) cSrc
;
2071 BYTE
* const ostart
= (BYTE
*) dst
;
2072 BYTE
* const oend
= ostart
+ dstSize
;
2073 const void* const dtPtr
= DTable
;
2074 const HUFv05_DEltX2
* const dt
= ((const HUFv05_DEltX2
*)dtPtr
) +1;
2075 const U32 dtLog
= DTable
[0];
2079 BITv05_DStream_t bitD1
;
2080 BITv05_DStream_t bitD2
;
2081 BITv05_DStream_t bitD3
;
2082 BITv05_DStream_t bitD4
;
2083 const size_t length1
= MEM_readLE16(istart
);
2084 const size_t length2
= MEM_readLE16(istart
+2);
2085 const size_t length3
= MEM_readLE16(istart
+4);
2087 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2088 const BYTE
* const istart2
= istart1
+ length1
;
2089 const BYTE
* const istart3
= istart2
+ length2
;
2090 const BYTE
* const istart4
= istart3
+ length3
;
2091 const size_t segmentSize
= (dstSize
+3) / 4;
2092 BYTE
* const opStart2
= ostart
+ segmentSize
;
2093 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2094 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2096 BYTE
* op2
= opStart2
;
2097 BYTE
* op3
= opStart3
;
2098 BYTE
* op4
= opStart4
;
2102 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2104 length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2105 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2106 errorCode
= BITv05_initDStream(&bitD1
, istart1
, length1
);
2107 if (HUFv05_isError(errorCode
)) return errorCode
;
2108 errorCode
= BITv05_initDStream(&bitD2
, istart2
, length2
);
2109 if (HUFv05_isError(errorCode
)) return errorCode
;
2110 errorCode
= BITv05_initDStream(&bitD3
, istart3
, length3
);
2111 if (HUFv05_isError(errorCode
)) return errorCode
;
2112 errorCode
= BITv05_initDStream(&bitD4
, istart4
, length4
);
2113 if (HUFv05_isError(errorCode
)) return errorCode
;
2115 /* 16-32 symbols per loop (4-8 symbols per stream) */
2116 endSignal
= BITv05_reloadDStream(&bitD1
) | BITv05_reloadDStream(&bitD2
) | BITv05_reloadDStream(&bitD3
) | BITv05_reloadDStream(&bitD4
);
2117 for ( ; (endSignal
==BITv05_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2118 HUFv05_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2119 HUFv05_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2120 HUFv05_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2121 HUFv05_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2122 HUFv05_DECODE_SYMBOLX2_1(op1
, &bitD1
);
2123 HUFv05_DECODE_SYMBOLX2_1(op2
, &bitD2
);
2124 HUFv05_DECODE_SYMBOLX2_1(op3
, &bitD3
);
2125 HUFv05_DECODE_SYMBOLX2_1(op4
, &bitD4
);
2126 HUFv05_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2127 HUFv05_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2128 HUFv05_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2129 HUFv05_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2130 HUFv05_DECODE_SYMBOLX2_0(op1
, &bitD1
);
2131 HUFv05_DECODE_SYMBOLX2_0(op2
, &bitD2
);
2132 HUFv05_DECODE_SYMBOLX2_0(op3
, &bitD3
);
2133 HUFv05_DECODE_SYMBOLX2_0(op4
, &bitD4
);
2134 endSignal
= BITv05_reloadDStream(&bitD1
) | BITv05_reloadDStream(&bitD2
) | BITv05_reloadDStream(&bitD3
) | BITv05_reloadDStream(&bitD4
);
2137 /* check corruption */
2138 if (op1
> opStart2
) return ERROR(corruption_detected
);
2139 if (op2
> opStart3
) return ERROR(corruption_detected
);
2140 if (op3
> opStart4
) return ERROR(corruption_detected
);
2141 /* note : op4 supposed already verified within main loop */
2143 /* finish bitStreams one by one */
2144 HUFv05_decodeStreamX2(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2145 HUFv05_decodeStreamX2(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2146 HUFv05_decodeStreamX2(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2147 HUFv05_decodeStreamX2(op4
, &bitD4
, oend
, dt
, dtLog
);
2150 endSignal
= BITv05_endOfDStream(&bitD1
) & BITv05_endOfDStream(&bitD2
) & BITv05_endOfDStream(&bitD3
) & BITv05_endOfDStream(&bitD4
);
2151 if (!endSignal
) return ERROR(corruption_detected
);
2158 size_t HUFv05_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2160 HUFv05_CREATE_STATIC_DTABLEX2(DTable
, HUFv05_MAX_TABLELOG
);
2161 const BYTE
* ip
= (const BYTE
*) cSrc
;
2164 errorCode
= HUFv05_readDTableX2 (DTable
, cSrc
, cSrcSize
);
2165 if (HUFv05_isError(errorCode
)) return errorCode
;
2166 if (errorCode
>= cSrcSize
) return ERROR(srcSize_wrong
);
2168 cSrcSize
-= errorCode
;
2170 return HUFv05_decompress4X2_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2174 /* *************************/
2175 /* double-symbols decoding */
2176 /* *************************/
2178 static void HUFv05_fillDTableX4Level2(HUFv05_DEltX4
* DTable
, U32 sizeLog
, const U32 consumed
,
2179 const U32
* rankValOrigin
, const int minWeight
,
2180 const sortedSymbol_t
* sortedSymbols
, const U32 sortedListSize
,
2181 U32 nbBitsBaseline
, U16 baseSeq
)
2184 U32 rankVal
[HUFv05_ABSOLUTEMAX_TABLELOG
+ 1];
2187 /* get pre-calculated rankVal */
2188 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2190 /* fill skipped values */
2192 U32 i
, skipSize
= rankVal
[minWeight
];
2193 MEM_writeLE16(&(DElt
.sequence
), baseSeq
);
2194 DElt
.nbBits
= (BYTE
)(consumed
);
2196 for (i
= 0; i
< skipSize
; i
++)
2201 for (s
=0; s
<sortedListSize
; s
++) { /* note : sortedSymbols already skipped */
2202 const U32 symbol
= sortedSymbols
[s
].symbol
;
2203 const U32 weight
= sortedSymbols
[s
].weight
;
2204 const U32 nbBits
= nbBitsBaseline
- weight
;
2205 const U32 length
= 1 << (sizeLog
-nbBits
);
2206 const U32 start
= rankVal
[weight
];
2208 const U32 end
= start
+ length
;
2210 MEM_writeLE16(&(DElt
.sequence
), (U16
)(baseSeq
+ (symbol
<< 8)));
2211 DElt
.nbBits
= (BYTE
)(nbBits
+ consumed
);
2213 do { DTable
[i
++] = DElt
; } while (i
<end
); /* since length >= 1 */
2215 rankVal
[weight
] += length
;
2219 typedef U32 rankVal_t
[HUFv05_ABSOLUTEMAX_TABLELOG
][HUFv05_ABSOLUTEMAX_TABLELOG
+ 1];
2221 static void HUFv05_fillDTableX4(HUFv05_DEltX4
* DTable
, const U32 targetLog
,
2222 const sortedSymbol_t
* sortedList
, const U32 sortedListSize
,
2223 const U32
* rankStart
, rankVal_t rankValOrigin
, const U32 maxWeight
,
2224 const U32 nbBitsBaseline
)
2226 U32 rankVal
[HUFv05_ABSOLUTEMAX_TABLELOG
+ 1];
2227 const int scaleLog
= nbBitsBaseline
- targetLog
; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2228 const U32 minBits
= nbBitsBaseline
- maxWeight
;
2231 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2234 for (s
=0; s
<sortedListSize
; s
++) {
2235 const U16 symbol
= sortedList
[s
].symbol
;
2236 const U32 weight
= sortedList
[s
].weight
;
2237 const U32 nbBits
= nbBitsBaseline
- weight
;
2238 const U32 start
= rankVal
[weight
];
2239 const U32 length
= 1 << (targetLog
-nbBits
);
2241 if (targetLog
-nbBits
>= minBits
) { /* enough room for a second symbol */
2243 int minWeight
= nbBits
+ scaleLog
;
2244 if (minWeight
< 1) minWeight
= 1;
2245 sortedRank
= rankStart
[minWeight
];
2246 HUFv05_fillDTableX4Level2(DTable
+start
, targetLog
-nbBits
, nbBits
,
2247 rankValOrigin
[nbBits
], minWeight
,
2248 sortedList
+sortedRank
, sortedListSize
-sortedRank
,
2249 nbBitsBaseline
, symbol
);
2252 const U32 end
= start
+ length
;
2255 MEM_writeLE16(&(DElt
.sequence
), symbol
);
2256 DElt
.nbBits
= (BYTE
)(nbBits
);
2258 for (i
= start
; i
< end
; i
++)
2261 rankVal
[weight
] += length
;
2265 size_t HUFv05_readDTableX4 (U32
* DTable
, const void* src
, size_t srcSize
)
2267 BYTE weightList
[HUFv05_MAX_SYMBOL_VALUE
+ 1];
2268 sortedSymbol_t sortedSymbol
[HUFv05_MAX_SYMBOL_VALUE
+ 1];
2269 U32 rankStats
[HUFv05_ABSOLUTEMAX_TABLELOG
+ 1] = { 0 };
2270 U32 rankStart0
[HUFv05_ABSOLUTEMAX_TABLELOG
+ 2] = { 0 };
2271 U32
* const rankStart
= rankStart0
+1;
2273 U32 tableLog
, maxW
, sizeOfSort
, nbSymbols
;
2274 const U32 memLog
= DTable
[0];
2276 void* dtPtr
= DTable
;
2277 HUFv05_DEltX4
* const dt
= ((HUFv05_DEltX4
*)dtPtr
) + 1;
2279 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX4
) == sizeof(U32
)); /* if compilation fails here, assertion is false */
2280 if (memLog
> HUFv05_ABSOLUTEMAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
2281 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2283 iSize
= HUFv05_readStats(weightList
, HUFv05_MAX_SYMBOL_VALUE
+ 1, rankStats
, &nbSymbols
, &tableLog
, src
, srcSize
);
2284 if (HUFv05_isError(iSize
)) return iSize
;
2287 if (tableLog
> memLog
) return ERROR(tableLog_tooLarge
); /* DTable can't fit code depth */
2289 /* find maxWeight */
2290 for (maxW
= tableLog
; rankStats
[maxW
]==0; maxW
--) {} /* necessarily finds a solution before 0 */
2292 /* Get start index of each weight */
2294 U32 w
, nextRankStart
= 0;
2295 for (w
=1; w
<=maxW
; w
++) {
2296 U32 current
= nextRankStart
;
2297 nextRankStart
+= rankStats
[w
];
2298 rankStart
[w
] = current
;
2300 rankStart
[0] = nextRankStart
; /* put all 0w symbols at the end of sorted list*/
2301 sizeOfSort
= nextRankStart
;
2304 /* sort symbols by weight */
2307 for (s
=0; s
<nbSymbols
; s
++) {
2308 U32 w
= weightList
[s
];
2309 U32 r
= rankStart
[w
]++;
2310 sortedSymbol
[r
].symbol
= (BYTE
)s
;
2311 sortedSymbol
[r
].weight
= (BYTE
)w
;
2313 rankStart
[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2318 const U32 minBits
= tableLog
+1 - maxW
;
2319 U32 nextRankVal
= 0;
2321 const int rescale
= (memLog
-tableLog
) - 1; /* tableLog <= memLog */
2322 U32
* rankVal0
= rankVal
[0];
2323 for (w
=1; w
<=maxW
; w
++) {
2324 U32 current
= nextRankVal
;
2325 nextRankVal
+= rankStats
[w
] << (w
+rescale
);
2326 rankVal0
[w
] = current
;
2328 for (consumed
= minBits
; consumed
<= memLog
- minBits
; consumed
++) {
2329 U32
* rankValPtr
= rankVal
[consumed
];
2330 for (w
= 1; w
<= maxW
; w
++) {
2331 rankValPtr
[w
] = rankVal0
[w
] >> consumed
;
2334 HUFv05_fillDTableX4(dt
, memLog
,
2335 sortedSymbol
, sizeOfSort
,
2336 rankStart0
, rankVal
, maxW
,
2343 static U32
HUFv05_decodeSymbolX4(void* op
, BITv05_DStream_t
* DStream
, const HUFv05_DEltX4
* dt
, const U32 dtLog
)
2345 const size_t val
= BITv05_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2346 memcpy(op
, dt
+val
, 2);
2347 BITv05_skipBits(DStream
, dt
[val
].nbBits
);
2348 return dt
[val
].length
;
2351 static U32
HUFv05_decodeLastSymbolX4(void* op
, BITv05_DStream_t
* DStream
, const HUFv05_DEltX4
* dt
, const U32 dtLog
)
2353 const size_t val
= BITv05_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2354 memcpy(op
, dt
+val
, 1);
2355 if (dt
[val
].length
==1) BITv05_skipBits(DStream
, dt
[val
].nbBits
);
2357 if (DStream
->bitsConsumed
< (sizeof(DStream
->bitContainer
)*8)) {
2358 BITv05_skipBits(DStream
, dt
[val
].nbBits
);
2359 if (DStream
->bitsConsumed
> (sizeof(DStream
->bitContainer
)*8))
2360 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 */
2366 #define HUFv05_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2367 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2369 #define HUFv05_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2370 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
2371 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2373 #define HUFv05_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2375 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2377 static inline size_t HUFv05_decodeStreamX4(BYTE
* p
, BITv05_DStream_t
* bitDPtr
, BYTE
* const pEnd
, const HUFv05_DEltX4
* const dt
, const U32 dtLog
)
2379 BYTE
* const pStart
= p
;
2381 /* up to 8 symbols at a time */
2382 while ((BITv05_reloadDStream(bitDPtr
) == BITv05_DStream_unfinished
) && (p
< pEnd
-7)) {
2383 HUFv05_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2384 HUFv05_DECODE_SYMBOLX4_1(p
, bitDPtr
);
2385 HUFv05_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2386 HUFv05_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2389 /* closer to the end */
2390 while ((BITv05_reloadDStream(bitDPtr
) == BITv05_DStream_unfinished
) && (p
<= pEnd
-2))
2391 HUFv05_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2394 HUFv05_DECODE_SYMBOLX4_0(p
, bitDPtr
); /* no need to reload : reached the end of DStream */
2397 p
+= HUFv05_decodeLastSymbolX4(p
, bitDPtr
, dt
, dtLog
);
2403 size_t HUFv05_decompress1X4_usingDTable(
2404 void* dst
, size_t dstSize
,
2405 const void* cSrc
, size_t cSrcSize
,
2408 const BYTE
* const istart
= (const BYTE
*) cSrc
;
2409 BYTE
* const ostart
= (BYTE
*) dst
;
2410 BYTE
* const oend
= ostart
+ dstSize
;
2412 const U32 dtLog
= DTable
[0];
2413 const void* const dtPtr
= DTable
;
2414 const HUFv05_DEltX4
* const dt
= ((const HUFv05_DEltX4
*)dtPtr
) +1;
2418 BITv05_DStream_t bitD
;
2419 errorCode
= BITv05_initDStream(&bitD
, istart
, cSrcSize
);
2420 if (HUFv05_isError(errorCode
)) return errorCode
;
2422 /* finish bitStreams one by one */
2423 HUFv05_decodeStreamX4(ostart
, &bitD
, oend
, dt
, dtLog
);
2426 if (!BITv05_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
2432 size_t HUFv05_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2434 HUFv05_CREATE_STATIC_DTABLEX4(DTable
, HUFv05_MAX_TABLELOG
);
2435 const BYTE
* ip
= (const BYTE
*) cSrc
;
2437 size_t hSize
= HUFv05_readDTableX4 (DTable
, cSrc
, cSrcSize
);
2438 if (HUFv05_isError(hSize
)) return hSize
;
2439 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2443 return HUFv05_decompress1X4_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2446 size_t HUFv05_decompress4X4_usingDTable(
2447 void* dst
, size_t dstSize
,
2448 const void* cSrc
, size_t cSrcSize
,
2451 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2454 const BYTE
* const istart
= (const BYTE
*) cSrc
;
2455 BYTE
* const ostart
= (BYTE
*) dst
;
2456 BYTE
* const oend
= ostart
+ dstSize
;
2457 const void* const dtPtr
= DTable
;
2458 const HUFv05_DEltX4
* const dt
= ((const HUFv05_DEltX4
*)dtPtr
) +1;
2459 const U32 dtLog
= DTable
[0];
2463 BITv05_DStream_t bitD1
;
2464 BITv05_DStream_t bitD2
;
2465 BITv05_DStream_t bitD3
;
2466 BITv05_DStream_t bitD4
;
2467 const size_t length1
= MEM_readLE16(istart
);
2468 const size_t length2
= MEM_readLE16(istart
+2);
2469 const size_t length3
= MEM_readLE16(istart
+4);
2471 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2472 const BYTE
* const istart2
= istart1
+ length1
;
2473 const BYTE
* const istart3
= istart2
+ length2
;
2474 const BYTE
* const istart4
= istart3
+ length3
;
2475 const size_t segmentSize
= (dstSize
+3) / 4;
2476 BYTE
* const opStart2
= ostart
+ segmentSize
;
2477 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2478 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2480 BYTE
* op2
= opStart2
;
2481 BYTE
* op3
= opStart3
;
2482 BYTE
* op4
= opStart4
;
2485 length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2486 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2487 errorCode
= BITv05_initDStream(&bitD1
, istart1
, length1
);
2488 if (HUFv05_isError(errorCode
)) return errorCode
;
2489 errorCode
= BITv05_initDStream(&bitD2
, istart2
, length2
);
2490 if (HUFv05_isError(errorCode
)) return errorCode
;
2491 errorCode
= BITv05_initDStream(&bitD3
, istart3
, length3
);
2492 if (HUFv05_isError(errorCode
)) return errorCode
;
2493 errorCode
= BITv05_initDStream(&bitD4
, istart4
, length4
);
2494 if (HUFv05_isError(errorCode
)) return errorCode
;
2496 /* 16-32 symbols per loop (4-8 symbols per stream) */
2497 endSignal
= BITv05_reloadDStream(&bitD1
) | BITv05_reloadDStream(&bitD2
) | BITv05_reloadDStream(&bitD3
) | BITv05_reloadDStream(&bitD4
);
2498 for ( ; (endSignal
==BITv05_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2499 HUFv05_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2500 HUFv05_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2501 HUFv05_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2502 HUFv05_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2503 HUFv05_DECODE_SYMBOLX4_1(op1
, &bitD1
);
2504 HUFv05_DECODE_SYMBOLX4_1(op2
, &bitD2
);
2505 HUFv05_DECODE_SYMBOLX4_1(op3
, &bitD3
);
2506 HUFv05_DECODE_SYMBOLX4_1(op4
, &bitD4
);
2507 HUFv05_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2508 HUFv05_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2509 HUFv05_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2510 HUFv05_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2511 HUFv05_DECODE_SYMBOLX4_0(op1
, &bitD1
);
2512 HUFv05_DECODE_SYMBOLX4_0(op2
, &bitD2
);
2513 HUFv05_DECODE_SYMBOLX4_0(op3
, &bitD3
);
2514 HUFv05_DECODE_SYMBOLX4_0(op4
, &bitD4
);
2516 endSignal
= BITv05_reloadDStream(&bitD1
) | BITv05_reloadDStream(&bitD2
) | BITv05_reloadDStream(&bitD3
) | BITv05_reloadDStream(&bitD4
);
2519 /* check corruption */
2520 if (op1
> opStart2
) return ERROR(corruption_detected
);
2521 if (op2
> opStart3
) return ERROR(corruption_detected
);
2522 if (op3
> opStart4
) return ERROR(corruption_detected
);
2523 /* note : op4 supposed already verified within main loop */
2525 /* finish bitStreams one by one */
2526 HUFv05_decodeStreamX4(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2527 HUFv05_decodeStreamX4(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2528 HUFv05_decodeStreamX4(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2529 HUFv05_decodeStreamX4(op4
, &bitD4
, oend
, dt
, dtLog
);
2532 endSignal
= BITv05_endOfDStream(&bitD1
) & BITv05_endOfDStream(&bitD2
) & BITv05_endOfDStream(&bitD3
) & BITv05_endOfDStream(&bitD4
);
2533 if (!endSignal
) return ERROR(corruption_detected
);
2541 size_t HUFv05_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2543 HUFv05_CREATE_STATIC_DTABLEX4(DTable
, HUFv05_MAX_TABLELOG
);
2544 const BYTE
* ip
= (const BYTE
*) cSrc
;
2546 size_t hSize
= HUFv05_readDTableX4 (DTable
, cSrc
, cSrcSize
);
2547 if (HUFv05_isError(hSize
)) return hSize
;
2548 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2552 return HUFv05_decompress4X4_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2556 /* ********************************/
2557 /* Generic decompression selector */
2558 /* ********************************/
2560 typedef struct { U32 tableTime
; U32 decode256Time
; } algo_time_t
;
2561 static const algo_time_t algoTime
[16 /* Quantization */][3 /* single, double, quad */] =
2563 /* single, double, quad */
2564 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2565 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2566 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2567 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2568 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2569 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2570 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2571 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2572 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2573 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2574 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2575 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2576 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2577 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2578 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2579 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2582 typedef size_t (*decompressionAlgo
)(void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
);
2584 size_t HUFv05_decompress (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2586 static const decompressionAlgo decompress
[3] = { HUFv05_decompress4X2
, HUFv05_decompress4X4
, NULL
};
2587 /* estimate decompression time */
2589 const U32 D256
= (U32
)(dstSize
>> 8);
2594 /* validation checks */
2595 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2596 if (cSrcSize
>= dstSize
) return ERROR(corruption_detected
); /* invalid, or not compressed, but not compressed already dealt with */
2597 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2599 /* decoder timing evaluation */
2600 Q
= (U32
)(cSrcSize
* 16 / dstSize
); /* Q < 16 since dstSize > cSrcSize */
2602 Dtime
[n
] = algoTime
[Q
][n
].tableTime
+ (algoTime
[Q
][n
].decode256Time
* D256
);
2604 Dtime
[1] += Dtime
[1] >> 4; Dtime
[2] += Dtime
[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2606 if (Dtime
[1] < Dtime
[0]) algoNb
= 1;
2608 return decompress
[algoNb
](dst
, dstSize
, cSrc
, cSrcSize
);
2610 //return HUFv05_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2611 //return HUFv05_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2612 //return HUFv05_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2615 zstd - standard compression library
2616 Copyright (C) 2014-2016, Yann Collet.
2618 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2620 Redistribution and use in source and binary forms, with or without
2621 modification, are permitted provided that the following conditions are
2623 * Redistributions of source code must retain the above copyright
2624 notice, this list of conditions and the following disclaimer.
2625 * Redistributions in binary form must reproduce the above
2626 copyright notice, this list of conditions and the following disclaimer
2627 in the documentation and/or other materials provided with the
2629 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2630 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2631 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2632 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2633 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2634 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2635 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2636 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2637 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2638 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2639 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2641 You can contact the author at :
2642 - zstd source repository : https://github.com/Cyan4973/zstd
2645 /* ***************************************************************
2647 *****************************************************************/
2650 * Select how default decompression function ZSTDv05_decompress() will allocate memory,
2651 * in memory stack (0), or in memory heap (1, requires malloc())
2653 #ifndef ZSTDv05_HEAPMODE
2654 # define ZSTDv05_HEAPMODE 1
2658 /*-*******************************************************
2660 *********************************************************/
2661 #include <stdlib.h> /* calloc */
2662 #include <string.h> /* memcpy, memmove */
2663 #include <stdio.h> /* debug only : printf */
2666 /*-*******************************************************
2667 * Compiler specifics
2668 *********************************************************/
2669 #ifdef _MSC_VER /* Visual Studio */
2670 # include <intrin.h> /* For Visual 2005 */
2671 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2672 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2676 /*-*************************************
2678 ***************************************/
2681 blockType_t blockType
;
2683 } blockProperties_t
;
2686 /* *******************************************************
2688 **********************************************************/
2689 static void ZSTDv05_copy4(void* dst
, const void* src
) { memcpy(dst
, src
, 4); }
2692 /* *************************************
2694 ***************************************/
2695 /*! ZSTDv05_isError() :
2696 * tells if a return value is an error code */
2697 unsigned ZSTDv05_isError(size_t code
) { return ERR_isError(code
); }
2700 /*! ZSTDv05_getErrorName() :
2701 * provides error code string (useful for debugging) */
2702 const char* ZSTDv05_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
2705 /* *************************************************************
2706 * Context management
2707 ***************************************************************/
2708 typedef enum { ZSTDv05ds_getFrameHeaderSize
, ZSTDv05ds_decodeFrameHeader
,
2709 ZSTDv05ds_decodeBlockHeader
, ZSTDv05ds_decompressBlock
} ZSTDv05_dStage
;
2711 struct ZSTDv05_DCtx_s
2713 FSEv05_DTable LLTable
[FSEv05_DTABLE_SIZE_U32(LLFSEv05Log
)];
2714 FSEv05_DTable OffTable
[FSEv05_DTABLE_SIZE_U32(OffFSEv05Log
)];
2715 FSEv05_DTable MLTable
[FSEv05_DTABLE_SIZE_U32(MLFSEv05Log
)];
2716 unsigned hufTableX4
[HUFv05_DTABLE_SIZE(HufLog
)];
2717 const void* previousDstEnd
;
2720 const void* dictEnd
;
2723 ZSTDv05_parameters params
;
2724 blockType_t bType
; /* used in ZSTDv05_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2725 ZSTDv05_dStage stage
;
2726 U32 flagStaticTables
;
2729 BYTE litBuffer
[BLOCKSIZE
+ WILDCOPY_OVERLENGTH
];
2730 BYTE headerBuffer
[ZSTDv05_frameHeaderSize_max
];
2731 }; /* typedef'd to ZSTDv05_DCtx within "zstd_static.h" */
2733 size_t ZSTDv05_sizeofDCtx (void) { return sizeof(ZSTDv05_DCtx
); }
2735 size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx
* dctx
)
2737 dctx
->expected
= ZSTDv05_frameHeaderSize_min
;
2738 dctx
->stage
= ZSTDv05ds_getFrameHeaderSize
;
2739 dctx
->previousDstEnd
= NULL
;
2742 dctx
->dictEnd
= NULL
;
2743 dctx
->hufTableX4
[0] = HufLog
;
2744 dctx
->flagStaticTables
= 0;
2748 ZSTDv05_DCtx
* ZSTDv05_createDCtx(void)
2750 ZSTDv05_DCtx
* dctx
= (ZSTDv05_DCtx
*)malloc(sizeof(ZSTDv05_DCtx
));
2751 if (dctx
==NULL
) return NULL
;
2752 ZSTDv05_decompressBegin(dctx
);
2756 size_t ZSTDv05_freeDCtx(ZSTDv05_DCtx
* dctx
)
2759 return 0; /* reserved as a potential error code in the future */
2762 void ZSTDv05_copyDCtx(ZSTDv05_DCtx
* dstDCtx
, const ZSTDv05_DCtx
* srcDCtx
)
2764 memcpy(dstDCtx
, srcDCtx
,
2765 sizeof(ZSTDv05_DCtx
) - (BLOCKSIZE
+WILDCOPY_OVERLENGTH
+ ZSTDv05_frameHeaderSize_max
)); /* no need to copy workspace */
2769 /* *************************************************************
2770 * Decompression section
2771 ***************************************************************/
2773 /* Frame format description
2774 Frame Header - [ Block Header - Block ] - Frame End
2776 - 4 bytes - Magic Number : ZSTDv05_MAGICNUMBER (defined within zstd_internal.h)
2777 - 1 byte - Window Descriptor
2779 - 3 bytes, starting with a 2-bits descriptor
2780 Uncompressed, Compressed, Frame End, unused
2782 See Block Format Description
2784 - 3 bytes, compatible with Block Header
2787 /* Block format description
2789 Block = Literal Section - Sequences Section
2790 Prerequisite : size of (compressed) block, maximum size of regenerated data
2794 1.1) Header : 1-5 bytes
2796 00 compressed by Huff0
2798 10 is Raw (uncompressed)
2800 Note : using 01 => Huff0 with precomputed table ?
2801 Note : delta map ? => compressed ?
2803 1.1.1) Huff0-compressed literal block : 3-5 bytes
2804 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2805 srcSize < 1 KB => 3 bytes (2-2-10-10)
2806 srcSize < 16KB => 4 bytes (2-2-14-14)
2807 else => 5 bytes (2-2-18-18)
2808 big endian convention
2810 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2811 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2812 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2814 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2818 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2819 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
2820 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2822 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2826 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2827 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2828 srcSize < 1 KB => 3 bytes (2-2-10-10)
2829 srcSize < 16KB => 4 bytes (2-2-14-14)
2830 else => 5 bytes (2-2-18-18)
2831 big endian convention
2833 1- CTable available (stored into workspace ?)
2834 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2837 1.2) Literal block content
2839 1.2.1) Huff0 block, using sizes from header
2842 1.2.2) Huff0 block, using prepared table
2849 2) Sequences section
2854 /** ZSTDv05_decodeFrameHeader_Part1() :
2855 * decode the 1st part of the Frame Header, which tells Frame Header size.
2856 * srcSize must be == ZSTDv05_frameHeaderSize_min.
2857 * @return : the full size of the Frame Header */
2858 static size_t ZSTDv05_decodeFrameHeader_Part1(ZSTDv05_DCtx
* zc
, const void* src
, size_t srcSize
)
2861 if (srcSize
!= ZSTDv05_frameHeaderSize_min
)
2862 return ERROR(srcSize_wrong
);
2863 magicNumber
= MEM_readLE32(src
);
2864 if (magicNumber
!= ZSTDv05_MAGICNUMBER
) return ERROR(prefix_unknown
);
2865 zc
->headerSize
= ZSTDv05_frameHeaderSize_min
;
2866 return zc
->headerSize
;
2870 size_t ZSTDv05_getFrameParams(ZSTDv05_parameters
* params
, const void* src
, size_t srcSize
)
2873 if (srcSize
< ZSTDv05_frameHeaderSize_min
) return ZSTDv05_frameHeaderSize_max
;
2874 magicNumber
= MEM_readLE32(src
);
2875 if (magicNumber
!= ZSTDv05_MAGICNUMBER
) return ERROR(prefix_unknown
);
2876 memset(params
, 0, sizeof(*params
));
2877 params
->windowLog
= (((const BYTE
*)src
)[4] & 15) + ZSTDv05_WINDOWLOG_ABSOLUTEMIN
;
2878 if ((((const BYTE
*)src
)[4] >> 4) != 0) return ERROR(frameParameter_unsupported
); /* reserved bits */
2882 /** ZSTDv05_decodeFrameHeader_Part2() :
2883 * decode the full Frame Header.
2884 * srcSize must be the size provided by ZSTDv05_decodeFrameHeader_Part1().
2885 * @return : 0, or an error code, which can be tested using ZSTDv05_isError() */
2886 static size_t ZSTDv05_decodeFrameHeader_Part2(ZSTDv05_DCtx
* zc
, const void* src
, size_t srcSize
)
2889 if (srcSize
!= zc
->headerSize
)
2890 return ERROR(srcSize_wrong
);
2891 result
= ZSTDv05_getFrameParams(&(zc
->params
), src
, srcSize
);
2892 if ((MEM_32bits()) && (zc
->params
.windowLog
> 25)) return ERROR(frameParameter_unsupported
);
2897 size_t ZSTDv05_getcBlockSize(const void* src
, size_t srcSize
, blockProperties_t
* bpPtr
)
2899 const BYTE
* const in
= (const BYTE
* const)src
;
2904 return ERROR(srcSize_wrong
);
2907 cSize
= in
[2] + (in
[1]<<8) + ((in
[0] & 7)<<16);
2909 bpPtr
->blockType
= (blockType_t
)(headerFlags
>> 6);
2910 bpPtr
->origSize
= (bpPtr
->blockType
== bt_rle
) ? cSize
: 0;
2912 if (bpPtr
->blockType
== bt_end
) return 0;
2913 if (bpPtr
->blockType
== bt_rle
) return 1;
2918 static size_t ZSTDv05_copyRawBlock(void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
2920 if (srcSize
> maxDstSize
) return ERROR(dstSize_tooSmall
);
2921 memcpy(dst
, src
, srcSize
);
2926 /*! ZSTDv05_decodeLiteralsBlock() :
2927 @return : nb of bytes read from src (< srcSize ) */
2928 size_t ZSTDv05_decodeLiteralsBlock(ZSTDv05_DCtx
* dctx
,
2929 const void* src
, size_t srcSize
) /* note : srcSize < BLOCKSIZE */
2931 const BYTE
* const istart
= (const BYTE
*) src
;
2933 /* any compressed block with literals segment must be at least this size */
2934 if (srcSize
< MIN_CBLOCK_SIZE
) return ERROR(corruption_detected
);
2936 switch(istart
[0]>> 6)
2940 size_t litSize
, litCSize
, singleStream
=0;
2941 U32 lhSize
= ((istart
[0]) >> 4) & 3;
2942 if (srcSize
< 5) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
2945 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2946 /* 2 - 2 - 10 - 10 */
2948 singleStream
= istart
[0] & 16;
2949 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
2950 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
2953 /* 2 - 2 - 14 - 14 */
2955 litSize
= ((istart
[0] & 15) << 10) + (istart
[1] << 2) + (istart
[2] >> 6);
2956 litCSize
= ((istart
[2] & 63) << 8) + istart
[3];
2959 /* 2 - 2 - 18 - 18 */
2961 litSize
= ((istart
[0] & 15) << 14) + (istart
[1] << 6) + (istart
[2] >> 2);
2962 litCSize
= ((istart
[2] & 3) << 16) + (istart
[3] << 8) + istart
[4];
2965 if (litSize
> BLOCKSIZE
) return ERROR(corruption_detected
);
2966 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
2968 if (HUFv05_isError(singleStream
?
2969 HUFv05_decompress1X2(dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) :
2970 HUFv05_decompress (dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) ))
2971 return ERROR(corruption_detected
);
2973 dctx
->litPtr
= dctx
->litBuffer
;
2974 dctx
->litSize
= litSize
;
2975 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
2976 return litCSize
+ lhSize
;
2981 size_t litSize
, litCSize
;
2982 U32 lhSize
= ((istart
[0]) >> 4) & 3;
2983 if (lhSize
!= 1) /* only case supported for now : small litSize, single stream */
2984 return ERROR(corruption_detected
);
2985 if (!dctx
->flagStaticTables
)
2986 return ERROR(dictionary_corrupted
);
2988 /* 2 - 2 - 10 - 10 */
2990 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
2991 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
2992 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
2994 errorCode
= HUFv05_decompress1X4_usingDTable(dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
, dctx
->hufTableX4
);
2995 if (HUFv05_isError(errorCode
)) return ERROR(corruption_detected
);
2997 dctx
->litPtr
= dctx
->litBuffer
;
2998 dctx
->litSize
= litSize
;
2999 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3000 return litCSize
+ lhSize
;
3005 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3008 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3010 litSize
= istart
[0] & 31;
3013 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3016 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3020 if (lhSize
+litSize
+WILDCOPY_OVERLENGTH
> srcSize
) { /* risk reading beyond src buffer with wildcopy */
3021 if (litSize
+lhSize
> srcSize
) return ERROR(corruption_detected
);
3022 memcpy(dctx
->litBuffer
, istart
+lhSize
, litSize
);
3023 dctx
->litPtr
= dctx
->litBuffer
;
3024 dctx
->litSize
= litSize
;
3025 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3026 return lhSize
+litSize
;
3028 /* direct reference into compressed stream */
3029 dctx
->litPtr
= istart
+lhSize
;
3030 dctx
->litSize
= litSize
;
3031 return lhSize
+litSize
;
3036 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3039 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3041 litSize
= istart
[0] & 31;
3044 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3047 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3048 if (srcSize
<4) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3051 if (litSize
> BLOCKSIZE
) return ERROR(corruption_detected
);
3052 memset(dctx
->litBuffer
, istart
[lhSize
], litSize
+ WILDCOPY_OVERLENGTH
);
3053 dctx
->litPtr
= dctx
->litBuffer
;
3054 dctx
->litSize
= litSize
;
3058 return ERROR(corruption_detected
); /* impossible */
3063 size_t ZSTDv05_decodeSeqHeaders(int* nbSeq
, const BYTE
** dumpsPtr
, size_t* dumpsLengthPtr
,
3064 FSEv05_DTable
* DTableLL
, FSEv05_DTable
* DTableML
, FSEv05_DTable
* DTableOffb
,
3065 const void* src
, size_t srcSize
, U32 flagStaticTable
)
3067 const BYTE
* const istart
= (const BYTE
* const)src
;
3068 const BYTE
* ip
= istart
;
3069 const BYTE
* const iend
= istart
+ srcSize
;
3070 U32 LLtype
, Offtype
, MLtype
;
3071 U32 LLlog
, Offlog
, MLlog
;
3075 if (srcSize
< MIN_SEQUENCES_SIZE
)
3076 return ERROR(srcSize_wrong
);
3080 if (*nbSeq
==0) return 1;
3081 if (*nbSeq
>= 128) {
3082 if (ip
>= iend
) return ERROR(srcSize_wrong
);
3083 *nbSeq
= ((nbSeq
[0]-128)<<8) + *ip
++;
3086 if (ip
>= iend
) return ERROR(srcSize_wrong
);
3088 Offtype
= (*ip
>> 4) & 3;
3089 MLtype
= (*ip
>> 2) & 3;
3091 if (ip
+3 > iend
) return ERROR(srcSize_wrong
);
3092 dumpsLength
= ip
[2];
3093 dumpsLength
+= ip
[1] << 8;
3096 if (ip
+2 > iend
) return ERROR(srcSize_wrong
);
3097 dumpsLength
= ip
[1];
3098 dumpsLength
+= (ip
[0] & 1) << 8;
3103 *dumpsLengthPtr
= dumpsLength
;
3106 if (ip
> iend
-3) return ERROR(srcSize_wrong
); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3110 S16 norm
[MaxML
+1]; /* assumption : MaxML >= MaxLL >= MaxOff */
3116 case FSEv05_ENCODING_RLE
:
3118 FSEv05_buildDTable_rle(DTableLL
, *ip
++);
3120 case FSEv05_ENCODING_RAW
:
3122 FSEv05_buildDTable_raw(DTableLL
, LLbits
);
3124 case FSEv05_ENCODING_STATIC
:
3125 if (!flagStaticTable
) return ERROR(corruption_detected
);
3127 case FSEv05_ENCODING_DYNAMIC
:
3128 default : /* impossible */
3130 headerSize
= FSEv05_readNCount(norm
, &max
, &LLlog
, ip
, iend
-ip
);
3131 if (FSEv05_isError(headerSize
)) return ERROR(GENERIC
);
3132 if (LLlog
> LLFSEv05Log
) return ERROR(corruption_detected
);
3134 FSEv05_buildDTable(DTableLL
, norm
, max
, LLlog
);
3139 case FSEv05_ENCODING_RLE
:
3141 if (ip
> iend
-2) return ERROR(srcSize_wrong
); /* min : "raw", hence no header, but at least xxLog bits */
3142 FSEv05_buildDTable_rle(DTableOffb
, *ip
++ & MaxOff
); /* if *ip > MaxOff, data is corrupted */
3144 case FSEv05_ENCODING_RAW
:
3146 FSEv05_buildDTable_raw(DTableOffb
, Offbits
);
3148 case FSEv05_ENCODING_STATIC
:
3149 if (!flagStaticTable
) return ERROR(corruption_detected
);
3151 case FSEv05_ENCODING_DYNAMIC
:
3152 default : /* impossible */
3154 headerSize
= FSEv05_readNCount(norm
, &max
, &Offlog
, ip
, iend
-ip
);
3155 if (FSEv05_isError(headerSize
)) return ERROR(GENERIC
);
3156 if (Offlog
> OffFSEv05Log
) return ERROR(corruption_detected
);
3158 FSEv05_buildDTable(DTableOffb
, norm
, max
, Offlog
);
3163 case FSEv05_ENCODING_RLE
:
3165 if (ip
> iend
-2) return ERROR(srcSize_wrong
); /* min : "raw", hence no header, but at least xxLog bits */
3166 FSEv05_buildDTable_rle(DTableML
, *ip
++);
3168 case FSEv05_ENCODING_RAW
:
3170 FSEv05_buildDTable_raw(DTableML
, MLbits
);
3172 case FSEv05_ENCODING_STATIC
:
3173 if (!flagStaticTable
) return ERROR(corruption_detected
);
3175 case FSEv05_ENCODING_DYNAMIC
:
3176 default : /* impossible */
3178 headerSize
= FSEv05_readNCount(norm
, &max
, &MLlog
, ip
, iend
-ip
);
3179 if (FSEv05_isError(headerSize
)) return ERROR(GENERIC
);
3180 if (MLlog
> MLFSEv05Log
) return ERROR(corruption_detected
);
3182 FSEv05_buildDTable(DTableML
, norm
, max
, MLlog
);
3196 BITv05_DStream_t DStream
;
3197 FSEv05_DState_t stateLL
;
3198 FSEv05_DState_t stateOffb
;
3199 FSEv05_DState_t stateML
;
3202 const BYTE
* dumpsEnd
;
3207 static void ZSTDv05_decodeSequence(seq_t
* seq
, seqState_t
* seqState
)
3213 const BYTE
* dumps
= seqState
->dumps
;
3214 const BYTE
* const de
= seqState
->dumpsEnd
;
3216 /* Literal length */
3217 litLength
= FSEv05_peakSymbol(&(seqState
->stateLL
));
3218 prevOffset
= litLength
? seq
->offset
: seqState
->prevOffset
;
3219 if (litLength
== MaxLL
) {
3221 if (add
< 255) litLength
+= add
;
3223 litLength
= MEM_readLE32(dumps
) & 0xFFFFFF; /* no risk : dumps is always followed by seq tables > 1 byte */
3224 if (litLength
&1) litLength
>>=1, dumps
+= 3;
3225 else litLength
= (U16
)(litLength
)>>1, dumps
+= 2;
3227 if (dumps
> de
) { litLength
= MaxLL
+255; } /* late correction, to avoid using uninitialized memory */
3228 if (dumps
>= de
) { dumps
= de
-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3233 static const U32 offsetPrefix
[MaxOff
+1] = {
3234 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3235 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3236 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3237 U32 offsetCode
= FSEv05_peakSymbol(&(seqState
->stateOffb
)); /* <= maxOff, by table construction */
3238 U32 nbBits
= offsetCode
- 1;
3239 if (offsetCode
==0) nbBits
= 0; /* cmove */
3240 offset
= offsetPrefix
[offsetCode
] + BITv05_readBits(&(seqState
->DStream
), nbBits
);
3241 if (MEM_32bits()) BITv05_reloadDStream(&(seqState
->DStream
));
3242 if (offsetCode
==0) offset
= prevOffset
; /* repcode, cmove */
3243 if (offsetCode
| !litLength
) seqState
->prevOffset
= seq
->offset
; /* cmove */
3244 FSEv05_decodeSymbol(&(seqState
->stateOffb
), &(seqState
->DStream
)); /* update */
3247 /* Literal length update */
3248 FSEv05_decodeSymbol(&(seqState
->stateLL
), &(seqState
->DStream
)); /* update */
3249 if (MEM_32bits()) BITv05_reloadDStream(&(seqState
->DStream
));
3252 matchLength
= FSEv05_decodeSymbol(&(seqState
->stateML
), &(seqState
->DStream
));
3253 if (matchLength
== MaxML
) {
3255 if (add
< 255) matchLength
+= add
;
3257 matchLength
= MEM_readLE32(dumps
) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3258 if (matchLength
&1) matchLength
>>=1, dumps
+= 3;
3259 else matchLength
= (U16
)(matchLength
)>>1, dumps
+= 2;
3261 if (dumps
> de
) { matchLength
= MaxML
+255; } /* late correction, to avoid using uninitialized memory */
3262 if (dumps
>= de
) { dumps
= de
-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3264 matchLength
+= MINMATCH
;
3267 seq
->litLength
= litLength
;
3268 seq
->offset
= offset
;
3269 seq
->matchLength
= matchLength
;
3270 seqState
->dumps
= dumps
;
3274 static U64 totalDecoded
= 0;
3275 printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n",
3276 (U32
)(totalDecoded
), (U32
)litLength
, (U32
)matchLength
, (U32
)offset
);
3277 totalDecoded
+= litLength
+ matchLength
;
3283 static size_t ZSTDv05_execSequence(BYTE
* op
,
3284 BYTE
* const oend
, seq_t sequence
,
3285 const BYTE
** litPtr
, const BYTE
* const litLimit
,
3286 const BYTE
* const base
, const BYTE
* const vBase
, const BYTE
* const dictEnd
)
3288 static const int dec32table
[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3289 static const int dec64table
[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3290 BYTE
* const oLitEnd
= op
+ sequence
.litLength
;
3291 const size_t sequenceLength
= sequence
.litLength
+ sequence
.matchLength
;
3292 BYTE
* const oMatchEnd
= op
+ sequenceLength
; /* risk : address space overflow (32-bits) */
3293 BYTE
* const oend_8
= oend
-8;
3294 const BYTE
* const litEnd
= *litPtr
+ sequence
.litLength
;
3295 const BYTE
* match
= oLitEnd
- sequence
.offset
;
3298 if (oLitEnd
> oend_8
) return ERROR(dstSize_tooSmall
); /* last match must start at a minimum distance of 8 from oend */
3299 if (oMatchEnd
> oend
) return ERROR(dstSize_tooSmall
); /* overwrite beyond dst buffer */
3300 if (litEnd
> litLimit
) return ERROR(corruption_detected
); /* risk read beyond lit buffer */
3303 ZSTDv05_wildcopy(op
, *litPtr
, sequence
.litLength
); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3305 *litPtr
= litEnd
; /* update for next sequence */
3308 if (sequence
.offset
> (size_t)(oLitEnd
- base
)) {
3309 /* offset beyond prefix */
3310 if (sequence
.offset
> (size_t)(oLitEnd
- vBase
))
3311 return ERROR(corruption_detected
);
3312 match
= dictEnd
- (base
-match
);
3313 if (match
+ sequence
.matchLength
<= dictEnd
) {
3314 memmove(oLitEnd
, match
, sequence
.matchLength
);
3315 return sequenceLength
;
3317 /* span extDict & currentPrefixSegment */
3319 size_t length1
= dictEnd
- match
;
3320 memmove(oLitEnd
, match
, length1
);
3321 op
= oLitEnd
+ length1
;
3322 sequence
.matchLength
-= length1
;
3324 if (op
> oend_8
|| sequence
.matchLength
< MINMATCH
) {
3325 while (op
< oMatchEnd
) *op
++ = *match
++;
3326 return sequenceLength
;
3329 /* Requirement: op <= oend_8 */
3331 /* match within prefix */
3332 if (sequence
.offset
< 8) {
3333 /* close range match, overlap */
3334 const int sub2
= dec64table
[sequence
.offset
];
3339 match
+= dec32table
[sequence
.offset
];
3340 ZSTDv05_copy4(op
+4, match
);
3343 ZSTDv05_copy8(op
, match
);
3345 op
+= 8; match
+= 8;
3347 if (oMatchEnd
> oend
-(16-MINMATCH
)) {
3349 ZSTDv05_wildcopy(op
, match
, oend_8
- op
);
3350 match
+= oend_8
- op
;
3353 while (op
< oMatchEnd
)
3356 ZSTDv05_wildcopy(op
, match
, (ptrdiff_t)sequence
.matchLength
-8); /* works even if matchLength < 8 */
3358 return sequenceLength
;
3362 static size_t ZSTDv05_decompressSequences(
3364 void* dst
, size_t maxDstSize
,
3365 const void* seqStart
, size_t seqSize
)
3367 const BYTE
* ip
= (const BYTE
*)seqStart
;
3368 const BYTE
* const iend
= ip
+ seqSize
;
3369 BYTE
* const ostart
= (BYTE
* const)dst
;
3371 BYTE
* const oend
= ostart
+ maxDstSize
;
3372 size_t errorCode
, dumpsLength
;
3373 const BYTE
* litPtr
= dctx
->litPtr
;
3374 const BYTE
* const litEnd
= litPtr
+ dctx
->litSize
;
3377 U32
* DTableLL
= dctx
->LLTable
;
3378 U32
* DTableML
= dctx
->MLTable
;
3379 U32
* DTableOffb
= dctx
->OffTable
;
3380 const BYTE
* const base
= (const BYTE
*) (dctx
->base
);
3381 const BYTE
* const vBase
= (const BYTE
*) (dctx
->vBase
);
3382 const BYTE
* const dictEnd
= (const BYTE
*) (dctx
->dictEnd
);
3384 /* Build Decoding Tables */
3385 errorCode
= ZSTDv05_decodeSeqHeaders(&nbSeq
, &dumps
, &dumpsLength
,
3386 DTableLL
, DTableML
, DTableOffb
,
3387 ip
, seqSize
, dctx
->flagStaticTables
);
3388 if (ZSTDv05_isError(errorCode
)) return errorCode
;
3391 /* Regen sequences */
3394 seqState_t seqState
;
3396 memset(&sequence
, 0, sizeof(sequence
));
3397 sequence
.offset
= REPCODE_STARTVALUE
;
3398 seqState
.dumps
= dumps
;
3399 seqState
.dumpsEnd
= dumps
+ dumpsLength
;
3400 seqState
.prevOffset
= REPCODE_STARTVALUE
;
3401 errorCode
= BITv05_initDStream(&(seqState
.DStream
), ip
, iend
-ip
);
3402 if (ERR_isError(errorCode
)) return ERROR(corruption_detected
);
3403 FSEv05_initDState(&(seqState
.stateLL
), &(seqState
.DStream
), DTableLL
);
3404 FSEv05_initDState(&(seqState
.stateOffb
), &(seqState
.DStream
), DTableOffb
);
3405 FSEv05_initDState(&(seqState
.stateML
), &(seqState
.DStream
), DTableML
);
3407 for ( ; (BITv05_reloadDStream(&(seqState
.DStream
)) <= BITv05_DStream_completed
) && nbSeq
; ) {
3410 ZSTDv05_decodeSequence(&sequence
, &seqState
);
3411 oneSeqSize
= ZSTDv05_execSequence(op
, oend
, sequence
, &litPtr
, litEnd
, base
, vBase
, dictEnd
);
3412 if (ZSTDv05_isError(oneSeqSize
)) return oneSeqSize
;
3416 /* check if reached exact end */
3417 if (nbSeq
) return ERROR(corruption_detected
);
3420 /* last literal segment */
3422 size_t lastLLSize
= litEnd
- litPtr
;
3423 if (litPtr
> litEnd
) return ERROR(corruption_detected
); /* too many literals already used */
3424 if (op
+lastLLSize
> oend
) return ERROR(dstSize_tooSmall
);
3425 memcpy(op
, litPtr
, lastLLSize
);
3433 static void ZSTDv05_checkContinuity(ZSTDv05_DCtx
* dctx
, const void* dst
)
3435 if (dst
!= dctx
->previousDstEnd
) { /* not contiguous */
3436 dctx
->dictEnd
= dctx
->previousDstEnd
;
3437 dctx
->vBase
= (const char*)dst
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
3439 dctx
->previousDstEnd
= dst
;
3444 static size_t ZSTDv05_decompressBlock_internal(ZSTDv05_DCtx
* dctx
,
3445 void* dst
, size_t dstCapacity
,
3446 const void* src
, size_t srcSize
)
3447 { /* blockType == blockCompressed */
3448 const BYTE
* ip
= (const BYTE
*)src
;
3451 if (srcSize
>= BLOCKSIZE
) return ERROR(srcSize_wrong
);
3453 /* Decode literals sub-block */
3454 litCSize
= ZSTDv05_decodeLiteralsBlock(dctx
, src
, srcSize
);
3455 if (ZSTDv05_isError(litCSize
)) return litCSize
;
3457 srcSize
-= litCSize
;
3459 return ZSTDv05_decompressSequences(dctx
, dst
, dstCapacity
, ip
, srcSize
);
3463 size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx
* dctx
,
3464 void* dst
, size_t dstCapacity
,
3465 const void* src
, size_t srcSize
)
3467 ZSTDv05_checkContinuity(dctx
, dst
);
3468 return ZSTDv05_decompressBlock_internal(dctx
, dst
, dstCapacity
, src
, srcSize
);
3472 /*! ZSTDv05_decompress_continueDCtx
3473 * dctx must have been properly initialized */
3474 static size_t ZSTDv05_decompress_continueDCtx(ZSTDv05_DCtx
* dctx
,
3475 void* dst
, size_t maxDstSize
,
3476 const void* src
, size_t srcSize
)
3478 const BYTE
* ip
= (const BYTE
*)src
;
3479 const BYTE
* iend
= ip
+ srcSize
;
3480 BYTE
* const ostart
= (BYTE
* const)dst
;
3482 BYTE
* const oend
= ostart
+ maxDstSize
;
3483 size_t remainingSize
= srcSize
;
3484 blockProperties_t blockProperties
;
3488 size_t frameHeaderSize
;
3489 if (srcSize
< ZSTDv05_frameHeaderSize_min
+ZSTDv05_blockHeaderSize
) return ERROR(srcSize_wrong
);
3490 frameHeaderSize
= ZSTDv05_decodeFrameHeader_Part1(dctx
, src
, ZSTDv05_frameHeaderSize_min
);
3491 if (ZSTDv05_isError(frameHeaderSize
)) return frameHeaderSize
;
3492 if (srcSize
< frameHeaderSize
+ZSTDv05_blockHeaderSize
) return ERROR(srcSize_wrong
);
3493 ip
+= frameHeaderSize
; remainingSize
-= frameHeaderSize
;
3494 frameHeaderSize
= ZSTDv05_decodeFrameHeader_Part2(dctx
, src
, frameHeaderSize
);
3495 if (ZSTDv05_isError(frameHeaderSize
)) return frameHeaderSize
;
3498 /* Loop on each block */
3501 size_t decodedSize
=0;
3502 size_t cBlockSize
= ZSTDv05_getcBlockSize(ip
, iend
-ip
, &blockProperties
);
3503 if (ZSTDv05_isError(cBlockSize
)) return cBlockSize
;
3505 ip
+= ZSTDv05_blockHeaderSize
;
3506 remainingSize
-= ZSTDv05_blockHeaderSize
;
3507 if (cBlockSize
> remainingSize
) return ERROR(srcSize_wrong
);
3509 switch(blockProperties
.blockType
)
3512 decodedSize
= ZSTDv05_decompressBlock_internal(dctx
, op
, oend
-op
, ip
, cBlockSize
);
3515 decodedSize
= ZSTDv05_copyRawBlock(op
, oend
-op
, ip
, cBlockSize
);
3518 return ERROR(GENERIC
); /* not yet supported */
3522 if (remainingSize
) return ERROR(srcSize_wrong
);
3525 return ERROR(GENERIC
); /* impossible */
3527 if (cBlockSize
== 0) break; /* bt_end */
3529 if (ZSTDv05_isError(decodedSize
)) return decodedSize
;
3532 remainingSize
-= cBlockSize
;
3539 size_t ZSTDv05_decompress_usingPreparedDCtx(ZSTDv05_DCtx
* dctx
, const ZSTDv05_DCtx
* refDCtx
,
3540 void* dst
, size_t maxDstSize
,
3541 const void* src
, size_t srcSize
)
3543 ZSTDv05_copyDCtx(dctx
, refDCtx
);
3544 ZSTDv05_checkContinuity(dctx
, dst
);
3545 return ZSTDv05_decompress_continueDCtx(dctx
, dst
, maxDstSize
, src
, srcSize
);
3549 size_t ZSTDv05_decompress_usingDict(ZSTDv05_DCtx
* dctx
,
3550 void* dst
, size_t maxDstSize
,
3551 const void* src
, size_t srcSize
,
3552 const void* dict
, size_t dictSize
)
3554 ZSTDv05_decompressBegin_usingDict(dctx
, dict
, dictSize
);
3555 ZSTDv05_checkContinuity(dctx
, dst
);
3556 return ZSTDv05_decompress_continueDCtx(dctx
, dst
, maxDstSize
, src
, srcSize
);
3560 size_t ZSTDv05_decompressDCtx(ZSTDv05_DCtx
* dctx
, void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3562 return ZSTDv05_decompress_usingDict(dctx
, dst
, maxDstSize
, src
, srcSize
, NULL
, 0);
3565 size_t ZSTDv05_decompress(void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3567 #if defined(ZSTDv05_HEAPMODE) && (ZSTDv05_HEAPMODE==1)
3569 ZSTDv05_DCtx
* dctx
= ZSTDv05_createDCtx();
3570 if (dctx
==NULL
) return ERROR(memory_allocation
);
3571 regenSize
= ZSTDv05_decompressDCtx(dctx
, dst
, maxDstSize
, src
, srcSize
);
3572 ZSTDv05_freeDCtx(dctx
);
3576 return ZSTDv05_decompressDCtx(&dctx
, dst
, maxDstSize
, src
, srcSize
);
3580 size_t ZSTDv05_findFrameCompressedSize(const void *src
, size_t srcSize
)
3582 const BYTE
* ip
= (const BYTE
*)src
;
3583 size_t remainingSize
= srcSize
;
3584 blockProperties_t blockProperties
;
3587 if (srcSize
< ZSTDv05_frameHeaderSize_min
) return ERROR(srcSize_wrong
);
3588 if (MEM_readLE32(src
) != ZSTDv05_MAGICNUMBER
) return ERROR(prefix_unknown
);
3589 ip
+= ZSTDv05_frameHeaderSize_min
; remainingSize
-= ZSTDv05_frameHeaderSize_min
;
3591 /* Loop on each block */
3594 size_t cBlockSize
= ZSTDv05_getcBlockSize(ip
, remainingSize
, &blockProperties
);
3595 if (ZSTDv05_isError(cBlockSize
)) return cBlockSize
;
3597 ip
+= ZSTDv05_blockHeaderSize
;
3598 remainingSize
-= ZSTDv05_blockHeaderSize
;
3599 if (cBlockSize
> remainingSize
) return ERROR(srcSize_wrong
);
3601 if (cBlockSize
== 0) break; /* bt_end */
3604 remainingSize
-= cBlockSize
;
3607 return ip
- (const BYTE
*)src
;
3610 /* ******************************
3611 * Streaming Decompression API
3612 ********************************/
3613 size_t ZSTDv05_nextSrcSizeToDecompress(ZSTDv05_DCtx
* dctx
)
3615 return dctx
->expected
;
3618 size_t ZSTDv05_decompressContinue(ZSTDv05_DCtx
* dctx
, void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3621 if (srcSize
!= dctx
->expected
) return ERROR(srcSize_wrong
);
3622 ZSTDv05_checkContinuity(dctx
, dst
);
3624 /* Decompress : frame header; part 1 */
3625 switch (dctx
->stage
)
3627 case ZSTDv05ds_getFrameHeaderSize
:
3628 /* get frame header size */
3629 if (srcSize
!= ZSTDv05_frameHeaderSize_min
) return ERROR(srcSize_wrong
); /* impossible */
3630 dctx
->headerSize
= ZSTDv05_decodeFrameHeader_Part1(dctx
, src
, ZSTDv05_frameHeaderSize_min
);
3631 if (ZSTDv05_isError(dctx
->headerSize
)) return dctx
->headerSize
;
3632 memcpy(dctx
->headerBuffer
, src
, ZSTDv05_frameHeaderSize_min
);
3633 if (dctx
->headerSize
> ZSTDv05_frameHeaderSize_min
) return ERROR(GENERIC
); /* should never happen */
3634 dctx
->expected
= 0; /* not necessary to copy more */
3636 case ZSTDv05ds_decodeFrameHeader
:
3637 /* get frame header */
3638 { size_t const result
= ZSTDv05_decodeFrameHeader_Part2(dctx
, dctx
->headerBuffer
, dctx
->headerSize
);
3639 if (ZSTDv05_isError(result
)) return result
;
3640 dctx
->expected
= ZSTDv05_blockHeaderSize
;
3641 dctx
->stage
= ZSTDv05ds_decodeBlockHeader
;
3644 case ZSTDv05ds_decodeBlockHeader
:
3646 /* Decode block header */
3647 blockProperties_t bp
;
3648 size_t blockSize
= ZSTDv05_getcBlockSize(src
, ZSTDv05_blockHeaderSize
, &bp
);
3649 if (ZSTDv05_isError(blockSize
)) return blockSize
;
3650 if (bp
.blockType
== bt_end
) {
3652 dctx
->stage
= ZSTDv05ds_getFrameHeaderSize
;
3655 dctx
->expected
= blockSize
;
3656 dctx
->bType
= bp
.blockType
;
3657 dctx
->stage
= ZSTDv05ds_decompressBlock
;
3661 case ZSTDv05ds_decompressBlock
:
3663 /* Decompress : block content */
3668 rSize
= ZSTDv05_decompressBlock_internal(dctx
, dst
, maxDstSize
, src
, srcSize
);
3671 rSize
= ZSTDv05_copyRawBlock(dst
, maxDstSize
, src
, srcSize
);
3674 return ERROR(GENERIC
); /* not yet handled */
3676 case bt_end
: /* should never happen (filtered at phase 1) */
3680 return ERROR(GENERIC
); /* impossible */
3682 dctx
->stage
= ZSTDv05ds_decodeBlockHeader
;
3683 dctx
->expected
= ZSTDv05_blockHeaderSize
;
3684 dctx
->previousDstEnd
= (char*)dst
+ rSize
;
3688 return ERROR(GENERIC
); /* impossible */
3693 static void ZSTDv05_refDictContent(ZSTDv05_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3695 dctx
->dictEnd
= dctx
->previousDstEnd
;
3696 dctx
->vBase
= (const char*)dict
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
3698 dctx
->previousDstEnd
= (const char*)dict
+ dictSize
;
3701 static size_t ZSTDv05_loadEntropy(ZSTDv05_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3703 size_t hSize
, offcodeHeaderSize
, matchlengthHeaderSize
, errorCode
, litlengthHeaderSize
;
3704 short offcodeNCount
[MaxOff
+1];
3705 U32 offcodeMaxValue
=MaxOff
, offcodeLog
;
3706 short matchlengthNCount
[MaxML
+1];
3707 unsigned matchlengthMaxValue
= MaxML
, matchlengthLog
;
3708 short litlengthNCount
[MaxLL
+1];
3709 unsigned litlengthMaxValue
= MaxLL
, litlengthLog
;
3711 hSize
= HUFv05_readDTableX4(dctx
->hufTableX4
, dict
, dictSize
);
3712 if (HUFv05_isError(hSize
)) return ERROR(dictionary_corrupted
);
3713 dict
= (const char*)dict
+ hSize
;
3716 offcodeHeaderSize
= FSEv05_readNCount(offcodeNCount
, &offcodeMaxValue
, &offcodeLog
, dict
, dictSize
);
3717 if (FSEv05_isError(offcodeHeaderSize
)) return ERROR(dictionary_corrupted
);
3718 if (offcodeLog
> OffFSEv05Log
) return ERROR(dictionary_corrupted
);
3719 errorCode
= FSEv05_buildDTable(dctx
->OffTable
, offcodeNCount
, offcodeMaxValue
, offcodeLog
);
3720 if (FSEv05_isError(errorCode
)) return ERROR(dictionary_corrupted
);
3721 dict
= (const char*)dict
+ offcodeHeaderSize
;
3722 dictSize
-= offcodeHeaderSize
;
3724 matchlengthHeaderSize
= FSEv05_readNCount(matchlengthNCount
, &matchlengthMaxValue
, &matchlengthLog
, dict
, dictSize
);
3725 if (FSEv05_isError(matchlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
3726 if (matchlengthLog
> MLFSEv05Log
) return ERROR(dictionary_corrupted
);
3727 errorCode
= FSEv05_buildDTable(dctx
->MLTable
, matchlengthNCount
, matchlengthMaxValue
, matchlengthLog
);
3728 if (FSEv05_isError(errorCode
)) return ERROR(dictionary_corrupted
);
3729 dict
= (const char*)dict
+ matchlengthHeaderSize
;
3730 dictSize
-= matchlengthHeaderSize
;
3732 litlengthHeaderSize
= FSEv05_readNCount(litlengthNCount
, &litlengthMaxValue
, &litlengthLog
, dict
, dictSize
);
3733 if (litlengthLog
> LLFSEv05Log
) return ERROR(dictionary_corrupted
);
3734 if (FSEv05_isError(litlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
3735 errorCode
= FSEv05_buildDTable(dctx
->LLTable
, litlengthNCount
, litlengthMaxValue
, litlengthLog
);
3736 if (FSEv05_isError(errorCode
)) return ERROR(dictionary_corrupted
);
3738 dctx
->flagStaticTables
= 1;
3739 return hSize
+ offcodeHeaderSize
+ matchlengthHeaderSize
+ litlengthHeaderSize
;
3742 static size_t ZSTDv05_decompress_insertDictionary(ZSTDv05_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3745 U32 magic
= MEM_readLE32(dict
);
3746 if (magic
!= ZSTDv05_DICT_MAGIC
) {
3747 /* pure content mode */
3748 ZSTDv05_refDictContent(dctx
, dict
, dictSize
);
3751 /* load entropy tables */
3752 dict
= (const char*)dict
+ 4;
3754 eSize
= ZSTDv05_loadEntropy(dctx
, dict
, dictSize
);
3755 if (ZSTDv05_isError(eSize
)) return ERROR(dictionary_corrupted
);
3757 /* reference dictionary content */
3758 dict
= (const char*)dict
+ eSize
;
3760 ZSTDv05_refDictContent(dctx
, dict
, dictSize
);
3766 size_t ZSTDv05_decompressBegin_usingDict(ZSTDv05_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3769 errorCode
= ZSTDv05_decompressBegin(dctx
);
3770 if (ZSTDv05_isError(errorCode
)) return errorCode
;
3772 if (dict
&& dictSize
) {
3773 errorCode
= ZSTDv05_decompress_insertDictionary(dctx
, dict
, dictSize
);
3774 if (ZSTDv05_isError(errorCode
)) return ERROR(dictionary_corrupted
);
3781 Buffered version of Zstd compression library
3782 Copyright (C) 2015-2016, Yann Collet.
3784 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
3786 Redistribution and use in source and binary forms, with or without
3787 modification, are permitted provided that the following conditions are
3789 * Redistributions of source code must retain the above copyright
3790 notice, this list of conditions and the following disclaimer.
3791 * Redistributions in binary form must reproduce the above
3792 copyright notice, this list of conditions and the following disclaimer
3793 in the documentation and/or other materials provided with the
3795 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3796 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3797 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3798 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3799 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3800 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3801 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3802 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3803 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3804 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3805 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3807 You can contact the author at :
3808 - zstd source repository : https://github.com/Cyan4973/zstd
3809 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3812 /* The objects defined into this file should be considered experimental.
3813 * They are not labelled stable, as their prototype may change in the future.
3814 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3819 /* *************************************
3821 ***************************************/
3822 static size_t ZBUFFv05_blockHeaderSize
= 3;
3826 /* *** Compression *** */
3828 static size_t ZBUFFv05_limitCopy(void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3830 size_t length
= MIN(maxDstSize
, srcSize
);
3831 memcpy(dst
, src
, length
);
3838 /** ************************************************
3839 * Streaming decompression
3841 * A ZBUFFv05_DCtx object is required to track streaming operation.
3842 * Use ZBUFFv05_createDCtx() and ZBUFFv05_freeDCtx() to create/release resources.
3843 * Use ZBUFFv05_decompressInit() to start a new decompression operation.
3844 * ZBUFFv05_DCtx objects can be reused multiple times.
3846 * Use ZBUFFv05_decompressContinue() repetitively to consume your input.
3847 * *srcSizePtr and *maxDstSizePtr can be any size.
3848 * The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3849 * 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.
3850 * The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3851 * return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3852 * or 0 when a frame is completely decoded
3853 * or an error code, which can be tested using ZBUFFv05_isError().
3855 * Hint : recommended buffer sizes (not compulsory)
3856 * output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3857 * input : just follow indications from ZBUFFv05_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3858 * **************************************************/
3860 typedef enum { ZBUFFv05ds_init
, ZBUFFv05ds_readHeader
, ZBUFFv05ds_loadHeader
, ZBUFFv05ds_decodeHeader
,
3861 ZBUFFv05ds_read
, ZBUFFv05ds_load
, ZBUFFv05ds_flush
} ZBUFFv05_dStage
;
3863 /* *** Resource management *** */
3865 #define ZSTDv05_frameHeaderSize_max 5 /* too magical, should come from reference */
3866 struct ZBUFFv05_DCtx_s
{
3868 ZSTDv05_parameters params
;
3877 ZBUFFv05_dStage stage
;
3878 unsigned char headerBuffer
[ZSTDv05_frameHeaderSize_max
];
3879 }; /* typedef'd to ZBUFFv05_DCtx within "zstd_buffered.h" */
3882 ZBUFFv05_DCtx
* ZBUFFv05_createDCtx(void)
3884 ZBUFFv05_DCtx
* zbc
= (ZBUFFv05_DCtx
*)malloc(sizeof(ZBUFFv05_DCtx
));
3885 if (zbc
==NULL
) return NULL
;
3886 memset(zbc
, 0, sizeof(*zbc
));
3887 zbc
->zc
= ZSTDv05_createDCtx();
3888 zbc
->stage
= ZBUFFv05ds_init
;
3892 size_t ZBUFFv05_freeDCtx(ZBUFFv05_DCtx
* zbc
)
3894 if (zbc
==NULL
) return 0; /* support free on null */
3895 ZSTDv05_freeDCtx(zbc
->zc
);
3903 /* *** Initialization *** */
3905 size_t ZBUFFv05_decompressInitDictionary(ZBUFFv05_DCtx
* zbc
, const void* dict
, size_t dictSize
)
3907 zbc
->stage
= ZBUFFv05ds_readHeader
;
3908 zbc
->hPos
= zbc
->inPos
= zbc
->outStart
= zbc
->outEnd
= 0;
3909 return ZSTDv05_decompressBegin_usingDict(zbc
->zc
, dict
, dictSize
);
3912 size_t ZBUFFv05_decompressInit(ZBUFFv05_DCtx
* zbc
)
3914 return ZBUFFv05_decompressInitDictionary(zbc
, NULL
, 0);
3918 /* *** Decompression *** */
3920 size_t ZBUFFv05_decompressContinue(ZBUFFv05_DCtx
* zbc
, void* dst
, size_t* maxDstSizePtr
, const void* src
, size_t* srcSizePtr
)
3922 const char* const istart
= (const char*)src
;
3923 const char* ip
= istart
;
3924 const char* const iend
= istart
+ *srcSizePtr
;
3925 char* const ostart
= (char*)dst
;
3927 char* const oend
= ostart
+ *maxDstSizePtr
;
3933 case ZBUFFv05ds_init
:
3934 return ERROR(init_missing
);
3936 case ZBUFFv05ds_readHeader
:
3937 /* read header from src */
3939 size_t headerSize
= ZSTDv05_getFrameParams(&(zbc
->params
), src
, *srcSizePtr
);
3940 if (ZSTDv05_isError(headerSize
)) return headerSize
;
3942 /* not enough input to decode header : tell how many bytes would be necessary */
3943 memcpy(zbc
->headerBuffer
+zbc
->hPos
, src
, *srcSizePtr
);
3944 zbc
->hPos
+= *srcSizePtr
;
3946 zbc
->stage
= ZBUFFv05ds_loadHeader
;
3947 return headerSize
- zbc
->hPos
;
3949 zbc
->stage
= ZBUFFv05ds_decodeHeader
;
3953 case ZBUFFv05ds_loadHeader
:
3954 /* complete header from src */
3956 size_t headerSize
= ZBUFFv05_limitCopy(
3957 zbc
->headerBuffer
+ zbc
->hPos
, ZSTDv05_frameHeaderSize_max
- zbc
->hPos
,
3959 zbc
->hPos
+= headerSize
;
3961 headerSize
= ZSTDv05_getFrameParams(&(zbc
->params
), zbc
->headerBuffer
, zbc
->hPos
);
3962 if (ZSTDv05_isError(headerSize
)) return headerSize
;
3964 /* not enough input to decode header : tell how many bytes would be necessary */
3966 return headerSize
- zbc
->hPos
;
3968 // zbc->stage = ZBUFFv05ds_decodeHeader; break; /* useless : stage follows */
3971 case ZBUFFv05ds_decodeHeader
:
3972 /* apply header to create / resize buffers */
3974 size_t neededOutSize
= (size_t)1 << zbc
->params
.windowLog
;
3975 size_t neededInSize
= BLOCKSIZE
; /* a block is never > BLOCKSIZE */
3976 if (zbc
->inBuffSize
< neededInSize
) {
3978 zbc
->inBuffSize
= neededInSize
;
3979 zbc
->inBuff
= (char*)malloc(neededInSize
);
3980 if (zbc
->inBuff
== NULL
) return ERROR(memory_allocation
);
3982 if (zbc
->outBuffSize
< neededOutSize
) {
3984 zbc
->outBuffSize
= neededOutSize
;
3985 zbc
->outBuff
= (char*)malloc(neededOutSize
);
3986 if (zbc
->outBuff
== NULL
) return ERROR(memory_allocation
);
3989 /* some data already loaded into headerBuffer : transfer into inBuff */
3990 memcpy(zbc
->inBuff
, zbc
->headerBuffer
, zbc
->hPos
);
3991 zbc
->inPos
= zbc
->hPos
;
3993 zbc
->stage
= ZBUFFv05ds_load
;
3996 zbc
->stage
= ZBUFFv05ds_read
;
3998 case ZBUFFv05ds_read
:
4000 size_t neededInSize
= ZSTDv05_nextSrcSizeToDecompress(zbc
->zc
);
4001 if (neededInSize
==0) { /* end of frame */
4002 zbc
->stage
= ZBUFFv05ds_init
;
4006 if ((size_t)(iend
-ip
) >= neededInSize
) {
4007 /* directly decode from src */
4008 size_t decodedSize
= ZSTDv05_decompressContinue(zbc
->zc
,
4009 zbc
->outBuff
+ zbc
->outStart
, zbc
->outBuffSize
- zbc
->outStart
,
4011 if (ZSTDv05_isError(decodedSize
)) return decodedSize
;
4013 if (!decodedSize
) break; /* this was just a header */
4014 zbc
->outEnd
= zbc
->outStart
+ decodedSize
;
4015 zbc
->stage
= ZBUFFv05ds_flush
;
4018 if (ip
==iend
) { notDone
= 0; break; } /* no more input */
4019 zbc
->stage
= ZBUFFv05ds_load
;
4022 case ZBUFFv05ds_load
:
4024 size_t neededInSize
= ZSTDv05_nextSrcSizeToDecompress(zbc
->zc
);
4025 size_t toLoad
= neededInSize
- zbc
->inPos
; /* should always be <= remaining space within inBuff */
4027 if (toLoad
> zbc
->inBuffSize
- zbc
->inPos
) return ERROR(corruption_detected
); /* should never happen */
4028 loadedSize
= ZBUFFv05_limitCopy(zbc
->inBuff
+ zbc
->inPos
, toLoad
, ip
, iend
-ip
);
4030 zbc
->inPos
+= loadedSize
;
4031 if (loadedSize
< toLoad
) { notDone
= 0; break; } /* not enough input, wait for more */
4033 size_t decodedSize
= ZSTDv05_decompressContinue(zbc
->zc
,
4034 zbc
->outBuff
+ zbc
->outStart
, zbc
->outBuffSize
- zbc
->outStart
,
4035 zbc
->inBuff
, neededInSize
);
4036 if (ZSTDv05_isError(decodedSize
)) return decodedSize
;
4037 zbc
->inPos
= 0; /* input is consumed */
4038 if (!decodedSize
) { zbc
->stage
= ZBUFFv05ds_read
; break; } /* this was just a header */
4039 zbc
->outEnd
= zbc
->outStart
+ decodedSize
;
4040 zbc
->stage
= ZBUFFv05ds_flush
;
4041 // break; /* ZBUFFv05ds_flush follows */
4045 case ZBUFFv05ds_flush
:
4047 size_t toFlushSize
= zbc
->outEnd
- zbc
->outStart
;
4048 size_t flushedSize
= ZBUFFv05_limitCopy(op
, oend
-op
, zbc
->outBuff
+ zbc
->outStart
, toFlushSize
);
4050 zbc
->outStart
+= flushedSize
;
4051 if (flushedSize
== toFlushSize
) {
4052 zbc
->stage
= ZBUFFv05ds_read
;
4053 if (zbc
->outStart
+ BLOCKSIZE
> zbc
->outBuffSize
)
4054 zbc
->outStart
= zbc
->outEnd
= 0;
4057 /* cannot flush everything */
4061 default: return ERROR(GENERIC
); /* impossible */
4064 *srcSizePtr
= ip
-istart
;
4065 *maxDstSizePtr
= op
-ostart
;
4067 { size_t nextSrcSizeHint
= ZSTDv05_nextSrcSizeToDecompress(zbc
->zc
);
4068 if (nextSrcSizeHint
> ZBUFFv05_blockHeaderSize
) nextSrcSizeHint
+= ZBUFFv05_blockHeaderSize
; /* get next block header too */
4069 nextSrcSizeHint
-= zbc
->inPos
; /* already loaded*/
4070 return nextSrcSizeHint
;
4076 /* *************************************
4078 ***************************************/
4079 unsigned ZBUFFv05_isError(size_t errorCode
) { return ERR_isError(errorCode
); }
4080 const char* ZBUFFv05_getErrorName(size_t errorCode
) { return ERR_getErrorName(errorCode
); }
4082 size_t ZBUFFv05_recommendedDInSize(void) { return BLOCKSIZE
+ ZBUFFv05_blockHeaderSize
/* block header size*/ ; }
4083 size_t ZBUFFv05_recommendedDOutSize(void) { return BLOCKSIZE
; }