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.
12 #include <stddef.h> /* size_t, ptrdiff_t */
13 #include <string.h> /* memcpy */
14 #include <stdlib.h> /* malloc, free, qsort */
16 #define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
17 #include "xxhash.h" /* XXH64_* */
20 #define FSEv07_STATIC_LINKING_ONLY /* FSEv07_MIN_TABLELOG */
21 #define HUFv07_STATIC_LINKING_ONLY /* HUFv07_TABLELOG_ABSOLUTEMAX */
22 #define ZSTDv07_STATIC_LINKING_ONLY
24 #include "error_private.h"
27 #ifdef ZSTDv07_STATIC_LINKING_ONLY
29 /* ====================================================================================
30 * The definitions in this section are considered experimental.
31 * They should never be used with a dynamic library, as they may change in the future.
32 * They are provided for advanced usages.
33 * Use them only in association with static linking.
34 * ==================================================================================== */
37 #define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U
39 #define ZSTDv07_WINDOWLOG_MAX_32 25
40 #define ZSTDv07_WINDOWLOG_MAX_64 27
41 #define ZSTDv07_WINDOWLOG_MAX ((U32)(MEM_32bits() ? ZSTDv07_WINDOWLOG_MAX_32 : ZSTDv07_WINDOWLOG_MAX_64))
42 #define ZSTDv07_WINDOWLOG_MIN 18
43 #define ZSTDv07_CHAINLOG_MAX (ZSTDv07_WINDOWLOG_MAX+1)
44 #define ZSTDv07_CHAINLOG_MIN 4
45 #define ZSTDv07_HASHLOG_MAX ZSTDv07_WINDOWLOG_MAX
46 #define ZSTDv07_HASHLOG_MIN 12
47 #define ZSTDv07_HASHLOG3_MAX 17
48 #define ZSTDv07_SEARCHLOG_MAX (ZSTDv07_WINDOWLOG_MAX-1)
49 #define ZSTDv07_SEARCHLOG_MIN 1
50 #define ZSTDv07_SEARCHLENGTH_MAX 7
51 #define ZSTDv07_SEARCHLENGTH_MIN 3
52 #define ZSTDv07_TARGETLENGTH_MIN 4
53 #define ZSTDv07_TARGETLENGTH_MAX 999
55 #define ZSTDv07_FRAMEHEADERSIZE_MAX 18 /* for static allocation */
56 static const size_t ZSTDv07_frameHeaderSize_min
= 5;
57 static const size_t ZSTDv07_frameHeaderSize_max
= ZSTDv07_FRAMEHEADERSIZE_MAX
;
58 static const size_t ZSTDv07_skippableHeaderSize
= 8; /* magic number + skippable frame length */
61 /* custom memory allocation functions */
62 typedef void* (*ZSTDv07_allocFunction
) (void* opaque
, size_t size
);
63 typedef void (*ZSTDv07_freeFunction
) (void* opaque
, void* address
);
64 typedef struct { ZSTDv07_allocFunction customAlloc
; ZSTDv07_freeFunction customFree
; void* opaque
; } ZSTDv07_customMem
;
67 /*--- Advanced Decompression functions ---*/
69 /*! ZSTDv07_estimateDCtxSize() :
70 * Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */
71 ZSTDLIBv07_API
size_t ZSTDv07_estimateDCtxSize(void);
73 /*! ZSTDv07_createDCtx_advanced() :
74 * Create a ZSTD decompression context using external alloc and free functions */
75 ZSTDLIBv07_API ZSTDv07_DCtx
* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem
);
77 /*! ZSTDv07_sizeofDCtx() :
78 * Gives the amount of memory used by a given ZSTDv07_DCtx */
79 ZSTDLIBv07_API
size_t ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx
* dctx
);
82 /* ******************************************************************
83 * Buffer-less streaming functions (synchronous mode)
84 ********************************************************************/
86 ZSTDLIBv07_API
size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx
* dctx
);
87 ZSTDLIBv07_API
size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
);
88 ZSTDLIBv07_API
void ZSTDv07_copyDCtx(ZSTDv07_DCtx
* dctx
, const ZSTDv07_DCtx
* preparedDCtx
);
90 ZSTDLIBv07_API
size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx
* dctx
);
91 ZSTDLIBv07_API
size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
);
94 Buffer-less streaming decompression (synchronous mode)
96 A ZSTDv07_DCtx object is required to track streaming operations.
97 Use ZSTDv07_createDCtx() / ZSTDv07_freeDCtx() to manage it.
98 A ZSTDv07_DCtx object can be re-used multiple times.
100 First optional operation is to retrieve frame parameters, using ZSTDv07_getFrameParams(), which doesn't consume the input.
101 It can provide the minimum size of rolling buffer required to properly decompress data (`windowSize`),
102 and optionally the final size of uncompressed content.
103 (Note : content size is an optional info that may not be present. 0 means : content size unknown)
104 Frame parameters are extracted from the beginning of compressed frame.
105 The amount of data to read is variable, from ZSTDv07_frameHeaderSize_min to ZSTDv07_frameHeaderSize_max (so if `srcSize` >= ZSTDv07_frameHeaderSize_max, it will always work)
106 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
107 Result : 0 when successful, it means the ZSTDv07_frameParams structure has been filled.
108 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
109 errorCode, which can be tested using ZSTDv07_isError()
111 Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().
112 Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().
114 Then use ZSTDv07_nextSrcSizeToDecompress() and ZSTDv07_decompressContinue() alternatively.
115 ZSTDv07_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv07_decompressContinue().
116 ZSTDv07_decompressContinue() requires this exact amount of bytes, or it will fail.
118 @result of ZSTDv07_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity).
119 It can be zero, which is not an error; it just means ZSTDv07_decompressContinue() has decoded some header.
121 ZSTDv07_decompressContinue() needs previous data blocks during decompression, up to `windowSize`.
122 They should preferably be located contiguously, prior to current block.
123 Alternatively, a round buffer of sufficient size is also possible. Sufficient size is determined by frame parameters.
124 ZSTDv07_decompressContinue() is very sensitive to contiguity,
125 if 2 blocks don't follow each other, make sure that either the compressor breaks contiguity at the same place,
126 or that previous contiguous segment is large enough to properly handle maximum back-reference.
128 A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.
129 Context can then be reset to start a new decompression.
132 == Special case : skippable frames ==
134 Skippable frames allow the integration of user-defined data into a flow of concatenated frames.
135 Skippable frames will be ignored (skipped) by a decompressor. The format of skippable frame is following:
136 a) Skippable frame ID - 4 Bytes, Little endian format, any value from 0x184D2A50 to 0x184D2A5F
137 b) Frame Size - 4 Bytes, Little endian format, unsigned 32-bits
138 c) Frame Content - any content (User Data) of length equal to Frame Size
139 For skippable frames ZSTDv07_decompressContinue() always returns 0.
140 For skippable frames ZSTDv07_getFrameParams() returns fparamsPtr->windowLog==0 what means that a frame is skippable.
141 It also returns Frame Size as fparamsPtr->frameContentSize.
145 /* **************************************
147 ****************************************/
148 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
149 Frame metadata cost is typically ~18 bytes, which can be non-negligible for very small blocks (< 100 bytes).
150 User will have to take in charge required information to regenerate data, such as compressed and content sizes.
152 A few rules to respect :
153 - Compressing and decompressing require a context structure
154 + Use ZSTDv07_createCCtx() and ZSTDv07_createDCtx()
155 - It is necessary to init context before starting
156 + compression : ZSTDv07_compressBegin()
157 + decompression : ZSTDv07_decompressBegin()
158 + variants _usingDict() are also allowed
159 + copyCCtx() and copyDCtx() work too
160 - Block size is limited, it must be <= ZSTDv07_getBlockSizeMax()
161 + If you need to compress more, cut data into multiple blocks
162 + Consider using the regular ZSTDv07_compress() instead, as frame metadata costs become negligible when source size is large.
163 - When a block is considered not compressible enough, ZSTDv07_compressBlock() result will be zero.
164 In which case, nothing is produced into `dst`.
165 + User must test for such outcome and deal directly with uncompressed data
166 + ZSTDv07_decompressBlock() doesn't accept uncompressed data as input !!!
167 + In case of multiple successive blocks, decoder must be informed of uncompressed block existence to follow proper history.
168 Use ZSTDv07_insertBlock() in such a case.
171 #define ZSTDv07_BLOCKSIZE_ABSOLUTEMAX (128 * 1024) /* define, for static allocation */
172 ZSTDLIBv07_API
size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
);
173 ZSTDLIBv07_API
size_t ZSTDv07_insertBlock(ZSTDv07_DCtx
* dctx
, const void* blockStart
, size_t blockSize
); /**< insert block into `dctx` history. Useful for uncompressed blocks */
176 #endif /* ZSTDv07_STATIC_LINKING_ONLY */
179 /* ******************************************************************
181 low-level memory access routines
182 Copyright (C) 2013-2015, Yann Collet.
184 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
186 Redistribution and use in source and binary forms, with or without
187 modification, are permitted provided that the following conditions are
190 * Redistributions of source code must retain the above copyright
191 notice, this list of conditions and the following disclaimer.
192 * Redistributions in binary form must reproduce the above
193 copyright notice, this list of conditions and the following disclaimer
194 in the documentation and/or other materials provided with the
197 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
198 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
199 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
200 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
201 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
202 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
203 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
204 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
205 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
206 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
207 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
209 You can contact the author at :
210 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
211 - Public forum : https://groups.google.com/forum/#!forum/lz4c
212 ****************************************************************** */
216 #if defined (__cplusplus)
220 /*-****************************************
222 ******************************************/
223 #if defined(_MSC_VER) /* Visual Studio */
224 # include <stdlib.h> /* _byteswap_ulong */
225 # include <intrin.h> /* _byteswap_* */
227 #if defined(__GNUC__)
228 # define MEM_STATIC static __attribute__((unused))
229 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
230 # define MEM_STATIC static inline
231 #elif defined(_MSC_VER)
232 # define MEM_STATIC static __inline
234 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
238 /*-**************************************************************
240 *****************************************************************/
241 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
243 typedef uint8_t BYTE
;
244 typedef uint16_t U16
;
246 typedef uint32_t U32
;
248 typedef uint64_t U64
;
251 typedef unsigned char BYTE
;
252 typedef unsigned short U16
;
253 typedef signed short S16
;
254 typedef unsigned int U32
;
255 typedef signed int S32
;
256 typedef unsigned long long U64
;
257 typedef signed long long S64
;
261 /*-**************************************************************
263 *****************************************************************/
264 /* MEM_FORCE_MEMORY_ACCESS :
265 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
266 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
267 * The below switch allow to select different access method for improved performance.
268 * Method 0 (default) : use `memcpy()`. Safe and portable.
269 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
270 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
271 * Method 2 : direct access. This method is portable but violate C standard.
272 * It can generate buggy code on targets depending on alignment.
273 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
274 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
275 * Prefer these methods in priority order (0 > 1 > 2)
277 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
278 # 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__) )
279 # define MEM_FORCE_MEMORY_ACCESS 2
280 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
281 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
282 # define MEM_FORCE_MEMORY_ACCESS 1
286 MEM_STATIC
unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
287 MEM_STATIC
unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
289 MEM_STATIC
unsigned MEM_isLittleEndian(void)
291 const union { U32 u
; BYTE c
[4]; } one
= { 1 }; /* don't use static : performance detrimental */
295 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
297 /* violates C standard, by lying on structure alignment.
298 Only use if no other choice to achieve best performance on target platform */
299 MEM_STATIC U16
MEM_read16(const void* memPtr
) { return *(const U16
*) memPtr
; }
300 MEM_STATIC U32
MEM_read32(const void* memPtr
) { return *(const U32
*) memPtr
; }
301 MEM_STATIC U64
MEM_read64(const void* memPtr
) { return *(const U64
*) memPtr
; }
303 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { *(U16
*)memPtr
= value
; }
305 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
307 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
308 /* currently only defined for gcc and icc */
309 typedef union { U16 u16
; U32 u32
; U64 u64
; size_t st
; } __attribute__((packed
)) unalign
;
311 MEM_STATIC U16
MEM_read16(const void* ptr
) { return ((const unalign
*)ptr
)->u16
; }
312 MEM_STATIC U32
MEM_read32(const void* ptr
) { return ((const unalign
*)ptr
)->u32
; }
313 MEM_STATIC U64
MEM_read64(const void* ptr
) { return ((const unalign
*)ptr
)->u64
; }
315 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { ((unalign
*)memPtr
)->u16
= value
; }
319 /* default method, safe and standard.
320 can sometimes prove slower */
322 MEM_STATIC U16
MEM_read16(const void* memPtr
)
324 U16 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
327 MEM_STATIC U32
MEM_read32(const void* memPtr
)
329 U32 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
332 MEM_STATIC U64
MEM_read64(const void* memPtr
)
334 U64 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
337 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
)
339 memcpy(memPtr
, &value
, sizeof(value
));
342 #endif /* MEM_FORCE_MEMORY_ACCESS */
344 MEM_STATIC U32
MEM_swap32(U32 in
)
346 #if defined(_MSC_VER) /* Visual Studio */
347 return _byteswap_ulong(in
);
348 #elif defined (__GNUC__)
349 return __builtin_bswap32(in
);
351 return ((in
<< 24) & 0xff000000 ) |
352 ((in
<< 8) & 0x00ff0000 ) |
353 ((in
>> 8) & 0x0000ff00 ) |
354 ((in
>> 24) & 0x000000ff );
358 MEM_STATIC U64
MEM_swap64(U64 in
)
360 #if defined(_MSC_VER) /* Visual Studio */
361 return _byteswap_uint64(in
);
362 #elif defined (__GNUC__)
363 return __builtin_bswap64(in
);
365 return ((in
<< 56) & 0xff00000000000000ULL
) |
366 ((in
<< 40) & 0x00ff000000000000ULL
) |
367 ((in
<< 24) & 0x0000ff0000000000ULL
) |
368 ((in
<< 8) & 0x000000ff00000000ULL
) |
369 ((in
>> 8) & 0x00000000ff000000ULL
) |
370 ((in
>> 24) & 0x0000000000ff0000ULL
) |
371 ((in
>> 40) & 0x000000000000ff00ULL
) |
372 ((in
>> 56) & 0x00000000000000ffULL
);
377 /*=== Little endian r/w ===*/
379 MEM_STATIC U16
MEM_readLE16(const void* memPtr
)
381 if (MEM_isLittleEndian())
382 return MEM_read16(memPtr
);
384 const BYTE
* p
= (const BYTE
*)memPtr
;
385 return (U16
)(p
[0] + (p
[1]<<8));
389 MEM_STATIC
void MEM_writeLE16(void* memPtr
, U16 val
)
391 if (MEM_isLittleEndian()) {
392 MEM_write16(memPtr
, val
);
394 BYTE
* p
= (BYTE
*)memPtr
;
396 p
[1] = (BYTE
)(val
>>8);
400 MEM_STATIC U32
MEM_readLE32(const void* memPtr
)
402 if (MEM_isLittleEndian())
403 return MEM_read32(memPtr
);
405 return MEM_swap32(MEM_read32(memPtr
));
409 MEM_STATIC U64
MEM_readLE64(const void* memPtr
)
411 if (MEM_isLittleEndian())
412 return MEM_read64(memPtr
);
414 return MEM_swap64(MEM_read64(memPtr
));
417 MEM_STATIC
size_t MEM_readLEST(const void* memPtr
)
420 return (size_t)MEM_readLE32(memPtr
);
422 return (size_t)MEM_readLE64(memPtr
);
427 #if defined (__cplusplus)
431 #endif /* MEM_H_MODULE */
432 /* ******************************************************************
435 header file (to include)
436 Copyright (C) 2013-2016, Yann Collet.
438 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
440 Redistribution and use in source and binary forms, with or without
441 modification, are permitted provided that the following conditions are
444 * Redistributions of source code must retain the above copyright
445 notice, this list of conditions and the following disclaimer.
446 * Redistributions in binary form must reproduce the above
447 copyright notice, this list of conditions and the following disclaimer
448 in the documentation and/or other materials provided with the
451 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
452 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
453 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
454 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
455 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
456 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
457 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
458 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
459 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
460 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
461 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
463 You can contact the author at :
464 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
465 ****************************************************************** */
466 #ifndef BITSTREAM_H_MODULE
467 #define BITSTREAM_H_MODULE
469 #if defined (__cplusplus)
475 * This API consists of small unitary functions, which must be inlined for best performance.
476 * Since link-time-optimization is not available for all compilers,
477 * these functions are defined into a .h to be included.
481 /*=========================================
483 =========================================*/
484 #if defined(__BMI__) && defined(__GNUC__)
485 # include <immintrin.h> /* support for bextr (experimental) */
488 /*-********************************************
489 * bitStream decoding API (read backward)
490 **********************************************/
494 unsigned bitsConsumed
;
499 typedef enum { BITv07_DStream_unfinished
= 0,
500 BITv07_DStream_endOfBuffer
= 1,
501 BITv07_DStream_completed
= 2,
502 BITv07_DStream_overflow
= 3 } BITv07_DStream_status
; /* result of BITv07_reloadDStream() */
503 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
505 MEM_STATIC
size_t BITv07_initDStream(BITv07_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
);
506 MEM_STATIC
size_t BITv07_readBits(BITv07_DStream_t
* bitD
, unsigned nbBits
);
507 MEM_STATIC BITv07_DStream_status
BITv07_reloadDStream(BITv07_DStream_t
* bitD
);
508 MEM_STATIC
unsigned BITv07_endOfDStream(const BITv07_DStream_t
* bitD
);
511 /* Start by invoking BITv07_initDStream().
512 * A chunk of the bitStream is then stored into a local register.
513 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
514 * You can then retrieve bitFields stored into the local register, **in reverse order**.
515 * Local register is explicitly reloaded from memory by the BITv07_reloadDStream() method.
516 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BITv07_DStream_unfinished.
517 * Otherwise, it can be less than that, so proceed accordingly.
518 * Checking if DStream has reached its end can be performed with BITv07_endOfDStream().
522 /*-****************************************
524 ******************************************/
525 MEM_STATIC
size_t BITv07_readBitsFast(BITv07_DStream_t
* bitD
, unsigned nbBits
);
526 /* faster, but works only if nbBits >= 1 */
530 /*-**************************************************************
532 ****************************************************************/
533 MEM_STATIC
unsigned BITv07_highbit32 (register U32 val
)
535 # if defined(_MSC_VER) /* Visual */
537 _BitScanReverse ( &r
, val
);
539 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
540 return 31 - __builtin_clz (val
);
541 # else /* Software version */
542 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 };
549 return DeBruijnClz
[ (U32
) (v
* 0x07C4ACDDU
) >> 27];
555 /*-********************************************************
557 **********************************************************/
558 /*! BITv07_initDStream() :
559 * Initialize a BITv07_DStream_t.
560 * `bitD` : a pointer to an already allocated BITv07_DStream_t structure.
561 * `srcSize` must be the *exact* size of the bitStream, in bytes.
562 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
564 MEM_STATIC
size_t BITv07_initDStream(BITv07_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
)
566 if (srcSize
< 1) { memset(bitD
, 0, sizeof(*bitD
)); return ERROR(srcSize_wrong
); }
568 if (srcSize
>= sizeof(bitD
->bitContainer
)) { /* normal case */
569 bitD
->start
= (const char*)srcBuffer
;
570 bitD
->ptr
= (const char*)srcBuffer
+ srcSize
- sizeof(bitD
->bitContainer
);
571 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
572 { BYTE
const lastByte
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
573 bitD
->bitsConsumed
= lastByte
? 8 - BITv07_highbit32(lastByte
) : 0;
574 if (lastByte
== 0) return ERROR(GENERIC
); /* endMark not present */ }
576 bitD
->start
= (const char*)srcBuffer
;
577 bitD
->ptr
= bitD
->start
;
578 bitD
->bitContainer
= *(const BYTE
*)(bitD
->start
);
581 case 7: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[6]) << (sizeof(bitD
->bitContainer
)*8 - 16);
582 case 6: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[5]) << (sizeof(bitD
->bitContainer
)*8 - 24);
583 case 5: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[4]) << (sizeof(bitD
->bitContainer
)*8 - 32);
584 case 4: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[3]) << 24;
585 case 3: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[2]) << 16;
586 case 2: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[1]) << 8;
589 { BYTE
const lastByte
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
590 bitD
->bitsConsumed
= lastByte
? 8 - BITv07_highbit32(lastByte
) : 0;
591 if (lastByte
== 0) return ERROR(GENERIC
); /* endMark not present */ }
592 bitD
->bitsConsumed
+= (U32
)(sizeof(bitD
->bitContainer
) - srcSize
)*8;
599 /*! BITv07_lookBits() :
600 * Provides next n bits from local register.
601 * local register is not modified.
602 * On 32-bits, maxNbBits==24.
603 * On 64-bits, maxNbBits==56.
604 * @return : value extracted
606 MEM_STATIC
size_t BITv07_lookBits(const BITv07_DStream_t
* bitD
, U32 nbBits
)
608 U32
const bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
609 return ((bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> 1) >> ((bitMask
-nbBits
) & bitMask
);
612 /*! BITv07_lookBitsFast() :
613 * unsafe version; only works only if nbBits >= 1 */
614 MEM_STATIC
size_t BITv07_lookBitsFast(const BITv07_DStream_t
* bitD
, U32 nbBits
)
616 U32
const bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
617 return (bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> (((bitMask
+1)-nbBits
) & bitMask
);
620 MEM_STATIC
void BITv07_skipBits(BITv07_DStream_t
* bitD
, U32 nbBits
)
622 bitD
->bitsConsumed
+= nbBits
;
625 /*! BITv07_readBits() :
626 * Read (consume) next n bits from local register and update.
627 * Pay attention to not read more than nbBits contained into local register.
628 * @return : extracted value.
630 MEM_STATIC
size_t BITv07_readBits(BITv07_DStream_t
* bitD
, U32 nbBits
)
632 size_t const value
= BITv07_lookBits(bitD
, nbBits
);
633 BITv07_skipBits(bitD
, nbBits
);
637 /*! BITv07_readBitsFast() :
638 * unsafe version; only works only if nbBits >= 1 */
639 MEM_STATIC
size_t BITv07_readBitsFast(BITv07_DStream_t
* bitD
, U32 nbBits
)
641 size_t const value
= BITv07_lookBitsFast(bitD
, nbBits
);
642 BITv07_skipBits(bitD
, nbBits
);
646 /*! BITv07_reloadDStream() :
647 * Refill `BITv07_DStream_t` from src buffer previously defined (see BITv07_initDStream() ).
648 * This function is safe, it guarantees it will not read beyond src buffer.
649 * @return : status of `BITv07_DStream_t` internal register.
650 if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
651 MEM_STATIC BITv07_DStream_status
BITv07_reloadDStream(BITv07_DStream_t
* bitD
)
653 if (bitD
->bitsConsumed
> (sizeof(bitD
->bitContainer
)*8)) /* should not happen => corruption detected */
654 return BITv07_DStream_overflow
;
656 if (bitD
->ptr
>= bitD
->start
+ sizeof(bitD
->bitContainer
)) {
657 bitD
->ptr
-= bitD
->bitsConsumed
>> 3;
658 bitD
->bitsConsumed
&= 7;
659 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
660 return BITv07_DStream_unfinished
;
662 if (bitD
->ptr
== bitD
->start
) {
663 if (bitD
->bitsConsumed
< sizeof(bitD
->bitContainer
)*8) return BITv07_DStream_endOfBuffer
;
664 return BITv07_DStream_completed
;
666 { U32 nbBytes
= bitD
->bitsConsumed
>> 3;
667 BITv07_DStream_status result
= BITv07_DStream_unfinished
;
668 if (bitD
->ptr
- nbBytes
< bitD
->start
) {
669 nbBytes
= (U32
)(bitD
->ptr
- bitD
->start
); /* ptr > start */
670 result
= BITv07_DStream_endOfBuffer
;
672 bitD
->ptr
-= nbBytes
;
673 bitD
->bitsConsumed
-= nbBytes
*8;
674 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
); /* reminder : srcSize > sizeof(bitD) */
679 /*! BITv07_endOfDStream() :
680 * @return Tells if DStream has exactly reached its end (all bits consumed).
682 MEM_STATIC
unsigned BITv07_endOfDStream(const BITv07_DStream_t
* DStream
)
684 return ((DStream
->ptr
== DStream
->start
) && (DStream
->bitsConsumed
== sizeof(DStream
->bitContainer
)*8));
687 #if defined (__cplusplus)
691 #endif /* BITSTREAM_H_MODULE */
692 /* ******************************************************************
693 FSE : Finite State Entropy codec
694 Public Prototypes declaration
695 Copyright (C) 2013-2016, Yann Collet.
697 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
699 Redistribution and use in source and binary forms, with or without
700 modification, are permitted provided that the following conditions are
703 * Redistributions of source code must retain the above copyright
704 notice, this list of conditions and the following disclaimer.
705 * Redistributions in binary form must reproduce the above
706 copyright notice, this list of conditions and the following disclaimer
707 in the documentation and/or other materials provided with the
710 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
711 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
712 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
713 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
714 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
715 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
716 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
717 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
718 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
719 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
720 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
722 You can contact the author at :
723 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
724 ****************************************************************** */
728 #if defined (__cplusplus)
734 /*-****************************************
735 * FSE simple functions
736 ******************************************/
738 /*! FSEv07_decompress():
739 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
740 into already allocated destination buffer 'dst', of size 'dstCapacity'.
741 @return : size of regenerated data (<= maxDstSize),
742 or an error code, which can be tested using FSEv07_isError() .
744 ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!
745 Why ? : making this distinction requires a header.
746 Header management is intentionally delegated to the user layer, which can better manage special cases.
748 size_t FSEv07_decompress(void* dst
, size_t dstCapacity
,
749 const void* cSrc
, size_t cSrcSize
);
752 /* Error Management */
753 unsigned FSEv07_isError(size_t code
); /* tells if a return value is an error code */
754 const char* FSEv07_getErrorName(size_t code
); /* provides error code string (useful for debugging) */
757 /*-*****************************************
759 ******************************************/
761 FSEv07_decompress() does the following:
762 1. read normalized counters with readNCount()
763 2. build decoding table 'DTable' from normalized counters
764 3. decode the data stream using decoding table 'DTable'
766 The following API allows targeting specific sub-functions for advanced tasks.
767 For example, it's possible to compress several blocks using the same 'CTable',
768 or to save and provide normalized distribution using external method.
772 /* *** DECOMPRESSION *** */
774 /*! FSEv07_readNCount():
775 Read compactly saved 'normalizedCounter' from 'rBuffer'.
776 @return : size read from 'rBuffer',
777 or an errorCode, which can be tested using FSEv07_isError().
778 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
779 size_t FSEv07_readNCount (short* normalizedCounter
, unsigned* maxSymbolValuePtr
, unsigned* tableLogPtr
, const void* rBuffer
, size_t rBuffSize
);
781 /*! Constructor and Destructor of FSEv07_DTable.
782 Note that its size depends on 'tableLog' */
783 typedef unsigned FSEv07_DTable
; /* don't allocate that. It's just a way to be more restrictive than void* */
784 FSEv07_DTable
* FSEv07_createDTable(unsigned tableLog
);
785 void FSEv07_freeDTable(FSEv07_DTable
* dt
);
787 /*! FSEv07_buildDTable():
788 Builds 'dt', which must be already allocated, using FSEv07_createDTable().
789 return : 0, or an errorCode, which can be tested using FSEv07_isError() */
790 size_t FSEv07_buildDTable (FSEv07_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
);
792 /*! FSEv07_decompress_usingDTable():
793 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
794 into `dst` which must be already allocated.
795 @return : size of regenerated data (necessarily <= `dstCapacity`),
796 or an errorCode, which can be tested using FSEv07_isError() */
797 size_t FSEv07_decompress_usingDTable(void* dst
, size_t dstCapacity
, const void* cSrc
, size_t cSrcSize
, const FSEv07_DTable
* dt
);
802 (Note : these functions only decompress FSE-compressed blocks.
803 If block is uncompressed, use memcpy() instead
804 If block is a single repeated byte, use memset() instead )
806 The first step is to obtain the normalized frequencies of symbols.
807 This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().
808 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
809 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
810 or size the table to handle worst case situations (typically 256).
811 FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
812 The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.
813 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
814 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
816 The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.
817 This is performed by the function FSEv07_buildDTable().
818 The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().
819 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
821 `FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().
822 `cSrcSize` must be strictly correct, otherwise decompression will fail.
823 FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
824 If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)
828 #ifdef FSEv07_STATIC_LINKING_ONLY
831 /* *****************************************
833 *******************************************/
834 /* FSE buffer bounds */
835 #define FSEv07_NCOUNTBOUND 512
836 #define FSEv07_BLOCKBOUND(size) (size + (size>>7))
838 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
839 #define FSEv07_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
842 /* *****************************************
844 *******************************************/
845 size_t FSEv07_countFast(unsigned* count
, unsigned* maxSymbolValuePtr
, const void* src
, size_t srcSize
);
846 /**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
848 unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog
, size_t srcSize
, unsigned maxSymbolValue
, unsigned minus
);
849 /**< same as FSEv07_optimalTableLog(), which used `minus==2` */
851 size_t FSEv07_buildDTable_raw (FSEv07_DTable
* dt
, unsigned nbBits
);
852 /**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
854 size_t FSEv07_buildDTable_rle (FSEv07_DTable
* dt
, unsigned char symbolValue
);
855 /**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */
859 /* *****************************************
860 * FSE symbol decompression API
861 *******************************************/
865 const void* table
; /* precise table may vary, depending on U16 */
869 static void FSEv07_initDState(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
, const FSEv07_DTable
* dt
);
871 static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
);
875 Let's now decompose FSEv07_decompress_usingDTable() into its unitary components.
876 You will decode FSE-encoded symbols from the bitStream,
877 and also any other bitFields you put in, **in reverse order**.
879 You will need a few variables to track your bitStream. They are :
881 BITv07_DStream_t DStream; // Stream context
882 FSEv07_DState_t DState; // State context. Multiple ones are possible
883 FSEv07_DTable* DTablePtr; // Decoding table, provided by FSEv07_buildDTable()
885 The first thing to do is to init the bitStream.
886 errorCode = BITv07_initDStream(&DStream, srcBuffer, srcSize);
888 You should then retrieve your initial state(s)
889 (in reverse flushing order if you have several ones) :
890 errorCode = FSEv07_initDState(&DState, &DStream, DTablePtr);
892 You can then decode your data, symbol after symbol.
893 For information the maximum number of bits read by FSEv07_decodeSymbol() is 'tableLog'.
894 Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
895 unsigned char symbol = FSEv07_decodeSymbol(&DState, &DStream);
897 You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
898 Note : maximum allowed nbBits is 25, for 32-bits compatibility
899 size_t bitField = BITv07_readBits(&DStream, nbBits);
901 All above operations only read from local register (which size depends on size_t).
902 Refueling the register from memory is manually performed by the reload method.
903 endSignal = FSEv07_reloadDStream(&DStream);
905 BITv07_reloadDStream() result tells if there is still some more data to read from DStream.
906 BITv07_DStream_unfinished : there is still some data left into the DStream.
907 BITv07_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
908 BITv07_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
909 BITv07_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
911 When reaching end of buffer (BITv07_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
912 to properly detect the exact end of stream.
913 After each decoded symbol, check if DStream is fully consumed using this simple test :
914 BITv07_reloadDStream(&DStream) >= BITv07_DStream_completed
916 When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
917 Checking if DStream has reached its end is performed by :
918 BITv07_endOfDStream(&DStream);
919 Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
920 FSEv07_endOfDState(&DState);
924 /* *****************************************
926 *******************************************/
927 static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
);
928 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
931 /* ====== Decompression ====== */
936 } FSEv07_DTableHeader
; /* sizeof U32 */
940 unsigned short newState
;
941 unsigned char symbol
;
942 unsigned char nbBits
;
943 } FSEv07_decode_t
; /* size == U32 */
945 MEM_STATIC
void FSEv07_initDState(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
, const FSEv07_DTable
* dt
)
947 const void* ptr
= dt
;
948 const FSEv07_DTableHeader
* const DTableH
= (const FSEv07_DTableHeader
*)ptr
;
949 DStatePtr
->state
= BITv07_readBits(bitD
, DTableH
->tableLog
);
950 BITv07_reloadDStream(bitD
);
951 DStatePtr
->table
= dt
+ 1;
954 MEM_STATIC BYTE
FSEv07_peekSymbol(const FSEv07_DState_t
* DStatePtr
)
956 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
960 MEM_STATIC
void FSEv07_updateState(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
)
962 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
963 U32
const nbBits
= DInfo
.nbBits
;
964 size_t const lowBits
= BITv07_readBits(bitD
, nbBits
);
965 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
968 MEM_STATIC BYTE
FSEv07_decodeSymbol(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
)
970 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
971 U32
const nbBits
= DInfo
.nbBits
;
972 BYTE
const symbol
= DInfo
.symbol
;
973 size_t const lowBits
= BITv07_readBits(bitD
, nbBits
);
975 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
979 /*! FSEv07_decodeSymbolFast() :
980 unsafe, only works if no symbol has a probability > 50% */
981 MEM_STATIC BYTE
FSEv07_decodeSymbolFast(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
)
983 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
984 U32
const nbBits
= DInfo
.nbBits
;
985 BYTE
const symbol
= DInfo
.symbol
;
986 size_t const lowBits
= BITv07_readBitsFast(bitD
, nbBits
);
988 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
994 #ifndef FSEv07_COMMONDEFS_ONLY
996 /* **************************************************************
998 ****************************************************************/
1000 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1001 * Increasing memory usage improves compression ratio
1002 * Reduced memory usage can improve speed, due to cache effect
1003 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1004 #define FSEv07_MAX_MEMORY_USAGE 14
1005 #define FSEv07_DEFAULT_MEMORY_USAGE 13
1007 /*!FSEv07_MAX_SYMBOL_VALUE :
1008 * Maximum symbol value authorized.
1009 * Required for proper stack allocation */
1010 #define FSEv07_MAX_SYMBOL_VALUE 255
1013 /* **************************************************************
1014 * template functions type & suffix
1015 ****************************************************************/
1016 #define FSEv07_FUNCTION_TYPE BYTE
1017 #define FSEv07_FUNCTION_EXTENSION
1018 #define FSEv07_DECODE_TYPE FSEv07_decode_t
1021 #endif /* !FSEv07_COMMONDEFS_ONLY */
1024 /* ***************************************************************
1026 *****************************************************************/
1027 #define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2)
1028 #define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)
1029 #define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)
1030 #define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)
1031 #define FSEv07_MIN_TABLELOG 5
1033 #define FSEv07_TABLELOG_ABSOLUTE_MAX 15
1034 #if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX
1035 # error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"
1038 #define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
1041 #endif /* FSEv07_STATIC_LINKING_ONLY */
1044 #if defined (__cplusplus)
1048 #endif /* FSEv07_H */
1049 /* ******************************************************************
1050 Huffman coder, part of New Generation Entropy library
1052 Copyright (C) 2013-2016, Yann Collet.
1054 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1056 Redistribution and use in source and binary forms, with or without
1057 modification, are permitted provided that the following conditions are
1060 * Redistributions of source code must retain the above copyright
1061 notice, this list of conditions and the following disclaimer.
1062 * Redistributions in binary form must reproduce the above
1063 copyright notice, this list of conditions and the following disclaimer
1064 in the documentation and/or other materials provided with the
1067 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1068 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1069 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1070 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1071 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1072 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1073 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1074 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1075 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1076 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1077 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1079 You can contact the author at :
1080 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1081 ****************************************************************** */
1082 #ifndef HUFv07_H_298734234
1083 #define HUFv07_H_298734234
1085 #if defined (__cplusplus)
1091 /* *** simple functions *** */
1093 HUFv07_decompress() :
1094 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1095 into already allocated buffer 'dst', of minimum size 'dstSize'.
1096 `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
1097 Note : in contrast with FSE, HUFv07_decompress can regenerate
1098 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1099 because it knows size to regenerate.
1100 @return : size of regenerated data (== dstSize),
1101 or an error code, which can be tested using HUFv07_isError()
1103 size_t HUFv07_decompress(void* dst
, size_t dstSize
,
1104 const void* cSrc
, size_t cSrcSize
);
1107 /* ****************************************
1109 ******************************************/
1110 #define HUFv07_BLOCKSIZE_MAX (128 * 1024)
1112 /* Error Management */
1113 unsigned HUFv07_isError(size_t code
); /**< tells if a return value is an error code */
1114 const char* HUFv07_getErrorName(size_t code
); /**< provides error code string (useful for debugging) */
1117 /* *** Advanced function *** */
1120 #ifdef HUFv07_STATIC_LINKING_ONLY
1123 /* *** Constants *** */
1124 #define HUFv07_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */
1125 #define HUFv07_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */
1126 #define HUFv07_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */
1127 #define HUFv07_SYMBOLVALUE_MAX 255
1128 #if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX)
1129 # error "HUFv07_TABLELOG_MAX is too large !"
1133 /* ****************************************
1135 ******************************************/
1136 /* HUF buffer bounds */
1137 #define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1139 /* static allocation of HUF's DTable */
1140 typedef U32 HUFv07_DTable
;
1141 #define HUFv07_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog)))
1142 #define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1143 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
1144 #define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1145 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
1148 /* ****************************************
1149 * Advanced decompression functions
1150 ******************************************/
1151 size_t HUFv07_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< single-symbol decoder */
1152 size_t HUFv07_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< double-symbols decoder */
1154 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< decodes RLE and uncompressed */
1155 size_t HUFv07_decompress4X_hufOnly(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< considers RLE and uncompressed as errors */
1156 size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< single-symbol decoder */
1157 size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< double-symbols decoder */
1159 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
);
1160 size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< single-symbol decoder */
1161 size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< double-symbols decoder */
1164 /* ****************************************
1166 ******************************************/
1168 The following API allows targeting specific sub-functions for advanced tasks.
1169 For example, it's possible to compress several blocks using the same 'CTable',
1170 or to save and regenerate 'CTable' using external methods.
1172 /* FSEv07_count() : find it within "fse.h" */
1174 /*! HUFv07_readStats() :
1175 Read compact Huffman tree, saved by HUFv07_writeCTable().
1176 `huffWeight` is destination buffer.
1177 @return : size read from `src` , or an error Code .
1178 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */
1179 size_t HUFv07_readStats(BYTE
* huffWeight
, size_t hwSize
, U32
* rankStats
,
1180 U32
* nbSymbolsPtr
, U32
* tableLogPtr
,
1181 const void* src
, size_t srcSize
);
1185 HUFv07_decompress() does the following:
1186 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1187 2. build Huffman table from save, using HUFv07_readDTableXn()
1188 3. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable
1191 /** HUFv07_selectDecoder() :
1192 * Tells which decoder is likely to decode faster,
1193 * based on a set of pre-determined metrics.
1194 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
1195 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
1196 U32
HUFv07_selectDecoder (size_t dstSize
, size_t cSrcSize
);
1198 size_t HUFv07_readDTableX2 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
);
1199 size_t HUFv07_readDTableX4 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
);
1201 size_t HUFv07_decompress4X_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1202 size_t HUFv07_decompress4X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1203 size_t HUFv07_decompress4X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1206 /* single stream variants */
1207 size_t HUFv07_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* single-symbol decoder */
1208 size_t HUFv07_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* double-symbol decoder */
1210 size_t HUFv07_decompress1X_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1211 size_t HUFv07_decompress1X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1212 size_t HUFv07_decompress1X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1215 #endif /* HUFv07_STATIC_LINKING_ONLY */
1218 #if defined (__cplusplus)
1222 #endif /* HUFv07_H_298734234 */
1224 Common functions of New Generation Entropy library
1225 Copyright (C) 2016, Yann Collet.
1227 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1229 Redistribution and use in source and binary forms, with or without
1230 modification, are permitted provided that the following conditions are
1233 * Redistributions of source code must retain the above copyright
1234 notice, this list of conditions and the following disclaimer.
1235 * Redistributions in binary form must reproduce the above
1236 copyright notice, this list of conditions and the following disclaimer
1237 in the documentation and/or other materials provided with the
1240 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1241 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1242 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1243 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1244 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1245 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1246 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1247 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1248 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1249 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1250 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1252 You can contact the author at :
1253 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1254 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1255 *************************************************************************** */
1259 /*-****************************************
1260 * FSE Error Management
1261 ******************************************/
1262 unsigned FSEv07_isError(size_t code
) { return ERR_isError(code
); }
1264 const char* FSEv07_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1267 /* **************************************************************
1268 * HUF Error Management
1269 ****************************************************************/
1270 unsigned HUFv07_isError(size_t code
) { return ERR_isError(code
); }
1272 const char* HUFv07_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1275 /*-**************************************************************
1276 * FSE NCount encoding-decoding
1277 ****************************************************************/
1278 static short FSEv07_abs(short a
) { return (short)(a
<0 ? -a
: a
); }
1280 size_t FSEv07_readNCount (short* normalizedCounter
, unsigned* maxSVPtr
, unsigned* tableLogPtr
,
1281 const void* headerBuffer
, size_t hbSize
)
1283 const BYTE
* const istart
= (const BYTE
*) headerBuffer
;
1284 const BYTE
* const iend
= istart
+ hbSize
;
1285 const BYTE
* ip
= istart
;
1291 unsigned charnum
= 0;
1294 if (hbSize
< 4) return ERROR(srcSize_wrong
);
1295 bitStream
= MEM_readLE32(ip
);
1296 nbBits
= (bitStream
& 0xF) + FSEv07_MIN_TABLELOG
; /* extract tableLog */
1297 if (nbBits
> FSEv07_TABLELOG_ABSOLUTE_MAX
) return ERROR(tableLog_tooLarge
);
1300 *tableLogPtr
= nbBits
;
1301 remaining
= (1<<nbBits
)+1;
1302 threshold
= 1<<nbBits
;
1305 while ((remaining
>1) && (charnum
<=*maxSVPtr
)) {
1307 unsigned n0
= charnum
;
1308 while ((bitStream
& 0xFFFF) == 0xFFFF) {
1312 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1317 while ((bitStream
& 3) == 3) {
1322 n0
+= bitStream
& 3;
1324 if (n0
> *maxSVPtr
) return ERROR(maxSymbolValue_tooSmall
);
1325 while (charnum
< n0
) normalizedCounter
[charnum
++] = 0;
1326 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1329 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1334 { short const max
= (short)((2*threshold
-1)-remaining
);
1337 if ((bitStream
& (threshold
-1)) < (U32
)max
) {
1338 count
= (short)(bitStream
& (threshold
-1));
1339 bitCount
+= nbBits
-1;
1341 count
= (short)(bitStream
& (2*threshold
-1));
1342 if (count
>= threshold
) count
-= max
;
1346 count
--; /* extra accuracy */
1347 remaining
-= FSEv07_abs(count
);
1348 normalizedCounter
[charnum
++] = count
;
1350 while (remaining
< threshold
) {
1355 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1359 bitCount
-= (int)(8 * (iend
- 4 - ip
));
1362 bitStream
= MEM_readLE32(ip
) >> (bitCount
& 31);
1363 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1364 if (remaining
!= 1) return ERROR(GENERIC
);
1365 *maxSVPtr
= charnum
-1;
1367 ip
+= (bitCount
+7)>>3;
1368 if ((size_t)(ip
-istart
) > hbSize
) return ERROR(srcSize_wrong
);
1373 /*! HUFv07_readStats() :
1374 Read compact Huffman tree, saved by HUFv07_writeCTable().
1375 `huffWeight` is destination buffer.
1376 @return : size read from `src` , or an error Code .
1377 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() .
1379 size_t HUFv07_readStats(BYTE
* huffWeight
, size_t hwSize
, U32
* rankStats
,
1380 U32
* nbSymbolsPtr
, U32
* tableLogPtr
,
1381 const void* src
, size_t srcSize
)
1384 const BYTE
* ip
= (const BYTE
*) src
;
1388 if (!srcSize
) return ERROR(srcSize_wrong
);
1390 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1392 if (iSize
>= 128) { /* special header */
1393 if (iSize
>= (242)) { /* RLE */
1394 static U32 l
[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1395 oSize
= l
[iSize
-242];
1396 memset(huffWeight
, 1, hwSize
);
1399 else { /* Incompressible */
1400 oSize
= iSize
- 127;
1401 iSize
= ((oSize
+1)/2);
1402 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1403 if (oSize
>= hwSize
) return ERROR(corruption_detected
);
1406 for (n
=0; n
<oSize
; n
+=2) {
1407 huffWeight
[n
] = ip
[n
/2] >> 4;
1408 huffWeight
[n
+1] = ip
[n
/2] & 15;
1410 else { /* header compressed with FSE (normal case) */
1411 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1412 oSize
= FSEv07_decompress(huffWeight
, hwSize
-1, ip
+1, iSize
); /* max (hwSize-1) values decoded, as last one is implied */
1413 if (FSEv07_isError(oSize
)) return oSize
;
1416 /* collect weight stats */
1417 memset(rankStats
, 0, (HUFv07_TABLELOG_ABSOLUTEMAX
+ 1) * sizeof(U32
));
1419 { U32 n
; for (n
=0; n
<oSize
; n
++) {
1420 if (huffWeight
[n
] >= HUFv07_TABLELOG_ABSOLUTEMAX
) return ERROR(corruption_detected
);
1421 rankStats
[huffWeight
[n
]]++;
1422 weightTotal
+= (1 << huffWeight
[n
]) >> 1;
1424 if (weightTotal
== 0) return ERROR(corruption_detected
);
1426 /* get last non-null symbol weight (implied, total must be 2^n) */
1427 { U32
const tableLog
= BITv07_highbit32(weightTotal
) + 1;
1428 if (tableLog
> HUFv07_TABLELOG_ABSOLUTEMAX
) return ERROR(corruption_detected
);
1429 *tableLogPtr
= tableLog
;
1430 /* determine last weight */
1431 { U32
const total
= 1 << tableLog
;
1432 U32
const rest
= total
- weightTotal
;
1433 U32
const verif
= 1 << BITv07_highbit32(rest
);
1434 U32
const lastWeight
= BITv07_highbit32(rest
) + 1;
1435 if (verif
!= rest
) return ERROR(corruption_detected
); /* last value must be a clean power of 2 */
1436 huffWeight
[oSize
] = (BYTE
)lastWeight
;
1437 rankStats
[lastWeight
]++;
1440 /* check tree construction validity */
1441 if ((rankStats
[1] < 2) || (rankStats
[1] & 1)) return ERROR(corruption_detected
); /* by construction : at least 2 elts of rank 1, must be even */
1444 *nbSymbolsPtr
= (U32
)(oSize
+1);
1447 /* ******************************************************************
1448 FSE : Finite State Entropy decoder
1449 Copyright (C) 2013-2015, Yann Collet.
1451 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1453 Redistribution and use in source and binary forms, with or without
1454 modification, are permitted provided that the following conditions are
1457 * Redistributions of source code must retain the above copyright
1458 notice, this list of conditions and the following disclaimer.
1459 * Redistributions in binary form must reproduce the above
1460 copyright notice, this list of conditions and the following disclaimer
1461 in the documentation and/or other materials provided with the
1464 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1465 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1466 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1467 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1468 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1469 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1470 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1471 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1472 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1473 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1474 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1476 You can contact the author at :
1477 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1478 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1479 ****************************************************************** */
1482 /* **************************************************************
1483 * Compiler specifics
1484 ****************************************************************/
1485 #ifdef _MSC_VER /* Visual Studio */
1486 # define FORCE_INLINE static __forceinline
1487 # include <intrin.h> /* For Visual 2005 */
1488 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1489 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1491 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1493 # define FORCE_INLINE static inline __attribute__((always_inline))
1495 # define FORCE_INLINE static inline
1498 # define FORCE_INLINE static
1499 # endif /* __STDC_VERSION__ */
1503 /* **************************************************************
1505 ****************************************************************/
1506 #define FSEv07_isError ERR_isError
1507 #define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1510 /* **************************************************************
1512 ****************************************************************/
1513 typedef U32 DTable_max_t
[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG
)];
1516 /* **************************************************************
1518 ****************************************************************/
1520 designed to be included
1521 for type-specific functions (template emulation in C)
1522 Objective is to write these functions only once, for improved maintenance
1526 #ifndef FSEv07_FUNCTION_EXTENSION
1527 # error "FSEv07_FUNCTION_EXTENSION must be defined"
1529 #ifndef FSEv07_FUNCTION_TYPE
1530 # error "FSEv07_FUNCTION_TYPE must be defined"
1533 /* Function names */
1534 #define FSEv07_CAT(X,Y) X##Y
1535 #define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y)
1536 #define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y)
1539 /* Function templates */
1540 FSEv07_DTable
* FSEv07_createDTable (unsigned tableLog
)
1542 if (tableLog
> FSEv07_TABLELOG_ABSOLUTE_MAX
) tableLog
= FSEv07_TABLELOG_ABSOLUTE_MAX
;
1543 return (FSEv07_DTable
*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog
) * sizeof (U32
) );
1546 void FSEv07_freeDTable (FSEv07_DTable
* dt
)
1551 size_t FSEv07_buildDTable(FSEv07_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
)
1553 void* const tdPtr
= dt
+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1554 FSEv07_DECODE_TYPE
* const tableDecode
= (FSEv07_DECODE_TYPE
*) (tdPtr
);
1555 U16 symbolNext
[FSEv07_MAX_SYMBOL_VALUE
+1];
1557 U32
const maxSV1
= maxSymbolValue
+ 1;
1558 U32
const tableSize
= 1 << tableLog
;
1559 U32 highThreshold
= tableSize
-1;
1562 if (maxSymbolValue
> FSEv07_MAX_SYMBOL_VALUE
) return ERROR(maxSymbolValue_tooLarge
);
1563 if (tableLog
> FSEv07_MAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
1565 /* Init, lay down lowprob symbols */
1566 { FSEv07_DTableHeader DTableH
;
1567 DTableH
.tableLog
= (U16
)tableLog
;
1568 DTableH
.fastMode
= 1;
1569 { S16
const largeLimit
= (S16
)(1 << (tableLog
-1));
1571 for (s
=0; s
<maxSV1
; s
++) {
1572 if (normalizedCounter
[s
]==-1) {
1573 tableDecode
[highThreshold
--].symbol
= (FSEv07_FUNCTION_TYPE
)s
;
1576 if (normalizedCounter
[s
] >= largeLimit
) DTableH
.fastMode
=0;
1577 symbolNext
[s
] = normalizedCounter
[s
];
1579 memcpy(dt
, &DTableH
, sizeof(DTableH
));
1582 /* Spread symbols */
1583 { U32
const tableMask
= tableSize
-1;
1584 U32
const step
= FSEv07_TABLESTEP(tableSize
);
1585 U32 s
, position
= 0;
1586 for (s
=0; s
<maxSV1
; s
++) {
1588 for (i
=0; i
<normalizedCounter
[s
]; i
++) {
1589 tableDecode
[position
].symbol
= (FSEv07_FUNCTION_TYPE
)s
;
1590 position
= (position
+ step
) & tableMask
;
1591 while (position
> highThreshold
) position
= (position
+ step
) & tableMask
; /* lowprob area */
1594 if (position
!=0) return ERROR(GENERIC
); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1597 /* Build Decoding table */
1599 for (u
=0; u
<tableSize
; u
++) {
1600 FSEv07_FUNCTION_TYPE
const symbol
= (FSEv07_FUNCTION_TYPE
)(tableDecode
[u
].symbol
);
1601 U16 nextState
= symbolNext
[symbol
]++;
1602 tableDecode
[u
].nbBits
= (BYTE
) (tableLog
- BITv07_highbit32 ((U32
)nextState
) );
1603 tableDecode
[u
].newState
= (U16
) ( (nextState
<< tableDecode
[u
].nbBits
) - tableSize
);
1611 #ifndef FSEv07_COMMONDEFS_ONLY
1613 /*-*******************************************************
1614 * Decompression (Byte symbols)
1615 *********************************************************/
1616 size_t FSEv07_buildDTable_rle (FSEv07_DTable
* dt
, BYTE symbolValue
)
1619 FSEv07_DTableHeader
* const DTableH
= (FSEv07_DTableHeader
*)ptr
;
1620 void* dPtr
= dt
+ 1;
1621 FSEv07_decode_t
* const cell
= (FSEv07_decode_t
*)dPtr
;
1623 DTableH
->tableLog
= 0;
1624 DTableH
->fastMode
= 0;
1627 cell
->symbol
= symbolValue
;
1634 size_t FSEv07_buildDTable_raw (FSEv07_DTable
* dt
, unsigned nbBits
)
1637 FSEv07_DTableHeader
* const DTableH
= (FSEv07_DTableHeader
*)ptr
;
1638 void* dPtr
= dt
+ 1;
1639 FSEv07_decode_t
* const dinfo
= (FSEv07_decode_t
*)dPtr
;
1640 const unsigned tableSize
= 1 << nbBits
;
1641 const unsigned tableMask
= tableSize
- 1;
1642 const unsigned maxSV1
= tableMask
+1;
1646 if (nbBits
< 1) return ERROR(GENERIC
); /* min size */
1648 /* Build Decoding Table */
1649 DTableH
->tableLog
= (U16
)nbBits
;
1650 DTableH
->fastMode
= 1;
1651 for (s
=0; s
<maxSV1
; s
++) {
1652 dinfo
[s
].newState
= 0;
1653 dinfo
[s
].symbol
= (BYTE
)s
;
1654 dinfo
[s
].nbBits
= (BYTE
)nbBits
;
1660 FORCE_INLINE
size_t FSEv07_decompress_usingDTable_generic(
1661 void* dst
, size_t maxDstSize
,
1662 const void* cSrc
, size_t cSrcSize
,
1663 const FSEv07_DTable
* dt
, const unsigned fast
)
1665 BYTE
* const ostart
= (BYTE
*) dst
;
1667 BYTE
* const omax
= op
+ maxDstSize
;
1668 BYTE
* const olimit
= omax
-3;
1670 BITv07_DStream_t bitD
;
1671 FSEv07_DState_t state1
;
1672 FSEv07_DState_t state2
;
1675 { size_t const errorCode
= BITv07_initDStream(&bitD
, cSrc
, cSrcSize
); /* replaced last arg by maxCompressed Size */
1676 if (FSEv07_isError(errorCode
)) return errorCode
; }
1678 FSEv07_initDState(&state1
, &bitD
, dt
);
1679 FSEv07_initDState(&state2
, &bitD
, dt
);
1681 #define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1683 /* 4 symbols per loop */
1684 for ( ; (BITv07_reloadDStream(&bitD
)==BITv07_DStream_unfinished
) && (op
<olimit
) ; op
+=4) {
1685 op
[0] = FSEv07_GETSYMBOL(&state1
);
1687 if (FSEv07_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1688 BITv07_reloadDStream(&bitD
);
1690 op
[1] = FSEv07_GETSYMBOL(&state2
);
1692 if (FSEv07_MAX_TABLELOG
*4+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1693 { if (BITv07_reloadDStream(&bitD
) > BITv07_DStream_unfinished
) { op
+=2; break; } }
1695 op
[2] = FSEv07_GETSYMBOL(&state1
);
1697 if (FSEv07_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1698 BITv07_reloadDStream(&bitD
);
1700 op
[3] = FSEv07_GETSYMBOL(&state2
);
1704 /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1706 if (op
>(omax
-2)) return ERROR(dstSize_tooSmall
);
1708 *op
++ = FSEv07_GETSYMBOL(&state1
);
1710 if (BITv07_reloadDStream(&bitD
)==BITv07_DStream_overflow
) {
1711 *op
++ = FSEv07_GETSYMBOL(&state2
);
1715 if (op
>(omax
-2)) return ERROR(dstSize_tooSmall
);
1717 *op
++ = FSEv07_GETSYMBOL(&state2
);
1719 if (BITv07_reloadDStream(&bitD
)==BITv07_DStream_overflow
) {
1720 *op
++ = FSEv07_GETSYMBOL(&state1
);
1728 size_t FSEv07_decompress_usingDTable(void* dst
, size_t originalSize
,
1729 const void* cSrc
, size_t cSrcSize
,
1730 const FSEv07_DTable
* dt
)
1732 const void* ptr
= dt
;
1733 const FSEv07_DTableHeader
* DTableH
= (const FSEv07_DTableHeader
*)ptr
;
1734 const U32 fastMode
= DTableH
->fastMode
;
1736 /* select fast mode (static) */
1737 if (fastMode
) return FSEv07_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 1);
1738 return FSEv07_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 0);
1742 size_t FSEv07_decompress(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
)
1744 const BYTE
* const istart
= (const BYTE
*)cSrc
;
1745 const BYTE
* ip
= istart
;
1746 short counting
[FSEv07_MAX_SYMBOL_VALUE
+1];
1747 DTable_max_t dt
; /* Static analyzer seems unable to understand this table will be properly initialized later */
1749 unsigned maxSymbolValue
= FSEv07_MAX_SYMBOL_VALUE
;
1751 if (cSrcSize
<2) return ERROR(srcSize_wrong
); /* too small input size */
1753 /* normal FSE decoding mode */
1754 { size_t const NCountLength
= FSEv07_readNCount (counting
, &maxSymbolValue
, &tableLog
, istart
, cSrcSize
);
1755 if (FSEv07_isError(NCountLength
)) return NCountLength
;
1756 if (NCountLength
>= cSrcSize
) return ERROR(srcSize_wrong
); /* too small input size */
1758 cSrcSize
-= NCountLength
;
1761 { size_t const errorCode
= FSEv07_buildDTable (dt
, counting
, maxSymbolValue
, tableLog
);
1762 if (FSEv07_isError(errorCode
)) return errorCode
; }
1764 return FSEv07_decompress_usingDTable (dst
, maxDstSize
, ip
, cSrcSize
, dt
); /* always return, even if it is an error code */
1769 #endif /* FSEv07_COMMONDEFS_ONLY */
1771 /* ******************************************************************
1772 Huffman decoder, part of New Generation Entropy library
1773 Copyright (C) 2013-2016, Yann Collet.
1775 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1777 Redistribution and use in source and binary forms, with or without
1778 modification, are permitted provided that the following conditions are
1781 * Redistributions of source code must retain the above copyright
1782 notice, this list of conditions and the following disclaimer.
1783 * Redistributions in binary form must reproduce the above
1784 copyright notice, this list of conditions and the following disclaimer
1785 in the documentation and/or other materials provided with the
1788 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1789 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1790 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1791 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1792 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1793 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1794 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1795 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1796 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1797 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1798 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1800 You can contact the author at :
1801 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1802 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1803 ****************************************************************** */
1805 /* **************************************************************
1806 * Compiler specifics
1807 ****************************************************************/
1808 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1809 /* inline is defined */
1810 #elif defined(_MSC_VER)
1811 # define inline __inline
1813 # define inline /* disable inline */
1817 #ifdef _MSC_VER /* Visual Studio */
1818 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1823 /* **************************************************************
1825 ****************************************************************/
1826 #define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1829 /*-***************************/
1830 /* generic DTableDesc */
1831 /*-***************************/
1833 typedef struct { BYTE maxTableLog
; BYTE tableType
; BYTE tableLog
; BYTE reserved
; } DTableDesc
;
1835 static DTableDesc
HUFv07_getDTableDesc(const HUFv07_DTable
* table
)
1838 memcpy(&dtd
, table
, sizeof(dtd
));
1843 /*-***************************/
1844 /* single-symbol decoding */
1845 /*-***************************/
1847 typedef struct { BYTE byte
; BYTE nbBits
; } HUFv07_DEltX2
; /* single-symbol decoding */
1849 size_t HUFv07_readDTableX2 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
)
1851 BYTE huffWeight
[HUFv07_SYMBOLVALUE_MAX
+ 1];
1852 U32 rankVal
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1]; /* large enough for values from 0 to 16 */
1856 void* const dtPtr
= DTable
+ 1;
1857 HUFv07_DEltX2
* const dt
= (HUFv07_DEltX2
*)dtPtr
;
1859 HUFv07_STATIC_ASSERT(sizeof(DTableDesc
) == sizeof(HUFv07_DTable
));
1860 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1862 iSize
= HUFv07_readStats(huffWeight
, HUFv07_SYMBOLVALUE_MAX
+ 1, rankVal
, &nbSymbols
, &tableLog
, src
, srcSize
);
1863 if (HUFv07_isError(iSize
)) return iSize
;
1866 { DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
1867 if (tableLog
> (U32
)(dtd
.maxTableLog
+1)) return ERROR(tableLog_tooLarge
); /* DTable too small, huffman tree cannot fit in */
1869 dtd
.tableLog
= (BYTE
)tableLog
;
1870 memcpy(DTable
, &dtd
, sizeof(dtd
));
1874 { U32 n
, nextRankStart
= 0;
1875 for (n
=1; n
<tableLog
+1; n
++) {
1876 U32 current
= nextRankStart
;
1877 nextRankStart
+= (rankVal
[n
] << (n
-1));
1878 rankVal
[n
] = current
;
1883 for (n
=0; n
<nbSymbols
; n
++) {
1884 U32
const w
= huffWeight
[n
];
1885 U32
const length
= (1 << w
) >> 1;
1888 D
.byte
= (BYTE
)n
; D
.nbBits
= (BYTE
)(tableLog
+ 1 - w
);
1889 for (i
= rankVal
[w
]; i
< rankVal
[w
] + length
; i
++)
1891 rankVal
[w
] += length
;
1898 static BYTE
HUFv07_decodeSymbolX2(BITv07_DStream_t
* Dstream
, const HUFv07_DEltX2
* dt
, const U32 dtLog
)
1900 size_t const val
= BITv07_lookBitsFast(Dstream
, dtLog
); /* note : dtLog >= 1 */
1901 BYTE
const c
= dt
[val
].byte
;
1902 BITv07_skipBits(Dstream
, dt
[val
].nbBits
);
1906 #define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1907 *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1909 #define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1910 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1911 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1913 #define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1915 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1917 static inline size_t HUFv07_decodeStreamX2(BYTE
* p
, BITv07_DStream_t
* const bitDPtr
, BYTE
* const pEnd
, const HUFv07_DEltX2
* const dt
, const U32 dtLog
)
1919 BYTE
* const pStart
= p
;
1921 /* up to 4 symbols at a time */
1922 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
<= pEnd
-4)) {
1923 HUFv07_DECODE_SYMBOLX2_2(p
, bitDPtr
);
1924 HUFv07_DECODE_SYMBOLX2_1(p
, bitDPtr
);
1925 HUFv07_DECODE_SYMBOLX2_2(p
, bitDPtr
);
1926 HUFv07_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1929 /* closer to the end */
1930 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
< pEnd
))
1931 HUFv07_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1933 /* no more data to retrieve from bitstream, hence no need to reload */
1935 HUFv07_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1940 static size_t HUFv07_decompress1X2_usingDTable_internal(
1941 void* dst
, size_t dstSize
,
1942 const void* cSrc
, size_t cSrcSize
,
1943 const HUFv07_DTable
* DTable
)
1945 BYTE
* op
= (BYTE
*)dst
;
1946 BYTE
* const oend
= op
+ dstSize
;
1947 const void* dtPtr
= DTable
+ 1;
1948 const HUFv07_DEltX2
* const dt
= (const HUFv07_DEltX2
*)dtPtr
;
1949 BITv07_DStream_t bitD
;
1950 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
1951 U32
const dtLog
= dtd
.tableLog
;
1953 { size_t const errorCode
= BITv07_initDStream(&bitD
, cSrc
, cSrcSize
);
1954 if (HUFv07_isError(errorCode
)) return errorCode
; }
1956 HUFv07_decodeStreamX2(op
, &bitD
, oend
, dt
, dtLog
);
1959 if (!BITv07_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
1964 size_t HUFv07_decompress1X2_usingDTable(
1965 void* dst
, size_t dstSize
,
1966 const void* cSrc
, size_t cSrcSize
,
1967 const HUFv07_DTable
* DTable
)
1969 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
1970 if (dtd
.tableType
!= 0) return ERROR(GENERIC
);
1971 return HUFv07_decompress1X2_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
1974 size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable
* DCtx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
1976 const BYTE
* ip
= (const BYTE
*) cSrc
;
1978 size_t const hSize
= HUFv07_readDTableX2 (DCtx
, cSrc
, cSrcSize
);
1979 if (HUFv07_isError(hSize
)) return hSize
;
1980 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
1981 ip
+= hSize
; cSrcSize
-= hSize
;
1983 return HUFv07_decompress1X2_usingDTable_internal (dst
, dstSize
, ip
, cSrcSize
, DCtx
);
1986 size_t HUFv07_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
1988 HUFv07_CREATE_STATIC_DTABLEX2(DTable
, HUFv07_TABLELOG_MAX
);
1989 return HUFv07_decompress1X2_DCtx (DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
1993 static size_t HUFv07_decompress4X2_usingDTable_internal(
1994 void* dst
, size_t dstSize
,
1995 const void* cSrc
, size_t cSrcSize
,
1996 const HUFv07_DTable
* DTable
)
1999 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2001 { const BYTE
* const istart
= (const BYTE
*) cSrc
;
2002 BYTE
* const ostart
= (BYTE
*) dst
;
2003 BYTE
* const oend
= ostart
+ dstSize
;
2004 const void* const dtPtr
= DTable
+ 1;
2005 const HUFv07_DEltX2
* const dt
= (const HUFv07_DEltX2
*)dtPtr
;
2008 BITv07_DStream_t bitD1
;
2009 BITv07_DStream_t bitD2
;
2010 BITv07_DStream_t bitD3
;
2011 BITv07_DStream_t bitD4
;
2012 size_t const length1
= MEM_readLE16(istart
);
2013 size_t const length2
= MEM_readLE16(istart
+2);
2014 size_t const length3
= MEM_readLE16(istart
+4);
2015 size_t const length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2016 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2017 const BYTE
* const istart2
= istart1
+ length1
;
2018 const BYTE
* const istart3
= istart2
+ length2
;
2019 const BYTE
* const istart4
= istart3
+ length3
;
2020 const size_t segmentSize
= (dstSize
+3) / 4;
2021 BYTE
* const opStart2
= ostart
+ segmentSize
;
2022 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2023 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2025 BYTE
* op2
= opStart2
;
2026 BYTE
* op3
= opStart3
;
2027 BYTE
* op4
= opStart4
;
2029 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2030 U32
const dtLog
= dtd
.tableLog
;
2032 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2033 { size_t const errorCode
= BITv07_initDStream(&bitD1
, istart1
, length1
);
2034 if (HUFv07_isError(errorCode
)) return errorCode
; }
2035 { size_t const errorCode
= BITv07_initDStream(&bitD2
, istart2
, length2
);
2036 if (HUFv07_isError(errorCode
)) return errorCode
; }
2037 { size_t const errorCode
= BITv07_initDStream(&bitD3
, istart3
, length3
);
2038 if (HUFv07_isError(errorCode
)) return errorCode
; }
2039 { size_t const errorCode
= BITv07_initDStream(&bitD4
, istart4
, length4
);
2040 if (HUFv07_isError(errorCode
)) return errorCode
; }
2042 /* 16-32 symbols per loop (4-8 symbols per stream) */
2043 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2044 for ( ; (endSignal
==BITv07_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2045 HUFv07_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2046 HUFv07_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2047 HUFv07_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2048 HUFv07_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2049 HUFv07_DECODE_SYMBOLX2_1(op1
, &bitD1
);
2050 HUFv07_DECODE_SYMBOLX2_1(op2
, &bitD2
);
2051 HUFv07_DECODE_SYMBOLX2_1(op3
, &bitD3
);
2052 HUFv07_DECODE_SYMBOLX2_1(op4
, &bitD4
);
2053 HUFv07_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2054 HUFv07_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2055 HUFv07_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2056 HUFv07_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2057 HUFv07_DECODE_SYMBOLX2_0(op1
, &bitD1
);
2058 HUFv07_DECODE_SYMBOLX2_0(op2
, &bitD2
);
2059 HUFv07_DECODE_SYMBOLX2_0(op3
, &bitD3
);
2060 HUFv07_DECODE_SYMBOLX2_0(op4
, &bitD4
);
2061 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2064 /* check corruption */
2065 if (op1
> opStart2
) return ERROR(corruption_detected
);
2066 if (op2
> opStart3
) return ERROR(corruption_detected
);
2067 if (op3
> opStart4
) return ERROR(corruption_detected
);
2068 /* note : op4 supposed already verified within main loop */
2070 /* finish bitStreams one by one */
2071 HUFv07_decodeStreamX2(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2072 HUFv07_decodeStreamX2(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2073 HUFv07_decodeStreamX2(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2074 HUFv07_decodeStreamX2(op4
, &bitD4
, oend
, dt
, dtLog
);
2077 endSignal
= BITv07_endOfDStream(&bitD1
) & BITv07_endOfDStream(&bitD2
) & BITv07_endOfDStream(&bitD3
) & BITv07_endOfDStream(&bitD4
);
2078 if (!endSignal
) return ERROR(corruption_detected
);
2086 size_t HUFv07_decompress4X2_usingDTable(
2087 void* dst
, size_t dstSize
,
2088 const void* cSrc
, size_t cSrcSize
,
2089 const HUFv07_DTable
* DTable
)
2091 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2092 if (dtd
.tableType
!= 0) return ERROR(GENERIC
);
2093 return HUFv07_decompress4X2_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
2097 size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2099 const BYTE
* ip
= (const BYTE
*) cSrc
;
2101 size_t const hSize
= HUFv07_readDTableX2 (dctx
, cSrc
, cSrcSize
);
2102 if (HUFv07_isError(hSize
)) return hSize
;
2103 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2104 ip
+= hSize
; cSrcSize
-= hSize
;
2106 return HUFv07_decompress4X2_usingDTable_internal (dst
, dstSize
, ip
, cSrcSize
, dctx
);
2109 size_t HUFv07_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2111 HUFv07_CREATE_STATIC_DTABLEX2(DTable
, HUFv07_TABLELOG_MAX
);
2112 return HUFv07_decompress4X2_DCtx(DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
2116 /* *************************/
2117 /* double-symbols decoding */
2118 /* *************************/
2119 typedef struct { U16 sequence
; BYTE nbBits
; BYTE length
; } HUFv07_DEltX4
; /* double-symbols decoding */
2121 typedef struct { BYTE symbol
; BYTE weight
; } sortedSymbol_t
;
2123 static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4
* DTable
, U32 sizeLog
, const U32 consumed
,
2124 const U32
* rankValOrigin
, const int minWeight
,
2125 const sortedSymbol_t
* sortedSymbols
, const U32 sortedListSize
,
2126 U32 nbBitsBaseline
, U16 baseSeq
)
2129 U32 rankVal
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1];
2131 /* get pre-calculated rankVal */
2132 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2134 /* fill skipped values */
2136 U32 i
, skipSize
= rankVal
[minWeight
];
2137 MEM_writeLE16(&(DElt
.sequence
), baseSeq
);
2138 DElt
.nbBits
= (BYTE
)(consumed
);
2140 for (i
= 0; i
< skipSize
; i
++)
2145 { U32 s
; for (s
=0; s
<sortedListSize
; s
++) { /* note : sortedSymbols already skipped */
2146 const U32 symbol
= sortedSymbols
[s
].symbol
;
2147 const U32 weight
= sortedSymbols
[s
].weight
;
2148 const U32 nbBits
= nbBitsBaseline
- weight
;
2149 const U32 length
= 1 << (sizeLog
-nbBits
);
2150 const U32 start
= rankVal
[weight
];
2152 const U32 end
= start
+ length
;
2154 MEM_writeLE16(&(DElt
.sequence
), (U16
)(baseSeq
+ (symbol
<< 8)));
2155 DElt
.nbBits
= (BYTE
)(nbBits
+ consumed
);
2157 do { DTable
[i
++] = DElt
; } while (i
<end
); /* since length >= 1 */
2159 rankVal
[weight
] += length
;
2163 typedef U32 rankVal_t
[HUFv07_TABLELOG_ABSOLUTEMAX
][HUFv07_TABLELOG_ABSOLUTEMAX
+ 1];
2165 static void HUFv07_fillDTableX4(HUFv07_DEltX4
* DTable
, const U32 targetLog
,
2166 const sortedSymbol_t
* sortedList
, const U32 sortedListSize
,
2167 const U32
* rankStart
, rankVal_t rankValOrigin
, const U32 maxWeight
,
2168 const U32 nbBitsBaseline
)
2170 U32 rankVal
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1];
2171 const int scaleLog
= nbBitsBaseline
- targetLog
; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2172 const U32 minBits
= nbBitsBaseline
- maxWeight
;
2175 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2178 for (s
=0; s
<sortedListSize
; s
++) {
2179 const U16 symbol
= sortedList
[s
].symbol
;
2180 const U32 weight
= sortedList
[s
].weight
;
2181 const U32 nbBits
= nbBitsBaseline
- weight
;
2182 const U32 start
= rankVal
[weight
];
2183 const U32 length
= 1 << (targetLog
-nbBits
);
2185 if (targetLog
-nbBits
>= minBits
) { /* enough room for a second symbol */
2187 int minWeight
= nbBits
+ scaleLog
;
2188 if (minWeight
< 1) minWeight
= 1;
2189 sortedRank
= rankStart
[minWeight
];
2190 HUFv07_fillDTableX4Level2(DTable
+start
, targetLog
-nbBits
, nbBits
,
2191 rankValOrigin
[nbBits
], minWeight
,
2192 sortedList
+sortedRank
, sortedListSize
-sortedRank
,
2193 nbBitsBaseline
, symbol
);
2196 MEM_writeLE16(&(DElt
.sequence
), symbol
);
2197 DElt
.nbBits
= (BYTE
)(nbBits
);
2200 const U32 end
= start
+ length
;
2201 for (u
= start
; u
< end
; u
++) DTable
[u
] = DElt
;
2203 rankVal
[weight
] += length
;
2207 size_t HUFv07_readDTableX4 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
)
2209 BYTE weightList
[HUFv07_SYMBOLVALUE_MAX
+ 1];
2210 sortedSymbol_t sortedSymbol
[HUFv07_SYMBOLVALUE_MAX
+ 1];
2211 U32 rankStats
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1] = { 0 };
2212 U32 rankStart0
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 2] = { 0 };
2213 U32
* const rankStart
= rankStart0
+1;
2215 U32 tableLog
, maxW
, sizeOfSort
, nbSymbols
;
2216 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2217 U32
const maxTableLog
= dtd
.maxTableLog
;
2219 void* dtPtr
= DTable
+1; /* force compiler to avoid strict-aliasing */
2220 HUFv07_DEltX4
* const dt
= (HUFv07_DEltX4
*)dtPtr
;
2222 HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4
) == sizeof(HUFv07_DTable
)); /* if compilation fails here, assertion is false */
2223 if (maxTableLog
> HUFv07_TABLELOG_ABSOLUTEMAX
) return ERROR(tableLog_tooLarge
);
2224 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2226 iSize
= HUFv07_readStats(weightList
, HUFv07_SYMBOLVALUE_MAX
+ 1, rankStats
, &nbSymbols
, &tableLog
, src
, srcSize
);
2227 if (HUFv07_isError(iSize
)) return iSize
;
2230 if (tableLog
> maxTableLog
) return ERROR(tableLog_tooLarge
); /* DTable can't fit code depth */
2232 /* find maxWeight */
2233 for (maxW
= tableLog
; rankStats
[maxW
]==0; maxW
--) {} /* necessarily finds a solution before 0 */
2235 /* Get start index of each weight */
2236 { U32 w
, nextRankStart
= 0;
2237 for (w
=1; w
<maxW
+1; w
++) {
2238 U32 current
= nextRankStart
;
2239 nextRankStart
+= rankStats
[w
];
2240 rankStart
[w
] = current
;
2242 rankStart
[0] = nextRankStart
; /* put all 0w symbols at the end of sorted list*/
2243 sizeOfSort
= nextRankStart
;
2246 /* sort symbols by weight */
2248 for (s
=0; s
<nbSymbols
; s
++) {
2249 U32
const w
= weightList
[s
];
2250 U32
const r
= rankStart
[w
]++;
2251 sortedSymbol
[r
].symbol
= (BYTE
)s
;
2252 sortedSymbol
[r
].weight
= (BYTE
)w
;
2254 rankStart
[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2258 { U32
* const rankVal0
= rankVal
[0];
2259 { int const rescale
= (maxTableLog
-tableLog
) - 1; /* tableLog <= maxTableLog */
2260 U32 nextRankVal
= 0;
2262 for (w
=1; w
<maxW
+1; w
++) {
2263 U32 current
= nextRankVal
;
2264 nextRankVal
+= rankStats
[w
] << (w
+rescale
);
2265 rankVal0
[w
] = current
;
2267 { U32
const minBits
= tableLog
+1 - maxW
;
2269 for (consumed
= minBits
; consumed
< maxTableLog
- minBits
+ 1; consumed
++) {
2270 U32
* const rankValPtr
= rankVal
[consumed
];
2272 for (w
= 1; w
< maxW
+1; w
++) {
2273 rankValPtr
[w
] = rankVal0
[w
] >> consumed
;
2276 HUFv07_fillDTableX4(dt
, maxTableLog
,
2277 sortedSymbol
, sizeOfSort
,
2278 rankStart0
, rankVal
, maxW
,
2281 dtd
.tableLog
= (BYTE
)maxTableLog
;
2283 memcpy(DTable
, &dtd
, sizeof(dtd
));
2288 static U32
HUFv07_decodeSymbolX4(void* op
, BITv07_DStream_t
* DStream
, const HUFv07_DEltX4
* dt
, const U32 dtLog
)
2290 const size_t val
= BITv07_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2291 memcpy(op
, dt
+val
, 2);
2292 BITv07_skipBits(DStream
, dt
[val
].nbBits
);
2293 return dt
[val
].length
;
2296 static U32
HUFv07_decodeLastSymbolX4(void* op
, BITv07_DStream_t
* DStream
, const HUFv07_DEltX4
* dt
, const U32 dtLog
)
2298 const size_t val
= BITv07_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2299 memcpy(op
, dt
+val
, 1);
2300 if (dt
[val
].length
==1) BITv07_skipBits(DStream
, dt
[val
].nbBits
);
2302 if (DStream
->bitsConsumed
< (sizeof(DStream
->bitContainer
)*8)) {
2303 BITv07_skipBits(DStream
, dt
[val
].nbBits
);
2304 if (DStream
->bitsConsumed
> (sizeof(DStream
->bitContainer
)*8))
2305 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 */
2311 #define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2312 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2314 #define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2315 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
2316 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2318 #define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2320 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2322 static inline size_t HUFv07_decodeStreamX4(BYTE
* p
, BITv07_DStream_t
* bitDPtr
, BYTE
* const pEnd
, const HUFv07_DEltX4
* const dt
, const U32 dtLog
)
2324 BYTE
* const pStart
= p
;
2326 /* up to 8 symbols at a time */
2327 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
< pEnd
-7)) {
2328 HUFv07_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2329 HUFv07_DECODE_SYMBOLX4_1(p
, bitDPtr
);
2330 HUFv07_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2331 HUFv07_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2334 /* closer to end : up to 2 symbols at a time */
2335 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
<= pEnd
-2))
2336 HUFv07_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2339 HUFv07_DECODE_SYMBOLX4_0(p
, bitDPtr
); /* no need to reload : reached the end of DStream */
2342 p
+= HUFv07_decodeLastSymbolX4(p
, bitDPtr
, dt
, dtLog
);
2348 static size_t HUFv07_decompress1X4_usingDTable_internal(
2349 void* dst
, size_t dstSize
,
2350 const void* cSrc
, size_t cSrcSize
,
2351 const HUFv07_DTable
* DTable
)
2353 BITv07_DStream_t bitD
;
2356 { size_t const errorCode
= BITv07_initDStream(&bitD
, cSrc
, cSrcSize
);
2357 if (HUFv07_isError(errorCode
)) return errorCode
;
2361 { BYTE
* const ostart
= (BYTE
*) dst
;
2362 BYTE
* const oend
= ostart
+ dstSize
;
2363 const void* const dtPtr
= DTable
+1; /* force compiler to not use strict-aliasing */
2364 const HUFv07_DEltX4
* const dt
= (const HUFv07_DEltX4
*)dtPtr
;
2365 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2366 HUFv07_decodeStreamX4(ostart
, &bitD
, oend
, dt
, dtd
.tableLog
);
2370 if (!BITv07_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
2376 size_t HUFv07_decompress1X4_usingDTable(
2377 void* dst
, size_t dstSize
,
2378 const void* cSrc
, size_t cSrcSize
,
2379 const HUFv07_DTable
* DTable
)
2381 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2382 if (dtd
.tableType
!= 1) return ERROR(GENERIC
);
2383 return HUFv07_decompress1X4_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
2386 size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable
* DCtx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2388 const BYTE
* ip
= (const BYTE
*) cSrc
;
2390 size_t const hSize
= HUFv07_readDTableX4 (DCtx
, cSrc
, cSrcSize
);
2391 if (HUFv07_isError(hSize
)) return hSize
;
2392 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2393 ip
+= hSize
; cSrcSize
-= hSize
;
2395 return HUFv07_decompress1X4_usingDTable_internal (dst
, dstSize
, ip
, cSrcSize
, DCtx
);
2398 size_t HUFv07_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2400 HUFv07_CREATE_STATIC_DTABLEX4(DTable
, HUFv07_TABLELOG_MAX
);
2401 return HUFv07_decompress1X4_DCtx(DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
2404 static size_t HUFv07_decompress4X4_usingDTable_internal(
2405 void* dst
, size_t dstSize
,
2406 const void* cSrc
, size_t cSrcSize
,
2407 const HUFv07_DTable
* DTable
)
2409 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2411 { const BYTE
* const istart
= (const BYTE
*) cSrc
;
2412 BYTE
* const ostart
= (BYTE
*) dst
;
2413 BYTE
* const oend
= ostart
+ dstSize
;
2414 const void* const dtPtr
= DTable
+1;
2415 const HUFv07_DEltX4
* const dt
= (const HUFv07_DEltX4
*)dtPtr
;
2418 BITv07_DStream_t bitD1
;
2419 BITv07_DStream_t bitD2
;
2420 BITv07_DStream_t bitD3
;
2421 BITv07_DStream_t bitD4
;
2422 size_t const length1
= MEM_readLE16(istart
);
2423 size_t const length2
= MEM_readLE16(istart
+2);
2424 size_t const length3
= MEM_readLE16(istart
+4);
2425 size_t const length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2426 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2427 const BYTE
* const istart2
= istart1
+ length1
;
2428 const BYTE
* const istart3
= istart2
+ length2
;
2429 const BYTE
* const istart4
= istart3
+ length3
;
2430 size_t const segmentSize
= (dstSize
+3) / 4;
2431 BYTE
* const opStart2
= ostart
+ segmentSize
;
2432 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2433 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2435 BYTE
* op2
= opStart2
;
2436 BYTE
* op3
= opStart3
;
2437 BYTE
* op4
= opStart4
;
2439 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2440 U32
const dtLog
= dtd
.tableLog
;
2442 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2443 { size_t const errorCode
= BITv07_initDStream(&bitD1
, istart1
, length1
);
2444 if (HUFv07_isError(errorCode
)) return errorCode
; }
2445 { size_t const errorCode
= BITv07_initDStream(&bitD2
, istart2
, length2
);
2446 if (HUFv07_isError(errorCode
)) return errorCode
; }
2447 { size_t const errorCode
= BITv07_initDStream(&bitD3
, istart3
, length3
);
2448 if (HUFv07_isError(errorCode
)) return errorCode
; }
2449 { size_t const errorCode
= BITv07_initDStream(&bitD4
, istart4
, length4
);
2450 if (HUFv07_isError(errorCode
)) return errorCode
; }
2452 /* 16-32 symbols per loop (4-8 symbols per stream) */
2453 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2454 for ( ; (endSignal
==BITv07_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2455 HUFv07_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2456 HUFv07_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2457 HUFv07_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2458 HUFv07_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2459 HUFv07_DECODE_SYMBOLX4_1(op1
, &bitD1
);
2460 HUFv07_DECODE_SYMBOLX4_1(op2
, &bitD2
);
2461 HUFv07_DECODE_SYMBOLX4_1(op3
, &bitD3
);
2462 HUFv07_DECODE_SYMBOLX4_1(op4
, &bitD4
);
2463 HUFv07_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2464 HUFv07_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2465 HUFv07_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2466 HUFv07_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2467 HUFv07_DECODE_SYMBOLX4_0(op1
, &bitD1
);
2468 HUFv07_DECODE_SYMBOLX4_0(op2
, &bitD2
);
2469 HUFv07_DECODE_SYMBOLX4_0(op3
, &bitD3
);
2470 HUFv07_DECODE_SYMBOLX4_0(op4
, &bitD4
);
2472 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2475 /* check corruption */
2476 if (op1
> opStart2
) return ERROR(corruption_detected
);
2477 if (op2
> opStart3
) return ERROR(corruption_detected
);
2478 if (op3
> opStart4
) return ERROR(corruption_detected
);
2479 /* note : op4 supposed already verified within main loop */
2481 /* finish bitStreams one by one */
2482 HUFv07_decodeStreamX4(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2483 HUFv07_decodeStreamX4(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2484 HUFv07_decodeStreamX4(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2485 HUFv07_decodeStreamX4(op4
, &bitD4
, oend
, dt
, dtLog
);
2488 { U32
const endCheck
= BITv07_endOfDStream(&bitD1
) & BITv07_endOfDStream(&bitD2
) & BITv07_endOfDStream(&bitD3
) & BITv07_endOfDStream(&bitD4
);
2489 if (!endCheck
) return ERROR(corruption_detected
); }
2497 size_t HUFv07_decompress4X4_usingDTable(
2498 void* dst
, size_t dstSize
,
2499 const void* cSrc
, size_t cSrcSize
,
2500 const HUFv07_DTable
* DTable
)
2502 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2503 if (dtd
.tableType
!= 1) return ERROR(GENERIC
);
2504 return HUFv07_decompress4X4_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
2508 size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2510 const BYTE
* ip
= (const BYTE
*) cSrc
;
2512 size_t hSize
= HUFv07_readDTableX4 (dctx
, cSrc
, cSrcSize
);
2513 if (HUFv07_isError(hSize
)) return hSize
;
2514 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2515 ip
+= hSize
; cSrcSize
-= hSize
;
2517 return HUFv07_decompress4X4_usingDTable_internal(dst
, dstSize
, ip
, cSrcSize
, dctx
);
2520 size_t HUFv07_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2522 HUFv07_CREATE_STATIC_DTABLEX4(DTable
, HUFv07_TABLELOG_MAX
);
2523 return HUFv07_decompress4X4_DCtx(DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
2527 /* ********************************/
2528 /* Generic decompression selector */
2529 /* ********************************/
2531 size_t HUFv07_decompress1X_usingDTable(void* dst
, size_t maxDstSize
,
2532 const void* cSrc
, size_t cSrcSize
,
2533 const HUFv07_DTable
* DTable
)
2535 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2536 return dtd
.tableType
? HUFv07_decompress1X4_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
) :
2537 HUFv07_decompress1X2_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
);
2540 size_t HUFv07_decompress4X_usingDTable(void* dst
, size_t maxDstSize
,
2541 const void* cSrc
, size_t cSrcSize
,
2542 const HUFv07_DTable
* DTable
)
2544 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2545 return dtd
.tableType
? HUFv07_decompress4X4_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
) :
2546 HUFv07_decompress4X2_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
);
2550 typedef struct { U32 tableTime
; U32 decode256Time
; } algo_time_t
;
2551 static const algo_time_t algoTime
[16 /* Quantization */][3 /* single, double, quad */] =
2553 /* single, double, quad */
2554 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2555 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2556 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2557 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2558 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2559 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2560 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2561 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2562 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2563 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2564 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2565 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2566 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2567 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2568 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2569 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2572 /** HUFv07_selectDecoder() :
2573 * Tells which decoder is likely to decode faster,
2574 * based on a set of pre-determined metrics.
2575 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
2576 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
2577 U32
HUFv07_selectDecoder (size_t dstSize
, size_t cSrcSize
)
2579 /* decoder timing evaluation */
2580 U32
const Q
= (U32
)(cSrcSize
* 16 / dstSize
); /* Q < 16 since dstSize > cSrcSize */
2581 U32
const D256
= (U32
)(dstSize
>> 8);
2582 U32
const DTime0
= algoTime
[Q
][0].tableTime
+ (algoTime
[Q
][0].decode256Time
* D256
);
2583 U32 DTime1
= algoTime
[Q
][1].tableTime
+ (algoTime
[Q
][1].decode256Time
* D256
);
2584 DTime1
+= DTime1
>> 3; /* advantage to algorithm using less memory, for cache eviction */
2586 return DTime1
< DTime0
;
2590 typedef size_t (*decompressionAlgo
)(void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
);
2592 size_t HUFv07_decompress (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2594 static const decompressionAlgo decompress
[2] = { HUFv07_decompress4X2
, HUFv07_decompress4X4
};
2596 /* validation checks */
2597 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2598 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2599 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2600 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2602 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2603 return decompress
[algoNb
](dst
, dstSize
, cSrc
, cSrcSize
);
2606 //return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2607 //return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2610 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2612 /* validation checks */
2613 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2614 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2615 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2616 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2618 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2619 return algoNb
? HUFv07_decompress4X4_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) :
2620 HUFv07_decompress4X2_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) ;
2624 size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2626 /* validation checks */
2627 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2628 if ((cSrcSize
>= dstSize
) || (cSrcSize
<= 1)) return ERROR(corruption_detected
); /* invalid */
2630 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2631 return algoNb
? HUFv07_decompress4X4_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) :
2632 HUFv07_decompress4X2_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) ;
2636 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2638 /* validation checks */
2639 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2640 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2641 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2642 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2644 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2645 return algoNb
? HUFv07_decompress1X4_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) :
2646 HUFv07_decompress1X2_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) ;
2650 Common functions of Zstd compression library
2651 Copyright (C) 2015-2016, Yann Collet.
2653 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2655 Redistribution and use in source and binary forms, with or without
2656 modification, are permitted provided that the following conditions are
2658 * Redistributions of source code must retain the above copyright
2659 notice, this list of conditions and the following disclaimer.
2660 * Redistributions in binary form must reproduce the above
2661 copyright notice, this list of conditions and the following disclaimer
2662 in the documentation and/or other materials provided with the
2664 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2665 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2666 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2667 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2668 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2669 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2670 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2671 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2672 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2673 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2674 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2676 You can contact the author at :
2677 - zstd homepage : http://www.zstd.net/
2682 /*-****************************************
2683 * ZSTD Error Management
2684 ******************************************/
2685 /*! ZSTDv07_isError() :
2686 * tells if a return value is an error code */
2687 unsigned ZSTDv07_isError(size_t code
) { return ERR_isError(code
); }
2689 /*! ZSTDv07_getErrorName() :
2690 * provides error code string from function result (useful for debugging) */
2691 const char* ZSTDv07_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
2695 /* **************************************************************
2696 * ZBUFF Error Management
2697 ****************************************************************/
2698 unsigned ZBUFFv07_isError(size_t errorCode
) { return ERR_isError(errorCode
); }
2700 const char* ZBUFFv07_getErrorName(size_t errorCode
) { return ERR_getErrorName(errorCode
); }
2704 void* ZSTDv07_defaultAllocFunction(void* opaque
, size_t size
)
2706 void* address
= malloc(size
);
2708 /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2712 void ZSTDv07_defaultFreeFunction(void* opaque
, void* address
)
2715 /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2719 zstd_internal - common functions to include
2720 Header File for include
2721 Copyright (C) 2014-2016, Yann Collet.
2723 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2725 Redistribution and use in source and binary forms, with or without
2726 modification, are permitted provided that the following conditions are
2728 * Redistributions of source code must retain the above copyright
2729 notice, this list of conditions and the following disclaimer.
2730 * Redistributions in binary form must reproduce the above
2731 copyright notice, this list of conditions and the following disclaimer
2732 in the documentation and/or other materials provided with the
2734 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2735 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2736 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2737 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2738 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2739 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2740 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2741 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2742 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2743 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2744 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2746 You can contact the author at :
2747 - zstd homepage : https://www.zstd.net
2749 #ifndef ZSTDv07_CCOMMON_H_MODULE
2750 #define ZSTDv07_CCOMMON_H_MODULE
2753 /*-*************************************
2755 ***************************************/
2756 #define MIN(a,b) ((a)<(b) ? (a) : (b))
2757 #define MAX(a,b) ((a)>(b) ? (a) : (b))
2760 /*-*************************************
2762 ***************************************/
2763 #define ZSTDv07_OPT_NUM (1<<12)
2764 #define ZSTDv07_DICT_MAGIC 0xEC30A437 /* v0.7 */
2766 #define ZSTDv07_REP_NUM 3
2767 #define ZSTDv07_REP_INIT ZSTDv07_REP_NUM
2768 #define ZSTDv07_REP_MOVE (ZSTDv07_REP_NUM-1)
2769 static const U32 repStartValue
[ZSTDv07_REP_NUM
] = { 1, 4, 8 };
2771 #define KB *(1 <<10)
2772 #define MB *(1 <<20)
2773 #define GB *(1U<<30)
2782 #define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10
2783 static const size_t ZSTDv07_fcs_fieldSize
[4] = { 0, 2, 4, 8 };
2784 static const size_t ZSTDv07_did_fieldSize
[4] = { 0, 1, 2, 4 };
2786 #define ZSTDv07_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
2787 static const size_t ZSTDv07_blockHeaderSize
= ZSTDv07_BLOCKHEADERSIZE
;
2788 typedef enum { bt_compressed
, bt_raw
, bt_rle
, bt_end
} blockType_t
;
2790 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2791 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
2794 typedef enum { lbt_huffman
, lbt_repeat
, lbt_raw
, lbt_rle
} litBlockType_t
;
2796 #define LONGNBSEQ 0x7F00
2799 #define EQUAL_READ32 4
2802 #define MaxLit ((1<<Litbits) - 1)
2806 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
2811 #define FSEv07_ENCODING_RAW 0
2812 #define FSEv07_ENCODING_RLE 1
2813 #define FSEv07_ENCODING_STATIC 2
2814 #define FSEv07_ENCODING_DYNAMIC 3
2816 static const U32 LL_bits
[MaxLL
+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2817 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
2819 static const S16 LL_defaultNorm
[MaxLL
+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2820 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
2822 static const U32 LL_defaultNormLog
= 6;
2824 static const U32 ML_bits
[MaxML
+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2825 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2826 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
2828 static const S16 ML_defaultNorm
[MaxML
+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2829 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2830 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
2832 static const U32 ML_defaultNormLog
= 6;
2834 static const S16 OF_defaultNorm
[MaxOff
+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2835 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
2836 static const U32 OF_defaultNormLog
= 5;
2839 /*-*******************************************
2840 * Shared functions to include for inlining
2841 *********************************************/
2842 static void ZSTDv07_copy8(void* dst
, const void* src
) { memcpy(dst
, src
, 8); }
2843 #define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; }
2845 /*! ZSTDv07_wildcopy() :
2846 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
2847 #define WILDCOPY_OVERLENGTH 8
2848 MEM_STATIC
void ZSTDv07_wildcopy(void* dst
, const void* src
, ptrdiff_t length
)
2850 const BYTE
* ip
= (const BYTE
*)src
;
2851 BYTE
* op
= (BYTE
*)dst
;
2852 BYTE
* const oend
= op
+ length
;
2859 /*-*******************************************
2860 * Private interfaces
2861 *********************************************/
2862 typedef struct ZSTDv07_stats_s ZSTDv07_stats_t
;
2874 U32 rep
[ZSTDv07_REP_INIT
];
2875 } ZSTDv07_optimal_t
;
2877 struct ZSTDv07_stats_s
{ U32 unused
; };
2886 U16
* litLengthStart
;
2889 U16
* matchLengthStart
;
2892 U32 longLengthID
; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
2895 ZSTDv07_optimal_t
* priceTable
;
2896 ZSTDv07_match_t
* matchTable
;
2897 U32
* matchLengthFreq
;
2906 U32 log2matchLengthSum
;
2908 U32 log2litLengthSum
;
2913 U32 cachedLitLength
;
2914 const BYTE
* cachedLiterals
;
2915 ZSTDv07_stats_t stats
;
2918 void ZSTDv07_seqToCodes(const seqStore_t
* seqStorePtr
, size_t const nbSeq
);
2920 /* custom memory allocation functions */
2921 void* ZSTDv07_defaultAllocFunction(void* opaque
, size_t size
);
2922 void ZSTDv07_defaultFreeFunction(void* opaque
, void* address
);
2923 static const ZSTDv07_customMem defaultCustomMem
= { ZSTDv07_defaultAllocFunction
, ZSTDv07_defaultFreeFunction
, NULL
};
2925 #endif /* ZSTDv07_CCOMMON_H_MODULE */
2927 zstd - standard compression library
2928 Copyright (C) 2014-2016, Yann Collet.
2930 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2932 Redistribution and use in source and binary forms, with or without
2933 modification, are permitted provided that the following conditions are
2935 * Redistributions of source code must retain the above copyright
2936 notice, this list of conditions and the following disclaimer.
2937 * Redistributions in binary form must reproduce the above
2938 copyright notice, this list of conditions and the following disclaimer
2939 in the documentation and/or other materials provided with the
2941 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2942 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2943 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2944 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2945 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2946 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2947 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2948 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2949 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2950 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2951 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2953 You can contact the author at :
2954 - zstd homepage : http://www.zstd.net
2957 /* ***************************************************************
2959 *****************************************************************/
2962 * Select how default decompression function ZSTDv07_decompress() will allocate memory,
2963 * in memory stack (0), or in memory heap (1, requires malloc())
2965 #ifndef ZSTDv07_HEAPMODE
2966 # define ZSTDv07_HEAPMODE 1
2970 /*-*******************************************************
2971 * Compiler specifics
2972 *********************************************************/
2973 #ifdef _MSC_VER /* Visual Studio */
2974 # include <intrin.h> /* For Visual 2005 */
2975 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2976 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2977 # pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */
2981 /*-*************************************
2983 ***************************************/
2984 #define ZSTDv07_isError ERR_isError /* for inlining */
2985 #define FSEv07_isError ERR_isError
2986 #define HUFv07_isError ERR_isError
2989 /*_*******************************************************
2991 **********************************************************/
2992 static void ZSTDv07_copy4(void* dst
, const void* src
) { memcpy(dst
, src
, 4); }
2995 /*-*************************************************************
2996 * Context management
2997 ***************************************************************/
2998 typedef enum { ZSTDds_getFrameHeaderSize
, ZSTDds_decodeFrameHeader
,
2999 ZSTDds_decodeBlockHeader
, ZSTDds_decompressBlock
,
3000 ZSTDds_decodeSkippableHeader
, ZSTDds_skipFrame
} ZSTDv07_dStage
;
3002 struct ZSTDv07_DCtx_s
3004 FSEv07_DTable LLTable
[FSEv07_DTABLE_SIZE_U32(LLFSELog
)];
3005 FSEv07_DTable OffTable
[FSEv07_DTABLE_SIZE_U32(OffFSELog
)];
3006 FSEv07_DTable MLTable
[FSEv07_DTABLE_SIZE_U32(MLFSELog
)];
3007 HUFv07_DTable hufTable
[HUFv07_DTABLE_SIZE(HufLog
)]; /* can accommodate HUFv07_decompress4X */
3008 const void* previousDstEnd
;
3011 const void* dictEnd
;
3014 ZSTDv07_frameParams fParams
;
3015 blockType_t bType
; /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
3016 ZSTDv07_dStage stage
;
3019 XXH64_state_t xxhState
;
3023 ZSTDv07_customMem customMem
;
3025 BYTE litBuffer
[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
+ WILDCOPY_OVERLENGTH
];
3026 BYTE headerBuffer
[ZSTDv07_FRAMEHEADERSIZE_MAX
];
3027 }; /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */
3029 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx
* dctx
);
3031 size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx
* dctx
) { return sizeof(*dctx
); }
3033 size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx
); }
3035 size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx
* dctx
)
3037 dctx
->expected
= ZSTDv07_frameHeaderSize_min
;
3038 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
3039 dctx
->previousDstEnd
= NULL
;
3042 dctx
->dictEnd
= NULL
;
3043 dctx
->hufTable
[0] = (HUFv07_DTable
)((HufLog
)*0x1000001);
3044 dctx
->litEntropy
= dctx
->fseEntropy
= 0;
3046 { int i
; for (i
=0; i
<ZSTDv07_REP_NUM
; i
++) dctx
->rep
[i
] = repStartValue
[i
]; }
3050 ZSTDv07_DCtx
* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem
)
3054 if (!customMem
.customAlloc
&& !customMem
.customFree
)
3055 customMem
= defaultCustomMem
;
3057 if (!customMem
.customAlloc
|| !customMem
.customFree
)
3060 dctx
= (ZSTDv07_DCtx
*) customMem
.customAlloc(customMem
.opaque
, sizeof(ZSTDv07_DCtx
));
3061 if (!dctx
) return NULL
;
3062 memcpy(&dctx
->customMem
, &customMem
, sizeof(ZSTDv07_customMem
));
3063 ZSTDv07_decompressBegin(dctx
);
3067 ZSTDv07_DCtx
* ZSTDv07_createDCtx(void)
3069 return ZSTDv07_createDCtx_advanced(defaultCustomMem
);
3072 size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx
* dctx
)
3074 if (dctx
==NULL
) return 0; /* support free on NULL */
3075 dctx
->customMem
.customFree(dctx
->customMem
.opaque
, dctx
);
3076 return 0; /* reserved as a potential error code in the future */
3079 void ZSTDv07_copyDCtx(ZSTDv07_DCtx
* dstDCtx
, const ZSTDv07_DCtx
* srcDCtx
)
3081 memcpy(dstDCtx
, srcDCtx
,
3082 sizeof(ZSTDv07_DCtx
) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
+WILDCOPY_OVERLENGTH
+ ZSTDv07_frameHeaderSize_max
)); /* no need to copy workspace */
3086 /*-*************************************************************
3087 * Decompression section
3088 ***************************************************************/
3090 /* Frame format description
3091 Frame Header - [ Block Header - Block ] - Frame End
3093 - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h)
3094 - 1 byte - Frame Descriptor
3096 - 3 bytes, starting with a 2-bits descriptor
3097 Uncompressed, Compressed, Frame End, unused
3099 See Block Format Description
3101 - 3 bytes, compatible with Block Header
3107 1 byte - FrameHeaderDescription :
3108 bit 0-1 : dictID (0, 1, 2 or 4 bytes)
3109 bit 2 : checksumFlag
3110 bit 3 : reserved (must be zero)
3111 bit 4 : reserved (unused, can be any value)
3112 bit 5 : Single Segment (if 1, WindowLog byte is not present)
3113 bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
3114 if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
3116 Optional : WindowLog (0 or 1 byte)
3117 bit 0-2 : octal Fractional (1/8th)
3118 bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
3120 Optional : dictID (0, 1, 2 or 4 bytes)
3121 Automatic adaptation
3125 4 : all other values
3127 Optional : content size (0, 1, 2, 4 or 8 bytes)
3128 0 : unknown (fcfs==0 and swl==0)
3129 1 : 0-255 bytes (fcfs==0 and swl==1)
3130 2 : 256 - 65535+256 (fcfs==1)
3131 4 : 0 - 4GB-1 (fcfs==2)
3132 8 : 0 - 16EB-1 (fcfs==3)
3136 /* Compressed Block, format description
3138 Block = Literal Section - Sequences Section
3139 Prerequisite : size of (compressed) block, maximum size of regenerated data
3143 1.1) Header : 1-5 bytes
3145 00 compressed by Huff0
3147 10 is Raw (uncompressed)
3149 Note : using 01 => Huff0 with precomputed table ?
3150 Note : delta map ? => compressed ?
3152 1.1.1) Huff0-compressed literal block : 3-5 bytes
3153 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3154 srcSize < 1 KB => 3 bytes (2-2-10-10)
3155 srcSize < 16KB => 4 bytes (2-2-14-14)
3156 else => 5 bytes (2-2-18-18)
3157 big endian convention
3159 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
3160 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
3161 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
3163 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3167 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3168 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
3169 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3171 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3175 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3176 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3177 srcSize < 1 KB => 3 bytes (2-2-10-10)
3178 srcSize < 16KB => 4 bytes (2-2-14-14)
3179 else => 5 bytes (2-2-18-18)
3180 big endian convention
3182 1- CTable available (stored into workspace ?)
3183 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3186 1.2) Literal block content
3188 1.2.1) Huff0 block, using sizes from header
3191 1.2.2) Huff0 block, using prepared table
3198 2) Sequences section
3202 /** ZSTDv07_frameHeaderSize() :
3203 * srcSize must be >= ZSTDv07_frameHeaderSize_min.
3204 * @return : size of the Frame Header */
3205 static size_t ZSTDv07_frameHeaderSize(const void* src
, size_t srcSize
)
3207 if (srcSize
< ZSTDv07_frameHeaderSize_min
) return ERROR(srcSize_wrong
);
3208 { BYTE
const fhd
= ((const BYTE
*)src
)[4];
3209 U32
const dictID
= fhd
& 3;
3210 U32
const directMode
= (fhd
>> 5) & 1;
3211 U32
const fcsId
= fhd
>> 6;
3212 return ZSTDv07_frameHeaderSize_min
+ !directMode
+ ZSTDv07_did_fieldSize
[dictID
] + ZSTDv07_fcs_fieldSize
[fcsId
]
3213 + (directMode
&& !ZSTDv07_fcs_fieldSize
[fcsId
]);
3218 /** ZSTDv07_getFrameParams() :
3219 * decode Frame Header, or require larger `srcSize`.
3220 * @return : 0, `fparamsPtr` is correctly filled,
3221 * >0, `srcSize` is too small, result is expected `srcSize`,
3222 * or an error code, which can be tested using ZSTDv07_isError() */
3223 size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams
* fparamsPtr
, const void* src
, size_t srcSize
)
3225 const BYTE
* ip
= (const BYTE
*)src
;
3227 if (srcSize
< ZSTDv07_frameHeaderSize_min
) return ZSTDv07_frameHeaderSize_min
;
3228 if (MEM_readLE32(src
) != ZSTDv07_MAGICNUMBER
) {
3229 if ((MEM_readLE32(src
) & 0xFFFFFFF0U
) == ZSTDv07_MAGIC_SKIPPABLE_START
) {
3230 if (srcSize
< ZSTDv07_skippableHeaderSize
) return ZSTDv07_skippableHeaderSize
; /* magic number + skippable frame length */
3231 memset(fparamsPtr
, 0, sizeof(*fparamsPtr
));
3232 fparamsPtr
->frameContentSize
= MEM_readLE32((const char *)src
+ 4);
3233 fparamsPtr
->windowSize
= 0; /* windowSize==0 means a frame is skippable */
3236 return ERROR(prefix_unknown
);
3239 /* ensure there is enough `srcSize` to fully read/decode frame header */
3240 { size_t const fhsize
= ZSTDv07_frameHeaderSize(src
, srcSize
);
3241 if (srcSize
< fhsize
) return fhsize
; }
3243 { BYTE
const fhdByte
= ip
[4];
3245 U32
const dictIDSizeCode
= fhdByte
&3;
3246 U32
const checksumFlag
= (fhdByte
>>2)&1;
3247 U32
const directMode
= (fhdByte
>>5)&1;
3248 U32
const fcsID
= fhdByte
>>6;
3249 U32
const windowSizeMax
= 1U << ZSTDv07_WINDOWLOG_MAX
;
3252 U64 frameContentSize
= 0;
3253 if ((fhdByte
& 0x08) != 0) return ERROR(frameParameter_unsupported
); /* reserved bits, which must be zero */
3255 BYTE
const wlByte
= ip
[pos
++];
3256 U32
const windowLog
= (wlByte
>> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN
;
3257 if (windowLog
> ZSTDv07_WINDOWLOG_MAX
) return ERROR(frameParameter_unsupported
);
3258 windowSize
= (1U << windowLog
);
3259 windowSize
+= (windowSize
>> 3) * (wlByte
&7);
3262 switch(dictIDSizeCode
)
3264 default: /* impossible */
3266 case 1 : dictID
= ip
[pos
]; pos
++; break;
3267 case 2 : dictID
= MEM_readLE16(ip
+pos
); pos
+=2; break;
3268 case 3 : dictID
= MEM_readLE32(ip
+pos
); pos
+=4; break;
3272 default: /* impossible */
3273 case 0 : if (directMode
) frameContentSize
= ip
[pos
]; break;
3274 case 1 : frameContentSize
= MEM_readLE16(ip
+pos
)+256; break;
3275 case 2 : frameContentSize
= MEM_readLE32(ip
+pos
); break;
3276 case 3 : frameContentSize
= MEM_readLE64(ip
+pos
); break;
3278 if (!windowSize
) windowSize
= (U32
)frameContentSize
;
3279 if (windowSize
> windowSizeMax
) return ERROR(frameParameter_unsupported
);
3280 fparamsPtr
->frameContentSize
= frameContentSize
;
3281 fparamsPtr
->windowSize
= windowSize
;
3282 fparamsPtr
->dictID
= dictID
;
3283 fparamsPtr
->checksumFlag
= checksumFlag
;
3289 /** ZSTDv07_getDecompressedSize() :
3290 * compatible with legacy mode
3291 * @return : decompressed size if known, 0 otherwise
3292 note : 0 can mean any of the following :
3293 - decompressed size is not provided within frame header
3294 - frame header unknown / not supported
3295 - frame header not completely provided (`srcSize` too small) */
3296 unsigned long long ZSTDv07_getDecompressedSize(const void* src
, size_t srcSize
)
3298 { ZSTDv07_frameParams fparams
;
3299 size_t const frResult
= ZSTDv07_getFrameParams(&fparams
, src
, srcSize
);
3300 if (frResult
!=0) return 0;
3301 return fparams
.frameContentSize
;
3306 /** ZSTDv07_decodeFrameHeader() :
3307 * `srcSize` must be the size provided by ZSTDv07_frameHeaderSize().
3308 * @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */
3309 static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx
* dctx
, const void* src
, size_t srcSize
)
3311 size_t const result
= ZSTDv07_getFrameParams(&(dctx
->fParams
), src
, srcSize
);
3312 if (dctx
->fParams
.dictID
&& (dctx
->dictID
!= dctx
->fParams
.dictID
)) return ERROR(dictionary_wrong
);
3313 if (dctx
->fParams
.checksumFlag
) XXH64_reset(&dctx
->xxhState
, 0);
3320 blockType_t blockType
;
3322 } blockProperties_t
;
3324 /*! ZSTDv07_getcBlockSize() :
3325 * Provides the size of compressed block from block header `src` */
3326 size_t ZSTDv07_getcBlockSize(const void* src
, size_t srcSize
, blockProperties_t
* bpPtr
)
3328 const BYTE
* const in
= (const BYTE
* const)src
;
3331 if (srcSize
< ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3333 bpPtr
->blockType
= (blockType_t
)((*in
) >> 6);
3334 cSize
= in
[2] + (in
[1]<<8) + ((in
[0] & 7)<<16);
3335 bpPtr
->origSize
= (bpPtr
->blockType
== bt_rle
) ? cSize
: 0;
3337 if (bpPtr
->blockType
== bt_end
) return 0;
3338 if (bpPtr
->blockType
== bt_rle
) return 1;
3343 static size_t ZSTDv07_copyRawBlock(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3345 if (srcSize
> dstCapacity
) return ERROR(dstSize_tooSmall
);
3346 memcpy(dst
, src
, srcSize
);
3351 /*! ZSTDv07_decodeLiteralsBlock() :
3352 @return : nb of bytes read from src (< srcSize ) */
3353 size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx
* dctx
,
3354 const void* src
, size_t srcSize
) /* note : srcSize < BLOCKSIZE */
3356 const BYTE
* const istart
= (const BYTE
*) src
;
3358 if (srcSize
< MIN_CBLOCK_SIZE
) return ERROR(corruption_detected
);
3360 switch((litBlockType_t
)(istart
[0]>> 6))
3363 { size_t litSize
, litCSize
, singleStream
=0;
3364 U32 lhSize
= (istart
[0] >> 4) & 3;
3365 if (srcSize
< 5) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3368 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3369 /* 2 - 2 - 10 - 10 */
3371 singleStream
= istart
[0] & 16;
3372 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
3373 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
3376 /* 2 - 2 - 14 - 14 */
3378 litSize
= ((istart
[0] & 15) << 10) + (istart
[1] << 2) + (istart
[2] >> 6);
3379 litCSize
= ((istart
[2] & 63) << 8) + istart
[3];
3382 /* 2 - 2 - 18 - 18 */
3384 litSize
= ((istart
[0] & 15) << 14) + (istart
[1] << 6) + (istart
[2] >> 2);
3385 litCSize
= ((istart
[2] & 3) << 16) + (istart
[3] << 8) + istart
[4];
3388 if (litSize
> ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
) return ERROR(corruption_detected
);
3389 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
3391 if (HUFv07_isError(singleStream
?
3392 HUFv07_decompress1X2_DCtx(dctx
->hufTable
, dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) :
3393 HUFv07_decompress4X_hufOnly (dctx
->hufTable
, dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) ))
3394 return ERROR(corruption_detected
);
3396 dctx
->litPtr
= dctx
->litBuffer
;
3397 dctx
->litSize
= litSize
;
3398 dctx
->litEntropy
= 1;
3399 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3400 return litCSize
+ lhSize
;
3403 { size_t litSize
, litCSize
;
3404 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3405 if (lhSize
!= 1) /* only case supported for now : small litSize, single stream */
3406 return ERROR(corruption_detected
);
3407 if (dctx
->litEntropy
==0)
3408 return ERROR(dictionary_corrupted
);
3410 /* 2 - 2 - 10 - 10 */
3412 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
3413 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
3414 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
3416 { size_t const errorCode
= HUFv07_decompress1X4_usingDTable(dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
, dctx
->hufTable
);
3417 if (HUFv07_isError(errorCode
)) return ERROR(corruption_detected
);
3419 dctx
->litPtr
= dctx
->litBuffer
;
3420 dctx
->litSize
= litSize
;
3421 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3422 return litCSize
+ lhSize
;
3426 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3429 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3431 litSize
= istart
[0] & 31;
3434 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3437 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3441 if (lhSize
+litSize
+WILDCOPY_OVERLENGTH
> srcSize
) { /* risk reading beyond src buffer with wildcopy */
3442 if (litSize
+lhSize
> srcSize
) return ERROR(corruption_detected
);
3443 memcpy(dctx
->litBuffer
, istart
+lhSize
, litSize
);
3444 dctx
->litPtr
= dctx
->litBuffer
;
3445 dctx
->litSize
= litSize
;
3446 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3447 return lhSize
+litSize
;
3449 /* direct reference into compressed stream */
3450 dctx
->litPtr
= istart
+lhSize
;
3451 dctx
->litSize
= litSize
;
3452 return lhSize
+litSize
;
3456 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3459 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3461 litSize
= istart
[0] & 31;
3464 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3467 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3468 if (srcSize
<4) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3471 if (litSize
> ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
) return ERROR(corruption_detected
);
3472 memset(dctx
->litBuffer
, istart
[lhSize
], litSize
+ WILDCOPY_OVERLENGTH
);
3473 dctx
->litPtr
= dctx
->litBuffer
;
3474 dctx
->litSize
= litSize
;
3478 return ERROR(corruption_detected
); /* impossible */
3483 /*! ZSTDv07_buildSeqTable() :
3484 @return : nb bytes read from src,
3485 or an error code if it fails, testable with ZSTDv07_isError()
3487 size_t ZSTDv07_buildSeqTable(FSEv07_DTable
* DTable
, U32 type
, U32 max
, U32 maxLog
,
3488 const void* src
, size_t srcSize
,
3489 const S16
* defaultNorm
, U32 defaultLog
, U32 flagRepeatTable
)
3493 case FSEv07_ENCODING_RLE
:
3494 if (!srcSize
) return ERROR(srcSize_wrong
);
3495 if ( (*(const BYTE
*)src
) > max
) return ERROR(corruption_detected
);
3496 FSEv07_buildDTable_rle(DTable
, *(const BYTE
*)src
); /* if *src > max, data is corrupted */
3498 case FSEv07_ENCODING_RAW
:
3499 FSEv07_buildDTable(DTable
, defaultNorm
, max
, defaultLog
);
3501 case FSEv07_ENCODING_STATIC
:
3502 if (!flagRepeatTable
) return ERROR(corruption_detected
);
3504 default : /* impossible */
3505 case FSEv07_ENCODING_DYNAMIC
:
3508 size_t const headerSize
= FSEv07_readNCount(norm
, &max
, &tableLog
, src
, srcSize
);
3509 if (FSEv07_isError(headerSize
)) return ERROR(corruption_detected
);
3510 if (tableLog
> maxLog
) return ERROR(corruption_detected
);
3511 FSEv07_buildDTable(DTable
, norm
, max
, tableLog
);
3517 size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr
,
3518 FSEv07_DTable
* DTableLL
, FSEv07_DTable
* DTableML
, FSEv07_DTable
* DTableOffb
, U32 flagRepeatTable
,
3519 const void* src
, size_t srcSize
)
3521 const BYTE
* const istart
= (const BYTE
* const)src
;
3522 const BYTE
* const iend
= istart
+ srcSize
;
3523 const BYTE
* ip
= istart
;
3526 if (srcSize
< MIN_SEQUENCES_SIZE
) return ERROR(srcSize_wrong
);
3529 { int nbSeq
= *ip
++;
3530 if (!nbSeq
) { *nbSeqPtr
=0; return 1; }
3532 if (nbSeq
== 0xFF) {
3533 if (ip
+2 > iend
) return ERROR(srcSize_wrong
);
3534 nbSeq
= MEM_readLE16(ip
) + LONGNBSEQ
, ip
+=2;
3536 if (ip
>= iend
) return ERROR(srcSize_wrong
);
3537 nbSeq
= ((nbSeq
-0x80)<<8) + *ip
++;
3543 /* FSE table descriptors */
3544 { U32
const LLtype
= *ip
>> 6;
3545 U32
const OFtype
= (*ip
>> 4) & 3;
3546 U32
const MLtype
= (*ip
>> 2) & 3;
3550 if (ip
> iend
-3) return ERROR(srcSize_wrong
); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3553 { size_t const llhSize
= ZSTDv07_buildSeqTable(DTableLL
, LLtype
, MaxLL
, LLFSELog
, ip
, iend
-ip
, LL_defaultNorm
, LL_defaultNormLog
, flagRepeatTable
);
3554 if (ZSTDv07_isError(llhSize
)) return ERROR(corruption_detected
);
3557 { size_t const ofhSize
= ZSTDv07_buildSeqTable(DTableOffb
, OFtype
, MaxOff
, OffFSELog
, ip
, iend
-ip
, OF_defaultNorm
, OF_defaultNormLog
, flagRepeatTable
);
3558 if (ZSTDv07_isError(ofhSize
)) return ERROR(corruption_detected
);
3561 { size_t const mlhSize
= ZSTDv07_buildSeqTable(DTableML
, MLtype
, MaxML
, MLFSELog
, ip
, iend
-ip
, ML_defaultNorm
, ML_defaultNormLog
, flagRepeatTable
);
3562 if (ZSTDv07_isError(mlhSize
)) return ERROR(corruption_detected
);
3577 BITv07_DStream_t DStream
;
3578 FSEv07_DState_t stateLL
;
3579 FSEv07_DState_t stateOffb
;
3580 FSEv07_DState_t stateML
;
3581 size_t prevOffset
[ZSTDv07_REP_INIT
];
3585 static seq_t
ZSTDv07_decodeSequence(seqState_t
* seqState
)
3589 U32
const llCode
= FSEv07_peekSymbol(&(seqState
->stateLL
));
3590 U32
const mlCode
= FSEv07_peekSymbol(&(seqState
->stateML
));
3591 U32
const ofCode
= FSEv07_peekSymbol(&(seqState
->stateOffb
)); /* <= maxOff, by table construction */
3593 U32
const llBits
= LL_bits
[llCode
];
3594 U32
const mlBits
= ML_bits
[mlCode
];
3595 U32
const ofBits
= ofCode
;
3596 U32
const totalBits
= llBits
+mlBits
+ofBits
;
3598 static const U32 LL_base
[MaxLL
+1] = {
3599 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3600 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3601 0x2000, 0x4000, 0x8000, 0x10000 };
3603 static const U32 ML_base
[MaxML
+1] = {
3604 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
3605 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
3606 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3607 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3609 static const U32 OF_base
[MaxOff
+1] = {
3610 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
3611 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
3612 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3613 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3620 offset
= OF_base
[ofCode
] + BITv07_readBits(&(seqState
->DStream
), ofBits
); /* <= (ZSTDv07_WINDOWLOG_MAX-1) bits */
3621 if (MEM_32bits()) BITv07_reloadDStream(&(seqState
->DStream
));
3625 if ((llCode
== 0) & (offset
<= 1)) offset
= 1-offset
;
3627 size_t const temp
= seqState
->prevOffset
[offset
];
3628 if (offset
!= 1) seqState
->prevOffset
[2] = seqState
->prevOffset
[1];
3629 seqState
->prevOffset
[1] = seqState
->prevOffset
[0];
3630 seqState
->prevOffset
[0] = offset
= temp
;
3632 offset
= seqState
->prevOffset
[0];
3635 seqState
->prevOffset
[2] = seqState
->prevOffset
[1];
3636 seqState
->prevOffset
[1] = seqState
->prevOffset
[0];
3637 seqState
->prevOffset
[0] = offset
;
3639 seq
.offset
= offset
;
3642 seq
.matchLength
= ML_base
[mlCode
] + ((mlCode
>31) ? BITv07_readBits(&(seqState
->DStream
), mlBits
) : 0); /* <= 16 bits */
3643 if (MEM_32bits() && (mlBits
+llBits
>24)) BITv07_reloadDStream(&(seqState
->DStream
));
3645 seq
.litLength
= LL_base
[llCode
] + ((llCode
>15) ? BITv07_readBits(&(seqState
->DStream
), llBits
) : 0); /* <= 16 bits */
3647 (totalBits
> 64 - 7 - (LLFSELog
+MLFSELog
+OffFSELog
)) ) BITv07_reloadDStream(&(seqState
->DStream
));
3649 /* ANS state update */
3650 FSEv07_updateState(&(seqState
->stateLL
), &(seqState
->DStream
)); /* <= 9 bits */
3651 FSEv07_updateState(&(seqState
->stateML
), &(seqState
->DStream
)); /* <= 9 bits */
3652 if (MEM_32bits()) BITv07_reloadDStream(&(seqState
->DStream
)); /* <= 18 bits */
3653 FSEv07_updateState(&(seqState
->stateOffb
), &(seqState
->DStream
)); /* <= 8 bits */
3660 size_t ZSTDv07_execSequence(BYTE
* op
,
3661 BYTE
* const oend
, seq_t sequence
,
3662 const BYTE
** litPtr
, const BYTE
* const litLimit
,
3663 const BYTE
* const base
, const BYTE
* const vBase
, const BYTE
* const dictEnd
)
3665 BYTE
* const oLitEnd
= op
+ sequence
.litLength
;
3666 size_t const sequenceLength
= sequence
.litLength
+ sequence
.matchLength
;
3667 BYTE
* const oMatchEnd
= op
+ sequenceLength
; /* risk : address space overflow (32-bits) */
3668 BYTE
* const oend_w
= oend
-WILDCOPY_OVERLENGTH
;
3669 const BYTE
* const iLitEnd
= *litPtr
+ sequence
.litLength
;
3670 const BYTE
* match
= oLitEnd
- sequence
.offset
;
3673 if ((oLitEnd
>oend_w
) | (oMatchEnd
>oend
)) return ERROR(dstSize_tooSmall
); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
3674 if (iLitEnd
> litLimit
) return ERROR(corruption_detected
); /* over-read beyond lit buffer */
3677 ZSTDv07_wildcopy(op
, *litPtr
, sequence
.litLength
); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3679 *litPtr
= iLitEnd
; /* update for next sequence */
3682 if (sequence
.offset
> (size_t)(oLitEnd
- base
)) {
3683 /* offset beyond prefix */
3684 if (sequence
.offset
> (size_t)(oLitEnd
- vBase
)) return ERROR(corruption_detected
);
3685 match
= dictEnd
- (base
-match
);
3686 if (match
+ sequence
.matchLength
<= dictEnd
) {
3687 memmove(oLitEnd
, match
, sequence
.matchLength
);
3688 return sequenceLength
;
3690 /* span extDict & currentPrefixSegment */
3691 { size_t const length1
= dictEnd
- match
;
3692 memmove(oLitEnd
, match
, length1
);
3693 op
= oLitEnd
+ length1
;
3694 sequence
.matchLength
-= length1
;
3696 if (op
> oend_w
|| sequence
.matchLength
< MINMATCH
) {
3697 while (op
< oMatchEnd
) *op
++ = *match
++;
3698 return sequenceLength
;
3701 /* Requirement: op <= oend_w */
3703 /* match within prefix */
3704 if (sequence
.offset
< 8) {
3705 /* close range match, overlap */
3706 static const U32 dec32table
[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3707 static const int dec64table
[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3708 int const sub2
= dec64table
[sequence
.offset
];
3713 match
+= dec32table
[sequence
.offset
];
3714 ZSTDv07_copy4(op
+4, match
);
3717 ZSTDv07_copy8(op
, match
);
3719 op
+= 8; match
+= 8;
3721 if (oMatchEnd
> oend
-(16-MINMATCH
)) {
3723 ZSTDv07_wildcopy(op
, match
, oend_w
- op
);
3724 match
+= oend_w
- op
;
3727 while (op
< oMatchEnd
) *op
++ = *match
++;
3729 ZSTDv07_wildcopy(op
, match
, (ptrdiff_t)sequence
.matchLength
-8); /* works even if matchLength < 8 */
3731 return sequenceLength
;
3735 static size_t ZSTDv07_decompressSequences(
3737 void* dst
, size_t maxDstSize
,
3738 const void* seqStart
, size_t seqSize
)
3740 const BYTE
* ip
= (const BYTE
*)seqStart
;
3741 const BYTE
* const iend
= ip
+ seqSize
;
3742 BYTE
* const ostart
= (BYTE
* const)dst
;
3743 BYTE
* const oend
= ostart
+ maxDstSize
;
3745 const BYTE
* litPtr
= dctx
->litPtr
;
3746 const BYTE
* const litEnd
= litPtr
+ dctx
->litSize
;
3747 FSEv07_DTable
* DTableLL
= dctx
->LLTable
;
3748 FSEv07_DTable
* DTableML
= dctx
->MLTable
;
3749 FSEv07_DTable
* DTableOffb
= dctx
->OffTable
;
3750 const BYTE
* const base
= (const BYTE
*) (dctx
->base
);
3751 const BYTE
* const vBase
= (const BYTE
*) (dctx
->vBase
);
3752 const BYTE
* const dictEnd
= (const BYTE
*) (dctx
->dictEnd
);
3755 /* Build Decoding Tables */
3756 { size_t const seqHSize
= ZSTDv07_decodeSeqHeaders(&nbSeq
, DTableLL
, DTableML
, DTableOffb
, dctx
->fseEntropy
, ip
, seqSize
);
3757 if (ZSTDv07_isError(seqHSize
)) return seqHSize
;
3761 /* Regen sequences */
3763 seqState_t seqState
;
3764 dctx
->fseEntropy
= 1;
3765 { U32 i
; for (i
=0; i
<ZSTDv07_REP_INIT
; i
++) seqState
.prevOffset
[i
] = dctx
->rep
[i
]; }
3766 { size_t const errorCode
= BITv07_initDStream(&(seqState
.DStream
), ip
, iend
-ip
);
3767 if (ERR_isError(errorCode
)) return ERROR(corruption_detected
); }
3768 FSEv07_initDState(&(seqState
.stateLL
), &(seqState
.DStream
), DTableLL
);
3769 FSEv07_initDState(&(seqState
.stateOffb
), &(seqState
.DStream
), DTableOffb
);
3770 FSEv07_initDState(&(seqState
.stateML
), &(seqState
.DStream
), DTableML
);
3772 for ( ; (BITv07_reloadDStream(&(seqState
.DStream
)) <= BITv07_DStream_completed
) && nbSeq
; ) {
3774 { seq_t
const sequence
= ZSTDv07_decodeSequence(&seqState
);
3775 size_t const oneSeqSize
= ZSTDv07_execSequence(op
, oend
, sequence
, &litPtr
, litEnd
, base
, vBase
, dictEnd
);
3776 if (ZSTDv07_isError(oneSeqSize
)) return oneSeqSize
;
3780 /* check if reached exact end */
3781 if (nbSeq
) return ERROR(corruption_detected
);
3782 /* save reps for next block */
3783 { U32 i
; for (i
=0; i
<ZSTDv07_REP_INIT
; i
++) dctx
->rep
[i
] = (U32
)(seqState
.prevOffset
[i
]); }
3786 /* last literal segment */
3787 { size_t const lastLLSize
= litEnd
- litPtr
;
3788 //if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3789 if (lastLLSize
> (size_t)(oend
-op
)) return ERROR(dstSize_tooSmall
);
3790 memcpy(op
, litPtr
, lastLLSize
);
3798 static void ZSTDv07_checkContinuity(ZSTDv07_DCtx
* dctx
, const void* dst
)
3800 if (dst
!= dctx
->previousDstEnd
) { /* not contiguous */
3801 dctx
->dictEnd
= dctx
->previousDstEnd
;
3802 dctx
->vBase
= (const char*)dst
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
3804 dctx
->previousDstEnd
= dst
;
3809 static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx
* dctx
,
3810 void* dst
, size_t dstCapacity
,
3811 const void* src
, size_t srcSize
)
3812 { /* blockType == blockCompressed */
3813 const BYTE
* ip
= (const BYTE
*)src
;
3815 if (srcSize
>= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
) return ERROR(srcSize_wrong
);
3817 /* Decode literals sub-block */
3818 { size_t const litCSize
= ZSTDv07_decodeLiteralsBlock(dctx
, src
, srcSize
);
3819 if (ZSTDv07_isError(litCSize
)) return litCSize
;
3821 srcSize
-= litCSize
;
3823 return ZSTDv07_decompressSequences(dctx
, dst
, dstCapacity
, ip
, srcSize
);
3827 size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx
* dctx
,
3828 void* dst
, size_t dstCapacity
,
3829 const void* src
, size_t srcSize
)
3832 ZSTDv07_checkContinuity(dctx
, dst
);
3833 dSize
= ZSTDv07_decompressBlock_internal(dctx
, dst
, dstCapacity
, src
, srcSize
);
3834 dctx
->previousDstEnd
= (char*)dst
+ dSize
;
3839 /** ZSTDv07_insertBlock() :
3840 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
3841 ZSTDLIBv07_API
size_t ZSTDv07_insertBlock(ZSTDv07_DCtx
* dctx
, const void* blockStart
, size_t blockSize
)
3843 ZSTDv07_checkContinuity(dctx
, blockStart
);
3844 dctx
->previousDstEnd
= (const char*)blockStart
+ blockSize
;
3849 size_t ZSTDv07_generateNxBytes(void* dst
, size_t dstCapacity
, BYTE byte
, size_t length
)
3851 if (length
> dstCapacity
) return ERROR(dstSize_tooSmall
);
3852 memset(dst
, byte
, length
);
3857 /*! ZSTDv07_decompressFrame() :
3858 * `dctx` must be properly initialized */
3859 static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx
* dctx
,
3860 void* dst
, size_t dstCapacity
,
3861 const void* src
, size_t srcSize
)
3863 const BYTE
* ip
= (const BYTE
*)src
;
3864 const BYTE
* const iend
= ip
+ srcSize
;
3865 BYTE
* const ostart
= (BYTE
* const)dst
;
3866 BYTE
* const oend
= ostart
+ dstCapacity
;
3868 size_t remainingSize
= srcSize
;
3871 if (srcSize
< ZSTDv07_frameHeaderSize_min
+ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3874 { size_t const frameHeaderSize
= ZSTDv07_frameHeaderSize(src
, ZSTDv07_frameHeaderSize_min
);
3875 if (ZSTDv07_isError(frameHeaderSize
)) return frameHeaderSize
;
3876 if (srcSize
< frameHeaderSize
+ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3877 if (ZSTDv07_decodeFrameHeader(dctx
, src
, frameHeaderSize
)) return ERROR(corruption_detected
);
3878 ip
+= frameHeaderSize
; remainingSize
-= frameHeaderSize
;
3881 /* Loop on each block */
3884 blockProperties_t blockProperties
;
3885 size_t const cBlockSize
= ZSTDv07_getcBlockSize(ip
, iend
-ip
, &blockProperties
);
3886 if (ZSTDv07_isError(cBlockSize
)) return cBlockSize
;
3888 ip
+= ZSTDv07_blockHeaderSize
;
3889 remainingSize
-= ZSTDv07_blockHeaderSize
;
3890 if (cBlockSize
> remainingSize
) return ERROR(srcSize_wrong
);
3892 switch(blockProperties
.blockType
)
3895 decodedSize
= ZSTDv07_decompressBlock_internal(dctx
, op
, oend
-op
, ip
, cBlockSize
);
3898 decodedSize
= ZSTDv07_copyRawBlock(op
, oend
-op
, ip
, cBlockSize
);
3901 decodedSize
= ZSTDv07_generateNxBytes(op
, oend
-op
, *ip
, blockProperties
.origSize
);
3905 if (remainingSize
) return ERROR(srcSize_wrong
);
3909 return ERROR(GENERIC
); /* impossible */
3911 if (blockProperties
.blockType
== bt_end
) break; /* bt_end */
3913 if (ZSTDv07_isError(decodedSize
)) return decodedSize
;
3914 if (dctx
->fParams
.checksumFlag
) XXH64_update(&dctx
->xxhState
, op
, decodedSize
);
3917 remainingSize
-= cBlockSize
;
3924 /*! ZSTDv07_decompress_usingPreparedDCtx() :
3925 * Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
3926 * It avoids reloading the dictionary each time.
3927 * `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict().
3928 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
3929 size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx
* dctx
, const ZSTDv07_DCtx
* refDCtx
,
3930 void* dst
, size_t dstCapacity
,
3931 const void* src
, size_t srcSize
)
3933 ZSTDv07_copyDCtx(dctx
, refDCtx
);
3934 ZSTDv07_checkContinuity(dctx
, dst
);
3935 return ZSTDv07_decompressFrame(dctx
, dst
, dstCapacity
, src
, srcSize
);
3939 size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx
* dctx
,
3940 void* dst
, size_t dstCapacity
,
3941 const void* src
, size_t srcSize
,
3942 const void* dict
, size_t dictSize
)
3944 ZSTDv07_decompressBegin_usingDict(dctx
, dict
, dictSize
);
3945 ZSTDv07_checkContinuity(dctx
, dst
);
3946 return ZSTDv07_decompressFrame(dctx
, dst
, dstCapacity
, src
, srcSize
);
3950 size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3952 return ZSTDv07_decompress_usingDict(dctx
, dst
, dstCapacity
, src
, srcSize
, NULL
, 0);
3956 size_t ZSTDv07_decompress(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3958 #if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1)
3960 ZSTDv07_DCtx
* const dctx
= ZSTDv07_createDCtx();
3961 if (dctx
==NULL
) return ERROR(memory_allocation
);
3962 regenSize
= ZSTDv07_decompressDCtx(dctx
, dst
, dstCapacity
, src
, srcSize
);
3963 ZSTDv07_freeDCtx(dctx
);
3965 #else /* stack mode */
3967 return ZSTDv07_decompressDCtx(&dctx
, dst
, dstCapacity
, src
, srcSize
);
3972 /*_******************************
3973 * Streaming Decompression API
3974 ********************************/
3975 size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx
* dctx
)
3977 return dctx
->expected
;
3980 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx
* dctx
)
3982 return dctx
->stage
== ZSTDds_skipFrame
;
3985 /** ZSTDv07_decompressContinue() :
3986 * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
3987 * or an error code, which can be tested using ZSTDv07_isError() */
3988 size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3991 if (srcSize
!= dctx
->expected
) return ERROR(srcSize_wrong
);
3992 if (dstCapacity
) ZSTDv07_checkContinuity(dctx
, dst
);
3994 switch (dctx
->stage
)
3996 case ZSTDds_getFrameHeaderSize
:
3997 if (srcSize
!= ZSTDv07_frameHeaderSize_min
) return ERROR(srcSize_wrong
); /* impossible */
3998 if ((MEM_readLE32(src
) & 0xFFFFFFF0U
) == ZSTDv07_MAGIC_SKIPPABLE_START
) {
3999 memcpy(dctx
->headerBuffer
, src
, ZSTDv07_frameHeaderSize_min
);
4000 dctx
->expected
= ZSTDv07_skippableHeaderSize
- ZSTDv07_frameHeaderSize_min
; /* magic number + skippable frame length */
4001 dctx
->stage
= ZSTDds_decodeSkippableHeader
;
4004 dctx
->headerSize
= ZSTDv07_frameHeaderSize(src
, ZSTDv07_frameHeaderSize_min
);
4005 if (ZSTDv07_isError(dctx
->headerSize
)) return dctx
->headerSize
;
4006 memcpy(dctx
->headerBuffer
, src
, ZSTDv07_frameHeaderSize_min
);
4007 if (dctx
->headerSize
> ZSTDv07_frameHeaderSize_min
) {
4008 dctx
->expected
= dctx
->headerSize
- ZSTDv07_frameHeaderSize_min
;
4009 dctx
->stage
= ZSTDds_decodeFrameHeader
;
4012 dctx
->expected
= 0; /* not necessary to copy more */
4014 case ZSTDds_decodeFrameHeader
:
4016 memcpy(dctx
->headerBuffer
+ ZSTDv07_frameHeaderSize_min
, src
, dctx
->expected
);
4017 result
= ZSTDv07_decodeFrameHeader(dctx
, dctx
->headerBuffer
, dctx
->headerSize
);
4018 if (ZSTDv07_isError(result
)) return result
;
4019 dctx
->expected
= ZSTDv07_blockHeaderSize
;
4020 dctx
->stage
= ZSTDds_decodeBlockHeader
;
4023 case ZSTDds_decodeBlockHeader
:
4024 { blockProperties_t bp
;
4025 size_t const cBlockSize
= ZSTDv07_getcBlockSize(src
, ZSTDv07_blockHeaderSize
, &bp
);
4026 if (ZSTDv07_isError(cBlockSize
)) return cBlockSize
;
4027 if (bp
.blockType
== bt_end
) {
4028 if (dctx
->fParams
.checksumFlag
) {
4029 U64
const h64
= XXH64_digest(&dctx
->xxhState
);
4030 U32
const h32
= (U32
)(h64
>>11) & ((1<<22)-1);
4031 const BYTE
* const ip
= (const BYTE
*)src
;
4032 U32
const check32
= ip
[2] + (ip
[1] << 8) + ((ip
[0] & 0x3F) << 16);
4033 if (check32
!= h32
) return ERROR(checksum_wrong
);
4036 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
4038 dctx
->expected
= cBlockSize
;
4039 dctx
->bType
= bp
.blockType
;
4040 dctx
->stage
= ZSTDds_decompressBlock
;
4044 case ZSTDds_decompressBlock
:
4049 rSize
= ZSTDv07_decompressBlock_internal(dctx
, dst
, dstCapacity
, src
, srcSize
);
4052 rSize
= ZSTDv07_copyRawBlock(dst
, dstCapacity
, src
, srcSize
);
4055 return ERROR(GENERIC
); /* not yet handled */
4057 case bt_end
: /* should never happen (filtered at phase 1) */
4061 return ERROR(GENERIC
); /* impossible */
4063 dctx
->stage
= ZSTDds_decodeBlockHeader
;
4064 dctx
->expected
= ZSTDv07_blockHeaderSize
;
4065 dctx
->previousDstEnd
= (char*)dst
+ rSize
;
4066 if (ZSTDv07_isError(rSize
)) return rSize
;
4067 if (dctx
->fParams
.checksumFlag
) XXH64_update(&dctx
->xxhState
, dst
, rSize
);
4070 case ZSTDds_decodeSkippableHeader
:
4071 { memcpy(dctx
->headerBuffer
+ ZSTDv07_frameHeaderSize_min
, src
, dctx
->expected
);
4072 dctx
->expected
= MEM_readLE32(dctx
->headerBuffer
+ 4);
4073 dctx
->stage
= ZSTDds_skipFrame
;
4076 case ZSTDds_skipFrame
:
4077 { dctx
->expected
= 0;
4078 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
4082 return ERROR(GENERIC
); /* impossible */
4087 static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
)
4089 dctx
->dictEnd
= dctx
->previousDstEnd
;
4090 dctx
->vBase
= (const char*)dict
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
4092 dctx
->previousDstEnd
= (const char*)dict
+ dictSize
;
4096 static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx
* dctx
, const void* const dict
, size_t const dictSize
)
4098 const BYTE
* dictPtr
= (const BYTE
*)dict
;
4099 const BYTE
* const dictEnd
= dictPtr
+ dictSize
;
4101 { size_t const hSize
= HUFv07_readDTableX4(dctx
->hufTable
, dict
, dictSize
);
4102 if (HUFv07_isError(hSize
)) return ERROR(dictionary_corrupted
);
4106 { short offcodeNCount
[MaxOff
+1];
4107 U32 offcodeMaxValue
=MaxOff
, offcodeLog
;
4108 size_t const offcodeHeaderSize
= FSEv07_readNCount(offcodeNCount
, &offcodeMaxValue
, &offcodeLog
, dictPtr
, dictEnd
-dictPtr
);
4109 if (FSEv07_isError(offcodeHeaderSize
)) return ERROR(dictionary_corrupted
);
4110 if (offcodeLog
> OffFSELog
) return ERROR(dictionary_corrupted
);
4111 { size_t const errorCode
= FSEv07_buildDTable(dctx
->OffTable
, offcodeNCount
, offcodeMaxValue
, offcodeLog
);
4112 if (FSEv07_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
4113 dictPtr
+= offcodeHeaderSize
;
4116 { short matchlengthNCount
[MaxML
+1];
4117 unsigned matchlengthMaxValue
= MaxML
, matchlengthLog
;
4118 size_t const matchlengthHeaderSize
= FSEv07_readNCount(matchlengthNCount
, &matchlengthMaxValue
, &matchlengthLog
, dictPtr
, dictEnd
-dictPtr
);
4119 if (FSEv07_isError(matchlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
4120 if (matchlengthLog
> MLFSELog
) return ERROR(dictionary_corrupted
);
4121 { size_t const errorCode
= FSEv07_buildDTable(dctx
->MLTable
, matchlengthNCount
, matchlengthMaxValue
, matchlengthLog
);
4122 if (FSEv07_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
4123 dictPtr
+= matchlengthHeaderSize
;
4126 { short litlengthNCount
[MaxLL
+1];
4127 unsigned litlengthMaxValue
= MaxLL
, litlengthLog
;
4128 size_t const litlengthHeaderSize
= FSEv07_readNCount(litlengthNCount
, &litlengthMaxValue
, &litlengthLog
, dictPtr
, dictEnd
-dictPtr
);
4129 if (FSEv07_isError(litlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
4130 if (litlengthLog
> LLFSELog
) return ERROR(dictionary_corrupted
);
4131 { size_t const errorCode
= FSEv07_buildDTable(dctx
->LLTable
, litlengthNCount
, litlengthMaxValue
, litlengthLog
);
4132 if (FSEv07_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
4133 dictPtr
+= litlengthHeaderSize
;
4136 if (dictPtr
+12 > dictEnd
) return ERROR(dictionary_corrupted
);
4137 dctx
->rep
[0] = MEM_readLE32(dictPtr
+0); if (dctx
->rep
[0] >= dictSize
) return ERROR(dictionary_corrupted
);
4138 dctx
->rep
[1] = MEM_readLE32(dictPtr
+4); if (dctx
->rep
[1] >= dictSize
) return ERROR(dictionary_corrupted
);
4139 dctx
->rep
[2] = MEM_readLE32(dictPtr
+8); if (dctx
->rep
[2] >= dictSize
) return ERROR(dictionary_corrupted
);
4142 dctx
->litEntropy
= dctx
->fseEntropy
= 1;
4143 return dictPtr
- (const BYTE
*)dict
;
4146 static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
)
4148 if (dictSize
< 8) return ZSTDv07_refDictContent(dctx
, dict
, dictSize
);
4149 { U32
const magic
= MEM_readLE32(dict
);
4150 if (magic
!= ZSTDv07_DICT_MAGIC
) {
4151 return ZSTDv07_refDictContent(dctx
, dict
, dictSize
); /* pure content mode */
4153 dctx
->dictID
= MEM_readLE32((const char*)dict
+ 4);
4155 /* load entropy tables */
4156 dict
= (const char*)dict
+ 8;
4158 { size_t const eSize
= ZSTDv07_loadEntropy(dctx
, dict
, dictSize
);
4159 if (ZSTDv07_isError(eSize
)) return ERROR(dictionary_corrupted
);
4160 dict
= (const char*)dict
+ eSize
;
4164 /* reference dictionary content */
4165 return ZSTDv07_refDictContent(dctx
, dict
, dictSize
);
4169 size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
)
4171 { size_t const errorCode
= ZSTDv07_decompressBegin(dctx
);
4172 if (ZSTDv07_isError(errorCode
)) return errorCode
; }
4174 if (dict
&& dictSize
) {
4175 size_t const errorCode
= ZSTDv07_decompress_insertDictionary(dctx
, dict
, dictSize
);
4176 if (ZSTDv07_isError(errorCode
)) return ERROR(dictionary_corrupted
);
4183 struct ZSTDv07_DDict_s
{
4186 ZSTDv07_DCtx
* refContext
;
4187 }; /* typedef'd tp ZSTDv07_CDict within zstd.h */
4189 ZSTDv07_DDict
* ZSTDv07_createDDict_advanced(const void* dict
, size_t dictSize
, ZSTDv07_customMem customMem
)
4191 if (!customMem
.customAlloc
&& !customMem
.customFree
)
4192 customMem
= defaultCustomMem
;
4194 if (!customMem
.customAlloc
|| !customMem
.customFree
)
4197 { ZSTDv07_DDict
* const ddict
= (ZSTDv07_DDict
*) customMem
.customAlloc(customMem
.opaque
, sizeof(*ddict
));
4198 void* const dictContent
= customMem
.customAlloc(customMem
.opaque
, dictSize
);
4199 ZSTDv07_DCtx
* const dctx
= ZSTDv07_createDCtx_advanced(customMem
);
4201 if (!dictContent
|| !ddict
|| !dctx
) {
4202 customMem
.customFree(customMem
.opaque
, dictContent
);
4203 customMem
.customFree(customMem
.opaque
, ddict
);
4204 customMem
.customFree(customMem
.opaque
, dctx
);
4208 memcpy(dictContent
, dict
, dictSize
);
4209 { size_t const errorCode
= ZSTDv07_decompressBegin_usingDict(dctx
, dictContent
, dictSize
);
4210 if (ZSTDv07_isError(errorCode
)) {
4211 customMem
.customFree(customMem
.opaque
, dictContent
);
4212 customMem
.customFree(customMem
.opaque
, ddict
);
4213 customMem
.customFree(customMem
.opaque
, dctx
);
4217 ddict
->dict
= dictContent
;
4218 ddict
->dictSize
= dictSize
;
4219 ddict
->refContext
= dctx
;
4224 /*! ZSTDv07_createDDict() :
4225 * Create a digested dictionary, ready to start decompression without startup delay.
4226 * `dict` can be released after `ZSTDv07_DDict` creation */
4227 ZSTDv07_DDict
* ZSTDv07_createDDict(const void* dict
, size_t dictSize
)
4229 ZSTDv07_customMem
const allocator
= { NULL
, NULL
, NULL
};
4230 return ZSTDv07_createDDict_advanced(dict
, dictSize
, allocator
);
4233 size_t ZSTDv07_freeDDict(ZSTDv07_DDict
* ddict
)
4235 ZSTDv07_freeFunction
const cFree
= ddict
->refContext
->customMem
.customFree
;
4236 void* const opaque
= ddict
->refContext
->customMem
.opaque
;
4237 ZSTDv07_freeDCtx(ddict
->refContext
);
4238 cFree(opaque
, ddict
->dict
);
4239 cFree(opaque
, ddict
);
4243 /*! ZSTDv07_decompress_usingDDict() :
4244 * Decompression using a pre-digested Dictionary
4245 * Use dictionary without significant overhead. */
4246 ZSTDLIBv07_API
size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx
* dctx
,
4247 void* dst
, size_t dstCapacity
,
4248 const void* src
, size_t srcSize
,
4249 const ZSTDv07_DDict
* ddict
)
4251 return ZSTDv07_decompress_usingPreparedDCtx(dctx
, ddict
->refContext
,
4256 Buffered version of Zstd compression library
4257 Copyright (C) 2015-2016, Yann Collet.
4259 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
4261 Redistribution and use in source and binary forms, with or without
4262 modification, are permitted provided that the following conditions are
4264 * Redistributions of source code must retain the above copyright
4265 notice, this list of conditions and the following disclaimer.
4266 * Redistributions in binary form must reproduce the above
4267 copyright notice, this list of conditions and the following disclaimer
4268 in the documentation and/or other materials provided with the
4270 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4271 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
4272 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
4273 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
4274 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4275 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
4276 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
4277 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
4278 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
4279 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
4280 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4282 You can contact the author at :
4283 - zstd homepage : http://www.zstd.net/
4288 /*-***************************************************************************
4289 * Streaming decompression howto
4291 * A ZBUFFv07_DCtx object is required to track streaming operations.
4292 * Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources.
4293 * Use ZBUFFv07_decompressInit() to start a new decompression operation,
4294 * or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary.
4295 * Note that ZBUFFv07_DCtx objects can be re-init multiple times.
4297 * Use ZBUFFv07_decompressContinue() repetitively to consume your input.
4298 * *srcSizePtr and *dstCapacityPtr can be any size.
4299 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
4300 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
4301 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
4302 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
4303 * or 0 when a frame is completely decoded,
4304 * or an error code, which can be tested using ZBUFFv07_isError().
4306 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize()
4307 * output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
4308 * input : ZBUFFv07_recommendedDInSize == 128KB + 3;
4309 * just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
4310 * *******************************************************************************/
4312 typedef enum { ZBUFFds_init
, ZBUFFds_loadHeader
,
4313 ZBUFFds_read
, ZBUFFds_load
, ZBUFFds_flush
} ZBUFFv07_dStage
;
4315 /* *** Resource management *** */
4316 struct ZBUFFv07_DCtx_s
{
4318 ZSTDv07_frameParams fParams
;
4319 ZBUFFv07_dStage stage
;
4328 BYTE headerBuffer
[ZSTDv07_FRAMEHEADERSIZE_MAX
];
4330 ZSTDv07_customMem customMem
;
4331 }; /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */
4333 ZSTDLIBv07_API ZBUFFv07_DCtx
* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem
);
4335 ZBUFFv07_DCtx
* ZBUFFv07_createDCtx(void)
4337 return ZBUFFv07_createDCtx_advanced(defaultCustomMem
);
4340 ZBUFFv07_DCtx
* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem
)
4344 if (!customMem
.customAlloc
&& !customMem
.customFree
)
4345 customMem
= defaultCustomMem
;
4347 if (!customMem
.customAlloc
|| !customMem
.customFree
)
4350 zbd
= (ZBUFFv07_DCtx
*)customMem
.customAlloc(customMem
.opaque
, sizeof(ZBUFFv07_DCtx
));
4351 if (zbd
==NULL
) return NULL
;
4352 memset(zbd
, 0, sizeof(ZBUFFv07_DCtx
));
4353 memcpy(&zbd
->customMem
, &customMem
, sizeof(ZSTDv07_customMem
));
4354 zbd
->zd
= ZSTDv07_createDCtx_advanced(customMem
);
4355 if (zbd
->zd
== NULL
) { ZBUFFv07_freeDCtx(zbd
); return NULL
; }
4356 zbd
->stage
= ZBUFFds_init
;
4360 size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx
* zbd
)
4362 if (zbd
==NULL
) return 0; /* support free on null */
4363 ZSTDv07_freeDCtx(zbd
->zd
);
4364 if (zbd
->inBuff
) zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->inBuff
);
4365 if (zbd
->outBuff
) zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->outBuff
);
4366 zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
);
4371 /* *** Initialization *** */
4373 size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx
* zbd
, const void* dict
, size_t dictSize
)
4375 zbd
->stage
= ZBUFFds_loadHeader
;
4376 zbd
->lhSize
= zbd
->inPos
= zbd
->outStart
= zbd
->outEnd
= 0;
4377 return ZSTDv07_decompressBegin_usingDict(zbd
->zd
, dict
, dictSize
);
4380 size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx
* zbd
)
4382 return ZBUFFv07_decompressInitDictionary(zbd
, NULL
, 0);
4386 /* internal util function */
4387 MEM_STATIC
size_t ZBUFFv07_limitCopy(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
4389 size_t const length
= MIN(dstCapacity
, srcSize
);
4390 memcpy(dst
, src
, length
);
4395 /* *** Decompression *** */
4397 size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx
* zbd
,
4398 void* dst
, size_t* dstCapacityPtr
,
4399 const void* src
, size_t* srcSizePtr
)
4401 const char* const istart
= (const char*)src
;
4402 const char* const iend
= istart
+ *srcSizePtr
;
4403 const char* ip
= istart
;
4404 char* const ostart
= (char*)dst
;
4405 char* const oend
= ostart
+ *dstCapacityPtr
;
4413 return ERROR(init_missing
);
4415 case ZBUFFds_loadHeader
:
4416 { size_t const hSize
= ZSTDv07_getFrameParams(&(zbd
->fParams
), zbd
->headerBuffer
, zbd
->lhSize
);
4417 if (ZSTDv07_isError(hSize
)) return hSize
;
4419 size_t const toLoad
= hSize
- zbd
->lhSize
; /* if hSize!=0, hSize > zbd->lhSize */
4420 if (toLoad
> (size_t)(iend
-ip
)) { /* not enough input to load full header */
4421 memcpy(zbd
->headerBuffer
+ zbd
->lhSize
, ip
, iend
-ip
);
4422 zbd
->lhSize
+= iend
-ip
;
4423 *dstCapacityPtr
= 0;
4424 return (hSize
- zbd
->lhSize
) + ZSTDv07_blockHeaderSize
; /* remaining header bytes + next block header */
4426 memcpy(zbd
->headerBuffer
+ zbd
->lhSize
, ip
, toLoad
); zbd
->lhSize
= hSize
; ip
+= toLoad
;
4430 /* Consume header */
4431 { size_t const h1Size
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
); /* == ZSTDv07_frameHeaderSize_min */
4432 size_t const h1Result
= ZSTDv07_decompressContinue(zbd
->zd
, NULL
, 0, zbd
->headerBuffer
, h1Size
);
4433 if (ZSTDv07_isError(h1Result
)) return h1Result
;
4434 if (h1Size
< zbd
->lhSize
) { /* long header */
4435 size_t const h2Size
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4436 size_t const h2Result
= ZSTDv07_decompressContinue(zbd
->zd
, NULL
, 0, zbd
->headerBuffer
+h1Size
, h2Size
);
4437 if (ZSTDv07_isError(h2Result
)) return h2Result
;
4440 zbd
->fParams
.windowSize
= MAX(zbd
->fParams
.windowSize
, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN
);
4442 /* Frame header instruct buffer sizes */
4443 { size_t const blockSize
= MIN(zbd
->fParams
.windowSize
, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
);
4444 zbd
->blockSize
= blockSize
;
4445 if (zbd
->inBuffSize
< blockSize
) {
4446 zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->inBuff
);
4447 zbd
->inBuffSize
= blockSize
;
4448 zbd
->inBuff
= (char*)zbd
->customMem
.customAlloc(zbd
->customMem
.opaque
, blockSize
);
4449 if (zbd
->inBuff
== NULL
) return ERROR(memory_allocation
);
4451 { size_t const neededOutSize
= zbd
->fParams
.windowSize
+ blockSize
;
4452 if (zbd
->outBuffSize
< neededOutSize
) {
4453 zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->outBuff
);
4454 zbd
->outBuffSize
= neededOutSize
;
4455 zbd
->outBuff
= (char*)zbd
->customMem
.customAlloc(zbd
->customMem
.opaque
, neededOutSize
);
4456 if (zbd
->outBuff
== NULL
) return ERROR(memory_allocation
);
4458 zbd
->stage
= ZBUFFds_read
;
4462 { size_t const neededInSize
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4463 if (neededInSize
==0) { /* end of frame */
4464 zbd
->stage
= ZBUFFds_init
;
4468 if ((size_t)(iend
-ip
) >= neededInSize
) { /* decode directly from src */
4469 const int isSkipFrame
= ZSTDv07_isSkipFrame(zbd
->zd
);
4470 size_t const decodedSize
= ZSTDv07_decompressContinue(zbd
->zd
,
4471 zbd
->outBuff
+ zbd
->outStart
, (isSkipFrame
? 0 : zbd
->outBuffSize
- zbd
->outStart
),
4473 if (ZSTDv07_isError(decodedSize
)) return decodedSize
;
4475 if (!decodedSize
&& !isSkipFrame
) break; /* this was just a header */
4476 zbd
->outEnd
= zbd
->outStart
+ decodedSize
;
4477 zbd
->stage
= ZBUFFds_flush
;
4480 if (ip
==iend
) { notDone
= 0; break; } /* no more input */
4481 zbd
->stage
= ZBUFFds_load
;
4485 { size_t const neededInSize
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4486 size_t const toLoad
= neededInSize
- zbd
->inPos
; /* should always be <= remaining space within inBuff */
4488 if (toLoad
> zbd
->inBuffSize
- zbd
->inPos
) return ERROR(corruption_detected
); /* should never happen */
4489 loadedSize
= ZBUFFv07_limitCopy(zbd
->inBuff
+ zbd
->inPos
, toLoad
, ip
, iend
-ip
);
4491 zbd
->inPos
+= loadedSize
;
4492 if (loadedSize
< toLoad
) { notDone
= 0; break; } /* not enough input, wait for more */
4494 /* decode loaded input */
4495 { const int isSkipFrame
= ZSTDv07_isSkipFrame(zbd
->zd
);
4496 size_t const decodedSize
= ZSTDv07_decompressContinue(zbd
->zd
,
4497 zbd
->outBuff
+ zbd
->outStart
, zbd
->outBuffSize
- zbd
->outStart
,
4498 zbd
->inBuff
, neededInSize
);
4499 if (ZSTDv07_isError(decodedSize
)) return decodedSize
;
4500 zbd
->inPos
= 0; /* input is consumed */
4501 if (!decodedSize
&& !isSkipFrame
) { zbd
->stage
= ZBUFFds_read
; break; } /* this was just a header */
4502 zbd
->outEnd
= zbd
->outStart
+ decodedSize
;
4503 zbd
->stage
= ZBUFFds_flush
;
4504 // break; /* ZBUFFds_flush follows */
4508 { size_t const toFlushSize
= zbd
->outEnd
- zbd
->outStart
;
4509 size_t const flushedSize
= ZBUFFv07_limitCopy(op
, oend
-op
, zbd
->outBuff
+ zbd
->outStart
, toFlushSize
);
4511 zbd
->outStart
+= flushedSize
;
4512 if (flushedSize
== toFlushSize
) {
4513 zbd
->stage
= ZBUFFds_read
;
4514 if (zbd
->outStart
+ zbd
->blockSize
> zbd
->outBuffSize
)
4515 zbd
->outStart
= zbd
->outEnd
= 0;
4518 /* cannot flush everything */
4522 default: return ERROR(GENERIC
); /* impossible */
4526 *srcSizePtr
= ip
-istart
;
4527 *dstCapacityPtr
= op
-ostart
;
4528 { size_t nextSrcSizeHint
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4529 nextSrcSizeHint
-= zbd
->inPos
; /* already loaded*/
4530 return nextSrcSizeHint
;
4536 /* *************************************
4538 ***************************************/
4539 size_t ZBUFFv07_recommendedDInSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
+ ZSTDv07_blockHeaderSize
/* block header size*/ ; }
4540 size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
; }