2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of this source tree. An additional grant
7 * of patent rights can be found in the PATENTS file in the same directory.
13 #include <stddef.h> /* size_t, ptrdiff_t */
14 #include <string.h> /* memcpy */
15 #include <stdlib.h> /* malloc, free, qsort */
16 #include "error_private.h"
20 /* ******************************************************************
22 low-level memory access routines
23 Copyright (C) 2013-2015, Yann Collet.
25 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
27 Redistribution and use in source and binary forms, with or without
28 modification, are permitted provided that the following conditions are
31 * Redistributions of source code must retain the above copyright
32 notice, this list of conditions and the following disclaimer.
33 * Redistributions in binary form must reproduce the above
34 copyright notice, this list of conditions and the following disclaimer
35 in the documentation and/or other materials provided with the
38 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
39 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
40 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
41 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
42 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
44 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
45 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
46 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
47 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
48 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
50 You can contact the author at :
51 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
52 - Public forum : https://groups.google.com/forum/#!forum/lz4c
53 ****************************************************************** */
57 #if defined (__cplusplus)
62 /*-****************************************
64 ******************************************/
65 #if defined(_MSC_VER) /* Visual Studio */
66 # include <stdlib.h> /* _byteswap_ulong */
67 # include <intrin.h> /* _byteswap_* */
70 # define MEM_STATIC static __attribute__((unused))
71 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
72 # define MEM_STATIC static inline
73 #elif defined(_MSC_VER)
74 # define MEM_STATIC static __inline
76 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
80 /*-**************************************************************
82 *****************************************************************/
83 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
93 typedef unsigned char BYTE
;
94 typedef unsigned short U16
;
95 typedef signed short S16
;
96 typedef unsigned int U32
;
97 typedef signed int S32
;
98 typedef unsigned long long U64
;
99 typedef signed long long S64
;
103 /*-**************************************************************
105 *****************************************************************/
106 /* MEM_FORCE_MEMORY_ACCESS :
107 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
108 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
109 * The below switch allow to select different access method for improved performance.
110 * Method 0 (default) : use `memcpy()`. Safe and portable.
111 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
112 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
113 * Method 2 : direct access. This method is portable but violate C standard.
114 * It can generate buggy code on targets depending on alignment.
115 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
116 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
117 * Prefer these methods in priority order (0 > 1 > 2)
119 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
120 # 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__) )
121 # define MEM_FORCE_MEMORY_ACCESS 2
122 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
123 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
124 # define MEM_FORCE_MEMORY_ACCESS 1
128 MEM_STATIC
unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
129 MEM_STATIC
unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
131 MEM_STATIC
unsigned MEM_isLittleEndian(void)
133 const union { U32 u
; BYTE c
[4]; } one
= { 1 }; /* don't use static : performance detrimental */
137 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
139 /* violates C standard, by lying on structure alignment.
140 Only use if no other choice to achieve best performance on target platform */
141 MEM_STATIC U16
MEM_read16(const void* memPtr
) { return *(const U16
*) memPtr
; }
142 MEM_STATIC U32
MEM_read32(const void* memPtr
) { return *(const U32
*) memPtr
; }
143 MEM_STATIC U64
MEM_read64(const void* memPtr
) { return *(const U64
*) memPtr
; }
145 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { *(U16
*)memPtr
= value
; }
147 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
149 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
150 /* currently only defined for gcc and icc */
151 typedef union { U16 u16
; U32 u32
; U64 u64
; size_t st
; } __attribute__((packed
)) unalign
;
153 MEM_STATIC U16
MEM_read16(const void* ptr
) { return ((const unalign
*)ptr
)->u16
; }
154 MEM_STATIC U32
MEM_read32(const void* ptr
) { return ((const unalign
*)ptr
)->u32
; }
155 MEM_STATIC U64
MEM_read64(const void* ptr
) { return ((const unalign
*)ptr
)->u64
; }
157 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { ((unalign
*)memPtr
)->u16
= value
; }
161 /* default method, safe and standard.
162 can sometimes prove slower */
164 MEM_STATIC U16
MEM_read16(const void* memPtr
)
166 U16 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
169 MEM_STATIC U32
MEM_read32(const void* memPtr
)
171 U32 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
174 MEM_STATIC U64
MEM_read64(const void* memPtr
)
176 U64 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
179 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
)
181 memcpy(memPtr
, &value
, sizeof(value
));
185 #endif /* MEM_FORCE_MEMORY_ACCESS */
187 MEM_STATIC U32
MEM_swap32(U32 in
)
189 #if defined(_MSC_VER) /* Visual Studio */
190 return _byteswap_ulong(in
);
191 #elif defined (__GNUC__)
192 return __builtin_bswap32(in
);
194 return ((in
<< 24) & 0xff000000 ) |
195 ((in
<< 8) & 0x00ff0000 ) |
196 ((in
>> 8) & 0x0000ff00 ) |
197 ((in
>> 24) & 0x000000ff );
201 MEM_STATIC U64
MEM_swap64(U64 in
)
203 #if defined(_MSC_VER) /* Visual Studio */
204 return _byteswap_uint64(in
);
205 #elif defined (__GNUC__)
206 return __builtin_bswap64(in
);
208 return ((in
<< 56) & 0xff00000000000000ULL
) |
209 ((in
<< 40) & 0x00ff000000000000ULL
) |
210 ((in
<< 24) & 0x0000ff0000000000ULL
) |
211 ((in
<< 8) & 0x000000ff00000000ULL
) |
212 ((in
>> 8) & 0x00000000ff000000ULL
) |
213 ((in
>> 24) & 0x0000000000ff0000ULL
) |
214 ((in
>> 40) & 0x000000000000ff00ULL
) |
215 ((in
>> 56) & 0x00000000000000ffULL
);
220 /*=== Little endian r/w ===*/
222 MEM_STATIC U16
MEM_readLE16(const void* memPtr
)
224 if (MEM_isLittleEndian())
225 return MEM_read16(memPtr
);
227 const BYTE
* p
= (const BYTE
*)memPtr
;
228 return (U16
)(p
[0] + (p
[1]<<8));
232 MEM_STATIC
void MEM_writeLE16(void* memPtr
, U16 val
)
234 if (MEM_isLittleEndian()) {
235 MEM_write16(memPtr
, val
);
237 BYTE
* p
= (BYTE
*)memPtr
;
239 p
[1] = (BYTE
)(val
>>8);
243 MEM_STATIC U32
MEM_readLE32(const void* memPtr
)
245 if (MEM_isLittleEndian())
246 return MEM_read32(memPtr
);
248 return MEM_swap32(MEM_read32(memPtr
));
252 MEM_STATIC U64
MEM_readLE64(const void* memPtr
)
254 if (MEM_isLittleEndian())
255 return MEM_read64(memPtr
);
257 return MEM_swap64(MEM_read64(memPtr
));
261 MEM_STATIC
size_t MEM_readLEST(const void* memPtr
)
264 return (size_t)MEM_readLE32(memPtr
);
266 return (size_t)MEM_readLE64(memPtr
);
271 #if defined (__cplusplus)
275 #endif /* MEM_H_MODULE */
278 zstd - standard compression library
279 Header File for static linking only
280 Copyright (C) 2014-2016, Yann Collet.
282 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
284 Redistribution and use in source and binary forms, with or without
285 modification, are permitted provided that the following conditions are
287 * Redistributions of source code must retain the above copyright
288 notice, this list of conditions and the following disclaimer.
289 * Redistributions in binary form must reproduce the above
290 copyright notice, this list of conditions and the following disclaimer
291 in the documentation and/or other materials provided with the
293 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
294 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
295 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
296 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
297 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
298 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
299 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
300 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
301 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
302 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
303 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
305 You can contact the author at :
306 - zstd homepage : http://www.zstd.net
308 #ifndef ZSTDv06_STATIC_H
309 #define ZSTDv06_STATIC_H
311 /* The prototypes defined within this file are considered experimental.
312 * They should not be used in the context DLL as they may change in the future.
313 * Prefer static linking if you need them, to control breaking version changes issues.
316 #if defined (__cplusplus)
322 /*- Advanced Decompression functions -*/
324 /*! ZSTDv06_decompress_usingPreparedDCtx() :
325 * Same as ZSTDv06_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
326 * It avoids reloading the dictionary each time.
327 * `preparedDCtx` must have been properly initialized using ZSTDv06_decompressBegin_usingDict().
328 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
329 ZSTDLIBv06_API
size_t ZSTDv06_decompress_usingPreparedDCtx(
330 ZSTDv06_DCtx
* dctx
, const ZSTDv06_DCtx
* preparedDCtx
,
331 void* dst
, size_t dstCapacity
,
332 const void* src
, size_t srcSize
);
336 #define ZSTDv06_FRAMEHEADERSIZE_MAX 13 /* for static allocation */
337 static const size_t ZSTDv06_frameHeaderSize_min
= 5;
338 static const size_t ZSTDv06_frameHeaderSize_max
= ZSTDv06_FRAMEHEADERSIZE_MAX
;
340 ZSTDLIBv06_API
size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx
* dctx
);
343 Streaming decompression, direct mode (bufferless)
345 A ZSTDv06_DCtx object is required to track streaming operations.
346 Use ZSTDv06_createDCtx() / ZSTDv06_freeDCtx() to manage it.
347 A ZSTDv06_DCtx object can be re-used multiple times.
349 First optional operation is to retrieve frame parameters, using ZSTDv06_getFrameParams(), which doesn't consume the input.
350 It can provide the minimum size of rolling buffer required to properly decompress data,
351 and optionally the final size of uncompressed content.
352 (Note : content size is an optional info that may not be present. 0 means : content size unknown)
353 Frame parameters are extracted from the beginning of compressed frame.
354 The amount of data to read is variable, from ZSTDv06_frameHeaderSize_min to ZSTDv06_frameHeaderSize_max (so if `srcSize` >= ZSTDv06_frameHeaderSize_max, it will always work)
355 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
356 Result : 0 when successful, it means the ZSTDv06_frameParams structure has been filled.
357 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
358 errorCode, which can be tested using ZSTDv06_isError()
360 Start decompression, with ZSTDv06_decompressBegin() or ZSTDv06_decompressBegin_usingDict().
361 Alternatively, you can copy a prepared context, using ZSTDv06_copyDCtx().
363 Then use ZSTDv06_nextSrcSizeToDecompress() and ZSTDv06_decompressContinue() alternatively.
364 ZSTDv06_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv06_decompressContinue().
365 ZSTDv06_decompressContinue() requires this exact amount of bytes, or it will fail.
366 ZSTDv06_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
367 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
369 @result of ZSTDv06_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity)
370 It can be zero, which is not an error; it just means ZSTDv06_decompressContinue() has decoded some header.
372 A frame is fully decoded when ZSTDv06_nextSrcSizeToDecompress() returns zero.
373 Context can then be reset to start a new decompression.
377 /* **************************************
379 ****************************************/
380 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
381 User will have to take in charge required information to regenerate data, such as compressed and content sizes.
383 A few rules to respect :
384 - Uncompressed block size must be <= ZSTDv06_BLOCKSIZE_MAX (128 KB)
385 - Compressing or decompressing requires a context structure
386 + Use ZSTDv06_createCCtx() and ZSTDv06_createDCtx()
387 - It is necessary to init context before starting
388 + compression : ZSTDv06_compressBegin()
389 + decompression : ZSTDv06_decompressBegin()
390 + variants _usingDict() are also allowed
391 + copyCCtx() and copyDCtx() work too
392 - When a block is considered not compressible enough, ZSTDv06_compressBlock() result will be zero.
393 In which case, nothing is produced into `dst`.
394 + User must test for such outcome and deal directly with uncompressed data
395 + ZSTDv06_decompressBlock() doesn't accept uncompressed data as input !!
398 #define ZSTDv06_BLOCKSIZE_MAX (128 * 1024) /* define, for static allocation */
399 ZSTDLIBv06_API
size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
);
403 #if defined (__cplusplus)
407 #endif /* ZSTDv06_STATIC_H */
409 zstd_internal - common functions to include
410 Header File for include
411 Copyright (C) 2014-2016, Yann Collet.
413 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
415 Redistribution and use in source and binary forms, with or without
416 modification, are permitted provided that the following conditions are
418 * Redistributions of source code must retain the above copyright
419 notice, this list of conditions and the following disclaimer.
420 * Redistributions in binary form must reproduce the above
421 copyright notice, this list of conditions and the following disclaimer
422 in the documentation and/or other materials provided with the
424 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
425 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
426 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
427 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
428 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
429 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
430 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
431 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
432 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
433 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
434 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
436 You can contact the author at :
437 - zstd homepage : https://www.zstd.net
439 #ifndef ZSTDv06_CCOMMON_H_MODULE
440 #define ZSTDv06_CCOMMON_H_MODULE
443 /*-*************************************
445 ***************************************/
446 #define MIN(a,b) ((a)<(b) ? (a) : (b))
447 #define MAX(a,b) ((a)>(b) ? (a) : (b))
450 /*-*************************************
452 ***************************************/
453 #define ZSTDv06_DICT_MAGIC 0xEC30A436
455 #define ZSTDv06_REP_NUM 3
456 #define ZSTDv06_REP_INIT ZSTDv06_REP_NUM
457 #define ZSTDv06_REP_MOVE (ZSTDv06_REP_NUM-1)
470 #define ZSTDv06_WINDOWLOG_ABSOLUTEMIN 12
471 static const size_t ZSTDv06_fcs_fieldSize
[4] = { 0, 1, 2, 8 };
473 #define ZSTDv06_BLOCKHEADERSIZE 3 /* because C standard does not allow a static const value to be defined using another static const value .... :( */
474 static const size_t ZSTDv06_blockHeaderSize
= ZSTDv06_BLOCKHEADERSIZE
;
475 typedef enum { bt_compressed
, bt_raw
, bt_rle
, bt_end
} blockType_t
;
477 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
478 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
487 #define LONGNBSEQ 0x7F00
490 #define EQUAL_READ32 4
491 #define REPCODE_STARTVALUE 1
494 #define MaxLit ((1<<Litbits) - 1)
498 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
503 #define FSEv06_ENCODING_RAW 0
504 #define FSEv06_ENCODING_RLE 1
505 #define FSEv06_ENCODING_STATIC 2
506 #define FSEv06_ENCODING_DYNAMIC 3
508 static const U32 LL_bits
[MaxLL
+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
509 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
511 static const S16 LL_defaultNorm
[MaxLL
+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
512 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
514 static const U32 LL_defaultNormLog
= 6;
516 static const U32 ML_bits
[MaxML
+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
517 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
518 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
520 static const S16 ML_defaultNorm
[MaxML
+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
521 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
522 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
524 static const U32 ML_defaultNormLog
= 6;
526 static const S16 OF_defaultNorm
[MaxOff
+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
527 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
528 static const U32 OF_defaultNormLog
= 5;
531 /*-*******************************************
532 * Shared functions to include for inlining
533 *********************************************/
534 static void ZSTDv06_copy8(void* dst
, const void* src
) { memcpy(dst
, src
, 8); }
535 #define COPY8(d,s) { ZSTDv06_copy8(d,s); d+=8; s+=8; }
537 /*! ZSTDv06_wildcopy() :
538 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
539 #define WILDCOPY_OVERLENGTH 8
540 MEM_STATIC
void ZSTDv06_wildcopy(void* dst
, const void* src
, ptrdiff_t length
)
542 const BYTE
* ip
= (const BYTE
*)src
;
543 BYTE
* op
= (BYTE
*)dst
;
544 BYTE
* const oend
= op
+ length
;
552 /*-*******************************************
554 *********************************************/
565 U32 rep
[ZSTDv06_REP_INIT
];
568 typedef struct { U32 unused
; } ZSTDv06_stats_t
;
580 U16
* matchLengthStart
;
583 U32 longLengthID
; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
586 ZSTDv06_optimal_t
* priceTable
;
587 ZSTDv06_match_t
* matchTable
;
588 U32
* matchLengthFreq
;
597 U32 log2matchLengthSum
;
599 U32 log2litLengthSum
;
605 const BYTE
* cachedLiterals
;
606 ZSTDv06_stats_t stats
;
609 void ZSTDv06_seqToCodes(const seqStore_t
* seqStorePtr
, size_t const nbSeq
);
612 #endif /* ZSTDv06_CCOMMON_H_MODULE */
613 /* ******************************************************************
614 FSE : Finite State Entropy codec
615 Public Prototypes declaration
616 Copyright (C) 2013-2016, Yann Collet.
618 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
620 Redistribution and use in source and binary forms, with or without
621 modification, are permitted provided that the following conditions are
624 * Redistributions of source code must retain the above copyright
625 notice, this list of conditions and the following disclaimer.
626 * Redistributions in binary form must reproduce the above
627 copyright notice, this list of conditions and the following disclaimer
628 in the documentation and/or other materials provided with the
631 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
632 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
633 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
634 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
635 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
636 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
637 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
638 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
639 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
640 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
641 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
643 You can contact the author at :
644 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
645 ****************************************************************** */
649 #if defined (__cplusplus)
655 /*-****************************************
656 * FSE simple functions
657 ******************************************/
658 /*! FSEv06_decompress():
659 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
660 into already allocated destination buffer 'dst', of size 'dstCapacity'.
661 @return : size of regenerated data (<= maxDstSize),
662 or an error code, which can be tested using FSEv06_isError() .
664 ** Important ** : FSEv06_decompress() does not decompress non-compressible nor RLE data !!!
665 Why ? : making this distinction requires a header.
666 Header management is intentionally delegated to the user layer, which can better manage special cases.
668 size_t FSEv06_decompress(void* dst
, size_t dstCapacity
,
669 const void* cSrc
, size_t cSrcSize
);
672 /*-*****************************************
674 ******************************************/
675 size_t FSEv06_compressBound(size_t size
); /* maximum compressed size */
677 /* Error Management */
678 unsigned FSEv06_isError(size_t code
); /* tells if a return value is an error code */
679 const char* FSEv06_getErrorName(size_t code
); /* provides error code string (useful for debugging) */
683 /*-*****************************************
685 ******************************************/
688 FSEv06_decompress() does the following:
689 1. read normalized counters with readNCount()
690 2. build decoding table 'DTable' from normalized counters
691 3. decode the data stream using decoding table 'DTable'
693 The following API allows targeting specific sub-functions for advanced tasks.
694 For example, it's possible to compress several blocks using the same 'CTable',
695 or to save and provide normalized distribution using external method.
699 /* *** DECOMPRESSION *** */
701 /*! FSEv06_readNCount():
702 Read compactly saved 'normalizedCounter' from 'rBuffer'.
703 @return : size read from 'rBuffer',
704 or an errorCode, which can be tested using FSEv06_isError().
705 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
706 size_t FSEv06_readNCount (short* normalizedCounter
, unsigned* maxSymbolValuePtr
, unsigned* tableLogPtr
, const void* rBuffer
, size_t rBuffSize
);
708 /*! Constructor and Destructor of FSEv06_DTable.
709 Note that its size depends on 'tableLog' */
710 typedef unsigned FSEv06_DTable
; /* don't allocate that. It's just a way to be more restrictive than void* */
711 FSEv06_DTable
* FSEv06_createDTable(unsigned tableLog
);
712 void FSEv06_freeDTable(FSEv06_DTable
* dt
);
714 /*! FSEv06_buildDTable():
715 Builds 'dt', which must be already allocated, using FSEv06_createDTable().
716 return : 0, or an errorCode, which can be tested using FSEv06_isError() */
717 size_t FSEv06_buildDTable (FSEv06_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
);
719 /*! FSEv06_decompress_usingDTable():
720 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
721 into `dst` which must be already allocated.
722 @return : size of regenerated data (necessarily <= `dstCapacity`),
723 or an errorCode, which can be tested using FSEv06_isError() */
724 size_t FSEv06_decompress_usingDTable(void* dst
, size_t dstCapacity
, const void* cSrc
, size_t cSrcSize
, const FSEv06_DTable
* dt
);
729 (Note : these functions only decompress FSE-compressed blocks.
730 If block is uncompressed, use memcpy() instead
731 If block is a single repeated byte, use memset() instead )
733 The first step is to obtain the normalized frequencies of symbols.
734 This can be performed by FSEv06_readNCount() if it was saved using FSEv06_writeNCount().
735 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
736 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
737 or size the table to handle worst case situations (typically 256).
738 FSEv06_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
739 The result of FSEv06_readNCount() is the number of bytes read from 'rBuffer'.
740 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
741 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
743 The next step is to build the decompression tables 'FSEv06_DTable' from 'normalizedCounter'.
744 This is performed by the function FSEv06_buildDTable().
745 The space required by 'FSEv06_DTable' must be already allocated using FSEv06_createDTable().
746 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
748 `FSEv06_DTable` can then be used to decompress `cSrc`, with FSEv06_decompress_usingDTable().
749 `cSrcSize` must be strictly correct, otherwise decompression will fail.
750 FSEv06_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
751 If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). (ex: dst buffer too small)
755 #if defined (__cplusplus)
759 #endif /* FSEv06_H */
760 /* ******************************************************************
763 header file (to include)
764 Copyright (C) 2013-2016, Yann Collet.
766 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
768 Redistribution and use in source and binary forms, with or without
769 modification, are permitted provided that the following conditions are
772 * Redistributions of source code must retain the above copyright
773 notice, this list of conditions and the following disclaimer.
774 * Redistributions in binary form must reproduce the above
775 copyright notice, this list of conditions and the following disclaimer
776 in the documentation and/or other materials provided with the
779 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
780 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
781 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
782 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
783 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
784 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
785 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
786 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
787 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
788 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
789 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
791 You can contact the author at :
792 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
793 ****************************************************************** */
794 #ifndef BITSTREAM_H_MODULE
795 #define BITSTREAM_H_MODULE
797 #if defined (__cplusplus)
803 * This API consists of small unitary functions, which must be inlined for best performance.
804 * Since link-time-optimization is not available for all compilers,
805 * these functions are defined into a .h to be included.
809 /*=========================================
811 =========================================*/
812 #if defined(__BMI__) && defined(__GNUC__)
813 # include <immintrin.h> /* support for bextr (experimental) */
818 /*-********************************************
819 * bitStream decoding API (read backward)
820 **********************************************/
824 unsigned bitsConsumed
;
829 typedef enum { BITv06_DStream_unfinished
= 0,
830 BITv06_DStream_endOfBuffer
= 1,
831 BITv06_DStream_completed
= 2,
832 BITv06_DStream_overflow
= 3 } BITv06_DStream_status
; /* result of BITv06_reloadDStream() */
833 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
835 MEM_STATIC
size_t BITv06_initDStream(BITv06_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
);
836 MEM_STATIC
size_t BITv06_readBits(BITv06_DStream_t
* bitD
, unsigned nbBits
);
837 MEM_STATIC BITv06_DStream_status
BITv06_reloadDStream(BITv06_DStream_t
* bitD
);
838 MEM_STATIC
unsigned BITv06_endOfDStream(const BITv06_DStream_t
* bitD
);
841 /* Start by invoking BITv06_initDStream().
842 * A chunk of the bitStream is then stored into a local register.
843 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
844 * You can then retrieve bitFields stored into the local register, **in reverse order**.
845 * Local register is explicitly reloaded from memory by the BITv06_reloadDStream() method.
846 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BITv06_DStream_unfinished.
847 * Otherwise, it can be less than that, so proceed accordingly.
848 * Checking if DStream has reached its end can be performed with BITv06_endOfDStream().
852 /*-****************************************
854 ******************************************/
855 MEM_STATIC
size_t BITv06_readBitsFast(BITv06_DStream_t
* bitD
, unsigned nbBits
);
856 /* faster, but works only if nbBits >= 1 */
860 /*-**************************************************************
862 ****************************************************************/
863 MEM_STATIC
unsigned BITv06_highbit32 (register U32 val
)
865 # if defined(_MSC_VER) /* Visual */
867 _BitScanReverse ( &r
, val
);
869 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
870 return 31 - __builtin_clz (val
);
871 # else /* Software version */
872 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 };
880 r
= DeBruijnClz
[ (U32
) (v
* 0x07C4ACDDU
) >> 27];
887 /*-********************************************************
889 **********************************************************/
890 /*! BITv06_initDStream() :
891 * Initialize a BITv06_DStream_t.
892 * `bitD` : a pointer to an already allocated BITv06_DStream_t structure.
893 * `srcSize` must be the *exact* size of the bitStream, in bytes.
894 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
896 MEM_STATIC
size_t BITv06_initDStream(BITv06_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
)
898 if (srcSize
< 1) { memset(bitD
, 0, sizeof(*bitD
)); return ERROR(srcSize_wrong
); }
900 if (srcSize
>= sizeof(bitD
->bitContainer
)) { /* normal case */
901 bitD
->start
= (const char*)srcBuffer
;
902 bitD
->ptr
= (const char*)srcBuffer
+ srcSize
- sizeof(bitD
->bitContainer
);
903 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
904 { BYTE
const lastByte
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
905 if (lastByte
== 0) return ERROR(GENERIC
); /* endMark not present */
906 bitD
->bitsConsumed
= 8 - BITv06_highbit32(lastByte
); }
908 bitD
->start
= (const char*)srcBuffer
;
909 bitD
->ptr
= bitD
->start
;
910 bitD
->bitContainer
= *(const BYTE
*)(bitD
->start
);
913 case 7: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[6]) << (sizeof(bitD
->bitContainer
)*8 - 16);
914 case 6: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[5]) << (sizeof(bitD
->bitContainer
)*8 - 24);
915 case 5: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[4]) << (sizeof(bitD
->bitContainer
)*8 - 32);
916 case 4: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[3]) << 24;
917 case 3: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[2]) << 16;
918 case 2: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[1]) << 8;
921 { BYTE
const lastByte
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
922 if (lastByte
== 0) return ERROR(GENERIC
); /* endMark not present */
923 bitD
->bitsConsumed
= 8 - BITv06_highbit32(lastByte
); }
924 bitD
->bitsConsumed
+= (U32
)(sizeof(bitD
->bitContainer
) - srcSize
)*8;
931 /*! BITv06_lookBits() :
932 * Provides next n bits from local register.
933 * local register is not modified.
934 * On 32-bits, maxNbBits==24.
935 * On 64-bits, maxNbBits==56.
936 * @return : value extracted
938 MEM_STATIC
size_t BITv06_lookBits(const BITv06_DStream_t
* bitD
, U32 nbBits
)
940 U32
const bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
941 return ((bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> 1) >> ((bitMask
-nbBits
) & bitMask
);
944 /*! BITv06_lookBitsFast() :
945 * unsafe version; only works only if nbBits >= 1 */
946 MEM_STATIC
size_t BITv06_lookBitsFast(const BITv06_DStream_t
* bitD
, U32 nbBits
)
948 U32
const bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
949 return (bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> (((bitMask
+1)-nbBits
) & bitMask
);
952 MEM_STATIC
void BITv06_skipBits(BITv06_DStream_t
* bitD
, U32 nbBits
)
954 bitD
->bitsConsumed
+= nbBits
;
957 /*! BITv06_readBits() :
958 * Read (consume) next n bits from local register and update.
959 * Pay attention to not read more than nbBits contained into local register.
960 * @return : extracted value.
962 MEM_STATIC
size_t BITv06_readBits(BITv06_DStream_t
* bitD
, U32 nbBits
)
964 size_t const value
= BITv06_lookBits(bitD
, nbBits
);
965 BITv06_skipBits(bitD
, nbBits
);
969 /*! BITv06_readBitsFast() :
970 * unsafe version; only works only if nbBits >= 1 */
971 MEM_STATIC
size_t BITv06_readBitsFast(BITv06_DStream_t
* bitD
, U32 nbBits
)
973 size_t const value
= BITv06_lookBitsFast(bitD
, nbBits
);
974 BITv06_skipBits(bitD
, nbBits
);
978 /*! BITv06_reloadDStream() :
979 * Refill `BITv06_DStream_t` from src buffer previously defined (see BITv06_initDStream() ).
980 * This function is safe, it guarantees it will not read beyond src buffer.
981 * @return : status of `BITv06_DStream_t` internal register.
982 if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
983 MEM_STATIC BITv06_DStream_status
BITv06_reloadDStream(BITv06_DStream_t
* bitD
)
985 if (bitD
->bitsConsumed
> (sizeof(bitD
->bitContainer
)*8)) /* should never happen */
986 return BITv06_DStream_overflow
;
988 if (bitD
->ptr
>= bitD
->start
+ sizeof(bitD
->bitContainer
)) {
989 bitD
->ptr
-= bitD
->bitsConsumed
>> 3;
990 bitD
->bitsConsumed
&= 7;
991 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
992 return BITv06_DStream_unfinished
;
994 if (bitD
->ptr
== bitD
->start
) {
995 if (bitD
->bitsConsumed
< sizeof(bitD
->bitContainer
)*8) return BITv06_DStream_endOfBuffer
;
996 return BITv06_DStream_completed
;
998 { U32 nbBytes
= bitD
->bitsConsumed
>> 3;
999 BITv06_DStream_status result
= BITv06_DStream_unfinished
;
1000 if (bitD
->ptr
- nbBytes
< bitD
->start
) {
1001 nbBytes
= (U32
)(bitD
->ptr
- bitD
->start
); /* ptr > start */
1002 result
= BITv06_DStream_endOfBuffer
;
1004 bitD
->ptr
-= nbBytes
;
1005 bitD
->bitsConsumed
-= nbBytes
*8;
1006 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
); /* reminder : srcSize > sizeof(bitD) */
1011 /*! BITv06_endOfDStream() :
1012 * @return Tells if DStream has exactly reached its end (all bits consumed).
1014 MEM_STATIC
unsigned BITv06_endOfDStream(const BITv06_DStream_t
* DStream
)
1016 return ((DStream
->ptr
== DStream
->start
) && (DStream
->bitsConsumed
== sizeof(DStream
->bitContainer
)*8));
1019 #if defined (__cplusplus)
1023 #endif /* BITSTREAM_H_MODULE */
1024 /* ******************************************************************
1025 FSE : Finite State Entropy coder
1026 header file for static linking (only)
1027 Copyright (C) 2013-2015, Yann Collet
1029 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1031 Redistribution and use in source and binary forms, with or without
1032 modification, are permitted provided that the following conditions are
1035 * Redistributions of source code must retain the above copyright
1036 notice, this list of conditions and the following disclaimer.
1037 * Redistributions in binary form must reproduce the above
1038 copyright notice, this list of conditions and the following disclaimer
1039 in the documentation and/or other materials provided with the
1042 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1043 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1044 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1045 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1046 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1047 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1048 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1049 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1050 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1051 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1052 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1054 You can contact the author at :
1055 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1056 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1057 ****************************************************************** */
1058 #ifndef FSEv06_STATIC_H
1059 #define FSEv06_STATIC_H
1061 #if defined (__cplusplus)
1066 /* *****************************************
1068 *******************************************/
1069 /* FSE buffer bounds */
1070 #define FSEv06_NCOUNTBOUND 512
1071 #define FSEv06_BLOCKBOUND(size) (size + (size>>7))
1072 #define FSEv06_COMPRESSBOUND(size) (FSEv06_NCOUNTBOUND + FSEv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
1074 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
1075 #define FSEv06_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
1078 /* *****************************************
1080 *******************************************/
1081 size_t FSEv06_countFast(unsigned* count
, unsigned* maxSymbolValuePtr
, const void* src
, size_t srcSize
);
1082 /* same as FSEv06_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
1084 size_t FSEv06_buildDTable_raw (FSEv06_DTable
* dt
, unsigned nbBits
);
1085 /* build a fake FSEv06_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
1087 size_t FSEv06_buildDTable_rle (FSEv06_DTable
* dt
, unsigned char symbolValue
);
1088 /* build a fake FSEv06_DTable, designed to always generate the same symbolValue */
1091 /* *****************************************
1092 * FSE symbol decompression API
1093 *******************************************/
1097 const void* table
; /* precise table may vary, depending on U16 */
1101 static void FSEv06_initDState(FSEv06_DState_t
* DStatePtr
, BITv06_DStream_t
* bitD
, const FSEv06_DTable
* dt
);
1103 static unsigned char FSEv06_decodeSymbol(FSEv06_DState_t
* DStatePtr
, BITv06_DStream_t
* bitD
);
1106 Let's now decompose FSEv06_decompress_usingDTable() into its unitary components.
1107 You will decode FSE-encoded symbols from the bitStream,
1108 and also any other bitFields you put in, **in reverse order**.
1110 You will need a few variables to track your bitStream. They are :
1112 BITv06_DStream_t DStream; // Stream context
1113 FSEv06_DState_t DState; // State context. Multiple ones are possible
1114 FSEv06_DTable* DTablePtr; // Decoding table, provided by FSEv06_buildDTable()
1116 The first thing to do is to init the bitStream.
1117 errorCode = BITv06_initDStream(&DStream, srcBuffer, srcSize);
1119 You should then retrieve your initial state(s)
1120 (in reverse flushing order if you have several ones) :
1121 errorCode = FSEv06_initDState(&DState, &DStream, DTablePtr);
1123 You can then decode your data, symbol after symbol.
1124 For information the maximum number of bits read by FSEv06_decodeSymbol() is 'tableLog'.
1125 Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
1126 unsigned char symbol = FSEv06_decodeSymbol(&DState, &DStream);
1128 You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
1129 Note : maximum allowed nbBits is 25, for 32-bits compatibility
1130 size_t bitField = BITv06_readBits(&DStream, nbBits);
1132 All above operations only read from local register (which size depends on size_t).
1133 Refueling the register from memory is manually performed by the reload method.
1134 endSignal = FSEv06_reloadDStream(&DStream);
1136 BITv06_reloadDStream() result tells if there is still some more data to read from DStream.
1137 BITv06_DStream_unfinished : there is still some data left into the DStream.
1138 BITv06_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
1139 BITv06_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
1140 BITv06_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
1142 When reaching end of buffer (BITv06_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
1143 to properly detect the exact end of stream.
1144 After each decoded symbol, check if DStream is fully consumed using this simple test :
1145 BITv06_reloadDStream(&DStream) >= BITv06_DStream_completed
1147 When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
1148 Checking if DStream has reached its end is performed by :
1149 BITv06_endOfDStream(&DStream);
1150 Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
1151 FSEv06_endOfDState(&DState);
1155 /* *****************************************
1157 *******************************************/
1158 static unsigned char FSEv06_decodeSymbolFast(FSEv06_DState_t
* DStatePtr
, BITv06_DStream_t
* bitD
);
1159 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
1162 /* *****************************************
1163 * Implementation of inlined functions
1164 *******************************************/
1167 /* ====== Decompression ====== */
1172 } FSEv06_DTableHeader
; /* sizeof U32 */
1176 unsigned short newState
;
1177 unsigned char symbol
;
1178 unsigned char nbBits
;
1179 } FSEv06_decode_t
; /* size == U32 */
1181 MEM_STATIC
void FSEv06_initDState(FSEv06_DState_t
* DStatePtr
, BITv06_DStream_t
* bitD
, const FSEv06_DTable
* dt
)
1183 const void* ptr
= dt
;
1184 const FSEv06_DTableHeader
* const DTableH
= (const FSEv06_DTableHeader
*)ptr
;
1185 DStatePtr
->state
= BITv06_readBits(bitD
, DTableH
->tableLog
);
1186 BITv06_reloadDStream(bitD
);
1187 DStatePtr
->table
= dt
+ 1;
1190 MEM_STATIC BYTE
FSEv06_peekSymbol(const FSEv06_DState_t
* DStatePtr
)
1192 FSEv06_decode_t
const DInfo
= ((const FSEv06_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
1193 return DInfo
.symbol
;
1196 MEM_STATIC
void FSEv06_updateState(FSEv06_DState_t
* DStatePtr
, BITv06_DStream_t
* bitD
)
1198 FSEv06_decode_t
const DInfo
= ((const FSEv06_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
1199 U32
const nbBits
= DInfo
.nbBits
;
1200 size_t const lowBits
= BITv06_readBits(bitD
, nbBits
);
1201 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
1204 MEM_STATIC BYTE
FSEv06_decodeSymbol(FSEv06_DState_t
* DStatePtr
, BITv06_DStream_t
* bitD
)
1206 FSEv06_decode_t
const DInfo
= ((const FSEv06_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
1207 U32
const nbBits
= DInfo
.nbBits
;
1208 BYTE
const symbol
= DInfo
.symbol
;
1209 size_t const lowBits
= BITv06_readBits(bitD
, nbBits
);
1211 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
1215 /*! FSEv06_decodeSymbolFast() :
1216 unsafe, only works if no symbol has a probability > 50% */
1217 MEM_STATIC BYTE
FSEv06_decodeSymbolFast(FSEv06_DState_t
* DStatePtr
, BITv06_DStream_t
* bitD
)
1219 FSEv06_decode_t
const DInfo
= ((const FSEv06_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
1220 U32
const nbBits
= DInfo
.nbBits
;
1221 BYTE
const symbol
= DInfo
.symbol
;
1222 size_t const lowBits
= BITv06_readBitsFast(bitD
, nbBits
);
1224 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
1230 #ifndef FSEv06_COMMONDEFS_ONLY
1232 /* **************************************************************
1234 ****************************************************************/
1236 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1237 * Increasing memory usage improves compression ratio
1238 * Reduced memory usage can improve speed, due to cache effect
1239 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1240 #define FSEv06_MAX_MEMORY_USAGE 14
1241 #define FSEv06_DEFAULT_MEMORY_USAGE 13
1243 /*!FSEv06_MAX_SYMBOL_VALUE :
1244 * Maximum symbol value authorized.
1245 * Required for proper stack allocation */
1246 #define FSEv06_MAX_SYMBOL_VALUE 255
1249 /* **************************************************************
1250 * template functions type & suffix
1251 ****************************************************************/
1252 #define FSEv06_FUNCTION_TYPE BYTE
1253 #define FSEv06_FUNCTION_EXTENSION
1254 #define FSEv06_DECODE_TYPE FSEv06_decode_t
1257 #endif /* !FSEv06_COMMONDEFS_ONLY */
1260 /* ***************************************************************
1262 *****************************************************************/
1263 #define FSEv06_MAX_TABLELOG (FSEv06_MAX_MEMORY_USAGE-2)
1264 #define FSEv06_MAX_TABLESIZE (1U<<FSEv06_MAX_TABLELOG)
1265 #define FSEv06_MAXTABLESIZE_MASK (FSEv06_MAX_TABLESIZE-1)
1266 #define FSEv06_DEFAULT_TABLELOG (FSEv06_DEFAULT_MEMORY_USAGE-2)
1267 #define FSEv06_MIN_TABLELOG 5
1269 #define FSEv06_TABLELOG_ABSOLUTE_MAX 15
1270 #if FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX
1271 #error "FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX is not supported"
1274 #define FSEv06_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
1277 #if defined (__cplusplus)
1281 #endif /* FSEv06_STATIC_H */
1283 Common functions of New Generation Entropy library
1284 Copyright (C) 2016, Yann Collet.
1286 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1288 Redistribution and use in source and binary forms, with or without
1289 modification, are permitted provided that the following conditions are
1292 * Redistributions of source code must retain the above copyright
1293 notice, this list of conditions and the following disclaimer.
1294 * Redistributions in binary form must reproduce the above
1295 copyright notice, this list of conditions and the following disclaimer
1296 in the documentation and/or other materials provided with the
1299 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1300 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1301 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1302 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1303 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1304 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1305 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1306 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1307 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1308 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1309 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1311 You can contact the author at :
1312 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1313 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1314 *************************************************************************** */
1317 /*-****************************************
1318 * FSE Error Management
1319 ******************************************/
1320 unsigned FSEv06_isError(size_t code
) { return ERR_isError(code
); }
1322 const char* FSEv06_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1325 /* **************************************************************
1326 * HUF Error Management
1327 ****************************************************************/
1328 unsigned HUFv06_isError(size_t code
) { return ERR_isError(code
); }
1330 const char* HUFv06_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1333 /*-**************************************************************
1334 * FSE NCount encoding-decoding
1335 ****************************************************************/
1336 static short FSEv06_abs(short a
) { return a
<0 ? -a
: a
; }
1338 size_t FSEv06_readNCount (short* normalizedCounter
, unsigned* maxSVPtr
, unsigned* tableLogPtr
,
1339 const void* headerBuffer
, size_t hbSize
)
1341 const BYTE
* const istart
= (const BYTE
*) headerBuffer
;
1342 const BYTE
* const iend
= istart
+ hbSize
;
1343 const BYTE
* ip
= istart
;
1349 unsigned charnum
= 0;
1352 if (hbSize
< 4) return ERROR(srcSize_wrong
);
1353 bitStream
= MEM_readLE32(ip
);
1354 nbBits
= (bitStream
& 0xF) + FSEv06_MIN_TABLELOG
; /* extract tableLog */
1355 if (nbBits
> FSEv06_TABLELOG_ABSOLUTE_MAX
) return ERROR(tableLog_tooLarge
);
1358 *tableLogPtr
= nbBits
;
1359 remaining
= (1<<nbBits
)+1;
1360 threshold
= 1<<nbBits
;
1363 while ((remaining
>1) && (charnum
<=*maxSVPtr
)) {
1365 unsigned n0
= charnum
;
1366 while ((bitStream
& 0xFFFF) == 0xFFFF) {
1370 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1375 while ((bitStream
& 3) == 3) {
1380 n0
+= bitStream
& 3;
1382 if (n0
> *maxSVPtr
) return ERROR(maxSymbolValue_tooSmall
);
1383 while (charnum
< n0
) normalizedCounter
[charnum
++] = 0;
1384 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1387 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1392 { short const max
= (short)((2*threshold
-1)-remaining
);
1395 if ((bitStream
& (threshold
-1)) < (U32
)max
) {
1396 count
= (short)(bitStream
& (threshold
-1));
1397 bitCount
+= nbBits
-1;
1399 count
= (short)(bitStream
& (2*threshold
-1));
1400 if (count
>= threshold
) count
-= max
;
1404 count
--; /* extra accuracy */
1405 remaining
-= FSEv06_abs(count
);
1406 normalizedCounter
[charnum
++] = count
;
1408 while (remaining
< threshold
) {
1413 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1417 bitCount
-= (int)(8 * (iend
- 4 - ip
));
1420 bitStream
= MEM_readLE32(ip
) >> (bitCount
& 31);
1421 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1422 if (remaining
!= 1) return ERROR(GENERIC
);
1423 *maxSVPtr
= charnum
-1;
1425 ip
+= (bitCount
+7)>>3;
1426 if ((size_t)(ip
-istart
) > hbSize
) return ERROR(srcSize_wrong
);
1429 /* ******************************************************************
1430 FSE : Finite State Entropy decoder
1431 Copyright (C) 2013-2015, Yann Collet.
1433 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1435 Redistribution and use in source and binary forms, with or without
1436 modification, are permitted provided that the following conditions are
1439 * Redistributions of source code must retain the above copyright
1440 notice, this list of conditions and the following disclaimer.
1441 * Redistributions in binary form must reproduce the above
1442 copyright notice, this list of conditions and the following disclaimer
1443 in the documentation and/or other materials provided with the
1446 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1447 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1448 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1449 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1450 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1451 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1452 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1453 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1454 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1455 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1456 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1458 You can contact the author at :
1459 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1460 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1461 ****************************************************************** */
1464 /* **************************************************************
1465 * Compiler specifics
1466 ****************************************************************/
1467 #ifdef _MSC_VER /* Visual Studio */
1468 # define FORCE_INLINE static __forceinline
1469 # include <intrin.h> /* For Visual 2005 */
1470 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1471 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1473 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1475 # define FORCE_INLINE static inline __attribute__((always_inline))
1477 # define FORCE_INLINE static inline
1480 # define FORCE_INLINE static
1481 # endif /* __STDC_VERSION__ */
1485 /* **************************************************************
1487 ****************************************************************/
1488 #define FSEv06_isError ERR_isError
1489 #define FSEv06_STATIC_ASSERT(c) { enum { FSEv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1492 /* **************************************************************
1494 ****************************************************************/
1495 typedef U32 DTable_max_t
[FSEv06_DTABLE_SIZE_U32(FSEv06_MAX_TABLELOG
)];
1498 /* **************************************************************
1500 ****************************************************************/
1502 designed to be included
1503 for type-specific functions (template emulation in C)
1504 Objective is to write these functions only once, for improved maintenance
1508 #ifndef FSEv06_FUNCTION_EXTENSION
1509 # error "FSEv06_FUNCTION_EXTENSION must be defined"
1511 #ifndef FSEv06_FUNCTION_TYPE
1512 # error "FSEv06_FUNCTION_TYPE must be defined"
1515 /* Function names */
1516 #define FSEv06_CAT(X,Y) X##Y
1517 #define FSEv06_FUNCTION_NAME(X,Y) FSEv06_CAT(X,Y)
1518 #define FSEv06_TYPE_NAME(X,Y) FSEv06_CAT(X,Y)
1521 /* Function templates */
1522 FSEv06_DTable
* FSEv06_createDTable (unsigned tableLog
)
1524 if (tableLog
> FSEv06_TABLELOG_ABSOLUTE_MAX
) tableLog
= FSEv06_TABLELOG_ABSOLUTE_MAX
;
1525 return (FSEv06_DTable
*)malloc( FSEv06_DTABLE_SIZE_U32(tableLog
) * sizeof (U32
) );
1528 void FSEv06_freeDTable (FSEv06_DTable
* dt
)
1533 size_t FSEv06_buildDTable(FSEv06_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
)
1535 void* const tdPtr
= dt
+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1536 FSEv06_DECODE_TYPE
* const tableDecode
= (FSEv06_DECODE_TYPE
*) (tdPtr
);
1537 U16 symbolNext
[FSEv06_MAX_SYMBOL_VALUE
+1];
1539 U32
const maxSV1
= maxSymbolValue
+ 1;
1540 U32
const tableSize
= 1 << tableLog
;
1541 U32 highThreshold
= tableSize
-1;
1544 if (maxSymbolValue
> FSEv06_MAX_SYMBOL_VALUE
) return ERROR(maxSymbolValue_tooLarge
);
1545 if (tableLog
> FSEv06_MAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
1547 /* Init, lay down lowprob symbols */
1548 { FSEv06_DTableHeader DTableH
;
1549 DTableH
.tableLog
= (U16
)tableLog
;
1550 DTableH
.fastMode
= 1;
1551 { S16
const largeLimit
= (S16
)(1 << (tableLog
-1));
1553 for (s
=0; s
<maxSV1
; s
++) {
1554 if (normalizedCounter
[s
]==-1) {
1555 tableDecode
[highThreshold
--].symbol
= (FSEv06_FUNCTION_TYPE
)s
;
1558 if (normalizedCounter
[s
] >= largeLimit
) DTableH
.fastMode
=0;
1559 symbolNext
[s
] = normalizedCounter
[s
];
1561 memcpy(dt
, &DTableH
, sizeof(DTableH
));
1564 /* Spread symbols */
1565 { U32
const tableMask
= tableSize
-1;
1566 U32
const step
= FSEv06_TABLESTEP(tableSize
);
1567 U32 s
, position
= 0;
1568 for (s
=0; s
<maxSV1
; s
++) {
1570 for (i
=0; i
<normalizedCounter
[s
]; i
++) {
1571 tableDecode
[position
].symbol
= (FSEv06_FUNCTION_TYPE
)s
;
1572 position
= (position
+ step
) & tableMask
;
1573 while (position
> highThreshold
) position
= (position
+ step
) & tableMask
; /* lowprob area */
1576 if (position
!=0) return ERROR(GENERIC
); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1579 /* Build Decoding table */
1581 for (u
=0; u
<tableSize
; u
++) {
1582 FSEv06_FUNCTION_TYPE
const symbol
= (FSEv06_FUNCTION_TYPE
)(tableDecode
[u
].symbol
);
1583 U16 nextState
= symbolNext
[symbol
]++;
1584 tableDecode
[u
].nbBits
= (BYTE
) (tableLog
- BITv06_highbit32 ((U32
)nextState
) );
1585 tableDecode
[u
].newState
= (U16
) ( (nextState
<< tableDecode
[u
].nbBits
) - tableSize
);
1593 #ifndef FSEv06_COMMONDEFS_ONLY
1595 /*-*******************************************************
1596 * Decompression (Byte symbols)
1597 *********************************************************/
1598 size_t FSEv06_buildDTable_rle (FSEv06_DTable
* dt
, BYTE symbolValue
)
1601 FSEv06_DTableHeader
* const DTableH
= (FSEv06_DTableHeader
*)ptr
;
1602 void* dPtr
= dt
+ 1;
1603 FSEv06_decode_t
* const cell
= (FSEv06_decode_t
*)dPtr
;
1605 DTableH
->tableLog
= 0;
1606 DTableH
->fastMode
= 0;
1609 cell
->symbol
= symbolValue
;
1616 size_t FSEv06_buildDTable_raw (FSEv06_DTable
* dt
, unsigned nbBits
)
1619 FSEv06_DTableHeader
* const DTableH
= (FSEv06_DTableHeader
*)ptr
;
1620 void* dPtr
= dt
+ 1;
1621 FSEv06_decode_t
* const dinfo
= (FSEv06_decode_t
*)dPtr
;
1622 const unsigned tableSize
= 1 << nbBits
;
1623 const unsigned tableMask
= tableSize
- 1;
1624 const unsigned maxSV1
= tableMask
+1;
1628 if (nbBits
< 1) return ERROR(GENERIC
); /* min size */
1630 /* Build Decoding Table */
1631 DTableH
->tableLog
= (U16
)nbBits
;
1632 DTableH
->fastMode
= 1;
1633 for (s
=0; s
<maxSV1
; s
++) {
1634 dinfo
[s
].newState
= 0;
1635 dinfo
[s
].symbol
= (BYTE
)s
;
1636 dinfo
[s
].nbBits
= (BYTE
)nbBits
;
1642 FORCE_INLINE
size_t FSEv06_decompress_usingDTable_generic(
1643 void* dst
, size_t maxDstSize
,
1644 const void* cSrc
, size_t cSrcSize
,
1645 const FSEv06_DTable
* dt
, const unsigned fast
)
1647 BYTE
* const ostart
= (BYTE
*) dst
;
1649 BYTE
* const omax
= op
+ maxDstSize
;
1650 BYTE
* const olimit
= omax
-3;
1652 BITv06_DStream_t bitD
;
1653 FSEv06_DState_t state1
;
1654 FSEv06_DState_t state2
;
1657 { size_t const errorCode
= BITv06_initDStream(&bitD
, cSrc
, cSrcSize
); /* replaced last arg by maxCompressed Size */
1658 if (FSEv06_isError(errorCode
)) return errorCode
; }
1660 FSEv06_initDState(&state1
, &bitD
, dt
);
1661 FSEv06_initDState(&state2
, &bitD
, dt
);
1663 #define FSEv06_GETSYMBOL(statePtr) fast ? FSEv06_decodeSymbolFast(statePtr, &bitD) : FSEv06_decodeSymbol(statePtr, &bitD)
1665 /* 4 symbols per loop */
1666 for ( ; (BITv06_reloadDStream(&bitD
)==BITv06_DStream_unfinished
) && (op
<olimit
) ; op
+=4) {
1667 op
[0] = FSEv06_GETSYMBOL(&state1
);
1669 if (FSEv06_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1670 BITv06_reloadDStream(&bitD
);
1672 op
[1] = FSEv06_GETSYMBOL(&state2
);
1674 if (FSEv06_MAX_TABLELOG
*4+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1675 { if (BITv06_reloadDStream(&bitD
) > BITv06_DStream_unfinished
) { op
+=2; break; } }
1677 op
[2] = FSEv06_GETSYMBOL(&state1
);
1679 if (FSEv06_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1680 BITv06_reloadDStream(&bitD
);
1682 op
[3] = FSEv06_GETSYMBOL(&state2
);
1686 /* note : BITv06_reloadDStream(&bitD) >= FSEv06_DStream_partiallyFilled; Ends at exactly BITv06_DStream_completed */
1688 if (op
>(omax
-2)) return ERROR(dstSize_tooSmall
);
1690 *op
++ = FSEv06_GETSYMBOL(&state1
);
1692 if (BITv06_reloadDStream(&bitD
)==BITv06_DStream_overflow
) {
1693 *op
++ = FSEv06_GETSYMBOL(&state2
);
1697 if (op
>(omax
-2)) return ERROR(dstSize_tooSmall
);
1699 *op
++ = FSEv06_GETSYMBOL(&state2
);
1701 if (BITv06_reloadDStream(&bitD
)==BITv06_DStream_overflow
) {
1702 *op
++ = FSEv06_GETSYMBOL(&state1
);
1710 size_t FSEv06_decompress_usingDTable(void* dst
, size_t originalSize
,
1711 const void* cSrc
, size_t cSrcSize
,
1712 const FSEv06_DTable
* dt
)
1714 const void* ptr
= dt
;
1715 const FSEv06_DTableHeader
* DTableH
= (const FSEv06_DTableHeader
*)ptr
;
1716 const U32 fastMode
= DTableH
->fastMode
;
1718 /* select fast mode (static) */
1719 if (fastMode
) return FSEv06_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 1);
1720 return FSEv06_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 0);
1724 size_t FSEv06_decompress(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
)
1726 const BYTE
* const istart
= (const BYTE
*)cSrc
;
1727 const BYTE
* ip
= istart
;
1728 short counting
[FSEv06_MAX_SYMBOL_VALUE
+1];
1729 DTable_max_t dt
; /* Static analyzer seems unable to understand this table will be properly initialized later */
1731 unsigned maxSymbolValue
= FSEv06_MAX_SYMBOL_VALUE
;
1733 if (cSrcSize
<2) return ERROR(srcSize_wrong
); /* too small input size */
1735 /* normal FSE decoding mode */
1736 { size_t const NCountLength
= FSEv06_readNCount (counting
, &maxSymbolValue
, &tableLog
, istart
, cSrcSize
);
1737 if (FSEv06_isError(NCountLength
)) return NCountLength
;
1738 if (NCountLength
>= cSrcSize
) return ERROR(srcSize_wrong
); /* too small input size */
1740 cSrcSize
-= NCountLength
;
1743 { size_t const errorCode
= FSEv06_buildDTable (dt
, counting
, maxSymbolValue
, tableLog
);
1744 if (FSEv06_isError(errorCode
)) return errorCode
; }
1746 return FSEv06_decompress_usingDTable (dst
, maxDstSize
, ip
, cSrcSize
, dt
); /* always return, even if it is an error code */
1751 #endif /* FSEv06_COMMONDEFS_ONLY */
1752 /* ******************************************************************
1753 Huffman coder, part of New Generation Entropy library
1755 Copyright (C) 2013-2016, Yann Collet.
1757 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1759 Redistribution and use in source and binary forms, with or without
1760 modification, are permitted provided that the following conditions are
1763 * Redistributions of source code must retain the above copyright
1764 notice, this list of conditions and the following disclaimer.
1765 * Redistributions in binary form must reproduce the above
1766 copyright notice, this list of conditions and the following disclaimer
1767 in the documentation and/or other materials provided with the
1770 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1771 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1772 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1773 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1774 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1775 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1776 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1777 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1778 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1779 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1780 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1782 You can contact the author at :
1783 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1784 ****************************************************************** */
1788 #if defined (__cplusplus)
1793 /* ****************************************
1794 * HUF simple functions
1795 ******************************************/
1796 size_t HUFv06_decompress(void* dst
, size_t dstSize
,
1797 const void* cSrc
, size_t cSrcSize
);
1799 HUFv06_decompress() :
1800 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1801 into already allocated destination buffer 'dst', of size 'dstSize'.
1802 `dstSize` : must be the **exact** size of original (uncompressed) data.
1803 Note : in contrast with FSE, HUFv06_decompress can regenerate
1804 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1805 because it knows size to regenerate.
1806 @return : size of regenerated data (== dstSize)
1807 or an error code, which can be tested using HUFv06_isError()
1811 /* ****************************************
1813 ******************************************/
1814 size_t HUFv06_compressBound(size_t size
); /**< maximum compressed size */
1817 #if defined (__cplusplus)
1821 #endif /* HUFv06_H */
1822 /* ******************************************************************
1823 Huffman codec, part of New Generation Entropy library
1824 header file, for static linking only
1825 Copyright (C) 2013-2016, Yann Collet
1827 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1829 Redistribution and use in source and binary forms, with or without
1830 modification, are permitted provided that the following conditions are
1833 * Redistributions of source code must retain the above copyright
1834 notice, this list of conditions and the following disclaimer.
1835 * Redistributions in binary form must reproduce the above
1836 copyright notice, this list of conditions and the following disclaimer
1837 in the documentation and/or other materials provided with the
1840 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1841 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1842 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1843 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1844 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1845 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1846 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1847 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1848 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1849 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1850 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1852 You can contact the author at :
1853 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1854 ****************************************************************** */
1855 #ifndef HUFv06_STATIC_H
1856 #define HUFv06_STATIC_H
1858 #if defined (__cplusplus)
1863 /* ****************************************
1865 ******************************************/
1866 /* HUF buffer bounds */
1867 #define HUFv06_CTABLEBOUND 129
1868 #define HUFv06_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1869 #define HUFv06_COMPRESSBOUND(size) (HUFv06_CTABLEBOUND + HUFv06_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
1871 /* static allocation of HUF's DTable */
1872 #define HUFv06_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1873 #define HUFv06_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1874 unsigned short DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1875 #define HUFv06_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1876 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1877 #define HUFv06_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1878 unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1881 /* ****************************************
1882 * Advanced decompression functions
1883 ******************************************/
1884 size_t HUFv06_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* single-symbol decoder */
1885 size_t HUFv06_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* double-symbols decoder */
1890 HUFv06_decompress() does the following:
1891 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1892 2. build Huffman table from save, using HUFv06_readDTableXn()
1893 3. decode 1 or 4 segments in parallel using HUFv06_decompressSXn_usingDTable
1895 size_t HUFv06_readDTableX2 (unsigned short* DTable
, const void* src
, size_t srcSize
);
1896 size_t HUFv06_readDTableX4 (unsigned* DTable
, const void* src
, size_t srcSize
);
1898 size_t HUFv06_decompress4X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned short* DTable
);
1899 size_t HUFv06_decompress4X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned* DTable
);
1902 /* single stream variants */
1903 size_t HUFv06_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* single-symbol decoder */
1904 size_t HUFv06_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* double-symbol decoder */
1906 size_t HUFv06_decompress1X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned short* DTable
);
1907 size_t HUFv06_decompress1X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const unsigned* DTable
);
1911 /* **************************************************************
1913 ****************************************************************/
1914 #define HUFv06_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv06_MAX_TABLELOG. Beyond that value, code does not work */
1915 #define HUFv06_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv06_ABSOLUTEMAX_TABLELOG */
1916 #define HUFv06_DEFAULT_TABLELOG HUFv06_MAX_TABLELOG /* tableLog by default, when not specified */
1917 #define HUFv06_MAX_SYMBOL_VALUE 255
1918 #if (HUFv06_MAX_TABLELOG > HUFv06_ABSOLUTEMAX_TABLELOG)
1919 # error "HUFv06_MAX_TABLELOG is too large !"
1924 /*! HUFv06_readStats() :
1925 Read compact Huffman tree, saved by HUFv06_writeCTable().
1926 `huffWeight` is destination buffer.
1927 @return : size read from `src`
1929 MEM_STATIC
size_t HUFv06_readStats(BYTE
* huffWeight
, size_t hwSize
, U32
* rankStats
,
1930 U32
* nbSymbolsPtr
, U32
* tableLogPtr
,
1931 const void* src
, size_t srcSize
)
1934 const BYTE
* ip
= (const BYTE
*) src
;
1938 if (!srcSize
) return ERROR(srcSize_wrong
);
1940 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1942 if (iSize
>= 128) { /* special header */
1943 if (iSize
>= (242)) { /* RLE */
1944 static U32 l
[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1945 oSize
= l
[iSize
-242];
1946 memset(huffWeight
, 1, hwSize
);
1949 else { /* Incompressible */
1950 oSize
= iSize
- 127;
1951 iSize
= ((oSize
+1)/2);
1952 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1953 if (oSize
>= hwSize
) return ERROR(corruption_detected
);
1956 for (n
=0; n
<oSize
; n
+=2) {
1957 huffWeight
[n
] = ip
[n
/2] >> 4;
1958 huffWeight
[n
+1] = ip
[n
/2] & 15;
1960 else { /* header compressed with FSE (normal case) */
1961 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1962 oSize
= FSEv06_decompress(huffWeight
, hwSize
-1, ip
+1, iSize
); /* max (hwSize-1) values decoded, as last one is implied */
1963 if (FSEv06_isError(oSize
)) return oSize
;
1966 /* collect weight stats */
1967 memset(rankStats
, 0, (HUFv06_ABSOLUTEMAX_TABLELOG
+ 1) * sizeof(U32
));
1969 { U32 n
; for (n
=0; n
<oSize
; n
++) {
1970 if (huffWeight
[n
] >= HUFv06_ABSOLUTEMAX_TABLELOG
) return ERROR(corruption_detected
);
1971 rankStats
[huffWeight
[n
]]++;
1972 weightTotal
+= (1 << huffWeight
[n
]) >> 1;
1974 if (weightTotal
== 0) return ERROR(corruption_detected
);
1976 /* get last non-null symbol weight (implied, total must be 2^n) */
1977 { U32
const tableLog
= BITv06_highbit32(weightTotal
) + 1;
1978 if (tableLog
> HUFv06_ABSOLUTEMAX_TABLELOG
) return ERROR(corruption_detected
);
1979 *tableLogPtr
= tableLog
;
1980 /* determine last weight */
1981 { U32
const total
= 1 << tableLog
;
1982 U32
const rest
= total
- weightTotal
;
1983 U32
const verif
= 1 << BITv06_highbit32(rest
);
1984 U32
const lastWeight
= BITv06_highbit32(rest
) + 1;
1985 if (verif
!= rest
) return ERROR(corruption_detected
); /* last value must be a clean power of 2 */
1986 huffWeight
[oSize
] = (BYTE
)lastWeight
;
1987 rankStats
[lastWeight
]++;
1990 /* check tree construction validity */
1991 if ((rankStats
[1] < 2) || (rankStats
[1] & 1)) return ERROR(corruption_detected
); /* by construction : at least 2 elts of rank 1, must be even */
1994 *nbSymbolsPtr
= (U32
)(oSize
+1);
2000 #if defined (__cplusplus)
2004 #endif /* HUFv06_STATIC_H */
2005 /* ******************************************************************
2006 Huffman decoder, part of New Generation Entropy library
2007 Copyright (C) 2013-2016, Yann Collet.
2009 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2011 Redistribution and use in source and binary forms, with or without
2012 modification, are permitted provided that the following conditions are
2015 * Redistributions of source code must retain the above copyright
2016 notice, this list of conditions and the following disclaimer.
2017 * Redistributions in binary form must reproduce the above
2018 copyright notice, this list of conditions and the following disclaimer
2019 in the documentation and/or other materials provided with the
2022 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2023 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2024 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2025 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2026 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2027 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2028 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2029 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2030 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2031 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2032 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2034 You can contact the author at :
2035 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
2036 - Public forum : https://groups.google.com/forum/#!forum/lz4c
2037 ****************************************************************** */
2039 /* **************************************************************
2040 * Compiler specifics
2041 ****************************************************************/
2042 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
2043 /* inline is defined */
2044 #elif defined(_MSC_VER)
2045 # define inline __inline
2047 # define inline /* disable inline */
2051 #ifdef _MSC_VER /* Visual Studio */
2052 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2057 /* **************************************************************
2059 ****************************************************************/
2060 #define HUFv06_STATIC_ASSERT(c) { enum { HUFv06_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
2064 /* *******************************************************
2065 * HUF : Huffman block decompression
2066 *********************************************************/
2067 typedef struct { BYTE byte
; BYTE nbBits
; } HUFv06_DEltX2
; /* single-symbol decoding */
2069 typedef struct { U16 sequence
; BYTE nbBits
; BYTE length
; } HUFv06_DEltX4
; /* double-symbols decoding */
2071 typedef struct { BYTE symbol
; BYTE weight
; } sortedSymbol_t
;
2075 /*-***************************/
2076 /* single-symbol decoding */
2077 /*-***************************/
2079 size_t HUFv06_readDTableX2 (U16
* DTable
, const void* src
, size_t srcSize
)
2081 BYTE huffWeight
[HUFv06_MAX_SYMBOL_VALUE
+ 1];
2082 U32 rankVal
[HUFv06_ABSOLUTEMAX_TABLELOG
+ 1]; /* large enough for values from 0 to 16 */
2088 void* const dtPtr
= DTable
+ 1;
2089 HUFv06_DEltX2
* const dt
= (HUFv06_DEltX2
*)dtPtr
;
2091 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX2
) == sizeof(U16
)); /* if compilation fails here, assertion is false */
2092 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
2094 iSize
= HUFv06_readStats(huffWeight
, HUFv06_MAX_SYMBOL_VALUE
+ 1, rankVal
, &nbSymbols
, &tableLog
, src
, srcSize
);
2095 if (HUFv06_isError(iSize
)) return iSize
;
2098 if (tableLog
> DTable
[0]) return ERROR(tableLog_tooLarge
); /* DTable is too small */
2099 DTable
[0] = (U16
)tableLog
; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
2103 for (n
=1; n
<tableLog
+1; n
++) {
2104 U32 current
= nextRankStart
;
2105 nextRankStart
+= (rankVal
[n
] << (n
-1));
2106 rankVal
[n
] = current
;
2110 for (n
=0; n
<nbSymbols
; n
++) {
2111 const U32 w
= huffWeight
[n
];
2112 const U32 length
= (1 << w
) >> 1;
2115 D
.byte
= (BYTE
)n
; D
.nbBits
= (BYTE
)(tableLog
+ 1 - w
);
2116 for (i
= rankVal
[w
]; i
< rankVal
[w
] + length
; i
++)
2118 rankVal
[w
] += length
;
2125 static BYTE
HUFv06_decodeSymbolX2(BITv06_DStream_t
* Dstream
, const HUFv06_DEltX2
* dt
, const U32 dtLog
)
2127 const size_t val
= BITv06_lookBitsFast(Dstream
, dtLog
); /* note : dtLog >= 1 */
2128 const BYTE c
= dt
[val
].byte
;
2129 BITv06_skipBits(Dstream
, dt
[val
].nbBits
);
2133 #define HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
2134 *ptr++ = HUFv06_decodeSymbolX2(DStreamPtr, dt, dtLog)
2136 #define HUFv06_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
2137 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2138 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2140 #define HUFv06_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
2142 HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2144 static inline size_t HUFv06_decodeStreamX2(BYTE
* p
, BITv06_DStream_t
* const bitDPtr
, BYTE
* const pEnd
, const HUFv06_DEltX2
* const dt
, const U32 dtLog
)
2146 BYTE
* const pStart
= p
;
2148 /* up to 4 symbols at a time */
2149 while ((BITv06_reloadDStream(bitDPtr
) == BITv06_DStream_unfinished
) && (p
<= pEnd
-4)) {
2150 HUFv06_DECODE_SYMBOLX2_2(p
, bitDPtr
);
2151 HUFv06_DECODE_SYMBOLX2_1(p
, bitDPtr
);
2152 HUFv06_DECODE_SYMBOLX2_2(p
, bitDPtr
);
2153 HUFv06_DECODE_SYMBOLX2_0(p
, bitDPtr
);
2156 /* closer to the end */
2157 while ((BITv06_reloadDStream(bitDPtr
) == BITv06_DStream_unfinished
) && (p
< pEnd
))
2158 HUFv06_DECODE_SYMBOLX2_0(p
, bitDPtr
);
2160 /* no more data to retrieve from bitstream, hence no need to reload */
2162 HUFv06_DECODE_SYMBOLX2_0(p
, bitDPtr
);
2167 size_t HUFv06_decompress1X2_usingDTable(
2168 void* dst
, size_t dstSize
,
2169 const void* cSrc
, size_t cSrcSize
,
2172 BYTE
* op
= (BYTE
*)dst
;
2173 BYTE
* const oend
= op
+ dstSize
;
2174 const U32 dtLog
= DTable
[0];
2175 const void* dtPtr
= DTable
;
2176 const HUFv06_DEltX2
* const dt
= ((const HUFv06_DEltX2
*)dtPtr
)+1;
2177 BITv06_DStream_t bitD
;
2179 { size_t const errorCode
= BITv06_initDStream(&bitD
, cSrc
, cSrcSize
);
2180 if (HUFv06_isError(errorCode
)) return errorCode
; }
2182 HUFv06_decodeStreamX2(op
, &bitD
, oend
, dt
, dtLog
);
2185 if (!BITv06_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
2190 size_t HUFv06_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2192 HUFv06_CREATE_STATIC_DTABLEX2(DTable
, HUFv06_MAX_TABLELOG
);
2193 const BYTE
* ip
= (const BYTE
*) cSrc
;
2195 size_t const errorCode
= HUFv06_readDTableX2 (DTable
, cSrc
, cSrcSize
);
2196 if (HUFv06_isError(errorCode
)) return errorCode
;
2197 if (errorCode
>= cSrcSize
) return ERROR(srcSize_wrong
);
2199 cSrcSize
-= errorCode
;
2201 return HUFv06_decompress1X2_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2205 size_t HUFv06_decompress4X2_usingDTable(
2206 void* dst
, size_t dstSize
,
2207 const void* cSrc
, size_t cSrcSize
,
2211 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2213 { const BYTE
* const istart
= (const BYTE
*) cSrc
;
2214 BYTE
* const ostart
= (BYTE
*) dst
;
2215 BYTE
* const oend
= ostart
+ dstSize
;
2216 const void* const dtPtr
= DTable
;
2217 const HUFv06_DEltX2
* const dt
= ((const HUFv06_DEltX2
*)dtPtr
) +1;
2218 const U32 dtLog
= DTable
[0];
2222 BITv06_DStream_t bitD1
;
2223 BITv06_DStream_t bitD2
;
2224 BITv06_DStream_t bitD3
;
2225 BITv06_DStream_t bitD4
;
2226 const size_t length1
= MEM_readLE16(istart
);
2227 const size_t length2
= MEM_readLE16(istart
+2);
2228 const size_t length3
= MEM_readLE16(istart
+4);
2230 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2231 const BYTE
* const istart2
= istart1
+ length1
;
2232 const BYTE
* const istart3
= istart2
+ length2
;
2233 const BYTE
* const istart4
= istart3
+ length3
;
2234 const size_t segmentSize
= (dstSize
+3) / 4;
2235 BYTE
* const opStart2
= ostart
+ segmentSize
;
2236 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2237 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2239 BYTE
* op2
= opStart2
;
2240 BYTE
* op3
= opStart3
;
2241 BYTE
* op4
= opStart4
;
2244 length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2245 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2246 errorCode
= BITv06_initDStream(&bitD1
, istart1
, length1
);
2247 if (HUFv06_isError(errorCode
)) return errorCode
;
2248 errorCode
= BITv06_initDStream(&bitD2
, istart2
, length2
);
2249 if (HUFv06_isError(errorCode
)) return errorCode
;
2250 errorCode
= BITv06_initDStream(&bitD3
, istart3
, length3
);
2251 if (HUFv06_isError(errorCode
)) return errorCode
;
2252 errorCode
= BITv06_initDStream(&bitD4
, istart4
, length4
);
2253 if (HUFv06_isError(errorCode
)) return errorCode
;
2255 /* 16-32 symbols per loop (4-8 symbols per stream) */
2256 endSignal
= BITv06_reloadDStream(&bitD1
) | BITv06_reloadDStream(&bitD2
) | BITv06_reloadDStream(&bitD3
) | BITv06_reloadDStream(&bitD4
);
2257 for ( ; (endSignal
==BITv06_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2258 HUFv06_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2259 HUFv06_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2260 HUFv06_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2261 HUFv06_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2262 HUFv06_DECODE_SYMBOLX2_1(op1
, &bitD1
);
2263 HUFv06_DECODE_SYMBOLX2_1(op2
, &bitD2
);
2264 HUFv06_DECODE_SYMBOLX2_1(op3
, &bitD3
);
2265 HUFv06_DECODE_SYMBOLX2_1(op4
, &bitD4
);
2266 HUFv06_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2267 HUFv06_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2268 HUFv06_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2269 HUFv06_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2270 HUFv06_DECODE_SYMBOLX2_0(op1
, &bitD1
);
2271 HUFv06_DECODE_SYMBOLX2_0(op2
, &bitD2
);
2272 HUFv06_DECODE_SYMBOLX2_0(op3
, &bitD3
);
2273 HUFv06_DECODE_SYMBOLX2_0(op4
, &bitD4
);
2274 endSignal
= BITv06_reloadDStream(&bitD1
) | BITv06_reloadDStream(&bitD2
) | BITv06_reloadDStream(&bitD3
) | BITv06_reloadDStream(&bitD4
);
2277 /* check corruption */
2278 if (op1
> opStart2
) return ERROR(corruption_detected
);
2279 if (op2
> opStart3
) return ERROR(corruption_detected
);
2280 if (op3
> opStart4
) return ERROR(corruption_detected
);
2281 /* note : op4 supposed already verified within main loop */
2283 /* finish bitStreams one by one */
2284 HUFv06_decodeStreamX2(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2285 HUFv06_decodeStreamX2(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2286 HUFv06_decodeStreamX2(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2287 HUFv06_decodeStreamX2(op4
, &bitD4
, oend
, dt
, dtLog
);
2290 endSignal
= BITv06_endOfDStream(&bitD1
) & BITv06_endOfDStream(&bitD2
) & BITv06_endOfDStream(&bitD3
) & BITv06_endOfDStream(&bitD4
);
2291 if (!endSignal
) return ERROR(corruption_detected
);
2299 size_t HUFv06_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2301 HUFv06_CREATE_STATIC_DTABLEX2(DTable
, HUFv06_MAX_TABLELOG
);
2302 const BYTE
* ip
= (const BYTE
*) cSrc
;
2304 size_t const errorCode
= HUFv06_readDTableX2 (DTable
, cSrc
, cSrcSize
);
2305 if (HUFv06_isError(errorCode
)) return errorCode
;
2306 if (errorCode
>= cSrcSize
) return ERROR(srcSize_wrong
);
2308 cSrcSize
-= errorCode
;
2310 return HUFv06_decompress4X2_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2314 /* *************************/
2315 /* double-symbols decoding */
2316 /* *************************/
2318 static void HUFv06_fillDTableX4Level2(HUFv06_DEltX4
* DTable
, U32 sizeLog
, const U32 consumed
,
2319 const U32
* rankValOrigin
, const int minWeight
,
2320 const sortedSymbol_t
* sortedSymbols
, const U32 sortedListSize
,
2321 U32 nbBitsBaseline
, U16 baseSeq
)
2324 U32 rankVal
[HUFv06_ABSOLUTEMAX_TABLELOG
+ 1];
2326 /* get pre-calculated rankVal */
2327 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2329 /* fill skipped values */
2331 U32 i
, skipSize
= rankVal
[minWeight
];
2332 MEM_writeLE16(&(DElt
.sequence
), baseSeq
);
2333 DElt
.nbBits
= (BYTE
)(consumed
);
2335 for (i
= 0; i
< skipSize
; i
++)
2340 { U32 s
; for (s
=0; s
<sortedListSize
; s
++) { /* note : sortedSymbols already skipped */
2341 const U32 symbol
= sortedSymbols
[s
].symbol
;
2342 const U32 weight
= sortedSymbols
[s
].weight
;
2343 const U32 nbBits
= nbBitsBaseline
- weight
;
2344 const U32 length
= 1 << (sizeLog
-nbBits
);
2345 const U32 start
= rankVal
[weight
];
2347 const U32 end
= start
+ length
;
2349 MEM_writeLE16(&(DElt
.sequence
), (U16
)(baseSeq
+ (symbol
<< 8)));
2350 DElt
.nbBits
= (BYTE
)(nbBits
+ consumed
);
2352 do { DTable
[i
++] = DElt
; } while (i
<end
); /* since length >= 1 */
2354 rankVal
[weight
] += length
;
2358 typedef U32 rankVal_t
[HUFv06_ABSOLUTEMAX_TABLELOG
][HUFv06_ABSOLUTEMAX_TABLELOG
+ 1];
2360 static void HUFv06_fillDTableX4(HUFv06_DEltX4
* DTable
, const U32 targetLog
,
2361 const sortedSymbol_t
* sortedList
, const U32 sortedListSize
,
2362 const U32
* rankStart
, rankVal_t rankValOrigin
, const U32 maxWeight
,
2363 const U32 nbBitsBaseline
)
2365 U32 rankVal
[HUFv06_ABSOLUTEMAX_TABLELOG
+ 1];
2366 const int scaleLog
= nbBitsBaseline
- targetLog
; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2367 const U32 minBits
= nbBitsBaseline
- maxWeight
;
2370 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2373 for (s
=0; s
<sortedListSize
; s
++) {
2374 const U16 symbol
= sortedList
[s
].symbol
;
2375 const U32 weight
= sortedList
[s
].weight
;
2376 const U32 nbBits
= nbBitsBaseline
- weight
;
2377 const U32 start
= rankVal
[weight
];
2378 const U32 length
= 1 << (targetLog
-nbBits
);
2380 if (targetLog
-nbBits
>= minBits
) { /* enough room for a second symbol */
2382 int minWeight
= nbBits
+ scaleLog
;
2383 if (minWeight
< 1) minWeight
= 1;
2384 sortedRank
= rankStart
[minWeight
];
2385 HUFv06_fillDTableX4Level2(DTable
+start
, targetLog
-nbBits
, nbBits
,
2386 rankValOrigin
[nbBits
], minWeight
,
2387 sortedList
+sortedRank
, sortedListSize
-sortedRank
,
2388 nbBitsBaseline
, symbol
);
2391 MEM_writeLE16(&(DElt
.sequence
), symbol
);
2392 DElt
.nbBits
= (BYTE
)(nbBits
);
2395 const U32 end
= start
+ length
;
2396 for (u
= start
; u
< end
; u
++) DTable
[u
] = DElt
;
2398 rankVal
[weight
] += length
;
2402 size_t HUFv06_readDTableX4 (U32
* DTable
, const void* src
, size_t srcSize
)
2404 BYTE weightList
[HUFv06_MAX_SYMBOL_VALUE
+ 1];
2405 sortedSymbol_t sortedSymbol
[HUFv06_MAX_SYMBOL_VALUE
+ 1];
2406 U32 rankStats
[HUFv06_ABSOLUTEMAX_TABLELOG
+ 1] = { 0 };
2407 U32 rankStart0
[HUFv06_ABSOLUTEMAX_TABLELOG
+ 2] = { 0 };
2408 U32
* const rankStart
= rankStart0
+1;
2410 U32 tableLog
, maxW
, sizeOfSort
, nbSymbols
;
2411 const U32 memLog
= DTable
[0];
2413 void* dtPtr
= DTable
;
2414 HUFv06_DEltX4
* const dt
= ((HUFv06_DEltX4
*)dtPtr
) + 1;
2416 HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX4
) == sizeof(U32
)); /* if compilation fails here, assertion is false */
2417 if (memLog
> HUFv06_ABSOLUTEMAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
2418 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2420 iSize
= HUFv06_readStats(weightList
, HUFv06_MAX_SYMBOL_VALUE
+ 1, rankStats
, &nbSymbols
, &tableLog
, src
, srcSize
);
2421 if (HUFv06_isError(iSize
)) return iSize
;
2424 if (tableLog
> memLog
) return ERROR(tableLog_tooLarge
); /* DTable can't fit code depth */
2426 /* find maxWeight */
2427 for (maxW
= tableLog
; rankStats
[maxW
]==0; maxW
--) {} /* necessarily finds a solution before 0 */
2429 /* Get start index of each weight */
2430 { U32 w
, nextRankStart
= 0;
2431 for (w
=1; w
<maxW
+1; w
++) {
2432 U32 current
= nextRankStart
;
2433 nextRankStart
+= rankStats
[w
];
2434 rankStart
[w
] = current
;
2436 rankStart
[0] = nextRankStart
; /* put all 0w symbols at the end of sorted list*/
2437 sizeOfSort
= nextRankStart
;
2440 /* sort symbols by weight */
2442 for (s
=0; s
<nbSymbols
; s
++) {
2443 U32
const w
= weightList
[s
];
2444 U32
const r
= rankStart
[w
]++;
2445 sortedSymbol
[r
].symbol
= (BYTE
)s
;
2446 sortedSymbol
[r
].weight
= (BYTE
)w
;
2448 rankStart
[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2452 { U32
* const rankVal0
= rankVal
[0];
2453 { int const rescale
= (memLog
-tableLog
) - 1; /* tableLog <= memLog */
2454 U32 nextRankVal
= 0;
2456 for (w
=1; w
<maxW
+1; w
++) {
2457 U32 current
= nextRankVal
;
2458 nextRankVal
+= rankStats
[w
] << (w
+rescale
);
2459 rankVal0
[w
] = current
;
2461 { U32
const minBits
= tableLog
+1 - maxW
;
2463 for (consumed
= minBits
; consumed
< memLog
- minBits
+ 1; consumed
++) {
2464 U32
* const rankValPtr
= rankVal
[consumed
];
2466 for (w
= 1; w
< maxW
+1; w
++) {
2467 rankValPtr
[w
] = rankVal0
[w
] >> consumed
;
2470 HUFv06_fillDTableX4(dt
, memLog
,
2471 sortedSymbol
, sizeOfSort
,
2472 rankStart0
, rankVal
, maxW
,
2479 static U32
HUFv06_decodeSymbolX4(void* op
, BITv06_DStream_t
* DStream
, const HUFv06_DEltX4
* dt
, const U32 dtLog
)
2481 const size_t val
= BITv06_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2482 memcpy(op
, dt
+val
, 2);
2483 BITv06_skipBits(DStream
, dt
[val
].nbBits
);
2484 return dt
[val
].length
;
2487 static U32
HUFv06_decodeLastSymbolX4(void* op
, BITv06_DStream_t
* DStream
, const HUFv06_DEltX4
* dt
, const U32 dtLog
)
2489 const size_t val
= BITv06_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2490 memcpy(op
, dt
+val
, 1);
2491 if (dt
[val
].length
==1) BITv06_skipBits(DStream
, dt
[val
].nbBits
);
2493 if (DStream
->bitsConsumed
< (sizeof(DStream
->bitContainer
)*8)) {
2494 BITv06_skipBits(DStream
, dt
[val
].nbBits
);
2495 if (DStream
->bitsConsumed
> (sizeof(DStream
->bitContainer
)*8))
2496 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 */
2502 #define HUFv06_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2503 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2505 #define HUFv06_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2506 if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2507 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2509 #define HUFv06_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2511 ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2513 static inline size_t HUFv06_decodeStreamX4(BYTE
* p
, BITv06_DStream_t
* bitDPtr
, BYTE
* const pEnd
, const HUFv06_DEltX4
* const dt
, const U32 dtLog
)
2515 BYTE
* const pStart
= p
;
2517 /* up to 8 symbols at a time */
2518 while ((BITv06_reloadDStream(bitDPtr
) == BITv06_DStream_unfinished
) && (p
< pEnd
-7)) {
2519 HUFv06_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2520 HUFv06_DECODE_SYMBOLX4_1(p
, bitDPtr
);
2521 HUFv06_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2522 HUFv06_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2525 /* closer to the end */
2526 while ((BITv06_reloadDStream(bitDPtr
) == BITv06_DStream_unfinished
) && (p
<= pEnd
-2))
2527 HUFv06_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2530 HUFv06_DECODE_SYMBOLX4_0(p
, bitDPtr
); /* no need to reload : reached the end of DStream */
2533 p
+= HUFv06_decodeLastSymbolX4(p
, bitDPtr
, dt
, dtLog
);
2539 size_t HUFv06_decompress1X4_usingDTable(
2540 void* dst
, size_t dstSize
,
2541 const void* cSrc
, size_t cSrcSize
,
2544 const BYTE
* const istart
= (const BYTE
*) cSrc
;
2545 BYTE
* const ostart
= (BYTE
*) dst
;
2546 BYTE
* const oend
= ostart
+ dstSize
;
2548 const U32 dtLog
= DTable
[0];
2549 const void* const dtPtr
= DTable
;
2550 const HUFv06_DEltX4
* const dt
= ((const HUFv06_DEltX4
*)dtPtr
) +1;
2553 BITv06_DStream_t bitD
;
2554 { size_t const errorCode
= BITv06_initDStream(&bitD
, istart
, cSrcSize
);
2555 if (HUFv06_isError(errorCode
)) return errorCode
; }
2558 HUFv06_decodeStreamX4(ostart
, &bitD
, oend
, dt
, dtLog
);
2561 if (!BITv06_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
2567 size_t HUFv06_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2569 HUFv06_CREATE_STATIC_DTABLEX4(DTable
, HUFv06_MAX_TABLELOG
);
2570 const BYTE
* ip
= (const BYTE
*) cSrc
;
2572 size_t const hSize
= HUFv06_readDTableX4 (DTable
, cSrc
, cSrcSize
);
2573 if (HUFv06_isError(hSize
)) return hSize
;
2574 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2578 return HUFv06_decompress1X4_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2581 size_t HUFv06_decompress4X4_usingDTable(
2582 void* dst
, size_t dstSize
,
2583 const void* cSrc
, size_t cSrcSize
,
2586 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2588 { const BYTE
* const istart
= (const BYTE
*) cSrc
;
2589 BYTE
* const ostart
= (BYTE
*) dst
;
2590 BYTE
* const oend
= ostart
+ dstSize
;
2591 const void* const dtPtr
= DTable
;
2592 const HUFv06_DEltX4
* const dt
= ((const HUFv06_DEltX4
*)dtPtr
) +1;
2593 const U32 dtLog
= DTable
[0];
2597 BITv06_DStream_t bitD1
;
2598 BITv06_DStream_t bitD2
;
2599 BITv06_DStream_t bitD3
;
2600 BITv06_DStream_t bitD4
;
2601 const size_t length1
= MEM_readLE16(istart
);
2602 const size_t length2
= MEM_readLE16(istart
+2);
2603 const size_t length3
= MEM_readLE16(istart
+4);
2605 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2606 const BYTE
* const istart2
= istart1
+ length1
;
2607 const BYTE
* const istart3
= istart2
+ length2
;
2608 const BYTE
* const istart4
= istart3
+ length3
;
2609 const size_t segmentSize
= (dstSize
+3) / 4;
2610 BYTE
* const opStart2
= ostart
+ segmentSize
;
2611 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2612 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2614 BYTE
* op2
= opStart2
;
2615 BYTE
* op3
= opStart3
;
2616 BYTE
* op4
= opStart4
;
2619 length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2620 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2621 errorCode
= BITv06_initDStream(&bitD1
, istart1
, length1
);
2622 if (HUFv06_isError(errorCode
)) return errorCode
;
2623 errorCode
= BITv06_initDStream(&bitD2
, istart2
, length2
);
2624 if (HUFv06_isError(errorCode
)) return errorCode
;
2625 errorCode
= BITv06_initDStream(&bitD3
, istart3
, length3
);
2626 if (HUFv06_isError(errorCode
)) return errorCode
;
2627 errorCode
= BITv06_initDStream(&bitD4
, istart4
, length4
);
2628 if (HUFv06_isError(errorCode
)) return errorCode
;
2630 /* 16-32 symbols per loop (4-8 symbols per stream) */
2631 endSignal
= BITv06_reloadDStream(&bitD1
) | BITv06_reloadDStream(&bitD2
) | BITv06_reloadDStream(&bitD3
) | BITv06_reloadDStream(&bitD4
);
2632 for ( ; (endSignal
==BITv06_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2633 HUFv06_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2634 HUFv06_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2635 HUFv06_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2636 HUFv06_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2637 HUFv06_DECODE_SYMBOLX4_1(op1
, &bitD1
);
2638 HUFv06_DECODE_SYMBOLX4_1(op2
, &bitD2
);
2639 HUFv06_DECODE_SYMBOLX4_1(op3
, &bitD3
);
2640 HUFv06_DECODE_SYMBOLX4_1(op4
, &bitD4
);
2641 HUFv06_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2642 HUFv06_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2643 HUFv06_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2644 HUFv06_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2645 HUFv06_DECODE_SYMBOLX4_0(op1
, &bitD1
);
2646 HUFv06_DECODE_SYMBOLX4_0(op2
, &bitD2
);
2647 HUFv06_DECODE_SYMBOLX4_0(op3
, &bitD3
);
2648 HUFv06_DECODE_SYMBOLX4_0(op4
, &bitD4
);
2650 endSignal
= BITv06_reloadDStream(&bitD1
) | BITv06_reloadDStream(&bitD2
) | BITv06_reloadDStream(&bitD3
) | BITv06_reloadDStream(&bitD4
);
2653 /* check corruption */
2654 if (op1
> opStart2
) return ERROR(corruption_detected
);
2655 if (op2
> opStart3
) return ERROR(corruption_detected
);
2656 if (op3
> opStart4
) return ERROR(corruption_detected
);
2657 /* note : op4 supposed already verified within main loop */
2659 /* finish bitStreams one by one */
2660 HUFv06_decodeStreamX4(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2661 HUFv06_decodeStreamX4(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2662 HUFv06_decodeStreamX4(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2663 HUFv06_decodeStreamX4(op4
, &bitD4
, oend
, dt
, dtLog
);
2666 endSignal
= BITv06_endOfDStream(&bitD1
) & BITv06_endOfDStream(&bitD2
) & BITv06_endOfDStream(&bitD3
) & BITv06_endOfDStream(&bitD4
);
2667 if (!endSignal
) return ERROR(corruption_detected
);
2675 size_t HUFv06_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2677 HUFv06_CREATE_STATIC_DTABLEX4(DTable
, HUFv06_MAX_TABLELOG
);
2678 const BYTE
* ip
= (const BYTE
*) cSrc
;
2680 size_t hSize
= HUFv06_readDTableX4 (DTable
, cSrc
, cSrcSize
);
2681 if (HUFv06_isError(hSize
)) return hSize
;
2682 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2686 return HUFv06_decompress4X4_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2692 /* ********************************/
2693 /* Generic decompression selector */
2694 /* ********************************/
2696 typedef struct { U32 tableTime
; U32 decode256Time
; } algo_time_t
;
2697 static const algo_time_t algoTime
[16 /* Quantization */][3 /* single, double, quad */] =
2699 /* single, double, quad */
2700 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2701 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2702 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2703 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2704 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2705 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2706 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2707 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2708 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2709 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2710 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2711 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2712 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2713 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2714 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2715 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2718 typedef size_t (*decompressionAlgo
)(void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
);
2720 size_t HUFv06_decompress (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2722 static const decompressionAlgo decompress
[3] = { HUFv06_decompress4X2
, HUFv06_decompress4X4
, NULL
};
2723 U32 Dtime
[3]; /* decompression time estimation */
2725 /* validation checks */
2726 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2727 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2728 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2729 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2731 /* decoder timing evaluation */
2732 { U32
const Q
= (U32
)(cSrcSize
* 16 / dstSize
); /* Q < 16 since dstSize > cSrcSize */
2733 U32
const D256
= (U32
)(dstSize
>> 8);
2734 U32 n
; for (n
=0; n
<3; n
++)
2735 Dtime
[n
] = algoTime
[Q
][n
].tableTime
+ (algoTime
[Q
][n
].decode256Time
* D256
);
2738 Dtime
[1] += Dtime
[1] >> 4; Dtime
[2] += Dtime
[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2741 if (Dtime
[1] < Dtime
[0]) algoNb
= 1;
2742 // if (Dtime[2] < Dtime[algoNb]) algoNb = 2; /* current speed of HUFv06_decompress4X6 is not good */
2743 return decompress
[algoNb
](dst
, dstSize
, cSrc
, cSrcSize
);
2746 //return HUFv06_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2747 //return HUFv06_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2748 //return HUFv06_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2751 Common functions of Zstd compression library
2752 Copyright (C) 2015-2016, Yann Collet.
2754 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2756 Redistribution and use in source and binary forms, with or without
2757 modification, are permitted provided that the following conditions are
2759 * Redistributions of source code must retain the above copyright
2760 notice, this list of conditions and the following disclaimer.
2761 * Redistributions in binary form must reproduce the above
2762 copyright notice, this list of conditions and the following disclaimer
2763 in the documentation and/or other materials provided with the
2765 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2766 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2767 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2768 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2769 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2770 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2771 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2772 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2773 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2774 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2775 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2777 You can contact the author at :
2778 - zstd homepage : http://www.zstd.net/
2782 /*-****************************************
2784 ******************************************/
2786 /*-****************************************
2787 * ZSTD Error Management
2788 ******************************************/
2789 /*! ZSTDv06_isError() :
2790 * tells if a return value is an error code */
2791 unsigned ZSTDv06_isError(size_t code
) { return ERR_isError(code
); }
2793 /*! ZSTDv06_getErrorName() :
2794 * provides error code string from function result (useful for debugging) */
2795 const char* ZSTDv06_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
2798 /* **************************************************************
2799 * ZBUFF Error Management
2800 ****************************************************************/
2801 unsigned ZBUFFv06_isError(size_t errorCode
) { return ERR_isError(errorCode
); }
2803 const char* ZBUFFv06_getErrorName(size_t errorCode
) { return ERR_getErrorName(errorCode
); }
2805 zstd - standard compression library
2806 Copyright (C) 2014-2016, Yann Collet.
2808 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2810 Redistribution and use in source and binary forms, with or without
2811 modification, are permitted provided that the following conditions are
2813 * Redistributions of source code must retain the above copyright
2814 notice, this list of conditions and the following disclaimer.
2815 * Redistributions in binary form must reproduce the above
2816 copyright notice, this list of conditions and the following disclaimer
2817 in the documentation and/or other materials provided with the
2819 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2820 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2821 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2822 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2823 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2824 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2825 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2826 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2827 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2828 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2829 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2831 You can contact the author at :
2832 - zstd homepage : http://www.zstd.net
2835 /* ***************************************************************
2837 *****************************************************************/
2840 * Select how default decompression function ZSTDv06_decompress() will allocate memory,
2841 * in memory stack (0), or in memory heap (1, requires malloc())
2843 #ifndef ZSTDv06_HEAPMODE
2844 # define ZSTDv06_HEAPMODE 1
2849 /*-*******************************************************
2850 * Compiler specifics
2851 *********************************************************/
2852 #ifdef _MSC_VER /* Visual Studio */
2853 # include <intrin.h> /* For Visual 2005 */
2854 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2855 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2859 /*-*************************************
2861 ***************************************/
2862 #define ZSTDv06_isError ERR_isError /* for inlining */
2863 #define FSEv06_isError ERR_isError
2864 #define HUFv06_isError ERR_isError
2867 /*_*******************************************************
2869 **********************************************************/
2870 static void ZSTDv06_copy4(void* dst
, const void* src
) { memcpy(dst
, src
, 4); }
2873 /*-*************************************************************
2874 * Context management
2875 ***************************************************************/
2876 typedef enum { ZSTDds_getFrameHeaderSize
, ZSTDds_decodeFrameHeader
,
2877 ZSTDds_decodeBlockHeader
, ZSTDds_decompressBlock
} ZSTDv06_dStage
;
2879 struct ZSTDv06_DCtx_s
2881 FSEv06_DTable LLTable
[FSEv06_DTABLE_SIZE_U32(LLFSELog
)];
2882 FSEv06_DTable OffTable
[FSEv06_DTABLE_SIZE_U32(OffFSELog
)];
2883 FSEv06_DTable MLTable
[FSEv06_DTABLE_SIZE_U32(MLFSELog
)];
2884 unsigned hufTableX4
[HUFv06_DTABLE_SIZE(HufLog
)];
2885 const void* previousDstEnd
;
2888 const void* dictEnd
;
2891 ZSTDv06_frameParams fParams
;
2892 blockType_t bType
; /* used in ZSTDv06_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2893 ZSTDv06_dStage stage
;
2894 U32 flagRepeatTable
;
2897 BYTE litBuffer
[ZSTDv06_BLOCKSIZE_MAX
+ WILDCOPY_OVERLENGTH
];
2898 BYTE headerBuffer
[ZSTDv06_FRAMEHEADERSIZE_MAX
];
2899 }; /* typedef'd to ZSTDv06_DCtx within "zstd_static.h" */
2901 size_t ZSTDv06_sizeofDCtx (void) { return sizeof(ZSTDv06_DCtx
); } /* non published interface */
2903 size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx
* dctx
)
2905 dctx
->expected
= ZSTDv06_frameHeaderSize_min
;
2906 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
2907 dctx
->previousDstEnd
= NULL
;
2910 dctx
->dictEnd
= NULL
;
2911 dctx
->hufTableX4
[0] = HufLog
;
2912 dctx
->flagRepeatTable
= 0;
2916 ZSTDv06_DCtx
* ZSTDv06_createDCtx(void)
2918 ZSTDv06_DCtx
* dctx
= (ZSTDv06_DCtx
*)malloc(sizeof(ZSTDv06_DCtx
));
2919 if (dctx
==NULL
) return NULL
;
2920 ZSTDv06_decompressBegin(dctx
);
2924 size_t ZSTDv06_freeDCtx(ZSTDv06_DCtx
* dctx
)
2927 return 0; /* reserved as a potential error code in the future */
2930 void ZSTDv06_copyDCtx(ZSTDv06_DCtx
* dstDCtx
, const ZSTDv06_DCtx
* srcDCtx
)
2932 memcpy(dstDCtx
, srcDCtx
,
2933 sizeof(ZSTDv06_DCtx
) - (ZSTDv06_BLOCKSIZE_MAX
+WILDCOPY_OVERLENGTH
+ ZSTDv06_frameHeaderSize_max
)); /* no need to copy workspace */
2937 /*-*************************************************************
2938 * Decompression section
2939 ***************************************************************/
2941 /* Frame format description
2942 Frame Header - [ Block Header - Block ] - Frame End
2944 - 4 bytes - Magic Number : ZSTDv06_MAGICNUMBER (defined within zstd_static.h)
2945 - 1 byte - Frame Descriptor
2947 - 3 bytes, starting with a 2-bits descriptor
2948 Uncompressed, Compressed, Frame End, unused
2950 See Block Format Description
2952 - 3 bytes, compatible with Block Header
2959 bit 0-3 : windowLog - ZSTDv06_WINDOWLOG_ABSOLUTEMIN (see zstd_internal.h)
2960 bit 4 : minmatch 4(0) or 3(1)
2961 bit 5 : reserved (must be zero)
2962 bit 6-7 : Frame content size : unknown, 1 byte, 2 bytes, 8 bytes
2964 Optional : content size (0, 1, 2 or 8 bytes)
2972 /* Compressed Block, format description
2974 Block = Literal Section - Sequences Section
2975 Prerequisite : size of (compressed) block, maximum size of regenerated data
2979 1.1) Header : 1-5 bytes
2981 00 compressed by Huff0
2983 10 is Raw (uncompressed)
2985 Note : using 01 => Huff0 with precomputed table ?
2986 Note : delta map ? => compressed ?
2988 1.1.1) Huff0-compressed literal block : 3-5 bytes
2989 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2990 srcSize < 1 KB => 3 bytes (2-2-10-10)
2991 srcSize < 16KB => 4 bytes (2-2-14-14)
2992 else => 5 bytes (2-2-18-18)
2993 big endian convention
2995 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2996 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2997 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2999 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3003 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3004 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
3005 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3007 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3011 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3012 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3013 srcSize < 1 KB => 3 bytes (2-2-10-10)
3014 srcSize < 16KB => 4 bytes (2-2-14-14)
3015 else => 5 bytes (2-2-18-18)
3016 big endian convention
3018 1- CTable available (stored into workspace ?)
3019 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3022 1.2) Literal block content
3024 1.2.1) Huff0 block, using sizes from header
3027 1.2.2) Huff0 block, using prepared table
3034 2) Sequences section
3038 /** ZSTDv06_frameHeaderSize() :
3039 * srcSize must be >= ZSTDv06_frameHeaderSize_min.
3040 * @return : size of the Frame Header */
3041 static size_t ZSTDv06_frameHeaderSize(const void* src
, size_t srcSize
)
3043 if (srcSize
< ZSTDv06_frameHeaderSize_min
) return ERROR(srcSize_wrong
);
3044 { U32
const fcsId
= (((const BYTE
*)src
)[4]) >> 6;
3045 return ZSTDv06_frameHeaderSize_min
+ ZSTDv06_fcs_fieldSize
[fcsId
]; }
3049 /** ZSTDv06_getFrameParams() :
3050 * decode Frame Header, or provide expected `srcSize`.
3051 * @return : 0, `fparamsPtr` is correctly filled,
3052 * >0, `srcSize` is too small, result is expected `srcSize`,
3053 * or an error code, which can be tested using ZSTDv06_isError() */
3054 size_t ZSTDv06_getFrameParams(ZSTDv06_frameParams
* fparamsPtr
, const void* src
, size_t srcSize
)
3056 const BYTE
* ip
= (const BYTE
*)src
;
3058 if (srcSize
< ZSTDv06_frameHeaderSize_min
) return ZSTDv06_frameHeaderSize_min
;
3059 if (MEM_readLE32(src
) != ZSTDv06_MAGICNUMBER
) return ERROR(prefix_unknown
);
3061 /* ensure there is enough `srcSize` to fully read/decode frame header */
3062 { size_t const fhsize
= ZSTDv06_frameHeaderSize(src
, srcSize
);
3063 if (srcSize
< fhsize
) return fhsize
; }
3065 memset(fparamsPtr
, 0, sizeof(*fparamsPtr
));
3066 { BYTE
const frameDesc
= ip
[4];
3067 fparamsPtr
->windowLog
= (frameDesc
& 0xF) + ZSTDv06_WINDOWLOG_ABSOLUTEMIN
;
3068 if ((frameDesc
& 0x20) != 0) return ERROR(frameParameter_unsupported
); /* reserved 1 bit */
3069 switch(frameDesc
>> 6) /* fcsId */
3071 default: /* impossible */
3072 case 0 : fparamsPtr
->frameContentSize
= 0; break;
3073 case 1 : fparamsPtr
->frameContentSize
= ip
[5]; break;
3074 case 2 : fparamsPtr
->frameContentSize
= MEM_readLE16(ip
+5)+256; break;
3075 case 3 : fparamsPtr
->frameContentSize
= MEM_readLE64(ip
+5); break;
3081 /** ZSTDv06_decodeFrameHeader() :
3082 * `srcSize` must be the size provided by ZSTDv06_frameHeaderSize().
3083 * @return : 0 if success, or an error code, which can be tested using ZSTDv06_isError() */
3084 static size_t ZSTDv06_decodeFrameHeader(ZSTDv06_DCtx
* zc
, const void* src
, size_t srcSize
)
3086 size_t const result
= ZSTDv06_getFrameParams(&(zc
->fParams
), src
, srcSize
);
3087 if ((MEM_32bits()) && (zc
->fParams
.windowLog
> 25)) return ERROR(frameParameter_unsupportedBy32bits
);
3094 blockType_t blockType
;
3096 } blockProperties_t
;
3098 /*! ZSTDv06_getcBlockSize() :
3099 * Provides the size of compressed block from block header `src` */
3100 size_t ZSTDv06_getcBlockSize(const void* src
, size_t srcSize
, blockProperties_t
* bpPtr
)
3102 const BYTE
* const in
= (const BYTE
* const)src
;
3105 if (srcSize
< ZSTDv06_blockHeaderSize
) return ERROR(srcSize_wrong
);
3107 bpPtr
->blockType
= (blockType_t
)((*in
) >> 6);
3108 cSize
= in
[2] + (in
[1]<<8) + ((in
[0] & 7)<<16);
3109 bpPtr
->origSize
= (bpPtr
->blockType
== bt_rle
) ? cSize
: 0;
3111 if (bpPtr
->blockType
== bt_end
) return 0;
3112 if (bpPtr
->blockType
== bt_rle
) return 1;
3117 static size_t ZSTDv06_copyRawBlock(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3119 if (srcSize
> dstCapacity
) return ERROR(dstSize_tooSmall
);
3120 memcpy(dst
, src
, srcSize
);
3125 /*! ZSTDv06_decodeLiteralsBlock() :
3126 @return : nb of bytes read from src (< srcSize ) */
3127 size_t ZSTDv06_decodeLiteralsBlock(ZSTDv06_DCtx
* dctx
,
3128 const void* src
, size_t srcSize
) /* note : srcSize < BLOCKSIZE */
3130 const BYTE
* const istart
= (const BYTE
*) src
;
3132 /* any compressed block with literals segment must be at least this size */
3133 if (srcSize
< MIN_CBLOCK_SIZE
) return ERROR(corruption_detected
);
3135 switch(istart
[0]>> 6)
3138 { size_t litSize
, litCSize
, singleStream
=0;
3139 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3140 if (srcSize
< 5) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3143 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3144 /* 2 - 2 - 10 - 10 */
3146 singleStream
= istart
[0] & 16;
3147 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
3148 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
3151 /* 2 - 2 - 14 - 14 */
3153 litSize
= ((istart
[0] & 15) << 10) + (istart
[1] << 2) + (istart
[2] >> 6);
3154 litCSize
= ((istart
[2] & 63) << 8) + istart
[3];
3157 /* 2 - 2 - 18 - 18 */
3159 litSize
= ((istart
[0] & 15) << 14) + (istart
[1] << 6) + (istart
[2] >> 2);
3160 litCSize
= ((istart
[2] & 3) << 16) + (istart
[3] << 8) + istart
[4];
3163 if (litSize
> ZSTDv06_BLOCKSIZE_MAX
) return ERROR(corruption_detected
);
3164 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
3166 if (HUFv06_isError(singleStream
?
3167 HUFv06_decompress1X2(dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) :
3168 HUFv06_decompress (dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) ))
3169 return ERROR(corruption_detected
);
3171 dctx
->litPtr
= dctx
->litBuffer
;
3172 dctx
->litSize
= litSize
;
3173 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3174 return litCSize
+ lhSize
;
3177 { size_t litSize
, litCSize
;
3178 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3179 if (lhSize
!= 1) /* only case supported for now : small litSize, single stream */
3180 return ERROR(corruption_detected
);
3181 if (!dctx
->flagRepeatTable
)
3182 return ERROR(dictionary_corrupted
);
3184 /* 2 - 2 - 10 - 10 */
3186 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
3187 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
3188 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
3190 { size_t const errorCode
= HUFv06_decompress1X4_usingDTable(dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
, dctx
->hufTableX4
);
3191 if (HUFv06_isError(errorCode
)) return ERROR(corruption_detected
);
3193 dctx
->litPtr
= dctx
->litBuffer
;
3194 dctx
->litSize
= litSize
;
3195 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3196 return litCSize
+ lhSize
;
3200 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3203 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3205 litSize
= istart
[0] & 31;
3208 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3211 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3215 if (lhSize
+litSize
+WILDCOPY_OVERLENGTH
> srcSize
) { /* risk reading beyond src buffer with wildcopy */
3216 if (litSize
+lhSize
> srcSize
) return ERROR(corruption_detected
);
3217 memcpy(dctx
->litBuffer
, istart
+lhSize
, litSize
);
3218 dctx
->litPtr
= dctx
->litBuffer
;
3219 dctx
->litSize
= litSize
;
3220 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3221 return lhSize
+litSize
;
3223 /* direct reference into compressed stream */
3224 dctx
->litPtr
= istart
+lhSize
;
3225 dctx
->litSize
= litSize
;
3226 return lhSize
+litSize
;
3230 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3233 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3235 litSize
= istart
[0] & 31;
3238 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3241 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3242 if (srcSize
<4) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3245 if (litSize
> ZSTDv06_BLOCKSIZE_MAX
) return ERROR(corruption_detected
);
3246 memset(dctx
->litBuffer
, istart
[lhSize
], litSize
+ WILDCOPY_OVERLENGTH
);
3247 dctx
->litPtr
= dctx
->litBuffer
;
3248 dctx
->litSize
= litSize
;
3252 return ERROR(corruption_detected
); /* impossible */
3257 /*! ZSTDv06_buildSeqTable() :
3258 @return : nb bytes read from src,
3259 or an error code if it fails, testable with ZSTDv06_isError()
3261 size_t ZSTDv06_buildSeqTable(FSEv06_DTable
* DTable
, U32 type
, U32 max
, U32 maxLog
,
3262 const void* src
, size_t srcSize
,
3263 const S16
* defaultNorm
, U32 defaultLog
, U32 flagRepeatTable
)
3267 case FSEv06_ENCODING_RLE
:
3268 if (!srcSize
) return ERROR(srcSize_wrong
);
3269 if ( (*(const BYTE
*)src
) > max
) return ERROR(corruption_detected
);
3270 FSEv06_buildDTable_rle(DTable
, *(const BYTE
*)src
); /* if *src > max, data is corrupted */
3272 case FSEv06_ENCODING_RAW
:
3273 FSEv06_buildDTable(DTable
, defaultNorm
, max
, defaultLog
);
3275 case FSEv06_ENCODING_STATIC
:
3276 if (!flagRepeatTable
) return ERROR(corruption_detected
);
3278 default : /* impossible */
3279 case FSEv06_ENCODING_DYNAMIC
:
3282 size_t const headerSize
= FSEv06_readNCount(norm
, &max
, &tableLog
, src
, srcSize
);
3283 if (FSEv06_isError(headerSize
)) return ERROR(corruption_detected
);
3284 if (tableLog
> maxLog
) return ERROR(corruption_detected
);
3285 FSEv06_buildDTable(DTable
, norm
, max
, tableLog
);
3291 size_t ZSTDv06_decodeSeqHeaders(int* nbSeqPtr
,
3292 FSEv06_DTable
* DTableLL
, FSEv06_DTable
* DTableML
, FSEv06_DTable
* DTableOffb
, U32 flagRepeatTable
,
3293 const void* src
, size_t srcSize
)
3295 const BYTE
* const istart
= (const BYTE
* const)src
;
3296 const BYTE
* const iend
= istart
+ srcSize
;
3297 const BYTE
* ip
= istart
;
3300 if (srcSize
< MIN_SEQUENCES_SIZE
) return ERROR(srcSize_wrong
);
3303 { int nbSeq
= *ip
++;
3304 if (!nbSeq
) { *nbSeqPtr
=0; return 1; }
3306 if (nbSeq
== 0xFF) {
3307 if (ip
+2 > iend
) return ERROR(srcSize_wrong
);
3308 nbSeq
= MEM_readLE16(ip
) + LONGNBSEQ
, ip
+=2;
3310 if (ip
>= iend
) return ERROR(srcSize_wrong
);
3311 nbSeq
= ((nbSeq
-0x80)<<8) + *ip
++;
3317 /* FSE table descriptors */
3318 { U32
const LLtype
= *ip
>> 6;
3319 U32
const Offtype
= (*ip
>> 4) & 3;
3320 U32
const MLtype
= (*ip
>> 2) & 3;
3324 if (ip
> iend
-3) return ERROR(srcSize_wrong
); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3327 { size_t const bhSize
= ZSTDv06_buildSeqTable(DTableLL
, LLtype
, MaxLL
, LLFSELog
, ip
, iend
-ip
, LL_defaultNorm
, LL_defaultNormLog
, flagRepeatTable
);
3328 if (ZSTDv06_isError(bhSize
)) return ERROR(corruption_detected
);
3331 { size_t const bhSize
= ZSTDv06_buildSeqTable(DTableOffb
, Offtype
, MaxOff
, OffFSELog
, ip
, iend
-ip
, OF_defaultNorm
, OF_defaultNormLog
, flagRepeatTable
);
3332 if (ZSTDv06_isError(bhSize
)) return ERROR(corruption_detected
);
3335 { size_t const bhSize
= ZSTDv06_buildSeqTable(DTableML
, MLtype
, MaxML
, MLFSELog
, ip
, iend
-ip
, ML_defaultNorm
, ML_defaultNormLog
, flagRepeatTable
);
3336 if (ZSTDv06_isError(bhSize
)) return ERROR(corruption_detected
);
3351 BITv06_DStream_t DStream
;
3352 FSEv06_DState_t stateLL
;
3353 FSEv06_DState_t stateOffb
;
3354 FSEv06_DState_t stateML
;
3355 size_t prevOffset
[ZSTDv06_REP_INIT
];
3360 static void ZSTDv06_decodeSequence(seq_t
* seq
, seqState_t
* seqState
)
3362 /* Literal length */
3363 U32
const llCode
= FSEv06_peekSymbol(&(seqState
->stateLL
));
3364 U32
const mlCode
= FSEv06_peekSymbol(&(seqState
->stateML
));
3365 U32
const ofCode
= FSEv06_peekSymbol(&(seqState
->stateOffb
)); /* <= maxOff, by table construction */
3367 U32
const llBits
= LL_bits
[llCode
];
3368 U32
const mlBits
= ML_bits
[mlCode
];
3369 U32
const ofBits
= ofCode
;
3370 U32
const totalBits
= llBits
+mlBits
+ofBits
;
3372 static const U32 LL_base
[MaxLL
+1] = {
3373 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3374 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3375 0x2000, 0x4000, 0x8000, 0x10000 };
3377 static const U32 ML_base
[MaxML
+1] = {
3378 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3379 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
3380 32, 34, 36, 38, 40, 44, 48, 56, 64, 80, 96, 0x80, 0x100, 0x200, 0x400, 0x800,
3381 0x1000, 0x2000, 0x4000, 0x8000, 0x10000 };
3383 static const U32 OF_base
[MaxOff
+1] = {
3384 0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F,
3385 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF,
3386 0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
3387 0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1 };
3394 offset
= OF_base
[ofCode
] + BITv06_readBits(&(seqState
->DStream
), ofBits
); /* <= 26 bits */
3395 if (MEM_32bits()) BITv06_reloadDStream(&(seqState
->DStream
));
3398 if (offset
< ZSTDv06_REP_NUM
) {
3399 if (llCode
== 0 && offset
<= 1) offset
= 1-offset
;
3402 size_t temp
= seqState
->prevOffset
[offset
];
3404 seqState
->prevOffset
[2] = seqState
->prevOffset
[1];
3406 seqState
->prevOffset
[1] = seqState
->prevOffset
[0];
3407 seqState
->prevOffset
[0] = offset
= temp
;
3410 offset
= seqState
->prevOffset
[0];
3413 offset
-= ZSTDv06_REP_MOVE
;
3414 seqState
->prevOffset
[2] = seqState
->prevOffset
[1];
3415 seqState
->prevOffset
[1] = seqState
->prevOffset
[0];
3416 seqState
->prevOffset
[0] = offset
;
3418 seq
->offset
= offset
;
3421 seq
->matchLength
= ML_base
[mlCode
] + MINMATCH
+ ((mlCode
>31) ? BITv06_readBits(&(seqState
->DStream
), mlBits
) : 0); /* <= 16 bits */
3422 if (MEM_32bits() && (mlBits
+llBits
>24)) BITv06_reloadDStream(&(seqState
->DStream
));
3424 seq
->litLength
= LL_base
[llCode
] + ((llCode
>15) ? BITv06_readBits(&(seqState
->DStream
), llBits
) : 0); /* <= 16 bits */
3426 (totalBits
> 64 - 7 - (LLFSELog
+MLFSELog
+OffFSELog
)) ) BITv06_reloadDStream(&(seqState
->DStream
));
3428 /* ANS state update */
3429 FSEv06_updateState(&(seqState
->stateLL
), &(seqState
->DStream
)); /* <= 9 bits */
3430 FSEv06_updateState(&(seqState
->stateML
), &(seqState
->DStream
)); /* <= 9 bits */
3431 if (MEM_32bits()) BITv06_reloadDStream(&(seqState
->DStream
)); /* <= 18 bits */
3432 FSEv06_updateState(&(seqState
->stateOffb
), &(seqState
->DStream
)); /* <= 8 bits */
3436 size_t ZSTDv06_execSequence(BYTE
* op
,
3437 BYTE
* const oend
, seq_t sequence
,
3438 const BYTE
** litPtr
, const BYTE
* const litLimit
,
3439 const BYTE
* const base
, const BYTE
* const vBase
, const BYTE
* const dictEnd
)
3441 BYTE
* const oLitEnd
= op
+ sequence
.litLength
;
3442 size_t const sequenceLength
= sequence
.litLength
+ sequence
.matchLength
;
3443 BYTE
* const oMatchEnd
= op
+ sequenceLength
; /* risk : address space overflow (32-bits) */
3444 BYTE
* const oend_8
= oend
-8;
3445 const BYTE
* const iLitEnd
= *litPtr
+ sequence
.litLength
;
3446 const BYTE
* match
= oLitEnd
- sequence
.offset
;
3449 if (oLitEnd
> oend_8
) return ERROR(dstSize_tooSmall
); /* last match must start at a minimum distance of 8 from oend */
3450 if (oMatchEnd
> oend
) return ERROR(dstSize_tooSmall
); /* overwrite beyond dst buffer */
3451 if (iLitEnd
> litLimit
) return ERROR(corruption_detected
); /* over-read beyond lit buffer */
3454 ZSTDv06_wildcopy(op
, *litPtr
, sequence
.litLength
); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3456 *litPtr
= iLitEnd
; /* update for next sequence */
3459 if (sequence
.offset
> (size_t)(oLitEnd
- base
)) {
3460 /* offset beyond prefix */
3461 if (sequence
.offset
> (size_t)(oLitEnd
- vBase
)) return ERROR(corruption_detected
);
3462 match
= dictEnd
- (base
-match
);
3463 if (match
+ sequence
.matchLength
<= dictEnd
) {
3464 memmove(oLitEnd
, match
, sequence
.matchLength
);
3465 return sequenceLength
;
3467 /* span extDict & currentPrefixSegment */
3468 { size_t const length1
= dictEnd
- match
;
3469 memmove(oLitEnd
, match
, length1
);
3470 op
= oLitEnd
+ length1
;
3471 sequence
.matchLength
-= length1
;
3473 if (op
> oend_8
|| sequence
.matchLength
< MINMATCH
) {
3474 while (op
< oMatchEnd
) *op
++ = *match
++;
3475 return sequenceLength
;
3478 /* Requirement: op <= oend_8 */
3480 /* match within prefix */
3481 if (sequence
.offset
< 8) {
3482 /* close range match, overlap */
3483 static const U32 dec32table
[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3484 static const int dec64table
[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3485 int const sub2
= dec64table
[sequence
.offset
];
3490 match
+= dec32table
[sequence
.offset
];
3491 ZSTDv06_copy4(op
+4, match
);
3494 ZSTDv06_copy8(op
, match
);
3496 op
+= 8; match
+= 8;
3498 if (oMatchEnd
> oend
-(16-MINMATCH
)) {
3500 ZSTDv06_wildcopy(op
, match
, oend_8
- op
);
3501 match
+= oend_8
- op
;
3504 while (op
< oMatchEnd
) *op
++ = *match
++;
3506 ZSTDv06_wildcopy(op
, match
, (ptrdiff_t)sequence
.matchLength
-8); /* works even if matchLength < 8 */
3508 return sequenceLength
;
3512 static size_t ZSTDv06_decompressSequences(
3514 void* dst
, size_t maxDstSize
,
3515 const void* seqStart
, size_t seqSize
)
3517 const BYTE
* ip
= (const BYTE
*)seqStart
;
3518 const BYTE
* const iend
= ip
+ seqSize
;
3519 BYTE
* const ostart
= (BYTE
* const)dst
;
3520 BYTE
* const oend
= ostart
+ maxDstSize
;
3522 const BYTE
* litPtr
= dctx
->litPtr
;
3523 const BYTE
* const litEnd
= litPtr
+ dctx
->litSize
;
3524 FSEv06_DTable
* DTableLL
= dctx
->LLTable
;
3525 FSEv06_DTable
* DTableML
= dctx
->MLTable
;
3526 FSEv06_DTable
* DTableOffb
= dctx
->OffTable
;
3527 const BYTE
* const base
= (const BYTE
*) (dctx
->base
);
3528 const BYTE
* const vBase
= (const BYTE
*) (dctx
->vBase
);
3529 const BYTE
* const dictEnd
= (const BYTE
*) (dctx
->dictEnd
);
3532 /* Build Decoding Tables */
3533 { size_t const seqHSize
= ZSTDv06_decodeSeqHeaders(&nbSeq
, DTableLL
, DTableML
, DTableOffb
, dctx
->flagRepeatTable
, ip
, seqSize
);
3534 if (ZSTDv06_isError(seqHSize
)) return seqHSize
;
3536 dctx
->flagRepeatTable
= 0;
3539 /* Regen sequences */
3542 seqState_t seqState
;
3544 memset(&sequence
, 0, sizeof(sequence
));
3545 sequence
.offset
= REPCODE_STARTVALUE
;
3546 { U32 i
; for (i
=0; i
<ZSTDv06_REP_INIT
; i
++) seqState
.prevOffset
[i
] = REPCODE_STARTVALUE
; }
3547 { size_t const errorCode
= BITv06_initDStream(&(seqState
.DStream
), ip
, iend
-ip
);
3548 if (ERR_isError(errorCode
)) return ERROR(corruption_detected
); }
3549 FSEv06_initDState(&(seqState
.stateLL
), &(seqState
.DStream
), DTableLL
);
3550 FSEv06_initDState(&(seqState
.stateOffb
), &(seqState
.DStream
), DTableOffb
);
3551 FSEv06_initDState(&(seqState
.stateML
), &(seqState
.DStream
), DTableML
);
3553 for ( ; (BITv06_reloadDStream(&(seqState
.DStream
)) <= BITv06_DStream_completed
) && nbSeq
; ) {
3555 ZSTDv06_decodeSequence(&sequence
, &seqState
);
3558 static BYTE
* start
= NULL
;
3559 if (start
==NULL
) start
= op
;
3560 size_t pos
= (size_t)(op
-start
);
3561 if ((pos
>= 5810037) && (pos
< 5810400))
3562 printf("Dpos %6u :%5u literals & match %3u bytes at distance %6u \n",
3563 pos
, (U32
)sequence
.litLength
, (U32
)sequence
.matchLength
, (U32
)sequence
.offset
);
3566 { size_t const oneSeqSize
= ZSTDv06_execSequence(op
, oend
, sequence
, &litPtr
, litEnd
, base
, vBase
, dictEnd
);
3567 if (ZSTDv06_isError(oneSeqSize
)) return oneSeqSize
;
3571 /* check if reached exact end */
3572 if (nbSeq
) return ERROR(corruption_detected
);
3575 /* last literal segment */
3576 { size_t const lastLLSize
= litEnd
- litPtr
;
3577 if (litPtr
> litEnd
) return ERROR(corruption_detected
); /* too many literals already used */
3578 if (op
+lastLLSize
> oend
) return ERROR(dstSize_tooSmall
);
3579 memcpy(op
, litPtr
, lastLLSize
);
3587 static void ZSTDv06_checkContinuity(ZSTDv06_DCtx
* dctx
, const void* dst
)
3589 if (dst
!= dctx
->previousDstEnd
) { /* not contiguous */
3590 dctx
->dictEnd
= dctx
->previousDstEnd
;
3591 dctx
->vBase
= (const char*)dst
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
3593 dctx
->previousDstEnd
= dst
;
3598 static size_t ZSTDv06_decompressBlock_internal(ZSTDv06_DCtx
* dctx
,
3599 void* dst
, size_t dstCapacity
,
3600 const void* src
, size_t srcSize
)
3601 { /* blockType == blockCompressed */
3602 const BYTE
* ip
= (const BYTE
*)src
;
3604 if (srcSize
>= ZSTDv06_BLOCKSIZE_MAX
) return ERROR(srcSize_wrong
);
3606 /* Decode literals sub-block */
3607 { size_t const litCSize
= ZSTDv06_decodeLiteralsBlock(dctx
, src
, srcSize
);
3608 if (ZSTDv06_isError(litCSize
)) return litCSize
;
3610 srcSize
-= litCSize
;
3612 return ZSTDv06_decompressSequences(dctx
, dst
, dstCapacity
, ip
, srcSize
);
3616 size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx
* dctx
,
3617 void* dst
, size_t dstCapacity
,
3618 const void* src
, size_t srcSize
)
3620 ZSTDv06_checkContinuity(dctx
, dst
);
3621 return ZSTDv06_decompressBlock_internal(dctx
, dst
, dstCapacity
, src
, srcSize
);
3625 /*! ZSTDv06_decompressFrame() :
3626 * `dctx` must be properly initialized */
3627 static size_t ZSTDv06_decompressFrame(ZSTDv06_DCtx
* dctx
,
3628 void* dst
, size_t dstCapacity
,
3629 const void* src
, size_t srcSize
)
3631 const BYTE
* ip
= (const BYTE
*)src
;
3632 const BYTE
* const iend
= ip
+ srcSize
;
3633 BYTE
* const ostart
= (BYTE
* const)dst
;
3635 BYTE
* const oend
= ostart
+ dstCapacity
;
3636 size_t remainingSize
= srcSize
;
3637 blockProperties_t blockProperties
= { bt_compressed
, 0 };
3640 if (srcSize
< ZSTDv06_frameHeaderSize_min
+ZSTDv06_blockHeaderSize
) return ERROR(srcSize_wrong
);
3643 { size_t const frameHeaderSize
= ZSTDv06_frameHeaderSize(src
, ZSTDv06_frameHeaderSize_min
);
3644 if (ZSTDv06_isError(frameHeaderSize
)) return frameHeaderSize
;
3645 if (srcSize
< frameHeaderSize
+ZSTDv06_blockHeaderSize
) return ERROR(srcSize_wrong
);
3646 if (ZSTDv06_decodeFrameHeader(dctx
, src
, frameHeaderSize
)) return ERROR(corruption_detected
);
3647 ip
+= frameHeaderSize
; remainingSize
-= frameHeaderSize
;
3650 /* Loop on each block */
3652 size_t decodedSize
=0;
3653 size_t const cBlockSize
= ZSTDv06_getcBlockSize(ip
, iend
-ip
, &blockProperties
);
3654 if (ZSTDv06_isError(cBlockSize
)) return cBlockSize
;
3656 ip
+= ZSTDv06_blockHeaderSize
;
3657 remainingSize
-= ZSTDv06_blockHeaderSize
;
3658 if (cBlockSize
> remainingSize
) return ERROR(srcSize_wrong
);
3660 switch(blockProperties
.blockType
)
3663 decodedSize
= ZSTDv06_decompressBlock_internal(dctx
, op
, oend
-op
, ip
, cBlockSize
);
3666 decodedSize
= ZSTDv06_copyRawBlock(op
, oend
-op
, ip
, cBlockSize
);
3669 return ERROR(GENERIC
); /* not yet supported */
3673 if (remainingSize
) return ERROR(srcSize_wrong
);
3676 return ERROR(GENERIC
); /* impossible */
3678 if (cBlockSize
== 0) break; /* bt_end */
3680 if (ZSTDv06_isError(decodedSize
)) return decodedSize
;
3683 remainingSize
-= cBlockSize
;
3690 size_t ZSTDv06_decompress_usingPreparedDCtx(ZSTDv06_DCtx
* dctx
, const ZSTDv06_DCtx
* refDCtx
,
3691 void* dst
, size_t dstCapacity
,
3692 const void* src
, size_t srcSize
)
3694 ZSTDv06_copyDCtx(dctx
, refDCtx
);
3695 ZSTDv06_checkContinuity(dctx
, dst
);
3696 return ZSTDv06_decompressFrame(dctx
, dst
, dstCapacity
, src
, srcSize
);
3700 size_t ZSTDv06_decompress_usingDict(ZSTDv06_DCtx
* dctx
,
3701 void* dst
, size_t dstCapacity
,
3702 const void* src
, size_t srcSize
,
3703 const void* dict
, size_t dictSize
)
3705 ZSTDv06_decompressBegin_usingDict(dctx
, dict
, dictSize
);
3706 ZSTDv06_checkContinuity(dctx
, dst
);
3707 return ZSTDv06_decompressFrame(dctx
, dst
, dstCapacity
, src
, srcSize
);
3711 size_t ZSTDv06_decompressDCtx(ZSTDv06_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3713 return ZSTDv06_decompress_usingDict(dctx
, dst
, dstCapacity
, src
, srcSize
, NULL
, 0);
3717 size_t ZSTDv06_decompress(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3719 #if defined(ZSTDv06_HEAPMODE) && (ZSTDv06_HEAPMODE==1)
3721 ZSTDv06_DCtx
* dctx
= ZSTDv06_createDCtx();
3722 if (dctx
==NULL
) return ERROR(memory_allocation
);
3723 regenSize
= ZSTDv06_decompressDCtx(dctx
, dst
, dstCapacity
, src
, srcSize
);
3724 ZSTDv06_freeDCtx(dctx
);
3726 #else /* stack mode */
3728 return ZSTDv06_decompressDCtx(&dctx
, dst
, dstCapacity
, src
, srcSize
);
3733 /*_******************************
3734 * Streaming Decompression API
3735 ********************************/
3736 size_t ZSTDv06_nextSrcSizeToDecompress(ZSTDv06_DCtx
* dctx
)
3738 return dctx
->expected
;
3741 size_t ZSTDv06_decompressContinue(ZSTDv06_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3744 if (srcSize
!= dctx
->expected
) return ERROR(srcSize_wrong
);
3745 if (dstCapacity
) ZSTDv06_checkContinuity(dctx
, dst
);
3747 /* Decompress : frame header; part 1 */
3748 switch (dctx
->stage
)
3750 case ZSTDds_getFrameHeaderSize
:
3751 if (srcSize
!= ZSTDv06_frameHeaderSize_min
) return ERROR(srcSize_wrong
); /* impossible */
3752 dctx
->headerSize
= ZSTDv06_frameHeaderSize(src
, ZSTDv06_frameHeaderSize_min
);
3753 if (ZSTDv06_isError(dctx
->headerSize
)) return dctx
->headerSize
;
3754 memcpy(dctx
->headerBuffer
, src
, ZSTDv06_frameHeaderSize_min
);
3755 if (dctx
->headerSize
> ZSTDv06_frameHeaderSize_min
) {
3756 dctx
->expected
= dctx
->headerSize
- ZSTDv06_frameHeaderSize_min
;
3757 dctx
->stage
= ZSTDds_decodeFrameHeader
;
3760 dctx
->expected
= 0; /* not necessary to copy more */
3762 case ZSTDds_decodeFrameHeader
:
3764 memcpy(dctx
->headerBuffer
+ ZSTDv06_frameHeaderSize_min
, src
, dctx
->expected
);
3765 result
= ZSTDv06_decodeFrameHeader(dctx
, dctx
->headerBuffer
, dctx
->headerSize
);
3766 if (ZSTDv06_isError(result
)) return result
;
3767 dctx
->expected
= ZSTDv06_blockHeaderSize
;
3768 dctx
->stage
= ZSTDds_decodeBlockHeader
;
3771 case ZSTDds_decodeBlockHeader
:
3772 { blockProperties_t bp
;
3773 size_t const cBlockSize
= ZSTDv06_getcBlockSize(src
, ZSTDv06_blockHeaderSize
, &bp
);
3774 if (ZSTDv06_isError(cBlockSize
)) return cBlockSize
;
3775 if (bp
.blockType
== bt_end
) {
3777 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
3779 dctx
->expected
= cBlockSize
;
3780 dctx
->bType
= bp
.blockType
;
3781 dctx
->stage
= ZSTDds_decompressBlock
;
3785 case ZSTDds_decompressBlock
:
3790 rSize
= ZSTDv06_decompressBlock_internal(dctx
, dst
, dstCapacity
, src
, srcSize
);
3793 rSize
= ZSTDv06_copyRawBlock(dst
, dstCapacity
, src
, srcSize
);
3796 return ERROR(GENERIC
); /* not yet handled */
3798 case bt_end
: /* should never happen (filtered at phase 1) */
3802 return ERROR(GENERIC
); /* impossible */
3804 dctx
->stage
= ZSTDds_decodeBlockHeader
;
3805 dctx
->expected
= ZSTDv06_blockHeaderSize
;
3806 dctx
->previousDstEnd
= (char*)dst
+ rSize
;
3810 return ERROR(GENERIC
); /* impossible */
3815 static void ZSTDv06_refDictContent(ZSTDv06_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3817 dctx
->dictEnd
= dctx
->previousDstEnd
;
3818 dctx
->vBase
= (const char*)dict
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
3820 dctx
->previousDstEnd
= (const char*)dict
+ dictSize
;
3823 static size_t ZSTDv06_loadEntropy(ZSTDv06_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3825 size_t hSize
, offcodeHeaderSize
, matchlengthHeaderSize
, litlengthHeaderSize
;
3827 hSize
= HUFv06_readDTableX4(dctx
->hufTableX4
, dict
, dictSize
);
3828 if (HUFv06_isError(hSize
)) return ERROR(dictionary_corrupted
);
3829 dict
= (const char*)dict
+ hSize
;
3832 { short offcodeNCount
[MaxOff
+1];
3833 U32 offcodeMaxValue
=MaxOff
, offcodeLog
;
3834 offcodeHeaderSize
= FSEv06_readNCount(offcodeNCount
, &offcodeMaxValue
, &offcodeLog
, dict
, dictSize
);
3835 if (FSEv06_isError(offcodeHeaderSize
)) return ERROR(dictionary_corrupted
);
3836 if (offcodeLog
> OffFSELog
) return ERROR(dictionary_corrupted
);
3837 { size_t const errorCode
= FSEv06_buildDTable(dctx
->OffTable
, offcodeNCount
, offcodeMaxValue
, offcodeLog
);
3838 if (FSEv06_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
3839 dict
= (const char*)dict
+ offcodeHeaderSize
;
3840 dictSize
-= offcodeHeaderSize
;
3843 { short matchlengthNCount
[MaxML
+1];
3844 unsigned matchlengthMaxValue
= MaxML
, matchlengthLog
;
3845 matchlengthHeaderSize
= FSEv06_readNCount(matchlengthNCount
, &matchlengthMaxValue
, &matchlengthLog
, dict
, dictSize
);
3846 if (FSEv06_isError(matchlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
3847 if (matchlengthLog
> MLFSELog
) return ERROR(dictionary_corrupted
);
3848 { size_t const errorCode
= FSEv06_buildDTable(dctx
->MLTable
, matchlengthNCount
, matchlengthMaxValue
, matchlengthLog
);
3849 if (FSEv06_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
3850 dict
= (const char*)dict
+ matchlengthHeaderSize
;
3851 dictSize
-= matchlengthHeaderSize
;
3854 { short litlengthNCount
[MaxLL
+1];
3855 unsigned litlengthMaxValue
= MaxLL
, litlengthLog
;
3856 litlengthHeaderSize
= FSEv06_readNCount(litlengthNCount
, &litlengthMaxValue
, &litlengthLog
, dict
, dictSize
);
3857 if (FSEv06_isError(litlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
3858 if (litlengthLog
> LLFSELog
) return ERROR(dictionary_corrupted
);
3859 { size_t const errorCode
= FSEv06_buildDTable(dctx
->LLTable
, litlengthNCount
, litlengthMaxValue
, litlengthLog
);
3860 if (FSEv06_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
3863 dctx
->flagRepeatTable
= 1;
3864 return hSize
+ offcodeHeaderSize
+ matchlengthHeaderSize
+ litlengthHeaderSize
;
3867 static size_t ZSTDv06_decompress_insertDictionary(ZSTDv06_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3870 U32
const magic
= MEM_readLE32(dict
);
3871 if (magic
!= ZSTDv06_DICT_MAGIC
) {
3872 /* pure content mode */
3873 ZSTDv06_refDictContent(dctx
, dict
, dictSize
);
3876 /* load entropy tables */
3877 dict
= (const char*)dict
+ 4;
3879 eSize
= ZSTDv06_loadEntropy(dctx
, dict
, dictSize
);
3880 if (ZSTDv06_isError(eSize
)) return ERROR(dictionary_corrupted
);
3882 /* reference dictionary content */
3883 dict
= (const char*)dict
+ eSize
;
3885 ZSTDv06_refDictContent(dctx
, dict
, dictSize
);
3891 size_t ZSTDv06_decompressBegin_usingDict(ZSTDv06_DCtx
* dctx
, const void* dict
, size_t dictSize
)
3893 { size_t const errorCode
= ZSTDv06_decompressBegin(dctx
);
3894 if (ZSTDv06_isError(errorCode
)) return errorCode
; }
3896 if (dict
&& dictSize
) {
3897 size_t const errorCode
= ZSTDv06_decompress_insertDictionary(dctx
, dict
, dictSize
);
3898 if (ZSTDv06_isError(errorCode
)) return ERROR(dictionary_corrupted
);
3905 Buffered version of Zstd compression library
3906 Copyright (C) 2015-2016, Yann Collet.
3908 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
3910 Redistribution and use in source and binary forms, with or without
3911 modification, are permitted provided that the following conditions are
3913 * Redistributions of source code must retain the above copyright
3914 notice, this list of conditions and the following disclaimer.
3915 * Redistributions in binary form must reproduce the above
3916 copyright notice, this list of conditions and the following disclaimer
3917 in the documentation and/or other materials provided with the
3919 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3920 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3921 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3922 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3923 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3924 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3925 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3926 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3927 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3928 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3929 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3931 You can contact the author at :
3932 - zstd homepage : http://www.zstd.net/
3936 /*-***************************************************************************
3937 * Streaming decompression howto
3939 * A ZBUFFv06_DCtx object is required to track streaming operations.
3940 * Use ZBUFFv06_createDCtx() and ZBUFFv06_freeDCtx() to create/release resources.
3941 * Use ZBUFFv06_decompressInit() to start a new decompression operation,
3942 * or ZBUFFv06_decompressInitDictionary() if decompression requires a dictionary.
3943 * Note that ZBUFFv06_DCtx objects can be re-init multiple times.
3945 * Use ZBUFFv06_decompressContinue() repetitively to consume your input.
3946 * *srcSizePtr and *dstCapacityPtr can be any size.
3947 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
3948 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
3949 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
3950 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
3951 * or 0 when a frame is completely decoded,
3952 * or an error code, which can be tested using ZBUFFv06_isError().
3954 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv06_recommendedDInSize() and ZBUFFv06_recommendedDOutSize()
3955 * output : ZBUFFv06_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
3956 * input : ZBUFFv06_recommendedDInSize == 128KB + 3;
3957 * just follow indications from ZBUFFv06_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3958 * *******************************************************************************/
3960 typedef enum { ZBUFFds_init
, ZBUFFds_loadHeader
,
3961 ZBUFFds_read
, ZBUFFds_load
, ZBUFFds_flush
} ZBUFFv06_dStage
;
3963 /* *** Resource management *** */
3964 struct ZBUFFv06_DCtx_s
{
3966 ZSTDv06_frameParams fParams
;
3967 ZBUFFv06_dStage stage
;
3976 BYTE headerBuffer
[ZSTDv06_FRAMEHEADERSIZE_MAX
];
3978 }; /* typedef'd to ZBUFFv06_DCtx within "zstd_buffered.h" */
3981 ZBUFFv06_DCtx
* ZBUFFv06_createDCtx(void)
3983 ZBUFFv06_DCtx
* zbd
= (ZBUFFv06_DCtx
*)malloc(sizeof(ZBUFFv06_DCtx
));
3984 if (zbd
==NULL
) return NULL
;
3985 memset(zbd
, 0, sizeof(*zbd
));
3986 zbd
->zd
= ZSTDv06_createDCtx();
3987 zbd
->stage
= ZBUFFds_init
;
3991 size_t ZBUFFv06_freeDCtx(ZBUFFv06_DCtx
* zbd
)
3993 if (zbd
==NULL
) return 0; /* support free on null */
3994 ZSTDv06_freeDCtx(zbd
->zd
);
4002 /* *** Initialization *** */
4004 size_t ZBUFFv06_decompressInitDictionary(ZBUFFv06_DCtx
* zbd
, const void* dict
, size_t dictSize
)
4006 zbd
->stage
= ZBUFFds_loadHeader
;
4007 zbd
->lhSize
= zbd
->inPos
= zbd
->outStart
= zbd
->outEnd
= 0;
4008 return ZSTDv06_decompressBegin_usingDict(zbd
->zd
, dict
, dictSize
);
4011 size_t ZBUFFv06_decompressInit(ZBUFFv06_DCtx
* zbd
)
4013 return ZBUFFv06_decompressInitDictionary(zbd
, NULL
, 0);
4018 MEM_STATIC
size_t ZBUFFv06_limitCopy(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
4020 size_t length
= MIN(dstCapacity
, srcSize
);
4021 memcpy(dst
, src
, length
);
4026 /* *** Decompression *** */
4028 size_t ZBUFFv06_decompressContinue(ZBUFFv06_DCtx
* zbd
,
4029 void* dst
, size_t* dstCapacityPtr
,
4030 const void* src
, size_t* srcSizePtr
)
4032 const char* const istart
= (const char*)src
;
4033 const char* const iend
= istart
+ *srcSizePtr
;
4034 const char* ip
= istart
;
4035 char* const ostart
= (char*)dst
;
4036 char* const oend
= ostart
+ *dstCapacityPtr
;
4044 return ERROR(init_missing
);
4046 case ZBUFFds_loadHeader
:
4047 { size_t const hSize
= ZSTDv06_getFrameParams(&(zbd
->fParams
), zbd
->headerBuffer
, zbd
->lhSize
);
4049 size_t const toLoad
= hSize
- zbd
->lhSize
; /* if hSize!=0, hSize > zbd->lhSize */
4050 if (ZSTDv06_isError(hSize
)) return hSize
;
4051 if (toLoad
> (size_t)(iend
-ip
)) { /* not enough input to load full header */
4052 memcpy(zbd
->headerBuffer
+ zbd
->lhSize
, ip
, iend
-ip
);
4053 zbd
->lhSize
+= iend
-ip
; ip
= iend
; notDone
= 0;
4054 *dstCapacityPtr
= 0;
4055 return (hSize
- zbd
->lhSize
) + ZSTDv06_blockHeaderSize
; /* remaining header bytes + next block header */
4057 memcpy(zbd
->headerBuffer
+ zbd
->lhSize
, ip
, toLoad
); zbd
->lhSize
= hSize
; ip
+= toLoad
;
4061 /* Consume header */
4062 { size_t const h1Size
= ZSTDv06_nextSrcSizeToDecompress(zbd
->zd
); /* == ZSTDv06_frameHeaderSize_min */
4063 size_t const h1Result
= ZSTDv06_decompressContinue(zbd
->zd
, NULL
, 0, zbd
->headerBuffer
, h1Size
);
4064 if (ZSTDv06_isError(h1Result
)) return h1Result
;
4065 if (h1Size
< zbd
->lhSize
) { /* long header */
4066 size_t const h2Size
= ZSTDv06_nextSrcSizeToDecompress(zbd
->zd
);
4067 size_t const h2Result
= ZSTDv06_decompressContinue(zbd
->zd
, NULL
, 0, zbd
->headerBuffer
+h1Size
, h2Size
);
4068 if (ZSTDv06_isError(h2Result
)) return h2Result
;
4071 /* Frame header instruct buffer sizes */
4072 { size_t const blockSize
= MIN(1 << zbd
->fParams
.windowLog
, ZSTDv06_BLOCKSIZE_MAX
);
4073 zbd
->blockSize
= blockSize
;
4074 if (zbd
->inBuffSize
< blockSize
) {
4076 zbd
->inBuffSize
= blockSize
;
4077 zbd
->inBuff
= (char*)malloc(blockSize
);
4078 if (zbd
->inBuff
== NULL
) return ERROR(memory_allocation
);
4080 { size_t const neededOutSize
= ((size_t)1 << zbd
->fParams
.windowLog
) + blockSize
;
4081 if (zbd
->outBuffSize
< neededOutSize
) {
4083 zbd
->outBuffSize
= neededOutSize
;
4084 zbd
->outBuff
= (char*)malloc(neededOutSize
);
4085 if (zbd
->outBuff
== NULL
) return ERROR(memory_allocation
);
4087 zbd
->stage
= ZBUFFds_read
;
4090 { size_t const neededInSize
= ZSTDv06_nextSrcSizeToDecompress(zbd
->zd
);
4091 if (neededInSize
==0) { /* end of frame */
4092 zbd
->stage
= ZBUFFds_init
;
4096 if ((size_t)(iend
-ip
) >= neededInSize
) { /* decode directly from src */
4097 size_t const decodedSize
= ZSTDv06_decompressContinue(zbd
->zd
,
4098 zbd
->outBuff
+ zbd
->outStart
, zbd
->outBuffSize
- zbd
->outStart
,
4100 if (ZSTDv06_isError(decodedSize
)) return decodedSize
;
4102 if (!decodedSize
) break; /* this was just a header */
4103 zbd
->outEnd
= zbd
->outStart
+ decodedSize
;
4104 zbd
->stage
= ZBUFFds_flush
;
4107 if (ip
==iend
) { notDone
= 0; break; } /* no more input */
4108 zbd
->stage
= ZBUFFds_load
;
4112 { size_t const neededInSize
= ZSTDv06_nextSrcSizeToDecompress(zbd
->zd
);
4113 size_t const toLoad
= neededInSize
- zbd
->inPos
; /* should always be <= remaining space within inBuff */
4115 if (toLoad
> zbd
->inBuffSize
- zbd
->inPos
) return ERROR(corruption_detected
); /* should never happen */
4116 loadedSize
= ZBUFFv06_limitCopy(zbd
->inBuff
+ zbd
->inPos
, toLoad
, ip
, iend
-ip
);
4118 zbd
->inPos
+= loadedSize
;
4119 if (loadedSize
< toLoad
) { notDone
= 0; break; } /* not enough input, wait for more */
4121 /* decode loaded input */
4122 { size_t const decodedSize
= ZSTDv06_decompressContinue(zbd
->zd
,
4123 zbd
->outBuff
+ zbd
->outStart
, zbd
->outBuffSize
- zbd
->outStart
,
4124 zbd
->inBuff
, neededInSize
);
4125 if (ZSTDv06_isError(decodedSize
)) return decodedSize
;
4126 zbd
->inPos
= 0; /* input is consumed */
4127 if (!decodedSize
) { zbd
->stage
= ZBUFFds_read
; break; } /* this was just a header */
4128 zbd
->outEnd
= zbd
->outStart
+ decodedSize
;
4129 zbd
->stage
= ZBUFFds_flush
;
4130 // break; /* ZBUFFds_flush follows */
4134 { size_t const toFlushSize
= zbd
->outEnd
- zbd
->outStart
;
4135 size_t const flushedSize
= ZBUFFv06_limitCopy(op
, oend
-op
, zbd
->outBuff
+ zbd
->outStart
, toFlushSize
);
4137 zbd
->outStart
+= flushedSize
;
4138 if (flushedSize
== toFlushSize
) {
4139 zbd
->stage
= ZBUFFds_read
;
4140 if (zbd
->outStart
+ zbd
->blockSize
> zbd
->outBuffSize
)
4141 zbd
->outStart
= zbd
->outEnd
= 0;
4144 /* cannot flush everything */
4148 default: return ERROR(GENERIC
); /* impossible */
4152 *srcSizePtr
= ip
-istart
;
4153 *dstCapacityPtr
= op
-ostart
;
4154 { size_t nextSrcSizeHint
= ZSTDv06_nextSrcSizeToDecompress(zbd
->zd
);
4155 if (nextSrcSizeHint
> ZSTDv06_blockHeaderSize
) nextSrcSizeHint
+= ZSTDv06_blockHeaderSize
; /* get following block header too */
4156 nextSrcSizeHint
-= zbd
->inPos
; /* already loaded*/
4157 return nextSrcSizeHint
;
4163 /* *************************************
4165 ***************************************/
4166 size_t ZBUFFv06_recommendedDInSize(void) { return ZSTDv06_BLOCKSIZE_MAX
+ ZSTDv06_blockHeaderSize
/* block header size*/ ; }
4167 size_t ZBUFFv06_recommendedDOutSize(void) { return ZSTDv06_BLOCKSIZE_MAX
; }