2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
13 #include <stddef.h> /* size_t, ptrdiff_t */
14 #include <string.h> /* memcpy */
15 #include <stdlib.h> /* malloc, free, qsort */
17 #ifndef XXH_STATIC_LINKING_ONLY
18 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
20 #include "xxhash.h" /* XXH64_* */
23 #define FSEv07_STATIC_LINKING_ONLY /* FSEv07_MIN_TABLELOG */
24 #define HUFv07_STATIC_LINKING_ONLY /* HUFv07_TABLELOG_ABSOLUTEMAX */
25 #define ZSTDv07_STATIC_LINKING_ONLY
27 #include "error_private.h"
30 #ifdef ZSTDv07_STATIC_LINKING_ONLY
32 /* ====================================================================================
33 * The definitions in this section are considered experimental.
34 * They should never be used with a dynamic library, as they may change in the future.
35 * They are provided for advanced usages.
36 * Use them only in association with static linking.
37 * ==================================================================================== */
40 #define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U
42 #define ZSTDv07_WINDOWLOG_MAX_32 25
43 #define ZSTDv07_WINDOWLOG_MAX_64 27
44 #define ZSTDv07_WINDOWLOG_MAX ((U32)(MEM_32bits() ? ZSTDv07_WINDOWLOG_MAX_32 : ZSTDv07_WINDOWLOG_MAX_64))
45 #define ZSTDv07_WINDOWLOG_MIN 18
46 #define ZSTDv07_CHAINLOG_MAX (ZSTDv07_WINDOWLOG_MAX+1)
47 #define ZSTDv07_CHAINLOG_MIN 4
48 #define ZSTDv07_HASHLOG_MAX ZSTDv07_WINDOWLOG_MAX
49 #define ZSTDv07_HASHLOG_MIN 12
50 #define ZSTDv07_HASHLOG3_MAX 17
51 #define ZSTDv07_SEARCHLOG_MAX (ZSTDv07_WINDOWLOG_MAX-1)
52 #define ZSTDv07_SEARCHLOG_MIN 1
53 #define ZSTDv07_SEARCHLENGTH_MAX 7
54 #define ZSTDv07_SEARCHLENGTH_MIN 3
55 #define ZSTDv07_TARGETLENGTH_MIN 4
56 #define ZSTDv07_TARGETLENGTH_MAX 999
58 #define ZSTDv07_FRAMEHEADERSIZE_MAX 18 /* for static allocation */
59 static const size_t ZSTDv07_frameHeaderSize_min
= 5;
60 static const size_t ZSTDv07_frameHeaderSize_max
= ZSTDv07_FRAMEHEADERSIZE_MAX
;
61 static const size_t ZSTDv07_skippableHeaderSize
= 8; /* magic number + skippable frame length */
64 /* custom memory allocation functions */
65 typedef void* (*ZSTDv07_allocFunction
) (void* opaque
, size_t size
);
66 typedef void (*ZSTDv07_freeFunction
) (void* opaque
, void* address
);
67 typedef struct { ZSTDv07_allocFunction customAlloc
; ZSTDv07_freeFunction customFree
; void* opaque
; } ZSTDv07_customMem
;
70 /*--- Advanced Decompression functions ---*/
72 /*! ZSTDv07_estimateDCtxSize() :
73 * Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */
74 ZSTDLIBv07_API
size_t ZSTDv07_estimateDCtxSize(void);
76 /*! ZSTDv07_createDCtx_advanced() :
77 * Create a ZSTD decompression context using external alloc and free functions */
78 ZSTDLIBv07_API ZSTDv07_DCtx
* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem
);
80 /*! ZSTDv07_sizeofDCtx() :
81 * Gives the amount of memory used by a given ZSTDv07_DCtx */
82 ZSTDLIBv07_API
size_t ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx
* dctx
);
85 /* ******************************************************************
86 * Buffer-less streaming functions (synchronous mode)
87 ********************************************************************/
89 ZSTDLIBv07_API
size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx
* dctx
);
90 ZSTDLIBv07_API
size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
);
91 ZSTDLIBv07_API
void ZSTDv07_copyDCtx(ZSTDv07_DCtx
* dctx
, const ZSTDv07_DCtx
* preparedDCtx
);
93 ZSTDLIBv07_API
size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx
* dctx
);
94 ZSTDLIBv07_API
size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
);
97 Buffer-less streaming decompression (synchronous mode)
99 A ZSTDv07_DCtx object is required to track streaming operations.
100 Use ZSTDv07_createDCtx() / ZSTDv07_freeDCtx() to manage it.
101 A ZSTDv07_DCtx object can be re-used multiple times.
103 First optional operation is to retrieve frame parameters, using ZSTDv07_getFrameParams(), which doesn't consume the input.
104 It can provide the minimum size of rolling buffer required to properly decompress data (`windowSize`),
105 and optionally the final size of uncompressed content.
106 (Note : content size is an optional info that may not be present. 0 means : content size unknown)
107 Frame parameters are extracted from the beginning of compressed frame.
108 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)
109 If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
110 Result : 0 when successful, it means the ZSTDv07_frameParams structure has been filled.
111 >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
112 errorCode, which can be tested using ZSTDv07_isError()
114 Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().
115 Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().
117 Then use ZSTDv07_nextSrcSizeToDecompress() and ZSTDv07_decompressContinue() alternatively.
118 ZSTDv07_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv07_decompressContinue().
119 ZSTDv07_decompressContinue() requires this exact amount of bytes, or it will fail.
121 @result of ZSTDv07_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity).
122 It can be zero, which is not an error; it just means ZSTDv07_decompressContinue() has decoded some header.
124 ZSTDv07_decompressContinue() needs previous data blocks during decompression, up to `windowSize`.
125 They should preferably be located contiguously, prior to current block.
126 Alternatively, a round buffer of sufficient size is also possible. Sufficient size is determined by frame parameters.
127 ZSTDv07_decompressContinue() is very sensitive to contiguity,
128 if 2 blocks don't follow each other, make sure that either the compressor breaks contiguity at the same place,
129 or that previous contiguous segment is large enough to properly handle maximum back-reference.
131 A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.
132 Context can then be reset to start a new decompression.
135 == Special case : skippable frames ==
137 Skippable frames allow the integration of user-defined data into a flow of concatenated frames.
138 Skippable frames will be ignored (skipped) by a decompressor. The format of skippable frame is following:
139 a) Skippable frame ID - 4 Bytes, Little endian format, any value from 0x184D2A50 to 0x184D2A5F
140 b) Frame Size - 4 Bytes, Little endian format, unsigned 32-bits
141 c) Frame Content - any content (User Data) of length equal to Frame Size
142 For skippable frames ZSTDv07_decompressContinue() always returns 0.
143 For skippable frames ZSTDv07_getFrameParams() returns fparamsPtr->windowLog==0 what means that a frame is skippable.
144 It also returns Frame Size as fparamsPtr->frameContentSize.
148 /* **************************************
150 ****************************************/
151 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
152 Frame metadata cost is typically ~18 bytes, which can be non-negligible for very small blocks (< 100 bytes).
153 User will have to take in charge required information to regenerate data, such as compressed and content sizes.
155 A few rules to respect :
156 - Compressing and decompressing require a context structure
157 + Use ZSTDv07_createCCtx() and ZSTDv07_createDCtx()
158 - It is necessary to init context before starting
159 + compression : ZSTDv07_compressBegin()
160 + decompression : ZSTDv07_decompressBegin()
161 + variants _usingDict() are also allowed
162 + copyCCtx() and copyDCtx() work too
163 - Block size is limited, it must be <= ZSTDv07_getBlockSizeMax()
164 + If you need to compress more, cut data into multiple blocks
165 + Consider using the regular ZSTDv07_compress() instead, as frame metadata costs become negligible when source size is large.
166 - When a block is considered not compressible enough, ZSTDv07_compressBlock() result will be zero.
167 In which case, nothing is produced into `dst`.
168 + User must test for such outcome and deal directly with uncompressed data
169 + ZSTDv07_decompressBlock() doesn't accept uncompressed data as input !!!
170 + In case of multiple successive blocks, decoder must be informed of uncompressed block existence to follow proper history.
171 Use ZSTDv07_insertBlock() in such a case.
174 #define ZSTDv07_BLOCKSIZE_ABSOLUTEMAX (128 * 1024) /* define, for static allocation */
175 ZSTDLIBv07_API
size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
);
176 ZSTDLIBv07_API
size_t ZSTDv07_insertBlock(ZSTDv07_DCtx
* dctx
, const void* blockStart
, size_t blockSize
); /**< insert block into `dctx` history. Useful for uncompressed blocks */
179 #endif /* ZSTDv07_STATIC_LINKING_ONLY */
182 /* ******************************************************************
184 low-level memory access routines
185 Copyright (C) 2013-2015, Yann Collet.
187 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
189 Redistribution and use in source and binary forms, with or without
190 modification, are permitted provided that the following conditions are
193 * Redistributions of source code must retain the above copyright
194 notice, this list of conditions and the following disclaimer.
195 * Redistributions in binary form must reproduce the above
196 copyright notice, this list of conditions and the following disclaimer
197 in the documentation and/or other materials provided with the
200 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
201 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
202 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
203 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
204 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
205 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
206 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
207 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
208 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
209 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
210 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
212 You can contact the author at :
213 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
214 - Public forum : https://groups.google.com/forum/#!forum/lz4c
215 ****************************************************************** */
219 #if defined (__cplusplus)
223 /*-****************************************
225 ******************************************/
226 #if defined(_MSC_VER) /* Visual Studio */
227 # include <stdlib.h> /* _byteswap_ulong */
228 # include <intrin.h> /* _byteswap_* */
230 #if defined(__GNUC__)
231 # define MEM_STATIC static __attribute__((unused))
232 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
233 # define MEM_STATIC static inline
234 #elif defined(_MSC_VER)
235 # define MEM_STATIC static __inline
237 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
241 /*-**************************************************************
243 *****************************************************************/
244 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
246 typedef uint8_t BYTE
;
247 typedef uint16_t U16
;
249 typedef uint32_t U32
;
251 typedef uint64_t U64
;
254 typedef unsigned char BYTE
;
255 typedef unsigned short U16
;
256 typedef signed short S16
;
257 typedef unsigned int U32
;
258 typedef signed int S32
;
259 typedef unsigned long long U64
;
260 typedef signed long long S64
;
264 /*-**************************************************************
266 *****************************************************************/
267 /* MEM_FORCE_MEMORY_ACCESS :
268 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
269 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
270 * The below switch allow to select different access method for improved performance.
271 * Method 0 (default) : use `memcpy()`. Safe and portable.
272 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
273 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
274 * Method 2 : direct access. This method is portable but violate C standard.
275 * It can generate buggy code on targets depending on alignment.
276 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
277 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
278 * Prefer these methods in priority order (0 > 1 > 2)
280 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
281 # 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__) )
282 # define MEM_FORCE_MEMORY_ACCESS 2
283 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
284 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
285 # define MEM_FORCE_MEMORY_ACCESS 1
289 MEM_STATIC
unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
290 MEM_STATIC
unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
292 MEM_STATIC
unsigned MEM_isLittleEndian(void)
294 const union { U32 u
; BYTE c
[4]; } one
= { 1 }; /* don't use static : performance detrimental */
298 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
300 /* violates C standard, by lying on structure alignment.
301 Only use if no other choice to achieve best performance on target platform */
302 MEM_STATIC U16
MEM_read16(const void* memPtr
) { return *(const U16
*) memPtr
; }
303 MEM_STATIC U32
MEM_read32(const void* memPtr
) { return *(const U32
*) memPtr
; }
304 MEM_STATIC U64
MEM_read64(const void* memPtr
) { return *(const U64
*) memPtr
; }
306 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { *(U16
*)memPtr
= value
; }
308 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
310 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
311 /* currently only defined for gcc and icc */
312 typedef union { U16 u16
; U32 u32
; U64 u64
; size_t st
; } __attribute__((packed
)) unalign
;
314 MEM_STATIC U16
MEM_read16(const void* ptr
) { return ((const unalign
*)ptr
)->u16
; }
315 MEM_STATIC U32
MEM_read32(const void* ptr
) { return ((const unalign
*)ptr
)->u32
; }
316 MEM_STATIC U64
MEM_read64(const void* ptr
) { return ((const unalign
*)ptr
)->u64
; }
318 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { ((unalign
*)memPtr
)->u16
= value
; }
322 /* default method, safe and standard.
323 can sometimes prove slower */
325 MEM_STATIC U16
MEM_read16(const void* memPtr
)
327 U16 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
330 MEM_STATIC U32
MEM_read32(const void* memPtr
)
332 U32 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
335 MEM_STATIC U64
MEM_read64(const void* memPtr
)
337 U64 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
340 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
)
342 memcpy(memPtr
, &value
, sizeof(value
));
345 #endif /* MEM_FORCE_MEMORY_ACCESS */
347 MEM_STATIC U32
MEM_swap32(U32 in
)
349 #if defined(_MSC_VER) /* Visual Studio */
350 return _byteswap_ulong(in
);
351 #elif defined (__GNUC__)
352 return __builtin_bswap32(in
);
354 return ((in
<< 24) & 0xff000000 ) |
355 ((in
<< 8) & 0x00ff0000 ) |
356 ((in
>> 8) & 0x0000ff00 ) |
357 ((in
>> 24) & 0x000000ff );
361 MEM_STATIC U64
MEM_swap64(U64 in
)
363 #if defined(_MSC_VER) /* Visual Studio */
364 return _byteswap_uint64(in
);
365 #elif defined (__GNUC__)
366 return __builtin_bswap64(in
);
368 return ((in
<< 56) & 0xff00000000000000ULL
) |
369 ((in
<< 40) & 0x00ff000000000000ULL
) |
370 ((in
<< 24) & 0x0000ff0000000000ULL
) |
371 ((in
<< 8) & 0x000000ff00000000ULL
) |
372 ((in
>> 8) & 0x00000000ff000000ULL
) |
373 ((in
>> 24) & 0x0000000000ff0000ULL
) |
374 ((in
>> 40) & 0x000000000000ff00ULL
) |
375 ((in
>> 56) & 0x00000000000000ffULL
);
380 /*=== Little endian r/w ===*/
382 MEM_STATIC U16
MEM_readLE16(const void* memPtr
)
384 if (MEM_isLittleEndian())
385 return MEM_read16(memPtr
);
387 const BYTE
* p
= (const BYTE
*)memPtr
;
388 return (U16
)(p
[0] + (p
[1]<<8));
392 MEM_STATIC
void MEM_writeLE16(void* memPtr
, U16 val
)
394 if (MEM_isLittleEndian()) {
395 MEM_write16(memPtr
, val
);
397 BYTE
* p
= (BYTE
*)memPtr
;
399 p
[1] = (BYTE
)(val
>>8);
403 MEM_STATIC U32
MEM_readLE32(const void* memPtr
)
405 if (MEM_isLittleEndian())
406 return MEM_read32(memPtr
);
408 return MEM_swap32(MEM_read32(memPtr
));
412 MEM_STATIC U64
MEM_readLE64(const void* memPtr
)
414 if (MEM_isLittleEndian())
415 return MEM_read64(memPtr
);
417 return MEM_swap64(MEM_read64(memPtr
));
420 MEM_STATIC
size_t MEM_readLEST(const void* memPtr
)
423 return (size_t)MEM_readLE32(memPtr
);
425 return (size_t)MEM_readLE64(memPtr
);
430 #if defined (__cplusplus)
434 #endif /* MEM_H_MODULE */
435 /* ******************************************************************
438 header file (to include)
439 Copyright (C) 2013-2016, Yann Collet.
441 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
443 Redistribution and use in source and binary forms, with or without
444 modification, are permitted provided that the following conditions are
447 * Redistributions of source code must retain the above copyright
448 notice, this list of conditions and the following disclaimer.
449 * Redistributions in binary form must reproduce the above
450 copyright notice, this list of conditions and the following disclaimer
451 in the documentation and/or other materials provided with the
454 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
455 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
456 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
457 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
458 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
459 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
460 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
461 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
462 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
463 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
464 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
466 You can contact the author at :
467 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
468 ****************************************************************** */
469 #ifndef BITSTREAM_H_MODULE
470 #define BITSTREAM_H_MODULE
472 #if defined (__cplusplus)
478 * This API consists of small unitary functions, which must be inlined for best performance.
479 * Since link-time-optimization is not available for all compilers,
480 * these functions are defined into a .h to be included.
484 /*=========================================
486 =========================================*/
487 #if defined(__BMI__) && defined(__GNUC__)
488 # include <immintrin.h> /* support for bextr (experimental) */
491 /*-********************************************
492 * bitStream decoding API (read backward)
493 **********************************************/
497 unsigned bitsConsumed
;
502 typedef enum { BITv07_DStream_unfinished
= 0,
503 BITv07_DStream_endOfBuffer
= 1,
504 BITv07_DStream_completed
= 2,
505 BITv07_DStream_overflow
= 3 } BITv07_DStream_status
; /* result of BITv07_reloadDStream() */
506 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
508 MEM_STATIC
size_t BITv07_initDStream(BITv07_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
);
509 MEM_STATIC
size_t BITv07_readBits(BITv07_DStream_t
* bitD
, unsigned nbBits
);
510 MEM_STATIC BITv07_DStream_status
BITv07_reloadDStream(BITv07_DStream_t
* bitD
);
511 MEM_STATIC
unsigned BITv07_endOfDStream(const BITv07_DStream_t
* bitD
);
514 /* Start by invoking BITv07_initDStream().
515 * A chunk of the bitStream is then stored into a local register.
516 * Local register size is 64-bits on 64-bits systems, 32-bits on 32-bits systems (size_t).
517 * You can then retrieve bitFields stored into the local register, **in reverse order**.
518 * Local register is explicitly reloaded from memory by the BITv07_reloadDStream() method.
519 * A reload guarantee a minimum of ((8*sizeof(bitD->bitContainer))-7) bits when its result is BITv07_DStream_unfinished.
520 * Otherwise, it can be less than that, so proceed accordingly.
521 * Checking if DStream has reached its end can be performed with BITv07_endOfDStream().
525 /*-****************************************
527 ******************************************/
528 MEM_STATIC
size_t BITv07_readBitsFast(BITv07_DStream_t
* bitD
, unsigned nbBits
);
529 /* faster, but works only if nbBits >= 1 */
533 /*-**************************************************************
535 ****************************************************************/
536 MEM_STATIC
unsigned BITv07_highbit32 (register U32 val
)
538 # if defined(_MSC_VER) /* Visual */
540 _BitScanReverse ( &r
, val
);
542 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
543 return 31 - __builtin_clz (val
);
544 # else /* Software version */
545 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 };
552 return DeBruijnClz
[ (U32
) (v
* 0x07C4ACDDU
) >> 27];
558 /*-********************************************************
560 **********************************************************/
561 /*! BITv07_initDStream() :
562 * Initialize a BITv07_DStream_t.
563 * `bitD` : a pointer to an already allocated BITv07_DStream_t structure.
564 * `srcSize` must be the *exact* size of the bitStream, in bytes.
565 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
567 MEM_STATIC
size_t BITv07_initDStream(BITv07_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
)
569 if (srcSize
< 1) { memset(bitD
, 0, sizeof(*bitD
)); return ERROR(srcSize_wrong
); }
571 if (srcSize
>= sizeof(bitD
->bitContainer
)) { /* normal case */
572 bitD
->start
= (const char*)srcBuffer
;
573 bitD
->ptr
= (const char*)srcBuffer
+ srcSize
- sizeof(bitD
->bitContainer
);
574 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
575 { BYTE
const lastByte
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
576 bitD
->bitsConsumed
= lastByte
? 8 - BITv07_highbit32(lastByte
) : 0;
577 if (lastByte
== 0) return ERROR(GENERIC
); /* endMark not present */ }
579 bitD
->start
= (const char*)srcBuffer
;
580 bitD
->ptr
= bitD
->start
;
581 bitD
->bitContainer
= *(const BYTE
*)(bitD
->start
);
584 case 7: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[6]) << (sizeof(bitD
->bitContainer
)*8 - 16);/* fall-through */
585 case 6: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[5]) << (sizeof(bitD
->bitContainer
)*8 - 24);/* fall-through */
586 case 5: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[4]) << (sizeof(bitD
->bitContainer
)*8 - 32);/* fall-through */
587 case 4: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[3]) << 24; /* fall-through */
588 case 3: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[2]) << 16; /* fall-through */
589 case 2: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(srcBuffer
))[1]) << 8; /* fall-through */
592 { BYTE
const lastByte
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
593 bitD
->bitsConsumed
= lastByte
? 8 - BITv07_highbit32(lastByte
) : 0;
594 if (lastByte
== 0) return ERROR(GENERIC
); /* endMark not present */ }
595 bitD
->bitsConsumed
+= (U32
)(sizeof(bitD
->bitContainer
) - srcSize
)*8;
602 /*! BITv07_lookBits() :
603 * Provides next n bits from local register.
604 * local register is not modified.
605 * On 32-bits, maxNbBits==24.
606 * On 64-bits, maxNbBits==56.
607 * @return : value extracted
609 MEM_STATIC
size_t BITv07_lookBits(const BITv07_DStream_t
* bitD
, U32 nbBits
)
611 U32
const bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
612 return ((bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> 1) >> ((bitMask
-nbBits
) & bitMask
);
615 /*! BITv07_lookBitsFast() :
616 * unsafe version; only works only if nbBits >= 1 */
617 MEM_STATIC
size_t BITv07_lookBitsFast(const BITv07_DStream_t
* bitD
, U32 nbBits
)
619 U32
const bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
620 return (bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> (((bitMask
+1)-nbBits
) & bitMask
);
623 MEM_STATIC
void BITv07_skipBits(BITv07_DStream_t
* bitD
, U32 nbBits
)
625 bitD
->bitsConsumed
+= nbBits
;
628 /*! BITv07_readBits() :
629 * Read (consume) next n bits from local register and update.
630 * Pay attention to not read more than nbBits contained into local register.
631 * @return : extracted value.
633 MEM_STATIC
size_t BITv07_readBits(BITv07_DStream_t
* bitD
, U32 nbBits
)
635 size_t const value
= BITv07_lookBits(bitD
, nbBits
);
636 BITv07_skipBits(bitD
, nbBits
);
640 /*! BITv07_readBitsFast() :
641 * unsafe version; only works only if nbBits >= 1 */
642 MEM_STATIC
size_t BITv07_readBitsFast(BITv07_DStream_t
* bitD
, U32 nbBits
)
644 size_t const value
= BITv07_lookBitsFast(bitD
, nbBits
);
645 BITv07_skipBits(bitD
, nbBits
);
649 /*! BITv07_reloadDStream() :
650 * Refill `BITv07_DStream_t` from src buffer previously defined (see BITv07_initDStream() ).
651 * This function is safe, it guarantees it will not read beyond src buffer.
652 * @return : status of `BITv07_DStream_t` internal register.
653 if status == unfinished, internal register is filled with >= (sizeof(bitD->bitContainer)*8 - 7) bits */
654 MEM_STATIC BITv07_DStream_status
BITv07_reloadDStream(BITv07_DStream_t
* bitD
)
656 if (bitD
->bitsConsumed
> (sizeof(bitD
->bitContainer
)*8)) /* should not happen => corruption detected */
657 return BITv07_DStream_overflow
;
659 if (bitD
->ptr
>= bitD
->start
+ sizeof(bitD
->bitContainer
)) {
660 bitD
->ptr
-= bitD
->bitsConsumed
>> 3;
661 bitD
->bitsConsumed
&= 7;
662 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
663 return BITv07_DStream_unfinished
;
665 if (bitD
->ptr
== bitD
->start
) {
666 if (bitD
->bitsConsumed
< sizeof(bitD
->bitContainer
)*8) return BITv07_DStream_endOfBuffer
;
667 return BITv07_DStream_completed
;
669 { U32 nbBytes
= bitD
->bitsConsumed
>> 3;
670 BITv07_DStream_status result
= BITv07_DStream_unfinished
;
671 if (bitD
->ptr
- nbBytes
< bitD
->start
) {
672 nbBytes
= (U32
)(bitD
->ptr
- bitD
->start
); /* ptr > start */
673 result
= BITv07_DStream_endOfBuffer
;
675 bitD
->ptr
-= nbBytes
;
676 bitD
->bitsConsumed
-= nbBytes
*8;
677 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
); /* reminder : srcSize > sizeof(bitD) */
682 /*! BITv07_endOfDStream() :
683 * @return Tells if DStream has exactly reached its end (all bits consumed).
685 MEM_STATIC
unsigned BITv07_endOfDStream(const BITv07_DStream_t
* DStream
)
687 return ((DStream
->ptr
== DStream
->start
) && (DStream
->bitsConsumed
== sizeof(DStream
->bitContainer
)*8));
690 #if defined (__cplusplus)
694 #endif /* BITSTREAM_H_MODULE */
695 /* ******************************************************************
696 FSE : Finite State Entropy codec
697 Public Prototypes declaration
698 Copyright (C) 2013-2016, Yann Collet.
700 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
702 Redistribution and use in source and binary forms, with or without
703 modification, are permitted provided that the following conditions are
706 * Redistributions of source code must retain the above copyright
707 notice, this list of conditions and the following disclaimer.
708 * Redistributions in binary form must reproduce the above
709 copyright notice, this list of conditions and the following disclaimer
710 in the documentation and/or other materials provided with the
713 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
714 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
715 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
716 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
717 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
718 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
719 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
720 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
721 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
722 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
723 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
725 You can contact the author at :
726 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
727 ****************************************************************** */
731 #if defined (__cplusplus)
737 /*-****************************************
738 * FSE simple functions
739 ******************************************/
741 /*! FSEv07_decompress():
742 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
743 into already allocated destination buffer 'dst', of size 'dstCapacity'.
744 @return : size of regenerated data (<= maxDstSize),
745 or an error code, which can be tested using FSEv07_isError() .
747 ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!
748 Why ? : making this distinction requires a header.
749 Header management is intentionally delegated to the user layer, which can better manage special cases.
751 size_t FSEv07_decompress(void* dst
, size_t dstCapacity
,
752 const void* cSrc
, size_t cSrcSize
);
755 /* Error Management */
756 unsigned FSEv07_isError(size_t code
); /* tells if a return value is an error code */
757 const char* FSEv07_getErrorName(size_t code
); /* provides error code string (useful for debugging) */
760 /*-*****************************************
762 ******************************************/
764 FSEv07_decompress() does the following:
765 1. read normalized counters with readNCount()
766 2. build decoding table 'DTable' from normalized counters
767 3. decode the data stream using decoding table 'DTable'
769 The following API allows targeting specific sub-functions for advanced tasks.
770 For example, it's possible to compress several blocks using the same 'CTable',
771 or to save and provide normalized distribution using external method.
775 /* *** DECOMPRESSION *** */
777 /*! FSEv07_readNCount():
778 Read compactly saved 'normalizedCounter' from 'rBuffer'.
779 @return : size read from 'rBuffer',
780 or an errorCode, which can be tested using FSEv07_isError().
781 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
782 size_t FSEv07_readNCount (short* normalizedCounter
, unsigned* maxSymbolValuePtr
, unsigned* tableLogPtr
, const void* rBuffer
, size_t rBuffSize
);
784 /*! Constructor and Destructor of FSEv07_DTable.
785 Note that its size depends on 'tableLog' */
786 typedef unsigned FSEv07_DTable
; /* don't allocate that. It's just a way to be more restrictive than void* */
787 FSEv07_DTable
* FSEv07_createDTable(unsigned tableLog
);
788 void FSEv07_freeDTable(FSEv07_DTable
* dt
);
790 /*! FSEv07_buildDTable():
791 Builds 'dt', which must be already allocated, using FSEv07_createDTable().
792 return : 0, or an errorCode, which can be tested using FSEv07_isError() */
793 size_t FSEv07_buildDTable (FSEv07_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
);
795 /*! FSEv07_decompress_usingDTable():
796 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
797 into `dst` which must be already allocated.
798 @return : size of regenerated data (necessarily <= `dstCapacity`),
799 or an errorCode, which can be tested using FSEv07_isError() */
800 size_t FSEv07_decompress_usingDTable(void* dst
, size_t dstCapacity
, const void* cSrc
, size_t cSrcSize
, const FSEv07_DTable
* dt
);
805 (Note : these functions only decompress FSE-compressed blocks.
806 If block is uncompressed, use memcpy() instead
807 If block is a single repeated byte, use memset() instead )
809 The first step is to obtain the normalized frequencies of symbols.
810 This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().
811 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
812 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
813 or size the table to handle worst case situations (typically 256).
814 FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
815 The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.
816 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
817 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
819 The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.
820 This is performed by the function FSEv07_buildDTable().
821 The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().
822 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
824 `FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().
825 `cSrcSize` must be strictly correct, otherwise decompression will fail.
826 FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
827 If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)
831 #ifdef FSEv07_STATIC_LINKING_ONLY
834 /* *****************************************
836 *******************************************/
837 /* FSE buffer bounds */
838 #define FSEv07_NCOUNTBOUND 512
839 #define FSEv07_BLOCKBOUND(size) (size + (size>>7))
841 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
842 #define FSEv07_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
845 /* *****************************************
847 *******************************************/
848 size_t FSEv07_countFast(unsigned* count
, unsigned* maxSymbolValuePtr
, const void* src
, size_t srcSize
);
849 /**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
851 unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog
, size_t srcSize
, unsigned maxSymbolValue
, unsigned minus
);
852 /**< same as FSEv07_optimalTableLog(), which used `minus==2` */
854 size_t FSEv07_buildDTable_raw (FSEv07_DTable
* dt
, unsigned nbBits
);
855 /**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
857 size_t FSEv07_buildDTable_rle (FSEv07_DTable
* dt
, unsigned char symbolValue
);
858 /**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */
862 /* *****************************************
863 * FSE symbol decompression API
864 *******************************************/
868 const void* table
; /* precise table may vary, depending on U16 */
872 static void FSEv07_initDState(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
, const FSEv07_DTable
* dt
);
874 static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
);
878 Let's now decompose FSEv07_decompress_usingDTable() into its unitary components.
879 You will decode FSE-encoded symbols from the bitStream,
880 and also any other bitFields you put in, **in reverse order**.
882 You will need a few variables to track your bitStream. They are :
884 BITv07_DStream_t DStream; // Stream context
885 FSEv07_DState_t DState; // State context. Multiple ones are possible
886 FSEv07_DTable* DTablePtr; // Decoding table, provided by FSEv07_buildDTable()
888 The first thing to do is to init the bitStream.
889 errorCode = BITv07_initDStream(&DStream, srcBuffer, srcSize);
891 You should then retrieve your initial state(s)
892 (in reverse flushing order if you have several ones) :
893 errorCode = FSEv07_initDState(&DState, &DStream, DTablePtr);
895 You can then decode your data, symbol after symbol.
896 For information the maximum number of bits read by FSEv07_decodeSymbol() is 'tableLog'.
897 Keep in mind that symbols are decoded in reverse order, like a LIFO stack (last in, first out).
898 unsigned char symbol = FSEv07_decodeSymbol(&DState, &DStream);
900 You can retrieve any bitfield you eventually stored into the bitStream (in reverse order)
901 Note : maximum allowed nbBits is 25, for 32-bits compatibility
902 size_t bitField = BITv07_readBits(&DStream, nbBits);
904 All above operations only read from local register (which size depends on size_t).
905 Refueling the register from memory is manually performed by the reload method.
906 endSignal = FSEv07_reloadDStream(&DStream);
908 BITv07_reloadDStream() result tells if there is still some more data to read from DStream.
909 BITv07_DStream_unfinished : there is still some data left into the DStream.
910 BITv07_DStream_endOfBuffer : Dstream reached end of buffer. Its container may no longer be completely filled.
911 BITv07_DStream_completed : Dstream reached its exact end, corresponding in general to decompression completed.
912 BITv07_DStream_tooFar : Dstream went too far. Decompression result is corrupted.
914 When reaching end of buffer (BITv07_DStream_endOfBuffer), progress slowly, notably if you decode multiple symbols per loop,
915 to properly detect the exact end of stream.
916 After each decoded symbol, check if DStream is fully consumed using this simple test :
917 BITv07_reloadDStream(&DStream) >= BITv07_DStream_completed
919 When it's done, verify decompression is fully completed, by checking both DStream and the relevant states.
920 Checking if DStream has reached its end is performed by :
921 BITv07_endOfDStream(&DStream);
922 Check also the states. There might be some symbols left there, if some high probability ones (>50%) are possible.
923 FSEv07_endOfDState(&DState);
927 /* *****************************************
929 *******************************************/
930 static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
);
931 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
934 /* ====== Decompression ====== */
939 } FSEv07_DTableHeader
; /* sizeof U32 */
943 unsigned short newState
;
944 unsigned char symbol
;
945 unsigned char nbBits
;
946 } FSEv07_decode_t
; /* size == U32 */
948 MEM_STATIC
void FSEv07_initDState(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
, const FSEv07_DTable
* dt
)
950 const void* ptr
= dt
;
951 const FSEv07_DTableHeader
* const DTableH
= (const FSEv07_DTableHeader
*)ptr
;
952 DStatePtr
->state
= BITv07_readBits(bitD
, DTableH
->tableLog
);
953 BITv07_reloadDStream(bitD
);
954 DStatePtr
->table
= dt
+ 1;
957 MEM_STATIC BYTE
FSEv07_peekSymbol(const FSEv07_DState_t
* DStatePtr
)
959 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
963 MEM_STATIC
void FSEv07_updateState(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
)
965 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
966 U32
const nbBits
= DInfo
.nbBits
;
967 size_t const lowBits
= BITv07_readBits(bitD
, nbBits
);
968 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
971 MEM_STATIC BYTE
FSEv07_decodeSymbol(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
)
973 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
974 U32
const nbBits
= DInfo
.nbBits
;
975 BYTE
const symbol
= DInfo
.symbol
;
976 size_t const lowBits
= BITv07_readBits(bitD
, nbBits
);
978 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
982 /*! FSEv07_decodeSymbolFast() :
983 unsafe, only works if no symbol has a probability > 50% */
984 MEM_STATIC BYTE
FSEv07_decodeSymbolFast(FSEv07_DState_t
* DStatePtr
, BITv07_DStream_t
* bitD
)
986 FSEv07_decode_t
const DInfo
= ((const FSEv07_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
987 U32
const nbBits
= DInfo
.nbBits
;
988 BYTE
const symbol
= DInfo
.symbol
;
989 size_t const lowBits
= BITv07_readBitsFast(bitD
, nbBits
);
991 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
997 #ifndef FSEv07_COMMONDEFS_ONLY
999 /* **************************************************************
1001 ****************************************************************/
1003 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1004 * Increasing memory usage improves compression ratio
1005 * Reduced memory usage can improve speed, due to cache effect
1006 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1007 #define FSEv07_MAX_MEMORY_USAGE 14
1008 #define FSEv07_DEFAULT_MEMORY_USAGE 13
1010 /*!FSEv07_MAX_SYMBOL_VALUE :
1011 * Maximum symbol value authorized.
1012 * Required for proper stack allocation */
1013 #define FSEv07_MAX_SYMBOL_VALUE 255
1016 /* **************************************************************
1017 * template functions type & suffix
1018 ****************************************************************/
1019 #define FSEv07_FUNCTION_TYPE BYTE
1020 #define FSEv07_FUNCTION_EXTENSION
1021 #define FSEv07_DECODE_TYPE FSEv07_decode_t
1024 #endif /* !FSEv07_COMMONDEFS_ONLY */
1027 /* ***************************************************************
1029 *****************************************************************/
1030 #define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2)
1031 #define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)
1032 #define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)
1033 #define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)
1034 #define FSEv07_MIN_TABLELOG 5
1036 #define FSEv07_TABLELOG_ABSOLUTE_MAX 15
1037 #if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX
1038 # error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"
1041 #define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
1044 #endif /* FSEv07_STATIC_LINKING_ONLY */
1047 #if defined (__cplusplus)
1051 #endif /* FSEv07_H */
1052 /* ******************************************************************
1053 Huffman coder, part of New Generation Entropy library
1055 Copyright (C) 2013-2016, Yann Collet.
1057 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1059 Redistribution and use in source and binary forms, with or without
1060 modification, are permitted provided that the following conditions are
1063 * Redistributions of source code must retain the above copyright
1064 notice, this list of conditions and the following disclaimer.
1065 * Redistributions in binary form must reproduce the above
1066 copyright notice, this list of conditions and the following disclaimer
1067 in the documentation and/or other materials provided with the
1070 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1071 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1072 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1073 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1074 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1075 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1076 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1077 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1078 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1079 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1080 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1082 You can contact the author at :
1083 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1084 ****************************************************************** */
1085 #ifndef HUFv07_H_298734234
1086 #define HUFv07_H_298734234
1088 #if defined (__cplusplus)
1094 /* *** simple functions *** */
1096 HUFv07_decompress() :
1097 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1098 into already allocated buffer 'dst', of minimum size 'dstSize'.
1099 `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
1100 Note : in contrast with FSE, HUFv07_decompress can regenerate
1101 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1102 because it knows size to regenerate.
1103 @return : size of regenerated data (== dstSize),
1104 or an error code, which can be tested using HUFv07_isError()
1106 size_t HUFv07_decompress(void* dst
, size_t dstSize
,
1107 const void* cSrc
, size_t cSrcSize
);
1110 /* ****************************************
1112 ******************************************/
1113 #define HUFv07_BLOCKSIZE_MAX (128 * 1024)
1115 /* Error Management */
1116 unsigned HUFv07_isError(size_t code
); /**< tells if a return value is an error code */
1117 const char* HUFv07_getErrorName(size_t code
); /**< provides error code string (useful for debugging) */
1120 /* *** Advanced function *** */
1123 #ifdef HUFv07_STATIC_LINKING_ONLY
1126 /* *** Constants *** */
1127 #define HUFv07_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */
1128 #define HUFv07_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */
1129 #define HUFv07_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */
1130 #define HUFv07_SYMBOLVALUE_MAX 255
1131 #if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX)
1132 # error "HUFv07_TABLELOG_MAX is too large !"
1136 /* ****************************************
1138 ******************************************/
1139 /* HUF buffer bounds */
1140 #define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1142 /* static allocation of HUF's DTable */
1143 typedef U32 HUFv07_DTable
;
1144 #define HUFv07_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog)))
1145 #define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1146 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
1147 #define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1148 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
1151 /* ****************************************
1152 * Advanced decompression functions
1153 ******************************************/
1154 size_t HUFv07_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< single-symbol decoder */
1155 size_t HUFv07_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< double-symbols decoder */
1157 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< decodes RLE and uncompressed */
1158 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 */
1159 size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< single-symbol decoder */
1160 size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< double-symbols decoder */
1162 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
);
1163 size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< single-symbol decoder */
1164 size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /**< double-symbols decoder */
1167 /* ****************************************
1169 ******************************************/
1171 The following API allows targeting specific sub-functions for advanced tasks.
1172 For example, it's possible to compress several blocks using the same 'CTable',
1173 or to save and regenerate 'CTable' using external methods.
1175 /* FSEv07_count() : find it within "fse.h" */
1177 /*! HUFv07_readStats() :
1178 Read compact Huffman tree, saved by HUFv07_writeCTable().
1179 `huffWeight` is destination buffer.
1180 @return : size read from `src` , or an error Code .
1181 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */
1182 size_t HUFv07_readStats(BYTE
* huffWeight
, size_t hwSize
, U32
* rankStats
,
1183 U32
* nbSymbolsPtr
, U32
* tableLogPtr
,
1184 const void* src
, size_t srcSize
);
1188 HUFv07_decompress() does the following:
1189 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1190 2. build Huffman table from save, using HUFv07_readDTableXn()
1191 3. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable
1194 /** HUFv07_selectDecoder() :
1195 * Tells which decoder is likely to decode faster,
1196 * based on a set of pre-determined metrics.
1197 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
1198 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
1199 U32
HUFv07_selectDecoder (size_t dstSize
, size_t cSrcSize
);
1201 size_t HUFv07_readDTableX2 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
);
1202 size_t HUFv07_readDTableX4 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
);
1204 size_t HUFv07_decompress4X_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1205 size_t HUFv07_decompress4X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1206 size_t HUFv07_decompress4X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1209 /* single stream variants */
1210 size_t HUFv07_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* single-symbol decoder */
1211 size_t HUFv07_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* double-symbol decoder */
1213 size_t HUFv07_decompress1X_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1214 size_t HUFv07_decompress1X2_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1215 size_t HUFv07_decompress1X4_usingDTable(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
, const HUFv07_DTable
* DTable
);
1218 #endif /* HUFv07_STATIC_LINKING_ONLY */
1221 #if defined (__cplusplus)
1225 #endif /* HUFv07_H_298734234 */
1227 Common functions of New Generation Entropy library
1228 Copyright (C) 2016, Yann Collet.
1230 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1232 Redistribution and use in source and binary forms, with or without
1233 modification, are permitted provided that the following conditions are
1236 * Redistributions of source code must retain the above copyright
1237 notice, this list of conditions and the following disclaimer.
1238 * Redistributions in binary form must reproduce the above
1239 copyright notice, this list of conditions and the following disclaimer
1240 in the documentation and/or other materials provided with the
1243 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1244 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1245 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1246 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1247 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1248 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1249 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1250 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1251 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1252 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1253 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1255 You can contact the author at :
1256 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1257 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1258 *************************************************************************** */
1262 /*-****************************************
1263 * FSE Error Management
1264 ******************************************/
1265 unsigned FSEv07_isError(size_t code
) { return ERR_isError(code
); }
1267 const char* FSEv07_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1270 /* **************************************************************
1271 * HUF Error Management
1272 ****************************************************************/
1273 unsigned HUFv07_isError(size_t code
) { return ERR_isError(code
); }
1275 const char* HUFv07_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
1278 /*-**************************************************************
1279 * FSE NCount encoding-decoding
1280 ****************************************************************/
1281 static short FSEv07_abs(short a
) { return (short)(a
<0 ? -a
: a
); }
1283 size_t FSEv07_readNCount (short* normalizedCounter
, unsigned* maxSVPtr
, unsigned* tableLogPtr
,
1284 const void* headerBuffer
, size_t hbSize
)
1286 const BYTE
* const istart
= (const BYTE
*) headerBuffer
;
1287 const BYTE
* const iend
= istart
+ hbSize
;
1288 const BYTE
* ip
= istart
;
1294 unsigned charnum
= 0;
1297 if (hbSize
< 4) return ERROR(srcSize_wrong
);
1298 bitStream
= MEM_readLE32(ip
);
1299 nbBits
= (bitStream
& 0xF) + FSEv07_MIN_TABLELOG
; /* extract tableLog */
1300 if (nbBits
> FSEv07_TABLELOG_ABSOLUTE_MAX
) return ERROR(tableLog_tooLarge
);
1303 *tableLogPtr
= nbBits
;
1304 remaining
= (1<<nbBits
)+1;
1305 threshold
= 1<<nbBits
;
1308 while ((remaining
>1) && (charnum
<=*maxSVPtr
)) {
1310 unsigned n0
= charnum
;
1311 while ((bitStream
& 0xFFFF) == 0xFFFF) {
1315 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1320 while ((bitStream
& 3) == 3) {
1325 n0
+= bitStream
& 3;
1327 if (n0
> *maxSVPtr
) return ERROR(maxSymbolValue_tooSmall
);
1328 while (charnum
< n0
) normalizedCounter
[charnum
++] = 0;
1329 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1332 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1337 { short const max
= (short)((2*threshold
-1)-remaining
);
1340 if ((bitStream
& (threshold
-1)) < (U32
)max
) {
1341 count
= (short)(bitStream
& (threshold
-1));
1342 bitCount
+= nbBits
-1;
1344 count
= (short)(bitStream
& (2*threshold
-1));
1345 if (count
>= threshold
) count
-= max
;
1349 count
--; /* extra accuracy */
1350 remaining
-= FSEv07_abs(count
);
1351 normalizedCounter
[charnum
++] = count
;
1353 while (remaining
< threshold
) {
1358 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4)) {
1362 bitCount
-= (int)(8 * (iend
- 4 - ip
));
1365 bitStream
= MEM_readLE32(ip
) >> (bitCount
& 31);
1366 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1367 if (remaining
!= 1) return ERROR(GENERIC
);
1368 *maxSVPtr
= charnum
-1;
1370 ip
+= (bitCount
+7)>>3;
1371 if ((size_t)(ip
-istart
) > hbSize
) return ERROR(srcSize_wrong
);
1376 /*! HUFv07_readStats() :
1377 Read compact Huffman tree, saved by HUFv07_writeCTable().
1378 `huffWeight` is destination buffer.
1379 @return : size read from `src` , or an error Code .
1380 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() .
1382 size_t HUFv07_readStats(BYTE
* huffWeight
, size_t hwSize
, U32
* rankStats
,
1383 U32
* nbSymbolsPtr
, U32
* tableLogPtr
,
1384 const void* src
, size_t srcSize
)
1387 const BYTE
* ip
= (const BYTE
*) src
;
1391 if (!srcSize
) return ERROR(srcSize_wrong
);
1393 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1395 if (iSize
>= 128) { /* special header */
1396 if (iSize
>= (242)) { /* RLE */
1397 static U32 l
[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1398 oSize
= l
[iSize
-242];
1399 memset(huffWeight
, 1, hwSize
);
1402 else { /* Incompressible */
1403 oSize
= iSize
- 127;
1404 iSize
= ((oSize
+1)/2);
1405 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1406 if (oSize
>= hwSize
) return ERROR(corruption_detected
);
1409 for (n
=0; n
<oSize
; n
+=2) {
1410 huffWeight
[n
] = ip
[n
/2] >> 4;
1411 huffWeight
[n
+1] = ip
[n
/2] & 15;
1413 else { /* header compressed with FSE (normal case) */
1414 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1415 oSize
= FSEv07_decompress(huffWeight
, hwSize
-1, ip
+1, iSize
); /* max (hwSize-1) values decoded, as last one is implied */
1416 if (FSEv07_isError(oSize
)) return oSize
;
1419 /* collect weight stats */
1420 memset(rankStats
, 0, (HUFv07_TABLELOG_ABSOLUTEMAX
+ 1) * sizeof(U32
));
1422 { U32 n
; for (n
=0; n
<oSize
; n
++) {
1423 if (huffWeight
[n
] >= HUFv07_TABLELOG_ABSOLUTEMAX
) return ERROR(corruption_detected
);
1424 rankStats
[huffWeight
[n
]]++;
1425 weightTotal
+= (1 << huffWeight
[n
]) >> 1;
1427 if (weightTotal
== 0) return ERROR(corruption_detected
);
1429 /* get last non-null symbol weight (implied, total must be 2^n) */
1430 { U32
const tableLog
= BITv07_highbit32(weightTotal
) + 1;
1431 if (tableLog
> HUFv07_TABLELOG_ABSOLUTEMAX
) return ERROR(corruption_detected
);
1432 *tableLogPtr
= tableLog
;
1433 /* determine last weight */
1434 { U32
const total
= 1 << tableLog
;
1435 U32
const rest
= total
- weightTotal
;
1436 U32
const verif
= 1 << BITv07_highbit32(rest
);
1437 U32
const lastWeight
= BITv07_highbit32(rest
) + 1;
1438 if (verif
!= rest
) return ERROR(corruption_detected
); /* last value must be a clean power of 2 */
1439 huffWeight
[oSize
] = (BYTE
)lastWeight
;
1440 rankStats
[lastWeight
]++;
1443 /* check tree construction validity */
1444 if ((rankStats
[1] < 2) || (rankStats
[1] & 1)) return ERROR(corruption_detected
); /* by construction : at least 2 elts of rank 1, must be even */
1447 *nbSymbolsPtr
= (U32
)(oSize
+1);
1450 /* ******************************************************************
1451 FSE : Finite State Entropy decoder
1452 Copyright (C) 2013-2015, Yann Collet.
1454 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1456 Redistribution and use in source and binary forms, with or without
1457 modification, are permitted provided that the following conditions are
1460 * Redistributions of source code must retain the above copyright
1461 notice, this list of conditions and the following disclaimer.
1462 * Redistributions in binary form must reproduce the above
1463 copyright notice, this list of conditions and the following disclaimer
1464 in the documentation and/or other materials provided with the
1467 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1468 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1469 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1470 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1471 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1472 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1473 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1474 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1475 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1476 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1477 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1479 You can contact the author at :
1480 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1481 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1482 ****************************************************************** */
1485 /* **************************************************************
1486 * Compiler specifics
1487 ****************************************************************/
1488 #ifdef _MSC_VER /* Visual Studio */
1489 # define FORCE_INLINE static __forceinline
1490 # include <intrin.h> /* For Visual 2005 */
1491 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1492 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1494 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1496 # define FORCE_INLINE static inline __attribute__((always_inline))
1498 # define FORCE_INLINE static inline
1501 # define FORCE_INLINE static
1502 # endif /* __STDC_VERSION__ */
1506 /* **************************************************************
1508 ****************************************************************/
1509 #define FSEv07_isError ERR_isError
1510 #define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1513 /* **************************************************************
1515 ****************************************************************/
1516 typedef U32 DTable_max_t
[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG
)];
1519 /* **************************************************************
1521 ****************************************************************/
1523 designed to be included
1524 for type-specific functions (template emulation in C)
1525 Objective is to write these functions only once, for improved maintenance
1529 #ifndef FSEv07_FUNCTION_EXTENSION
1530 # error "FSEv07_FUNCTION_EXTENSION must be defined"
1532 #ifndef FSEv07_FUNCTION_TYPE
1533 # error "FSEv07_FUNCTION_TYPE must be defined"
1536 /* Function names */
1537 #define FSEv07_CAT(X,Y) X##Y
1538 #define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y)
1539 #define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y)
1542 /* Function templates */
1543 FSEv07_DTable
* FSEv07_createDTable (unsigned tableLog
)
1545 if (tableLog
> FSEv07_TABLELOG_ABSOLUTE_MAX
) tableLog
= FSEv07_TABLELOG_ABSOLUTE_MAX
;
1546 return (FSEv07_DTable
*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog
) * sizeof (U32
) );
1549 void FSEv07_freeDTable (FSEv07_DTable
* dt
)
1554 size_t FSEv07_buildDTable(FSEv07_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
)
1556 void* const tdPtr
= dt
+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1557 FSEv07_DECODE_TYPE
* const tableDecode
= (FSEv07_DECODE_TYPE
*) (tdPtr
);
1558 U16 symbolNext
[FSEv07_MAX_SYMBOL_VALUE
+1];
1560 U32
const maxSV1
= maxSymbolValue
+ 1;
1561 U32
const tableSize
= 1 << tableLog
;
1562 U32 highThreshold
= tableSize
-1;
1565 if (maxSymbolValue
> FSEv07_MAX_SYMBOL_VALUE
) return ERROR(maxSymbolValue_tooLarge
);
1566 if (tableLog
> FSEv07_MAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
1568 /* Init, lay down lowprob symbols */
1569 { FSEv07_DTableHeader DTableH
;
1570 DTableH
.tableLog
= (U16
)tableLog
;
1571 DTableH
.fastMode
= 1;
1572 { S16
const largeLimit
= (S16
)(1 << (tableLog
-1));
1574 for (s
=0; s
<maxSV1
; s
++) {
1575 if (normalizedCounter
[s
]==-1) {
1576 tableDecode
[highThreshold
--].symbol
= (FSEv07_FUNCTION_TYPE
)s
;
1579 if (normalizedCounter
[s
] >= largeLimit
) DTableH
.fastMode
=0;
1580 symbolNext
[s
] = normalizedCounter
[s
];
1582 memcpy(dt
, &DTableH
, sizeof(DTableH
));
1585 /* Spread symbols */
1586 { U32
const tableMask
= tableSize
-1;
1587 U32
const step
= FSEv07_TABLESTEP(tableSize
);
1588 U32 s
, position
= 0;
1589 for (s
=0; s
<maxSV1
; s
++) {
1591 for (i
=0; i
<normalizedCounter
[s
]; i
++) {
1592 tableDecode
[position
].symbol
= (FSEv07_FUNCTION_TYPE
)s
;
1593 position
= (position
+ step
) & tableMask
;
1594 while (position
> highThreshold
) position
= (position
+ step
) & tableMask
; /* lowprob area */
1597 if (position
!=0) return ERROR(GENERIC
); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1600 /* Build Decoding table */
1602 for (u
=0; u
<tableSize
; u
++) {
1603 FSEv07_FUNCTION_TYPE
const symbol
= (FSEv07_FUNCTION_TYPE
)(tableDecode
[u
].symbol
);
1604 U16 nextState
= symbolNext
[symbol
]++;
1605 tableDecode
[u
].nbBits
= (BYTE
) (tableLog
- BITv07_highbit32 ((U32
)nextState
) );
1606 tableDecode
[u
].newState
= (U16
) ( (nextState
<< tableDecode
[u
].nbBits
) - tableSize
);
1614 #ifndef FSEv07_COMMONDEFS_ONLY
1616 /*-*******************************************************
1617 * Decompression (Byte symbols)
1618 *********************************************************/
1619 size_t FSEv07_buildDTable_rle (FSEv07_DTable
* dt
, BYTE symbolValue
)
1622 FSEv07_DTableHeader
* const DTableH
= (FSEv07_DTableHeader
*)ptr
;
1623 void* dPtr
= dt
+ 1;
1624 FSEv07_decode_t
* const cell
= (FSEv07_decode_t
*)dPtr
;
1626 DTableH
->tableLog
= 0;
1627 DTableH
->fastMode
= 0;
1630 cell
->symbol
= symbolValue
;
1637 size_t FSEv07_buildDTable_raw (FSEv07_DTable
* dt
, unsigned nbBits
)
1640 FSEv07_DTableHeader
* const DTableH
= (FSEv07_DTableHeader
*)ptr
;
1641 void* dPtr
= dt
+ 1;
1642 FSEv07_decode_t
* const dinfo
= (FSEv07_decode_t
*)dPtr
;
1643 const unsigned tableSize
= 1 << nbBits
;
1644 const unsigned tableMask
= tableSize
- 1;
1645 const unsigned maxSV1
= tableMask
+1;
1649 if (nbBits
< 1) return ERROR(GENERIC
); /* min size */
1651 /* Build Decoding Table */
1652 DTableH
->tableLog
= (U16
)nbBits
;
1653 DTableH
->fastMode
= 1;
1654 for (s
=0; s
<maxSV1
; s
++) {
1655 dinfo
[s
].newState
= 0;
1656 dinfo
[s
].symbol
= (BYTE
)s
;
1657 dinfo
[s
].nbBits
= (BYTE
)nbBits
;
1663 FORCE_INLINE
size_t FSEv07_decompress_usingDTable_generic(
1664 void* dst
, size_t maxDstSize
,
1665 const void* cSrc
, size_t cSrcSize
,
1666 const FSEv07_DTable
* dt
, const unsigned fast
)
1668 BYTE
* const ostart
= (BYTE
*) dst
;
1670 BYTE
* const omax
= op
+ maxDstSize
;
1671 BYTE
* const olimit
= omax
-3;
1673 BITv07_DStream_t bitD
;
1674 FSEv07_DState_t state1
;
1675 FSEv07_DState_t state2
;
1678 { size_t const errorCode
= BITv07_initDStream(&bitD
, cSrc
, cSrcSize
); /* replaced last arg by maxCompressed Size */
1679 if (FSEv07_isError(errorCode
)) return errorCode
; }
1681 FSEv07_initDState(&state1
, &bitD
, dt
);
1682 FSEv07_initDState(&state2
, &bitD
, dt
);
1684 #define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1686 /* 4 symbols per loop */
1687 for ( ; (BITv07_reloadDStream(&bitD
)==BITv07_DStream_unfinished
) && (op
<olimit
) ; op
+=4) {
1688 op
[0] = FSEv07_GETSYMBOL(&state1
);
1690 if (FSEv07_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1691 BITv07_reloadDStream(&bitD
);
1693 op
[1] = FSEv07_GETSYMBOL(&state2
);
1695 if (FSEv07_MAX_TABLELOG
*4+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1696 { if (BITv07_reloadDStream(&bitD
) > BITv07_DStream_unfinished
) { op
+=2; break; } }
1698 op
[2] = FSEv07_GETSYMBOL(&state1
);
1700 if (FSEv07_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1701 BITv07_reloadDStream(&bitD
);
1703 op
[3] = FSEv07_GETSYMBOL(&state2
);
1707 /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1709 if (op
>(omax
-2)) return ERROR(dstSize_tooSmall
);
1711 *op
++ = FSEv07_GETSYMBOL(&state1
);
1713 if (BITv07_reloadDStream(&bitD
)==BITv07_DStream_overflow
) {
1714 *op
++ = FSEv07_GETSYMBOL(&state2
);
1718 if (op
>(omax
-2)) return ERROR(dstSize_tooSmall
);
1720 *op
++ = FSEv07_GETSYMBOL(&state2
);
1722 if (BITv07_reloadDStream(&bitD
)==BITv07_DStream_overflow
) {
1723 *op
++ = FSEv07_GETSYMBOL(&state1
);
1731 size_t FSEv07_decompress_usingDTable(void* dst
, size_t originalSize
,
1732 const void* cSrc
, size_t cSrcSize
,
1733 const FSEv07_DTable
* dt
)
1735 const void* ptr
= dt
;
1736 const FSEv07_DTableHeader
* DTableH
= (const FSEv07_DTableHeader
*)ptr
;
1737 const U32 fastMode
= DTableH
->fastMode
;
1739 /* select fast mode (static) */
1740 if (fastMode
) return FSEv07_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 1);
1741 return FSEv07_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 0);
1745 size_t FSEv07_decompress(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
)
1747 const BYTE
* const istart
= (const BYTE
*)cSrc
;
1748 const BYTE
* ip
= istart
;
1749 short counting
[FSEv07_MAX_SYMBOL_VALUE
+1];
1750 DTable_max_t dt
; /* Static analyzer seems unable to understand this table will be properly initialized later */
1752 unsigned maxSymbolValue
= FSEv07_MAX_SYMBOL_VALUE
;
1754 if (cSrcSize
<2) return ERROR(srcSize_wrong
); /* too small input size */
1756 /* normal FSE decoding mode */
1757 { size_t const NCountLength
= FSEv07_readNCount (counting
, &maxSymbolValue
, &tableLog
, istart
, cSrcSize
);
1758 if (FSEv07_isError(NCountLength
)) return NCountLength
;
1759 if (NCountLength
>= cSrcSize
) return ERROR(srcSize_wrong
); /* too small input size */
1761 cSrcSize
-= NCountLength
;
1764 { size_t const errorCode
= FSEv07_buildDTable (dt
, counting
, maxSymbolValue
, tableLog
);
1765 if (FSEv07_isError(errorCode
)) return errorCode
; }
1767 return FSEv07_decompress_usingDTable (dst
, maxDstSize
, ip
, cSrcSize
, dt
); /* always return, even if it is an error code */
1772 #endif /* FSEv07_COMMONDEFS_ONLY */
1774 /* ******************************************************************
1775 Huffman decoder, part of New Generation Entropy library
1776 Copyright (C) 2013-2016, Yann Collet.
1778 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1780 Redistribution and use in source and binary forms, with or without
1781 modification, are permitted provided that the following conditions are
1784 * Redistributions of source code must retain the above copyright
1785 notice, this list of conditions and the following disclaimer.
1786 * Redistributions in binary form must reproduce the above
1787 copyright notice, this list of conditions and the following disclaimer
1788 in the documentation and/or other materials provided with the
1791 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1792 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1793 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1794 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1795 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1796 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1797 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1798 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1799 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1800 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1801 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1803 You can contact the author at :
1804 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1805 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1806 ****************************************************************** */
1808 /* **************************************************************
1809 * Compiler specifics
1810 ****************************************************************/
1811 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1812 /* inline is defined */
1813 #elif defined(_MSC_VER)
1814 # define inline __inline
1816 # define inline /* disable inline */
1820 #ifdef _MSC_VER /* Visual Studio */
1821 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1826 /* **************************************************************
1828 ****************************************************************/
1829 #define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1832 /*-***************************/
1833 /* generic DTableDesc */
1834 /*-***************************/
1836 typedef struct { BYTE maxTableLog
; BYTE tableType
; BYTE tableLog
; BYTE reserved
; } DTableDesc
;
1838 static DTableDesc
HUFv07_getDTableDesc(const HUFv07_DTable
* table
)
1841 memcpy(&dtd
, table
, sizeof(dtd
));
1846 /*-***************************/
1847 /* single-symbol decoding */
1848 /*-***************************/
1850 typedef struct { BYTE byte
; BYTE nbBits
; } HUFv07_DEltX2
; /* single-symbol decoding */
1852 size_t HUFv07_readDTableX2 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
)
1854 BYTE huffWeight
[HUFv07_SYMBOLVALUE_MAX
+ 1];
1855 U32 rankVal
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1]; /* large enough for values from 0 to 16 */
1859 void* const dtPtr
= DTable
+ 1;
1860 HUFv07_DEltX2
* const dt
= (HUFv07_DEltX2
*)dtPtr
;
1862 HUFv07_STATIC_ASSERT(sizeof(DTableDesc
) == sizeof(HUFv07_DTable
));
1863 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1865 iSize
= HUFv07_readStats(huffWeight
, HUFv07_SYMBOLVALUE_MAX
+ 1, rankVal
, &nbSymbols
, &tableLog
, src
, srcSize
);
1866 if (HUFv07_isError(iSize
)) return iSize
;
1869 { DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
1870 if (tableLog
> (U32
)(dtd
.maxTableLog
+1)) return ERROR(tableLog_tooLarge
); /* DTable too small, huffman tree cannot fit in */
1872 dtd
.tableLog
= (BYTE
)tableLog
;
1873 memcpy(DTable
, &dtd
, sizeof(dtd
));
1877 { U32 n
, nextRankStart
= 0;
1878 for (n
=1; n
<tableLog
+1; n
++) {
1879 U32 current
= nextRankStart
;
1880 nextRankStart
+= (rankVal
[n
] << (n
-1));
1881 rankVal
[n
] = current
;
1886 for (n
=0; n
<nbSymbols
; n
++) {
1887 U32
const w
= huffWeight
[n
];
1888 U32
const length
= (1 << w
) >> 1;
1891 D
.byte
= (BYTE
)n
; D
.nbBits
= (BYTE
)(tableLog
+ 1 - w
);
1892 for (i
= rankVal
[w
]; i
< rankVal
[w
] + length
; i
++)
1894 rankVal
[w
] += length
;
1901 static BYTE
HUFv07_decodeSymbolX2(BITv07_DStream_t
* Dstream
, const HUFv07_DEltX2
* dt
, const U32 dtLog
)
1903 size_t const val
= BITv07_lookBitsFast(Dstream
, dtLog
); /* note : dtLog >= 1 */
1904 BYTE
const c
= dt
[val
].byte
;
1905 BITv07_skipBits(Dstream
, dt
[val
].nbBits
);
1909 #define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1910 *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1912 #define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1913 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1914 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1916 #define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1918 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1920 static inline size_t HUFv07_decodeStreamX2(BYTE
* p
, BITv07_DStream_t
* const bitDPtr
, BYTE
* const pEnd
, const HUFv07_DEltX2
* const dt
, const U32 dtLog
)
1922 BYTE
* const pStart
= p
;
1924 /* up to 4 symbols at a time */
1925 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
<= pEnd
-4)) {
1926 HUFv07_DECODE_SYMBOLX2_2(p
, bitDPtr
);
1927 HUFv07_DECODE_SYMBOLX2_1(p
, bitDPtr
);
1928 HUFv07_DECODE_SYMBOLX2_2(p
, bitDPtr
);
1929 HUFv07_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1932 /* closer to the end */
1933 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
< pEnd
))
1934 HUFv07_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1936 /* no more data to retrieve from bitstream, hence no need to reload */
1938 HUFv07_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1943 static size_t HUFv07_decompress1X2_usingDTable_internal(
1944 void* dst
, size_t dstSize
,
1945 const void* cSrc
, size_t cSrcSize
,
1946 const HUFv07_DTable
* DTable
)
1948 BYTE
* op
= (BYTE
*)dst
;
1949 BYTE
* const oend
= op
+ dstSize
;
1950 const void* dtPtr
= DTable
+ 1;
1951 const HUFv07_DEltX2
* const dt
= (const HUFv07_DEltX2
*)dtPtr
;
1952 BITv07_DStream_t bitD
;
1953 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
1954 U32
const dtLog
= dtd
.tableLog
;
1956 { size_t const errorCode
= BITv07_initDStream(&bitD
, cSrc
, cSrcSize
);
1957 if (HUFv07_isError(errorCode
)) return errorCode
; }
1959 HUFv07_decodeStreamX2(op
, &bitD
, oend
, dt
, dtLog
);
1962 if (!BITv07_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
1967 size_t HUFv07_decompress1X2_usingDTable(
1968 void* dst
, size_t dstSize
,
1969 const void* cSrc
, size_t cSrcSize
,
1970 const HUFv07_DTable
* DTable
)
1972 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
1973 if (dtd
.tableType
!= 0) return ERROR(GENERIC
);
1974 return HUFv07_decompress1X2_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
1977 size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable
* DCtx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
1979 const BYTE
* ip
= (const BYTE
*) cSrc
;
1981 size_t const hSize
= HUFv07_readDTableX2 (DCtx
, cSrc
, cSrcSize
);
1982 if (HUFv07_isError(hSize
)) return hSize
;
1983 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
1984 ip
+= hSize
; cSrcSize
-= hSize
;
1986 return HUFv07_decompress1X2_usingDTable_internal (dst
, dstSize
, ip
, cSrcSize
, DCtx
);
1989 size_t HUFv07_decompress1X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
1991 HUFv07_CREATE_STATIC_DTABLEX2(DTable
, HUFv07_TABLELOG_MAX
);
1992 return HUFv07_decompress1X2_DCtx (DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
1996 static size_t HUFv07_decompress4X2_usingDTable_internal(
1997 void* dst
, size_t dstSize
,
1998 const void* cSrc
, size_t cSrcSize
,
1999 const HUFv07_DTable
* DTable
)
2002 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2004 { const BYTE
* const istart
= (const BYTE
*) cSrc
;
2005 BYTE
* const ostart
= (BYTE
*) dst
;
2006 BYTE
* const oend
= ostart
+ dstSize
;
2007 const void* const dtPtr
= DTable
+ 1;
2008 const HUFv07_DEltX2
* const dt
= (const HUFv07_DEltX2
*)dtPtr
;
2011 BITv07_DStream_t bitD1
;
2012 BITv07_DStream_t bitD2
;
2013 BITv07_DStream_t bitD3
;
2014 BITv07_DStream_t bitD4
;
2015 size_t const length1
= MEM_readLE16(istart
);
2016 size_t const length2
= MEM_readLE16(istart
+2);
2017 size_t const length3
= MEM_readLE16(istart
+4);
2018 size_t const length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2019 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2020 const BYTE
* const istart2
= istart1
+ length1
;
2021 const BYTE
* const istart3
= istart2
+ length2
;
2022 const BYTE
* const istart4
= istart3
+ length3
;
2023 const size_t segmentSize
= (dstSize
+3) / 4;
2024 BYTE
* const opStart2
= ostart
+ segmentSize
;
2025 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2026 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2028 BYTE
* op2
= opStart2
;
2029 BYTE
* op3
= opStart3
;
2030 BYTE
* op4
= opStart4
;
2032 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2033 U32
const dtLog
= dtd
.tableLog
;
2035 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2036 { size_t const errorCode
= BITv07_initDStream(&bitD1
, istart1
, length1
);
2037 if (HUFv07_isError(errorCode
)) return errorCode
; }
2038 { size_t const errorCode
= BITv07_initDStream(&bitD2
, istart2
, length2
);
2039 if (HUFv07_isError(errorCode
)) return errorCode
; }
2040 { size_t const errorCode
= BITv07_initDStream(&bitD3
, istart3
, length3
);
2041 if (HUFv07_isError(errorCode
)) return errorCode
; }
2042 { size_t const errorCode
= BITv07_initDStream(&bitD4
, istart4
, length4
);
2043 if (HUFv07_isError(errorCode
)) return errorCode
; }
2045 /* 16-32 symbols per loop (4-8 symbols per stream) */
2046 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2047 for ( ; (endSignal
==BITv07_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2048 HUFv07_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2049 HUFv07_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2050 HUFv07_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2051 HUFv07_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2052 HUFv07_DECODE_SYMBOLX2_1(op1
, &bitD1
);
2053 HUFv07_DECODE_SYMBOLX2_1(op2
, &bitD2
);
2054 HUFv07_DECODE_SYMBOLX2_1(op3
, &bitD3
);
2055 HUFv07_DECODE_SYMBOLX2_1(op4
, &bitD4
);
2056 HUFv07_DECODE_SYMBOLX2_2(op1
, &bitD1
);
2057 HUFv07_DECODE_SYMBOLX2_2(op2
, &bitD2
);
2058 HUFv07_DECODE_SYMBOLX2_2(op3
, &bitD3
);
2059 HUFv07_DECODE_SYMBOLX2_2(op4
, &bitD4
);
2060 HUFv07_DECODE_SYMBOLX2_0(op1
, &bitD1
);
2061 HUFv07_DECODE_SYMBOLX2_0(op2
, &bitD2
);
2062 HUFv07_DECODE_SYMBOLX2_0(op3
, &bitD3
);
2063 HUFv07_DECODE_SYMBOLX2_0(op4
, &bitD4
);
2064 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2067 /* check corruption */
2068 if (op1
> opStart2
) return ERROR(corruption_detected
);
2069 if (op2
> opStart3
) return ERROR(corruption_detected
);
2070 if (op3
> opStart4
) return ERROR(corruption_detected
);
2071 /* note : op4 supposed already verified within main loop */
2073 /* finish bitStreams one by one */
2074 HUFv07_decodeStreamX2(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2075 HUFv07_decodeStreamX2(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2076 HUFv07_decodeStreamX2(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2077 HUFv07_decodeStreamX2(op4
, &bitD4
, oend
, dt
, dtLog
);
2080 endSignal
= BITv07_endOfDStream(&bitD1
) & BITv07_endOfDStream(&bitD2
) & BITv07_endOfDStream(&bitD3
) & BITv07_endOfDStream(&bitD4
);
2081 if (!endSignal
) return ERROR(corruption_detected
);
2089 size_t HUFv07_decompress4X2_usingDTable(
2090 void* dst
, size_t dstSize
,
2091 const void* cSrc
, size_t cSrcSize
,
2092 const HUFv07_DTable
* DTable
)
2094 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2095 if (dtd
.tableType
!= 0) return ERROR(GENERIC
);
2096 return HUFv07_decompress4X2_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
2100 size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2102 const BYTE
* ip
= (const BYTE
*) cSrc
;
2104 size_t const hSize
= HUFv07_readDTableX2 (dctx
, cSrc
, cSrcSize
);
2105 if (HUFv07_isError(hSize
)) return hSize
;
2106 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2107 ip
+= hSize
; cSrcSize
-= hSize
;
2109 return HUFv07_decompress4X2_usingDTable_internal (dst
, dstSize
, ip
, cSrcSize
, dctx
);
2112 size_t HUFv07_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2114 HUFv07_CREATE_STATIC_DTABLEX2(DTable
, HUFv07_TABLELOG_MAX
);
2115 return HUFv07_decompress4X2_DCtx(DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
2119 /* *************************/
2120 /* double-symbols decoding */
2121 /* *************************/
2122 typedef struct { U16 sequence
; BYTE nbBits
; BYTE length
; } HUFv07_DEltX4
; /* double-symbols decoding */
2124 typedef struct { BYTE symbol
; BYTE weight
; } sortedSymbol_t
;
2126 static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4
* DTable
, U32 sizeLog
, const U32 consumed
,
2127 const U32
* rankValOrigin
, const int minWeight
,
2128 const sortedSymbol_t
* sortedSymbols
, const U32 sortedListSize
,
2129 U32 nbBitsBaseline
, U16 baseSeq
)
2132 U32 rankVal
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1];
2134 /* get pre-calculated rankVal */
2135 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2137 /* fill skipped values */
2139 U32 i
, skipSize
= rankVal
[minWeight
];
2140 MEM_writeLE16(&(DElt
.sequence
), baseSeq
);
2141 DElt
.nbBits
= (BYTE
)(consumed
);
2143 for (i
= 0; i
< skipSize
; i
++)
2148 { U32 s
; for (s
=0; s
<sortedListSize
; s
++) { /* note : sortedSymbols already skipped */
2149 const U32 symbol
= sortedSymbols
[s
].symbol
;
2150 const U32 weight
= sortedSymbols
[s
].weight
;
2151 const U32 nbBits
= nbBitsBaseline
- weight
;
2152 const U32 length
= 1 << (sizeLog
-nbBits
);
2153 const U32 start
= rankVal
[weight
];
2155 const U32 end
= start
+ length
;
2157 MEM_writeLE16(&(DElt
.sequence
), (U16
)(baseSeq
+ (symbol
<< 8)));
2158 DElt
.nbBits
= (BYTE
)(nbBits
+ consumed
);
2160 do { DTable
[i
++] = DElt
; } while (i
<end
); /* since length >= 1 */
2162 rankVal
[weight
] += length
;
2166 typedef U32 rankVal_t
[HUFv07_TABLELOG_ABSOLUTEMAX
][HUFv07_TABLELOG_ABSOLUTEMAX
+ 1];
2168 static void HUFv07_fillDTableX4(HUFv07_DEltX4
* DTable
, const U32 targetLog
,
2169 const sortedSymbol_t
* sortedList
, const U32 sortedListSize
,
2170 const U32
* rankStart
, rankVal_t rankValOrigin
, const U32 maxWeight
,
2171 const U32 nbBitsBaseline
)
2173 U32 rankVal
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1];
2174 const int scaleLog
= nbBitsBaseline
- targetLog
; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2175 const U32 minBits
= nbBitsBaseline
- maxWeight
;
2178 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
2181 for (s
=0; s
<sortedListSize
; s
++) {
2182 const U16 symbol
= sortedList
[s
].symbol
;
2183 const U32 weight
= sortedList
[s
].weight
;
2184 const U32 nbBits
= nbBitsBaseline
- weight
;
2185 const U32 start
= rankVal
[weight
];
2186 const U32 length
= 1 << (targetLog
-nbBits
);
2188 if (targetLog
-nbBits
>= minBits
) { /* enough room for a second symbol */
2190 int minWeight
= nbBits
+ scaleLog
;
2191 if (minWeight
< 1) minWeight
= 1;
2192 sortedRank
= rankStart
[minWeight
];
2193 HUFv07_fillDTableX4Level2(DTable
+start
, targetLog
-nbBits
, nbBits
,
2194 rankValOrigin
[nbBits
], minWeight
,
2195 sortedList
+sortedRank
, sortedListSize
-sortedRank
,
2196 nbBitsBaseline
, symbol
);
2199 MEM_writeLE16(&(DElt
.sequence
), symbol
);
2200 DElt
.nbBits
= (BYTE
)(nbBits
);
2203 const U32 end
= start
+ length
;
2204 for (u
= start
; u
< end
; u
++) DTable
[u
] = DElt
;
2206 rankVal
[weight
] += length
;
2210 size_t HUFv07_readDTableX4 (HUFv07_DTable
* DTable
, const void* src
, size_t srcSize
)
2212 BYTE weightList
[HUFv07_SYMBOLVALUE_MAX
+ 1];
2213 sortedSymbol_t sortedSymbol
[HUFv07_SYMBOLVALUE_MAX
+ 1];
2214 U32 rankStats
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 1] = { 0 };
2215 U32 rankStart0
[HUFv07_TABLELOG_ABSOLUTEMAX
+ 2] = { 0 };
2216 U32
* const rankStart
= rankStart0
+1;
2218 U32 tableLog
, maxW
, sizeOfSort
, nbSymbols
;
2219 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2220 U32
const maxTableLog
= dtd
.maxTableLog
;
2222 void* dtPtr
= DTable
+1; /* force compiler to avoid strict-aliasing */
2223 HUFv07_DEltX4
* const dt
= (HUFv07_DEltX4
*)dtPtr
;
2225 HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4
) == sizeof(HUFv07_DTable
)); /* if compilation fails here, assertion is false */
2226 if (maxTableLog
> HUFv07_TABLELOG_ABSOLUTEMAX
) return ERROR(tableLog_tooLarge
);
2227 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2229 iSize
= HUFv07_readStats(weightList
, HUFv07_SYMBOLVALUE_MAX
+ 1, rankStats
, &nbSymbols
, &tableLog
, src
, srcSize
);
2230 if (HUFv07_isError(iSize
)) return iSize
;
2233 if (tableLog
> maxTableLog
) return ERROR(tableLog_tooLarge
); /* DTable can't fit code depth */
2235 /* find maxWeight */
2236 for (maxW
= tableLog
; rankStats
[maxW
]==0; maxW
--) {} /* necessarily finds a solution before 0 */
2238 /* Get start index of each weight */
2239 { U32 w
, nextRankStart
= 0;
2240 for (w
=1; w
<maxW
+1; w
++) {
2241 U32 current
= nextRankStart
;
2242 nextRankStart
+= rankStats
[w
];
2243 rankStart
[w
] = current
;
2245 rankStart
[0] = nextRankStart
; /* put all 0w symbols at the end of sorted list*/
2246 sizeOfSort
= nextRankStart
;
2249 /* sort symbols by weight */
2251 for (s
=0; s
<nbSymbols
; s
++) {
2252 U32
const w
= weightList
[s
];
2253 U32
const r
= rankStart
[w
]++;
2254 sortedSymbol
[r
].symbol
= (BYTE
)s
;
2255 sortedSymbol
[r
].weight
= (BYTE
)w
;
2257 rankStart
[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2261 { U32
* const rankVal0
= rankVal
[0];
2262 { int const rescale
= (maxTableLog
-tableLog
) - 1; /* tableLog <= maxTableLog */
2263 U32 nextRankVal
= 0;
2265 for (w
=1; w
<maxW
+1; w
++) {
2266 U32 current
= nextRankVal
;
2267 nextRankVal
+= rankStats
[w
] << (w
+rescale
);
2268 rankVal0
[w
] = current
;
2270 { U32
const minBits
= tableLog
+1 - maxW
;
2272 for (consumed
= minBits
; consumed
< maxTableLog
- minBits
+ 1; consumed
++) {
2273 U32
* const rankValPtr
= rankVal
[consumed
];
2275 for (w
= 1; w
< maxW
+1; w
++) {
2276 rankValPtr
[w
] = rankVal0
[w
] >> consumed
;
2279 HUFv07_fillDTableX4(dt
, maxTableLog
,
2280 sortedSymbol
, sizeOfSort
,
2281 rankStart0
, rankVal
, maxW
,
2284 dtd
.tableLog
= (BYTE
)maxTableLog
;
2286 memcpy(DTable
, &dtd
, sizeof(dtd
));
2291 static U32
HUFv07_decodeSymbolX4(void* op
, BITv07_DStream_t
* DStream
, const HUFv07_DEltX4
* dt
, const U32 dtLog
)
2293 const size_t val
= BITv07_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2294 memcpy(op
, dt
+val
, 2);
2295 BITv07_skipBits(DStream
, dt
[val
].nbBits
);
2296 return dt
[val
].length
;
2299 static U32
HUFv07_decodeLastSymbolX4(void* op
, BITv07_DStream_t
* DStream
, const HUFv07_DEltX4
* dt
, const U32 dtLog
)
2301 const size_t val
= BITv07_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2302 memcpy(op
, dt
+val
, 1);
2303 if (dt
[val
].length
==1) BITv07_skipBits(DStream
, dt
[val
].nbBits
);
2305 if (DStream
->bitsConsumed
< (sizeof(DStream
->bitContainer
)*8)) {
2306 BITv07_skipBits(DStream
, dt
[val
].nbBits
);
2307 if (DStream
->bitsConsumed
> (sizeof(DStream
->bitContainer
)*8))
2308 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 */
2314 #define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2315 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2317 #define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2318 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
2319 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2321 #define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2323 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2325 static inline size_t HUFv07_decodeStreamX4(BYTE
* p
, BITv07_DStream_t
* bitDPtr
, BYTE
* const pEnd
, const HUFv07_DEltX4
* const dt
, const U32 dtLog
)
2327 BYTE
* const pStart
= p
;
2329 /* up to 8 symbols at a time */
2330 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
< pEnd
-7)) {
2331 HUFv07_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2332 HUFv07_DECODE_SYMBOLX4_1(p
, bitDPtr
);
2333 HUFv07_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2334 HUFv07_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2337 /* closer to end : up to 2 symbols at a time */
2338 while ((BITv07_reloadDStream(bitDPtr
) == BITv07_DStream_unfinished
) && (p
<= pEnd
-2))
2339 HUFv07_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2342 HUFv07_DECODE_SYMBOLX4_0(p
, bitDPtr
); /* no need to reload : reached the end of DStream */
2345 p
+= HUFv07_decodeLastSymbolX4(p
, bitDPtr
, dt
, dtLog
);
2351 static size_t HUFv07_decompress1X4_usingDTable_internal(
2352 void* dst
, size_t dstSize
,
2353 const void* cSrc
, size_t cSrcSize
,
2354 const HUFv07_DTable
* DTable
)
2356 BITv07_DStream_t bitD
;
2359 { size_t const errorCode
= BITv07_initDStream(&bitD
, cSrc
, cSrcSize
);
2360 if (HUFv07_isError(errorCode
)) return errorCode
;
2364 { BYTE
* const ostart
= (BYTE
*) dst
;
2365 BYTE
* const oend
= ostart
+ dstSize
;
2366 const void* const dtPtr
= DTable
+1; /* force compiler to not use strict-aliasing */
2367 const HUFv07_DEltX4
* const dt
= (const HUFv07_DEltX4
*)dtPtr
;
2368 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2369 HUFv07_decodeStreamX4(ostart
, &bitD
, oend
, dt
, dtd
.tableLog
);
2373 if (!BITv07_endOfDStream(&bitD
)) return ERROR(corruption_detected
);
2379 size_t HUFv07_decompress1X4_usingDTable(
2380 void* dst
, size_t dstSize
,
2381 const void* cSrc
, size_t cSrcSize
,
2382 const HUFv07_DTable
* DTable
)
2384 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2385 if (dtd
.tableType
!= 1) return ERROR(GENERIC
);
2386 return HUFv07_decompress1X4_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
2389 size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable
* DCtx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2391 const BYTE
* ip
= (const BYTE
*) cSrc
;
2393 size_t const hSize
= HUFv07_readDTableX4 (DCtx
, cSrc
, cSrcSize
);
2394 if (HUFv07_isError(hSize
)) return hSize
;
2395 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2396 ip
+= hSize
; cSrcSize
-= hSize
;
2398 return HUFv07_decompress1X4_usingDTable_internal (dst
, dstSize
, ip
, cSrcSize
, DCtx
);
2401 size_t HUFv07_decompress1X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2403 HUFv07_CREATE_STATIC_DTABLEX4(DTable
, HUFv07_TABLELOG_MAX
);
2404 return HUFv07_decompress1X4_DCtx(DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
2407 static size_t HUFv07_decompress4X4_usingDTable_internal(
2408 void* dst
, size_t dstSize
,
2409 const void* cSrc
, size_t cSrcSize
,
2410 const HUFv07_DTable
* DTable
)
2412 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2414 { const BYTE
* const istart
= (const BYTE
*) cSrc
;
2415 BYTE
* const ostart
= (BYTE
*) dst
;
2416 BYTE
* const oend
= ostart
+ dstSize
;
2417 const void* const dtPtr
= DTable
+1;
2418 const HUFv07_DEltX4
* const dt
= (const HUFv07_DEltX4
*)dtPtr
;
2421 BITv07_DStream_t bitD1
;
2422 BITv07_DStream_t bitD2
;
2423 BITv07_DStream_t bitD3
;
2424 BITv07_DStream_t bitD4
;
2425 size_t const length1
= MEM_readLE16(istart
);
2426 size_t const length2
= MEM_readLE16(istart
+2);
2427 size_t const length3
= MEM_readLE16(istart
+4);
2428 size_t const length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2429 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2430 const BYTE
* const istart2
= istart1
+ length1
;
2431 const BYTE
* const istart3
= istart2
+ length2
;
2432 const BYTE
* const istart4
= istart3
+ length3
;
2433 size_t const segmentSize
= (dstSize
+3) / 4;
2434 BYTE
* const opStart2
= ostart
+ segmentSize
;
2435 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2436 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2438 BYTE
* op2
= opStart2
;
2439 BYTE
* op3
= opStart3
;
2440 BYTE
* op4
= opStart4
;
2442 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2443 U32
const dtLog
= dtd
.tableLog
;
2445 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2446 { size_t const errorCode
= BITv07_initDStream(&bitD1
, istart1
, length1
);
2447 if (HUFv07_isError(errorCode
)) return errorCode
; }
2448 { size_t const errorCode
= BITv07_initDStream(&bitD2
, istart2
, length2
);
2449 if (HUFv07_isError(errorCode
)) return errorCode
; }
2450 { size_t const errorCode
= BITv07_initDStream(&bitD3
, istart3
, length3
);
2451 if (HUFv07_isError(errorCode
)) return errorCode
; }
2452 { size_t const errorCode
= BITv07_initDStream(&bitD4
, istart4
, length4
);
2453 if (HUFv07_isError(errorCode
)) return errorCode
; }
2455 /* 16-32 symbols per loop (4-8 symbols per stream) */
2456 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2457 for ( ; (endSignal
==BITv07_DStream_unfinished
) && (op4
<(oend
-7)) ; ) {
2458 HUFv07_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2459 HUFv07_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2460 HUFv07_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2461 HUFv07_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2462 HUFv07_DECODE_SYMBOLX4_1(op1
, &bitD1
);
2463 HUFv07_DECODE_SYMBOLX4_1(op2
, &bitD2
);
2464 HUFv07_DECODE_SYMBOLX4_1(op3
, &bitD3
);
2465 HUFv07_DECODE_SYMBOLX4_1(op4
, &bitD4
);
2466 HUFv07_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2467 HUFv07_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2468 HUFv07_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2469 HUFv07_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2470 HUFv07_DECODE_SYMBOLX4_0(op1
, &bitD1
);
2471 HUFv07_DECODE_SYMBOLX4_0(op2
, &bitD2
);
2472 HUFv07_DECODE_SYMBOLX4_0(op3
, &bitD3
);
2473 HUFv07_DECODE_SYMBOLX4_0(op4
, &bitD4
);
2475 endSignal
= BITv07_reloadDStream(&bitD1
) | BITv07_reloadDStream(&bitD2
) | BITv07_reloadDStream(&bitD3
) | BITv07_reloadDStream(&bitD4
);
2478 /* check corruption */
2479 if (op1
> opStart2
) return ERROR(corruption_detected
);
2480 if (op2
> opStart3
) return ERROR(corruption_detected
);
2481 if (op3
> opStart4
) return ERROR(corruption_detected
);
2482 /* note : op4 supposed already verified within main loop */
2484 /* finish bitStreams one by one */
2485 HUFv07_decodeStreamX4(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2486 HUFv07_decodeStreamX4(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2487 HUFv07_decodeStreamX4(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2488 HUFv07_decodeStreamX4(op4
, &bitD4
, oend
, dt
, dtLog
);
2491 { U32
const endCheck
= BITv07_endOfDStream(&bitD1
) & BITv07_endOfDStream(&bitD2
) & BITv07_endOfDStream(&bitD3
) & BITv07_endOfDStream(&bitD4
);
2492 if (!endCheck
) return ERROR(corruption_detected
); }
2500 size_t HUFv07_decompress4X4_usingDTable(
2501 void* dst
, size_t dstSize
,
2502 const void* cSrc
, size_t cSrcSize
,
2503 const HUFv07_DTable
* DTable
)
2505 DTableDesc dtd
= HUFv07_getDTableDesc(DTable
);
2506 if (dtd
.tableType
!= 1) return ERROR(GENERIC
);
2507 return HUFv07_decompress4X4_usingDTable_internal(dst
, dstSize
, cSrc
, cSrcSize
, DTable
);
2511 size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2513 const BYTE
* ip
= (const BYTE
*) cSrc
;
2515 size_t hSize
= HUFv07_readDTableX4 (dctx
, cSrc
, cSrcSize
);
2516 if (HUFv07_isError(hSize
)) return hSize
;
2517 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2518 ip
+= hSize
; cSrcSize
-= hSize
;
2520 return HUFv07_decompress4X4_usingDTable_internal(dst
, dstSize
, ip
, cSrcSize
, dctx
);
2523 size_t HUFv07_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2525 HUFv07_CREATE_STATIC_DTABLEX4(DTable
, HUFv07_TABLELOG_MAX
);
2526 return HUFv07_decompress4X4_DCtx(DTable
, dst
, dstSize
, cSrc
, cSrcSize
);
2530 /* ********************************/
2531 /* Generic decompression selector */
2532 /* ********************************/
2534 size_t HUFv07_decompress1X_usingDTable(void* dst
, size_t maxDstSize
,
2535 const void* cSrc
, size_t cSrcSize
,
2536 const HUFv07_DTable
* DTable
)
2538 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2539 return dtd
.tableType
? HUFv07_decompress1X4_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
) :
2540 HUFv07_decompress1X2_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
);
2543 size_t HUFv07_decompress4X_usingDTable(void* dst
, size_t maxDstSize
,
2544 const void* cSrc
, size_t cSrcSize
,
2545 const HUFv07_DTable
* DTable
)
2547 DTableDesc
const dtd
= HUFv07_getDTableDesc(DTable
);
2548 return dtd
.tableType
? HUFv07_decompress4X4_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
) :
2549 HUFv07_decompress4X2_usingDTable_internal(dst
, maxDstSize
, cSrc
, cSrcSize
, DTable
);
2553 typedef struct { U32 tableTime
; U32 decode256Time
; } algo_time_t
;
2554 static const algo_time_t algoTime
[16 /* Quantization */][3 /* single, double, quad */] =
2556 /* single, double, quad */
2557 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2558 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2559 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2560 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2561 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2562 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2563 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2564 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2565 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2566 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2567 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2568 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2569 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2570 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2571 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2572 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2575 /** HUFv07_selectDecoder() :
2576 * Tells which decoder is likely to decode faster,
2577 * based on a set of pre-determined metrics.
2578 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
2579 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
2580 U32
HUFv07_selectDecoder (size_t dstSize
, size_t cSrcSize
)
2582 /* decoder timing evaluation */
2583 U32
const Q
= (U32
)(cSrcSize
* 16 / dstSize
); /* Q < 16 since dstSize > cSrcSize */
2584 U32
const D256
= (U32
)(dstSize
>> 8);
2585 U32
const DTime0
= algoTime
[Q
][0].tableTime
+ (algoTime
[Q
][0].decode256Time
* D256
);
2586 U32 DTime1
= algoTime
[Q
][1].tableTime
+ (algoTime
[Q
][1].decode256Time
* D256
);
2587 DTime1
+= DTime1
>> 3; /* advantage to algorithm using less memory, for cache eviction */
2589 return DTime1
< DTime0
;
2593 typedef size_t (*decompressionAlgo
)(void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
);
2595 size_t HUFv07_decompress (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2597 static const decompressionAlgo decompress
[2] = { HUFv07_decompress4X2
, HUFv07_decompress4X4
};
2599 /* validation checks */
2600 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2601 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2602 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2603 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2605 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2606 return decompress
[algoNb
](dst
, dstSize
, cSrc
, cSrcSize
);
2609 //return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2610 //return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2613 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2615 /* validation checks */
2616 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2617 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2618 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2619 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2621 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2622 return algoNb
? HUFv07_decompress4X4_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) :
2623 HUFv07_decompress4X2_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) ;
2627 size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2629 /* validation checks */
2630 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2631 if ((cSrcSize
>= dstSize
) || (cSrcSize
<= 1)) return ERROR(corruption_detected
); /* invalid */
2633 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2634 return algoNb
? HUFv07_decompress4X4_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) :
2635 HUFv07_decompress4X2_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) ;
2639 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable
* dctx
, void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2641 /* validation checks */
2642 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2643 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2644 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2645 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2647 { U32
const algoNb
= HUFv07_selectDecoder(dstSize
, cSrcSize
);
2648 return algoNb
? HUFv07_decompress1X4_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) :
2649 HUFv07_decompress1X2_DCtx(dctx
, dst
, dstSize
, cSrc
, cSrcSize
) ;
2653 Common functions of Zstd compression library
2654 Copyright (C) 2015-2016, Yann Collet.
2656 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2658 Redistribution and use in source and binary forms, with or without
2659 modification, are permitted provided that the following conditions are
2661 * Redistributions of source code must retain the above copyright
2662 notice, this list of conditions and the following disclaimer.
2663 * Redistributions in binary form must reproduce the above
2664 copyright notice, this list of conditions and the following disclaimer
2665 in the documentation and/or other materials provided with the
2667 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2668 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2669 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2670 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2671 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2672 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2673 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2674 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2675 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2676 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2677 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2679 You can contact the author at :
2680 - zstd homepage : http://www.zstd.net/
2685 /*-****************************************
2686 * ZSTD Error Management
2687 ******************************************/
2688 /*! ZSTDv07_isError() :
2689 * tells if a return value is an error code */
2690 unsigned ZSTDv07_isError(size_t code
) { return ERR_isError(code
); }
2692 /*! ZSTDv07_getErrorName() :
2693 * provides error code string from function result (useful for debugging) */
2694 const char* ZSTDv07_getErrorName(size_t code
) { return ERR_getErrorName(code
); }
2698 /* **************************************************************
2699 * ZBUFF Error Management
2700 ****************************************************************/
2701 unsigned ZBUFFv07_isError(size_t errorCode
) { return ERR_isError(errorCode
); }
2703 const char* ZBUFFv07_getErrorName(size_t errorCode
) { return ERR_getErrorName(errorCode
); }
2707 void* ZSTDv07_defaultAllocFunction(void* opaque
, size_t size
)
2709 void* address
= malloc(size
);
2711 /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2715 void ZSTDv07_defaultFreeFunction(void* opaque
, void* address
)
2718 /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2722 zstd_internal - common functions to include
2723 Header File for include
2724 Copyright (C) 2014-2016, Yann Collet.
2726 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2728 Redistribution and use in source and binary forms, with or without
2729 modification, are permitted provided that the following conditions are
2731 * Redistributions of source code must retain the above copyright
2732 notice, this list of conditions and the following disclaimer.
2733 * Redistributions in binary form must reproduce the above
2734 copyright notice, this list of conditions and the following disclaimer
2735 in the documentation and/or other materials provided with the
2737 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2738 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2739 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2740 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2741 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2742 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2743 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2744 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2745 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2746 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2747 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2749 You can contact the author at :
2750 - zstd homepage : https://www.zstd.net
2752 #ifndef ZSTDv07_CCOMMON_H_MODULE
2753 #define ZSTDv07_CCOMMON_H_MODULE
2756 /*-*************************************
2758 ***************************************/
2759 #define MIN(a,b) ((a)<(b) ? (a) : (b))
2760 #define MAX(a,b) ((a)>(b) ? (a) : (b))
2763 /*-*************************************
2765 ***************************************/
2766 #define ZSTDv07_OPT_NUM (1<<12)
2767 #define ZSTDv07_DICT_MAGIC 0xEC30A437 /* v0.7 */
2769 #define ZSTDv07_REP_NUM 3
2770 #define ZSTDv07_REP_INIT ZSTDv07_REP_NUM
2771 #define ZSTDv07_REP_MOVE (ZSTDv07_REP_NUM-1)
2772 static const U32 repStartValue
[ZSTDv07_REP_NUM
] = { 1, 4, 8 };
2774 #define KB *(1 <<10)
2775 #define MB *(1 <<20)
2776 #define GB *(1U<<30)
2785 #define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10
2786 static const size_t ZSTDv07_fcs_fieldSize
[4] = { 0, 2, 4, 8 };
2787 static const size_t ZSTDv07_did_fieldSize
[4] = { 0, 1, 2, 4 };
2789 #define ZSTDv07_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
2790 static const size_t ZSTDv07_blockHeaderSize
= ZSTDv07_BLOCKHEADERSIZE
;
2791 typedef enum { bt_compressed
, bt_raw
, bt_rle
, bt_end
} blockType_t
;
2793 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2794 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
2797 typedef enum { lbt_huffman
, lbt_repeat
, lbt_raw
, lbt_rle
} litBlockType_t
;
2799 #define LONGNBSEQ 0x7F00
2802 #define EQUAL_READ32 4
2805 #define MaxLit ((1<<Litbits) - 1)
2809 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
2814 #define FSEv07_ENCODING_RAW 0
2815 #define FSEv07_ENCODING_RLE 1
2816 #define FSEv07_ENCODING_STATIC 2
2817 #define FSEv07_ENCODING_DYNAMIC 3
2819 static const U32 LL_bits
[MaxLL
+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2820 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
2822 static const S16 LL_defaultNorm
[MaxLL
+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2823 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
2825 static const U32 LL_defaultNormLog
= 6;
2827 static const U32 ML_bits
[MaxML
+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2828 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2829 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
2831 static const S16 ML_defaultNorm
[MaxML
+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2832 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2833 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
2835 static const U32 ML_defaultNormLog
= 6;
2837 static const S16 OF_defaultNorm
[MaxOff
+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2838 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
2839 static const U32 OF_defaultNormLog
= 5;
2842 /*-*******************************************
2843 * Shared functions to include for inlining
2844 *********************************************/
2845 static void ZSTDv07_copy8(void* dst
, const void* src
) { memcpy(dst
, src
, 8); }
2846 #define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; }
2848 /*! ZSTDv07_wildcopy() :
2849 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
2850 #define WILDCOPY_OVERLENGTH 8
2851 MEM_STATIC
void ZSTDv07_wildcopy(void* dst
, const void* src
, ptrdiff_t length
)
2853 const BYTE
* ip
= (const BYTE
*)src
;
2854 BYTE
* op
= (BYTE
*)dst
;
2855 BYTE
* const oend
= op
+ length
;
2862 /*-*******************************************
2863 * Private interfaces
2864 *********************************************/
2865 typedef struct ZSTDv07_stats_s ZSTDv07_stats_t
;
2877 U32 rep
[ZSTDv07_REP_INIT
];
2878 } ZSTDv07_optimal_t
;
2880 struct ZSTDv07_stats_s
{ U32 unused
; };
2889 U16
* litLengthStart
;
2892 U16
* matchLengthStart
;
2895 U32 longLengthID
; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
2898 ZSTDv07_optimal_t
* priceTable
;
2899 ZSTDv07_match_t
* matchTable
;
2900 U32
* matchLengthFreq
;
2909 U32 log2matchLengthSum
;
2911 U32 log2litLengthSum
;
2916 U32 cachedLitLength
;
2917 const BYTE
* cachedLiterals
;
2918 ZSTDv07_stats_t stats
;
2921 void ZSTDv07_seqToCodes(const seqStore_t
* seqStorePtr
, size_t const nbSeq
);
2923 /* custom memory allocation functions */
2924 static const ZSTDv07_customMem defaultCustomMem
= { ZSTDv07_defaultAllocFunction
, ZSTDv07_defaultFreeFunction
, NULL
};
2926 #endif /* ZSTDv07_CCOMMON_H_MODULE */
2928 zstd - standard compression library
2929 Copyright (C) 2014-2016, Yann Collet.
2931 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2933 Redistribution and use in source and binary forms, with or without
2934 modification, are permitted provided that the following conditions are
2936 * Redistributions of source code must retain the above copyright
2937 notice, this list of conditions and the following disclaimer.
2938 * Redistributions in binary form must reproduce the above
2939 copyright notice, this list of conditions and the following disclaimer
2940 in the documentation and/or other materials provided with the
2942 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2943 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2944 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2945 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2946 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2947 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2948 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2949 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2950 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2951 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2952 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2954 You can contact the author at :
2955 - zstd homepage : http://www.zstd.net
2958 /* ***************************************************************
2960 *****************************************************************/
2963 * Select how default decompression function ZSTDv07_decompress() will allocate memory,
2964 * in memory stack (0), or in memory heap (1, requires malloc())
2966 #ifndef ZSTDv07_HEAPMODE
2967 # define ZSTDv07_HEAPMODE 1
2971 /*-*******************************************************
2972 * Compiler specifics
2973 *********************************************************/
2974 #ifdef _MSC_VER /* Visual Studio */
2975 # include <intrin.h> /* For Visual 2005 */
2976 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2977 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2978 # pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */
2982 /*-*************************************
2984 ***************************************/
2985 #define ZSTDv07_isError ERR_isError /* for inlining */
2986 #define FSEv07_isError ERR_isError
2987 #define HUFv07_isError ERR_isError
2990 /*_*******************************************************
2992 **********************************************************/
2993 static void ZSTDv07_copy4(void* dst
, const void* src
) { memcpy(dst
, src
, 4); }
2996 /*-*************************************************************
2997 * Context management
2998 ***************************************************************/
2999 typedef enum { ZSTDds_getFrameHeaderSize
, ZSTDds_decodeFrameHeader
,
3000 ZSTDds_decodeBlockHeader
, ZSTDds_decompressBlock
,
3001 ZSTDds_decodeSkippableHeader
, ZSTDds_skipFrame
} ZSTDv07_dStage
;
3003 struct ZSTDv07_DCtx_s
3005 FSEv07_DTable LLTable
[FSEv07_DTABLE_SIZE_U32(LLFSELog
)];
3006 FSEv07_DTable OffTable
[FSEv07_DTABLE_SIZE_U32(OffFSELog
)];
3007 FSEv07_DTable MLTable
[FSEv07_DTABLE_SIZE_U32(MLFSELog
)];
3008 HUFv07_DTable hufTable
[HUFv07_DTABLE_SIZE(HufLog
)]; /* can accommodate HUFv07_decompress4X */
3009 const void* previousDstEnd
;
3012 const void* dictEnd
;
3015 ZSTDv07_frameParams fParams
;
3016 blockType_t bType
; /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
3017 ZSTDv07_dStage stage
;
3020 XXH64_state_t xxhState
;
3024 ZSTDv07_customMem customMem
;
3026 BYTE litBuffer
[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
+ WILDCOPY_OVERLENGTH
];
3027 BYTE headerBuffer
[ZSTDv07_FRAMEHEADERSIZE_MAX
];
3028 }; /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */
3030 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx
* dctx
);
3032 size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx
* dctx
) { return sizeof(*dctx
); }
3034 size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx
); }
3036 size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx
* dctx
)
3038 dctx
->expected
= ZSTDv07_frameHeaderSize_min
;
3039 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
3040 dctx
->previousDstEnd
= NULL
;
3043 dctx
->dictEnd
= NULL
;
3044 dctx
->hufTable
[0] = (HUFv07_DTable
)((HufLog
)*0x1000001);
3045 dctx
->litEntropy
= dctx
->fseEntropy
= 0;
3047 { int i
; for (i
=0; i
<ZSTDv07_REP_NUM
; i
++) dctx
->rep
[i
] = repStartValue
[i
]; }
3051 ZSTDv07_DCtx
* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem
)
3055 if (!customMem
.customAlloc
&& !customMem
.customFree
)
3056 customMem
= defaultCustomMem
;
3058 if (!customMem
.customAlloc
|| !customMem
.customFree
)
3061 dctx
= (ZSTDv07_DCtx
*) customMem
.customAlloc(customMem
.opaque
, sizeof(ZSTDv07_DCtx
));
3062 if (!dctx
) return NULL
;
3063 memcpy(&dctx
->customMem
, &customMem
, sizeof(ZSTDv07_customMem
));
3064 ZSTDv07_decompressBegin(dctx
);
3068 ZSTDv07_DCtx
* ZSTDv07_createDCtx(void)
3070 return ZSTDv07_createDCtx_advanced(defaultCustomMem
);
3073 size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx
* dctx
)
3075 if (dctx
==NULL
) return 0; /* support free on NULL */
3076 dctx
->customMem
.customFree(dctx
->customMem
.opaque
, dctx
);
3077 return 0; /* reserved as a potential error code in the future */
3080 void ZSTDv07_copyDCtx(ZSTDv07_DCtx
* dstDCtx
, const ZSTDv07_DCtx
* srcDCtx
)
3082 memcpy(dstDCtx
, srcDCtx
,
3083 sizeof(ZSTDv07_DCtx
) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
+WILDCOPY_OVERLENGTH
+ ZSTDv07_frameHeaderSize_max
)); /* no need to copy workspace */
3087 /*-*************************************************************
3088 * Decompression section
3089 ***************************************************************/
3091 /* Frame format description
3092 Frame Header - [ Block Header - Block ] - Frame End
3094 - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h)
3095 - 1 byte - Frame Descriptor
3097 - 3 bytes, starting with a 2-bits descriptor
3098 Uncompressed, Compressed, Frame End, unused
3100 See Block Format Description
3102 - 3 bytes, compatible with Block Header
3108 1 byte - FrameHeaderDescription :
3109 bit 0-1 : dictID (0, 1, 2 or 4 bytes)
3110 bit 2 : checksumFlag
3111 bit 3 : reserved (must be zero)
3112 bit 4 : reserved (unused, can be any value)
3113 bit 5 : Single Segment (if 1, WindowLog byte is not present)
3114 bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
3115 if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
3117 Optional : WindowLog (0 or 1 byte)
3118 bit 0-2 : octal Fractional (1/8th)
3119 bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
3121 Optional : dictID (0, 1, 2 or 4 bytes)
3122 Automatic adaptation
3126 4 : all other values
3128 Optional : content size (0, 1, 2, 4 or 8 bytes)
3129 0 : unknown (fcfs==0 and swl==0)
3130 1 : 0-255 bytes (fcfs==0 and swl==1)
3131 2 : 256 - 65535+256 (fcfs==1)
3132 4 : 0 - 4GB-1 (fcfs==2)
3133 8 : 0 - 16EB-1 (fcfs==3)
3137 /* Compressed Block, format description
3139 Block = Literal Section - Sequences Section
3140 Prerequisite : size of (compressed) block, maximum size of regenerated data
3144 1.1) Header : 1-5 bytes
3146 00 compressed by Huff0
3148 10 is Raw (uncompressed)
3150 Note : using 01 => Huff0 with precomputed table ?
3151 Note : delta map ? => compressed ?
3153 1.1.1) Huff0-compressed literal block : 3-5 bytes
3154 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3155 srcSize < 1 KB => 3 bytes (2-2-10-10)
3156 srcSize < 16KB => 4 bytes (2-2-14-14)
3157 else => 5 bytes (2-2-18-18)
3158 big endian convention
3160 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
3161 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
3162 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
3164 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3168 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3169 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
3170 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3172 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3176 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3177 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3178 srcSize < 1 KB => 3 bytes (2-2-10-10)
3179 srcSize < 16KB => 4 bytes (2-2-14-14)
3180 else => 5 bytes (2-2-18-18)
3181 big endian convention
3183 1- CTable available (stored into workspace ?)
3184 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3187 1.2) Literal block content
3189 1.2.1) Huff0 block, using sizes from header
3192 1.2.2) Huff0 block, using prepared table
3199 2) Sequences section
3203 /** ZSTDv07_frameHeaderSize() :
3204 * srcSize must be >= ZSTDv07_frameHeaderSize_min.
3205 * @return : size of the Frame Header */
3206 static size_t ZSTDv07_frameHeaderSize(const void* src
, size_t srcSize
)
3208 if (srcSize
< ZSTDv07_frameHeaderSize_min
) return ERROR(srcSize_wrong
);
3209 { BYTE
const fhd
= ((const BYTE
*)src
)[4];
3210 U32
const dictID
= fhd
& 3;
3211 U32
const directMode
= (fhd
>> 5) & 1;
3212 U32
const fcsId
= fhd
>> 6;
3213 return ZSTDv07_frameHeaderSize_min
+ !directMode
+ ZSTDv07_did_fieldSize
[dictID
] + ZSTDv07_fcs_fieldSize
[fcsId
]
3214 + (directMode
&& !ZSTDv07_fcs_fieldSize
[fcsId
]);
3219 /** ZSTDv07_getFrameParams() :
3220 * decode Frame Header, or require larger `srcSize`.
3221 * @return : 0, `fparamsPtr` is correctly filled,
3222 * >0, `srcSize` is too small, result is expected `srcSize`,
3223 * or an error code, which can be tested using ZSTDv07_isError() */
3224 size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams
* fparamsPtr
, const void* src
, size_t srcSize
)
3226 const BYTE
* ip
= (const BYTE
*)src
;
3228 if (srcSize
< ZSTDv07_frameHeaderSize_min
) return ZSTDv07_frameHeaderSize_min
;
3229 if (MEM_readLE32(src
) != ZSTDv07_MAGICNUMBER
) {
3230 if ((MEM_readLE32(src
) & 0xFFFFFFF0U
) == ZSTDv07_MAGIC_SKIPPABLE_START
) {
3231 if (srcSize
< ZSTDv07_skippableHeaderSize
) return ZSTDv07_skippableHeaderSize
; /* magic number + skippable frame length */
3232 memset(fparamsPtr
, 0, sizeof(*fparamsPtr
));
3233 fparamsPtr
->frameContentSize
= MEM_readLE32((const char *)src
+ 4);
3234 fparamsPtr
->windowSize
= 0; /* windowSize==0 means a frame is skippable */
3237 return ERROR(prefix_unknown
);
3240 /* ensure there is enough `srcSize` to fully read/decode frame header */
3241 { size_t const fhsize
= ZSTDv07_frameHeaderSize(src
, srcSize
);
3242 if (srcSize
< fhsize
) return fhsize
; }
3244 { BYTE
const fhdByte
= ip
[4];
3246 U32
const dictIDSizeCode
= fhdByte
&3;
3247 U32
const checksumFlag
= (fhdByte
>>2)&1;
3248 U32
const directMode
= (fhdByte
>>5)&1;
3249 U32
const fcsID
= fhdByte
>>6;
3250 U32
const windowSizeMax
= 1U << ZSTDv07_WINDOWLOG_MAX
;
3253 U64 frameContentSize
= 0;
3254 if ((fhdByte
& 0x08) != 0) return ERROR(frameParameter_unsupported
); /* reserved bits, which must be zero */
3256 BYTE
const wlByte
= ip
[pos
++];
3257 U32
const windowLog
= (wlByte
>> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN
;
3258 if (windowLog
> ZSTDv07_WINDOWLOG_MAX
) return ERROR(frameParameter_unsupported
);
3259 windowSize
= (1U << windowLog
);
3260 windowSize
+= (windowSize
>> 3) * (wlByte
&7);
3263 switch(dictIDSizeCode
)
3265 default: /* impossible */
3267 case 1 : dictID
= ip
[pos
]; pos
++; break;
3268 case 2 : dictID
= MEM_readLE16(ip
+pos
); pos
+=2; break;
3269 case 3 : dictID
= MEM_readLE32(ip
+pos
); pos
+=4; break;
3273 default: /* impossible */
3274 case 0 : if (directMode
) frameContentSize
= ip
[pos
]; break;
3275 case 1 : frameContentSize
= MEM_readLE16(ip
+pos
)+256; break;
3276 case 2 : frameContentSize
= MEM_readLE32(ip
+pos
); break;
3277 case 3 : frameContentSize
= MEM_readLE64(ip
+pos
); break;
3279 if (!windowSize
) windowSize
= (U32
)frameContentSize
;
3280 if (windowSize
> windowSizeMax
) return ERROR(frameParameter_unsupported
);
3281 fparamsPtr
->frameContentSize
= frameContentSize
;
3282 fparamsPtr
->windowSize
= windowSize
;
3283 fparamsPtr
->dictID
= dictID
;
3284 fparamsPtr
->checksumFlag
= checksumFlag
;
3290 /** ZSTDv07_getDecompressedSize() :
3291 * compatible with legacy mode
3292 * @return : decompressed size if known, 0 otherwise
3293 note : 0 can mean any of the following :
3294 - decompressed size is not provided within frame header
3295 - frame header unknown / not supported
3296 - frame header not completely provided (`srcSize` too small) */
3297 unsigned long long ZSTDv07_getDecompressedSize(const void* src
, size_t srcSize
)
3299 { ZSTDv07_frameParams fparams
;
3300 size_t const frResult
= ZSTDv07_getFrameParams(&fparams
, src
, srcSize
);
3301 if (frResult
!=0) return 0;
3302 return fparams
.frameContentSize
;
3307 /** ZSTDv07_decodeFrameHeader() :
3308 * `srcSize` must be the size provided by ZSTDv07_frameHeaderSize().
3309 * @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */
3310 static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx
* dctx
, const void* src
, size_t srcSize
)
3312 size_t const result
= ZSTDv07_getFrameParams(&(dctx
->fParams
), src
, srcSize
);
3313 if (dctx
->fParams
.dictID
&& (dctx
->dictID
!= dctx
->fParams
.dictID
)) return ERROR(dictionary_wrong
);
3314 if (dctx
->fParams
.checksumFlag
) XXH64_reset(&dctx
->xxhState
, 0);
3321 blockType_t blockType
;
3323 } blockProperties_t
;
3325 /*! ZSTDv07_getcBlockSize() :
3326 * Provides the size of compressed block from block header `src` */
3327 size_t ZSTDv07_getcBlockSize(const void* src
, size_t srcSize
, blockProperties_t
* bpPtr
)
3329 const BYTE
* const in
= (const BYTE
* const)src
;
3332 if (srcSize
< ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3334 bpPtr
->blockType
= (blockType_t
)((*in
) >> 6);
3335 cSize
= in
[2] + (in
[1]<<8) + ((in
[0] & 7)<<16);
3336 bpPtr
->origSize
= (bpPtr
->blockType
== bt_rle
) ? cSize
: 0;
3338 if (bpPtr
->blockType
== bt_end
) return 0;
3339 if (bpPtr
->blockType
== bt_rle
) return 1;
3344 static size_t ZSTDv07_copyRawBlock(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3346 if (srcSize
> dstCapacity
) return ERROR(dstSize_tooSmall
);
3347 memcpy(dst
, src
, srcSize
);
3352 /*! ZSTDv07_decodeLiteralsBlock() :
3353 @return : nb of bytes read from src (< srcSize ) */
3354 size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx
* dctx
,
3355 const void* src
, size_t srcSize
) /* note : srcSize < BLOCKSIZE */
3357 const BYTE
* const istart
= (const BYTE
*) src
;
3359 if (srcSize
< MIN_CBLOCK_SIZE
) return ERROR(corruption_detected
);
3361 switch((litBlockType_t
)(istart
[0]>> 6))
3364 { size_t litSize
, litCSize
, singleStream
=0;
3365 U32 lhSize
= (istart
[0] >> 4) & 3;
3366 if (srcSize
< 5) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3369 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3370 /* 2 - 2 - 10 - 10 */
3372 singleStream
= istart
[0] & 16;
3373 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
3374 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
3377 /* 2 - 2 - 14 - 14 */
3379 litSize
= ((istart
[0] & 15) << 10) + (istart
[1] << 2) + (istart
[2] >> 6);
3380 litCSize
= ((istart
[2] & 63) << 8) + istart
[3];
3383 /* 2 - 2 - 18 - 18 */
3385 litSize
= ((istart
[0] & 15) << 14) + (istart
[1] << 6) + (istart
[2] >> 2);
3386 litCSize
= ((istart
[2] & 3) << 16) + (istart
[3] << 8) + istart
[4];
3389 if (litSize
> ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
) return ERROR(corruption_detected
);
3390 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
3392 if (HUFv07_isError(singleStream
?
3393 HUFv07_decompress1X2_DCtx(dctx
->hufTable
, dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) :
3394 HUFv07_decompress4X_hufOnly (dctx
->hufTable
, dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
) ))
3395 return ERROR(corruption_detected
);
3397 dctx
->litPtr
= dctx
->litBuffer
;
3398 dctx
->litSize
= litSize
;
3399 dctx
->litEntropy
= 1;
3400 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3401 return litCSize
+ lhSize
;
3404 { size_t litSize
, litCSize
;
3405 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3406 if (lhSize
!= 1) /* only case supported for now : small litSize, single stream */
3407 return ERROR(corruption_detected
);
3408 if (dctx
->litEntropy
==0)
3409 return ERROR(dictionary_corrupted
);
3411 /* 2 - 2 - 10 - 10 */
3413 litSize
= ((istart
[0] & 15) << 6) + (istart
[1] >> 2);
3414 litCSize
= ((istart
[1] & 3) << 8) + istart
[2];
3415 if (litCSize
+ lhSize
> srcSize
) return ERROR(corruption_detected
);
3417 { size_t const errorCode
= HUFv07_decompress1X4_usingDTable(dctx
->litBuffer
, litSize
, istart
+lhSize
, litCSize
, dctx
->hufTable
);
3418 if (HUFv07_isError(errorCode
)) return ERROR(corruption_detected
);
3420 dctx
->litPtr
= dctx
->litBuffer
;
3421 dctx
->litSize
= litSize
;
3422 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3423 return litCSize
+ lhSize
;
3427 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3430 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3432 litSize
= istart
[0] & 31;
3435 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3438 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3442 if (lhSize
+litSize
+WILDCOPY_OVERLENGTH
> srcSize
) { /* risk reading beyond src buffer with wildcopy */
3443 if (litSize
+lhSize
> srcSize
) return ERROR(corruption_detected
);
3444 memcpy(dctx
->litBuffer
, istart
+lhSize
, litSize
);
3445 dctx
->litPtr
= dctx
->litBuffer
;
3446 dctx
->litSize
= litSize
;
3447 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, WILDCOPY_OVERLENGTH
);
3448 return lhSize
+litSize
;
3450 /* direct reference into compressed stream */
3451 dctx
->litPtr
= istart
+lhSize
;
3452 dctx
->litSize
= litSize
;
3453 return lhSize
+litSize
;
3457 U32 lhSize
= ((istart
[0]) >> 4) & 3;
3460 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3462 litSize
= istart
[0] & 31;
3465 litSize
= ((istart
[0] & 15) << 8) + istart
[1];
3468 litSize
= ((istart
[0] & 15) << 16) + (istart
[1] << 8) + istart
[2];
3469 if (srcSize
<4) return ERROR(corruption_detected
); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3472 if (litSize
> ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
) return ERROR(corruption_detected
);
3473 memset(dctx
->litBuffer
, istart
[lhSize
], litSize
+ WILDCOPY_OVERLENGTH
);
3474 dctx
->litPtr
= dctx
->litBuffer
;
3475 dctx
->litSize
= litSize
;
3479 return ERROR(corruption_detected
); /* impossible */
3484 /*! ZSTDv07_buildSeqTable() :
3485 @return : nb bytes read from src,
3486 or an error code if it fails, testable with ZSTDv07_isError()
3488 size_t ZSTDv07_buildSeqTable(FSEv07_DTable
* DTable
, U32 type
, U32 max
, U32 maxLog
,
3489 const void* src
, size_t srcSize
,
3490 const S16
* defaultNorm
, U32 defaultLog
, U32 flagRepeatTable
)
3494 case FSEv07_ENCODING_RLE
:
3495 if (!srcSize
) return ERROR(srcSize_wrong
);
3496 if ( (*(const BYTE
*)src
) > max
) return ERROR(corruption_detected
);
3497 FSEv07_buildDTable_rle(DTable
, *(const BYTE
*)src
); /* if *src > max, data is corrupted */
3499 case FSEv07_ENCODING_RAW
:
3500 FSEv07_buildDTable(DTable
, defaultNorm
, max
, defaultLog
);
3502 case FSEv07_ENCODING_STATIC
:
3503 if (!flagRepeatTable
) return ERROR(corruption_detected
);
3505 default : /* impossible */
3506 case FSEv07_ENCODING_DYNAMIC
:
3509 size_t const headerSize
= FSEv07_readNCount(norm
, &max
, &tableLog
, src
, srcSize
);
3510 if (FSEv07_isError(headerSize
)) return ERROR(corruption_detected
);
3511 if (tableLog
> maxLog
) return ERROR(corruption_detected
);
3512 FSEv07_buildDTable(DTable
, norm
, max
, tableLog
);
3518 size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr
,
3519 FSEv07_DTable
* DTableLL
, FSEv07_DTable
* DTableML
, FSEv07_DTable
* DTableOffb
, U32 flagRepeatTable
,
3520 const void* src
, size_t srcSize
)
3522 const BYTE
* const istart
= (const BYTE
* const)src
;
3523 const BYTE
* const iend
= istart
+ srcSize
;
3524 const BYTE
* ip
= istart
;
3527 if (srcSize
< MIN_SEQUENCES_SIZE
) return ERROR(srcSize_wrong
);
3530 { int nbSeq
= *ip
++;
3531 if (!nbSeq
) { *nbSeqPtr
=0; return 1; }
3533 if (nbSeq
== 0xFF) {
3534 if (ip
+2 > iend
) return ERROR(srcSize_wrong
);
3535 nbSeq
= MEM_readLE16(ip
) + LONGNBSEQ
, ip
+=2;
3537 if (ip
>= iend
) return ERROR(srcSize_wrong
);
3538 nbSeq
= ((nbSeq
-0x80)<<8) + *ip
++;
3544 /* FSE table descriptors */
3545 { U32
const LLtype
= *ip
>> 6;
3546 U32
const OFtype
= (*ip
>> 4) & 3;
3547 U32
const MLtype
= (*ip
>> 2) & 3;
3551 if (ip
> iend
-3) return ERROR(srcSize_wrong
); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3554 { size_t const llhSize
= ZSTDv07_buildSeqTable(DTableLL
, LLtype
, MaxLL
, LLFSELog
, ip
, iend
-ip
, LL_defaultNorm
, LL_defaultNormLog
, flagRepeatTable
);
3555 if (ZSTDv07_isError(llhSize
)) return ERROR(corruption_detected
);
3558 { size_t const ofhSize
= ZSTDv07_buildSeqTable(DTableOffb
, OFtype
, MaxOff
, OffFSELog
, ip
, iend
-ip
, OF_defaultNorm
, OF_defaultNormLog
, flagRepeatTable
);
3559 if (ZSTDv07_isError(ofhSize
)) return ERROR(corruption_detected
);
3562 { size_t const mlhSize
= ZSTDv07_buildSeqTable(DTableML
, MLtype
, MaxML
, MLFSELog
, ip
, iend
-ip
, ML_defaultNorm
, ML_defaultNormLog
, flagRepeatTable
);
3563 if (ZSTDv07_isError(mlhSize
)) return ERROR(corruption_detected
);
3578 BITv07_DStream_t DStream
;
3579 FSEv07_DState_t stateLL
;
3580 FSEv07_DState_t stateOffb
;
3581 FSEv07_DState_t stateML
;
3582 size_t prevOffset
[ZSTDv07_REP_INIT
];
3586 static seq_t
ZSTDv07_decodeSequence(seqState_t
* seqState
)
3590 U32
const llCode
= FSEv07_peekSymbol(&(seqState
->stateLL
));
3591 U32
const mlCode
= FSEv07_peekSymbol(&(seqState
->stateML
));
3592 U32
const ofCode
= FSEv07_peekSymbol(&(seqState
->stateOffb
)); /* <= maxOff, by table construction */
3594 U32
const llBits
= LL_bits
[llCode
];
3595 U32
const mlBits
= ML_bits
[mlCode
];
3596 U32
const ofBits
= ofCode
;
3597 U32
const totalBits
= llBits
+mlBits
+ofBits
;
3599 static const U32 LL_base
[MaxLL
+1] = {
3600 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3601 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3602 0x2000, 0x4000, 0x8000, 0x10000 };
3604 static const U32 ML_base
[MaxML
+1] = {
3605 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
3606 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
3607 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3608 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3610 static const U32 OF_base
[MaxOff
+1] = {
3611 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
3612 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
3613 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3614 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3621 offset
= OF_base
[ofCode
] + BITv07_readBits(&(seqState
->DStream
), ofBits
); /* <= (ZSTDv07_WINDOWLOG_MAX-1) bits */
3622 if (MEM_32bits()) BITv07_reloadDStream(&(seqState
->DStream
));
3626 if ((llCode
== 0) & (offset
<= 1)) offset
= 1-offset
;
3628 size_t const temp
= seqState
->prevOffset
[offset
];
3629 if (offset
!= 1) seqState
->prevOffset
[2] = seqState
->prevOffset
[1];
3630 seqState
->prevOffset
[1] = seqState
->prevOffset
[0];
3631 seqState
->prevOffset
[0] = offset
= temp
;
3633 offset
= seqState
->prevOffset
[0];
3636 seqState
->prevOffset
[2] = seqState
->prevOffset
[1];
3637 seqState
->prevOffset
[1] = seqState
->prevOffset
[0];
3638 seqState
->prevOffset
[0] = offset
;
3640 seq
.offset
= offset
;
3643 seq
.matchLength
= ML_base
[mlCode
] + ((mlCode
>31) ? BITv07_readBits(&(seqState
->DStream
), mlBits
) : 0); /* <= 16 bits */
3644 if (MEM_32bits() && (mlBits
+llBits
>24)) BITv07_reloadDStream(&(seqState
->DStream
));
3646 seq
.litLength
= LL_base
[llCode
] + ((llCode
>15) ? BITv07_readBits(&(seqState
->DStream
), llBits
) : 0); /* <= 16 bits */
3648 (totalBits
> 64 - 7 - (LLFSELog
+MLFSELog
+OffFSELog
)) ) BITv07_reloadDStream(&(seqState
->DStream
));
3650 /* ANS state update */
3651 FSEv07_updateState(&(seqState
->stateLL
), &(seqState
->DStream
)); /* <= 9 bits */
3652 FSEv07_updateState(&(seqState
->stateML
), &(seqState
->DStream
)); /* <= 9 bits */
3653 if (MEM_32bits()) BITv07_reloadDStream(&(seqState
->DStream
)); /* <= 18 bits */
3654 FSEv07_updateState(&(seqState
->stateOffb
), &(seqState
->DStream
)); /* <= 8 bits */
3661 size_t ZSTDv07_execSequence(BYTE
* op
,
3662 BYTE
* const oend
, seq_t sequence
,
3663 const BYTE
** litPtr
, const BYTE
* const litLimit
,
3664 const BYTE
* const base
, const BYTE
* const vBase
, const BYTE
* const dictEnd
)
3666 BYTE
* const oLitEnd
= op
+ sequence
.litLength
;
3667 size_t const sequenceLength
= sequence
.litLength
+ sequence
.matchLength
;
3668 BYTE
* const oMatchEnd
= op
+ sequenceLength
; /* risk : address space overflow (32-bits) */
3669 BYTE
* const oend_w
= oend
-WILDCOPY_OVERLENGTH
;
3670 const BYTE
* const iLitEnd
= *litPtr
+ sequence
.litLength
;
3671 const BYTE
* match
= oLitEnd
- sequence
.offset
;
3674 if ((oLitEnd
>oend_w
) | (oMatchEnd
>oend
)) return ERROR(dstSize_tooSmall
); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
3675 if (iLitEnd
> litLimit
) return ERROR(corruption_detected
); /* over-read beyond lit buffer */
3678 ZSTDv07_wildcopy(op
, *litPtr
, sequence
.litLength
); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3680 *litPtr
= iLitEnd
; /* update for next sequence */
3683 if (sequence
.offset
> (size_t)(oLitEnd
- base
)) {
3684 /* offset beyond prefix */
3685 if (sequence
.offset
> (size_t)(oLitEnd
- vBase
)) return ERROR(corruption_detected
);
3686 match
= dictEnd
- (base
-match
);
3687 if (match
+ sequence
.matchLength
<= dictEnd
) {
3688 memmove(oLitEnd
, match
, sequence
.matchLength
);
3689 return sequenceLength
;
3691 /* span extDict & currentPrefixSegment */
3692 { size_t const length1
= dictEnd
- match
;
3693 memmove(oLitEnd
, match
, length1
);
3694 op
= oLitEnd
+ length1
;
3695 sequence
.matchLength
-= length1
;
3697 if (op
> oend_w
|| sequence
.matchLength
< MINMATCH
) {
3698 while (op
< oMatchEnd
) *op
++ = *match
++;
3699 return sequenceLength
;
3702 /* Requirement: op <= oend_w */
3704 /* match within prefix */
3705 if (sequence
.offset
< 8) {
3706 /* close range match, overlap */
3707 static const U32 dec32table
[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3708 static const int dec64table
[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3709 int const sub2
= dec64table
[sequence
.offset
];
3714 match
+= dec32table
[sequence
.offset
];
3715 ZSTDv07_copy4(op
+4, match
);
3718 ZSTDv07_copy8(op
, match
);
3720 op
+= 8; match
+= 8;
3722 if (oMatchEnd
> oend
-(16-MINMATCH
)) {
3724 ZSTDv07_wildcopy(op
, match
, oend_w
- op
);
3725 match
+= oend_w
- op
;
3728 while (op
< oMatchEnd
) *op
++ = *match
++;
3730 ZSTDv07_wildcopy(op
, match
, (ptrdiff_t)sequence
.matchLength
-8); /* works even if matchLength < 8 */
3732 return sequenceLength
;
3736 static size_t ZSTDv07_decompressSequences(
3738 void* dst
, size_t maxDstSize
,
3739 const void* seqStart
, size_t seqSize
)
3741 const BYTE
* ip
= (const BYTE
*)seqStart
;
3742 const BYTE
* const iend
= ip
+ seqSize
;
3743 BYTE
* const ostart
= (BYTE
* const)dst
;
3744 BYTE
* const oend
= ostart
+ maxDstSize
;
3746 const BYTE
* litPtr
= dctx
->litPtr
;
3747 const BYTE
* const litEnd
= litPtr
+ dctx
->litSize
;
3748 FSEv07_DTable
* DTableLL
= dctx
->LLTable
;
3749 FSEv07_DTable
* DTableML
= dctx
->MLTable
;
3750 FSEv07_DTable
* DTableOffb
= dctx
->OffTable
;
3751 const BYTE
* const base
= (const BYTE
*) (dctx
->base
);
3752 const BYTE
* const vBase
= (const BYTE
*) (dctx
->vBase
);
3753 const BYTE
* const dictEnd
= (const BYTE
*) (dctx
->dictEnd
);
3756 /* Build Decoding Tables */
3757 { size_t const seqHSize
= ZSTDv07_decodeSeqHeaders(&nbSeq
, DTableLL
, DTableML
, DTableOffb
, dctx
->fseEntropy
, ip
, seqSize
);
3758 if (ZSTDv07_isError(seqHSize
)) return seqHSize
;
3762 /* Regen sequences */
3764 seqState_t seqState
;
3765 dctx
->fseEntropy
= 1;
3766 { U32 i
; for (i
=0; i
<ZSTDv07_REP_INIT
; i
++) seqState
.prevOffset
[i
] = dctx
->rep
[i
]; }
3767 { size_t const errorCode
= BITv07_initDStream(&(seqState
.DStream
), ip
, iend
-ip
);
3768 if (ERR_isError(errorCode
)) return ERROR(corruption_detected
); }
3769 FSEv07_initDState(&(seqState
.stateLL
), &(seqState
.DStream
), DTableLL
);
3770 FSEv07_initDState(&(seqState
.stateOffb
), &(seqState
.DStream
), DTableOffb
);
3771 FSEv07_initDState(&(seqState
.stateML
), &(seqState
.DStream
), DTableML
);
3773 for ( ; (BITv07_reloadDStream(&(seqState
.DStream
)) <= BITv07_DStream_completed
) && nbSeq
; ) {
3775 { seq_t
const sequence
= ZSTDv07_decodeSequence(&seqState
);
3776 size_t const oneSeqSize
= ZSTDv07_execSequence(op
, oend
, sequence
, &litPtr
, litEnd
, base
, vBase
, dictEnd
);
3777 if (ZSTDv07_isError(oneSeqSize
)) return oneSeqSize
;
3781 /* check if reached exact end */
3782 if (nbSeq
) return ERROR(corruption_detected
);
3783 /* save reps for next block */
3784 { U32 i
; for (i
=0; i
<ZSTDv07_REP_INIT
; i
++) dctx
->rep
[i
] = (U32
)(seqState
.prevOffset
[i
]); }
3787 /* last literal segment */
3788 { size_t const lastLLSize
= litEnd
- litPtr
;
3789 //if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3790 if (lastLLSize
> (size_t)(oend
-op
)) return ERROR(dstSize_tooSmall
);
3791 memcpy(op
, litPtr
, lastLLSize
);
3799 static void ZSTDv07_checkContinuity(ZSTDv07_DCtx
* dctx
, const void* dst
)
3801 if (dst
!= dctx
->previousDstEnd
) { /* not contiguous */
3802 dctx
->dictEnd
= dctx
->previousDstEnd
;
3803 dctx
->vBase
= (const char*)dst
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
3805 dctx
->previousDstEnd
= dst
;
3810 static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx
* dctx
,
3811 void* dst
, size_t dstCapacity
,
3812 const void* src
, size_t srcSize
)
3813 { /* blockType == blockCompressed */
3814 const BYTE
* ip
= (const BYTE
*)src
;
3816 if (srcSize
>= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
) return ERROR(srcSize_wrong
);
3818 /* Decode literals sub-block */
3819 { size_t const litCSize
= ZSTDv07_decodeLiteralsBlock(dctx
, src
, srcSize
);
3820 if (ZSTDv07_isError(litCSize
)) return litCSize
;
3822 srcSize
-= litCSize
;
3824 return ZSTDv07_decompressSequences(dctx
, dst
, dstCapacity
, ip
, srcSize
);
3828 size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx
* dctx
,
3829 void* dst
, size_t dstCapacity
,
3830 const void* src
, size_t srcSize
)
3833 ZSTDv07_checkContinuity(dctx
, dst
);
3834 dSize
= ZSTDv07_decompressBlock_internal(dctx
, dst
, dstCapacity
, src
, srcSize
);
3835 dctx
->previousDstEnd
= (char*)dst
+ dSize
;
3840 /** ZSTDv07_insertBlock() :
3841 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
3842 ZSTDLIBv07_API
size_t ZSTDv07_insertBlock(ZSTDv07_DCtx
* dctx
, const void* blockStart
, size_t blockSize
)
3844 ZSTDv07_checkContinuity(dctx
, blockStart
);
3845 dctx
->previousDstEnd
= (const char*)blockStart
+ blockSize
;
3850 size_t ZSTDv07_generateNxBytes(void* dst
, size_t dstCapacity
, BYTE byte
, size_t length
)
3852 if (length
> dstCapacity
) return ERROR(dstSize_tooSmall
);
3853 memset(dst
, byte
, length
);
3858 /*! ZSTDv07_decompressFrame() :
3859 * `dctx` must be properly initialized */
3860 static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx
* dctx
,
3861 void* dst
, size_t dstCapacity
,
3862 const void* src
, size_t srcSize
)
3864 const BYTE
* ip
= (const BYTE
*)src
;
3865 const BYTE
* const iend
= ip
+ srcSize
;
3866 BYTE
* const ostart
= (BYTE
* const)dst
;
3867 BYTE
* const oend
= ostart
+ dstCapacity
;
3869 size_t remainingSize
= srcSize
;
3872 if (srcSize
< ZSTDv07_frameHeaderSize_min
+ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3875 { size_t const frameHeaderSize
= ZSTDv07_frameHeaderSize(src
, ZSTDv07_frameHeaderSize_min
);
3876 if (ZSTDv07_isError(frameHeaderSize
)) return frameHeaderSize
;
3877 if (srcSize
< frameHeaderSize
+ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3878 if (ZSTDv07_decodeFrameHeader(dctx
, src
, frameHeaderSize
)) return ERROR(corruption_detected
);
3879 ip
+= frameHeaderSize
; remainingSize
-= frameHeaderSize
;
3882 /* Loop on each block */
3885 blockProperties_t blockProperties
;
3886 size_t const cBlockSize
= ZSTDv07_getcBlockSize(ip
, iend
-ip
, &blockProperties
);
3887 if (ZSTDv07_isError(cBlockSize
)) return cBlockSize
;
3889 ip
+= ZSTDv07_blockHeaderSize
;
3890 remainingSize
-= ZSTDv07_blockHeaderSize
;
3891 if (cBlockSize
> remainingSize
) return ERROR(srcSize_wrong
);
3893 switch(blockProperties
.blockType
)
3896 decodedSize
= ZSTDv07_decompressBlock_internal(dctx
, op
, oend
-op
, ip
, cBlockSize
);
3899 decodedSize
= ZSTDv07_copyRawBlock(op
, oend
-op
, ip
, cBlockSize
);
3902 decodedSize
= ZSTDv07_generateNxBytes(op
, oend
-op
, *ip
, blockProperties
.origSize
);
3906 if (remainingSize
) return ERROR(srcSize_wrong
);
3910 return ERROR(GENERIC
); /* impossible */
3912 if (blockProperties
.blockType
== bt_end
) break; /* bt_end */
3914 if (ZSTDv07_isError(decodedSize
)) return decodedSize
;
3915 if (dctx
->fParams
.checksumFlag
) XXH64_update(&dctx
->xxhState
, op
, decodedSize
);
3918 remainingSize
-= cBlockSize
;
3925 /*! ZSTDv07_decompress_usingPreparedDCtx() :
3926 * Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
3927 * It avoids reloading the dictionary each time.
3928 * `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict().
3929 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
3930 size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx
* dctx
, const ZSTDv07_DCtx
* refDCtx
,
3931 void* dst
, size_t dstCapacity
,
3932 const void* src
, size_t srcSize
)
3934 ZSTDv07_copyDCtx(dctx
, refDCtx
);
3935 ZSTDv07_checkContinuity(dctx
, dst
);
3936 return ZSTDv07_decompressFrame(dctx
, dst
, dstCapacity
, src
, srcSize
);
3940 size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx
* dctx
,
3941 void* dst
, size_t dstCapacity
,
3942 const void* src
, size_t srcSize
,
3943 const void* dict
, size_t dictSize
)
3945 ZSTDv07_decompressBegin_usingDict(dctx
, dict
, dictSize
);
3946 ZSTDv07_checkContinuity(dctx
, dst
);
3947 return ZSTDv07_decompressFrame(dctx
, dst
, dstCapacity
, src
, srcSize
);
3951 size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3953 return ZSTDv07_decompress_usingDict(dctx
, dst
, dstCapacity
, src
, srcSize
, NULL
, 0);
3957 size_t ZSTDv07_decompress(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
3959 #if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1)
3961 ZSTDv07_DCtx
* const dctx
= ZSTDv07_createDCtx();
3962 if (dctx
==NULL
) return ERROR(memory_allocation
);
3963 regenSize
= ZSTDv07_decompressDCtx(dctx
, dst
, dstCapacity
, src
, srcSize
);
3964 ZSTDv07_freeDCtx(dctx
);
3966 #else /* stack mode */
3968 return ZSTDv07_decompressDCtx(&dctx
, dst
, dstCapacity
, src
, srcSize
);
3972 size_t ZSTDv07_findFrameCompressedSize(const void* src
, size_t srcSize
)
3974 const BYTE
* ip
= (const BYTE
*)src
;
3975 size_t remainingSize
= srcSize
;
3978 if (srcSize
< ZSTDv07_frameHeaderSize_min
+ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3981 { size_t const frameHeaderSize
= ZSTDv07_frameHeaderSize(src
, ZSTDv07_frameHeaderSize_min
);
3982 if (ZSTDv07_isError(frameHeaderSize
)) return frameHeaderSize
;
3983 if (MEM_readLE32(src
) != ZSTDv07_MAGICNUMBER
) return ERROR(prefix_unknown
);
3984 if (srcSize
< frameHeaderSize
+ZSTDv07_blockHeaderSize
) return ERROR(srcSize_wrong
);
3985 ip
+= frameHeaderSize
; remainingSize
-= frameHeaderSize
;
3988 /* Loop on each block */
3990 blockProperties_t blockProperties
;
3991 size_t const cBlockSize
= ZSTDv07_getcBlockSize(ip
, remainingSize
, &blockProperties
);
3992 if (ZSTDv07_isError(cBlockSize
)) return cBlockSize
;
3994 ip
+= ZSTDv07_blockHeaderSize
;
3995 remainingSize
-= ZSTDv07_blockHeaderSize
;
3997 if (blockProperties
.blockType
== bt_end
) break;
3999 if (cBlockSize
> remainingSize
) return ERROR(srcSize_wrong
);
4002 remainingSize
-= cBlockSize
;
4005 return ip
- (const BYTE
*)src
;
4008 /*_******************************
4009 * Streaming Decompression API
4010 ********************************/
4011 size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx
* dctx
)
4013 return dctx
->expected
;
4016 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx
* dctx
)
4018 return dctx
->stage
== ZSTDds_skipFrame
;
4021 /** ZSTDv07_decompressContinue() :
4022 * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
4023 * or an error code, which can be tested using ZSTDv07_isError() */
4024 size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx
* dctx
, void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
4027 if (srcSize
!= dctx
->expected
) return ERROR(srcSize_wrong
);
4028 if (dstCapacity
) ZSTDv07_checkContinuity(dctx
, dst
);
4030 switch (dctx
->stage
)
4032 case ZSTDds_getFrameHeaderSize
:
4033 if (srcSize
!= ZSTDv07_frameHeaderSize_min
) return ERROR(srcSize_wrong
); /* impossible */
4034 if ((MEM_readLE32(src
) & 0xFFFFFFF0U
) == ZSTDv07_MAGIC_SKIPPABLE_START
) {
4035 memcpy(dctx
->headerBuffer
, src
, ZSTDv07_frameHeaderSize_min
);
4036 dctx
->expected
= ZSTDv07_skippableHeaderSize
- ZSTDv07_frameHeaderSize_min
; /* magic number + skippable frame length */
4037 dctx
->stage
= ZSTDds_decodeSkippableHeader
;
4040 dctx
->headerSize
= ZSTDv07_frameHeaderSize(src
, ZSTDv07_frameHeaderSize_min
);
4041 if (ZSTDv07_isError(dctx
->headerSize
)) return dctx
->headerSize
;
4042 memcpy(dctx
->headerBuffer
, src
, ZSTDv07_frameHeaderSize_min
);
4043 if (dctx
->headerSize
> ZSTDv07_frameHeaderSize_min
) {
4044 dctx
->expected
= dctx
->headerSize
- ZSTDv07_frameHeaderSize_min
;
4045 dctx
->stage
= ZSTDds_decodeFrameHeader
;
4048 dctx
->expected
= 0; /* not necessary to copy more */
4050 case ZSTDds_decodeFrameHeader
:
4052 memcpy(dctx
->headerBuffer
+ ZSTDv07_frameHeaderSize_min
, src
, dctx
->expected
);
4053 result
= ZSTDv07_decodeFrameHeader(dctx
, dctx
->headerBuffer
, dctx
->headerSize
);
4054 if (ZSTDv07_isError(result
)) return result
;
4055 dctx
->expected
= ZSTDv07_blockHeaderSize
;
4056 dctx
->stage
= ZSTDds_decodeBlockHeader
;
4059 case ZSTDds_decodeBlockHeader
:
4060 { blockProperties_t bp
;
4061 size_t const cBlockSize
= ZSTDv07_getcBlockSize(src
, ZSTDv07_blockHeaderSize
, &bp
);
4062 if (ZSTDv07_isError(cBlockSize
)) return cBlockSize
;
4063 if (bp
.blockType
== bt_end
) {
4064 if (dctx
->fParams
.checksumFlag
) {
4065 U64
const h64
= XXH64_digest(&dctx
->xxhState
);
4066 U32
const h32
= (U32
)(h64
>>11) & ((1<<22)-1);
4067 const BYTE
* const ip
= (const BYTE
*)src
;
4068 U32
const check32
= ip
[2] + (ip
[1] << 8) + ((ip
[0] & 0x3F) << 16);
4069 if (check32
!= h32
) return ERROR(checksum_wrong
);
4072 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
4074 dctx
->expected
= cBlockSize
;
4075 dctx
->bType
= bp
.blockType
;
4076 dctx
->stage
= ZSTDds_decompressBlock
;
4080 case ZSTDds_decompressBlock
:
4085 rSize
= ZSTDv07_decompressBlock_internal(dctx
, dst
, dstCapacity
, src
, srcSize
);
4088 rSize
= ZSTDv07_copyRawBlock(dst
, dstCapacity
, src
, srcSize
);
4091 return ERROR(GENERIC
); /* not yet handled */
4093 case bt_end
: /* should never happen (filtered at phase 1) */
4097 return ERROR(GENERIC
); /* impossible */
4099 dctx
->stage
= ZSTDds_decodeBlockHeader
;
4100 dctx
->expected
= ZSTDv07_blockHeaderSize
;
4101 dctx
->previousDstEnd
= (char*)dst
+ rSize
;
4102 if (ZSTDv07_isError(rSize
)) return rSize
;
4103 if (dctx
->fParams
.checksumFlag
) XXH64_update(&dctx
->xxhState
, dst
, rSize
);
4106 case ZSTDds_decodeSkippableHeader
:
4107 { memcpy(dctx
->headerBuffer
+ ZSTDv07_frameHeaderSize_min
, src
, dctx
->expected
);
4108 dctx
->expected
= MEM_readLE32(dctx
->headerBuffer
+ 4);
4109 dctx
->stage
= ZSTDds_skipFrame
;
4112 case ZSTDds_skipFrame
:
4113 { dctx
->expected
= 0;
4114 dctx
->stage
= ZSTDds_getFrameHeaderSize
;
4118 return ERROR(GENERIC
); /* impossible */
4123 static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
)
4125 dctx
->dictEnd
= dctx
->previousDstEnd
;
4126 dctx
->vBase
= (const char*)dict
- ((const char*)(dctx
->previousDstEnd
) - (const char*)(dctx
->base
));
4128 dctx
->previousDstEnd
= (const char*)dict
+ dictSize
;
4132 static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx
* dctx
, const void* const dict
, size_t const dictSize
)
4134 const BYTE
* dictPtr
= (const BYTE
*)dict
;
4135 const BYTE
* const dictEnd
= dictPtr
+ dictSize
;
4137 { size_t const hSize
= HUFv07_readDTableX4(dctx
->hufTable
, dict
, dictSize
);
4138 if (HUFv07_isError(hSize
)) return ERROR(dictionary_corrupted
);
4142 { short offcodeNCount
[MaxOff
+1];
4143 U32 offcodeMaxValue
=MaxOff
, offcodeLog
;
4144 size_t const offcodeHeaderSize
= FSEv07_readNCount(offcodeNCount
, &offcodeMaxValue
, &offcodeLog
, dictPtr
, dictEnd
-dictPtr
);
4145 if (FSEv07_isError(offcodeHeaderSize
)) return ERROR(dictionary_corrupted
);
4146 if (offcodeLog
> OffFSELog
) return ERROR(dictionary_corrupted
);
4147 { size_t const errorCode
= FSEv07_buildDTable(dctx
->OffTable
, offcodeNCount
, offcodeMaxValue
, offcodeLog
);
4148 if (FSEv07_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
4149 dictPtr
+= offcodeHeaderSize
;
4152 { short matchlengthNCount
[MaxML
+1];
4153 unsigned matchlengthMaxValue
= MaxML
, matchlengthLog
;
4154 size_t const matchlengthHeaderSize
= FSEv07_readNCount(matchlengthNCount
, &matchlengthMaxValue
, &matchlengthLog
, dictPtr
, dictEnd
-dictPtr
);
4155 if (FSEv07_isError(matchlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
4156 if (matchlengthLog
> MLFSELog
) return ERROR(dictionary_corrupted
);
4157 { size_t const errorCode
= FSEv07_buildDTable(dctx
->MLTable
, matchlengthNCount
, matchlengthMaxValue
, matchlengthLog
);
4158 if (FSEv07_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
4159 dictPtr
+= matchlengthHeaderSize
;
4162 { short litlengthNCount
[MaxLL
+1];
4163 unsigned litlengthMaxValue
= MaxLL
, litlengthLog
;
4164 size_t const litlengthHeaderSize
= FSEv07_readNCount(litlengthNCount
, &litlengthMaxValue
, &litlengthLog
, dictPtr
, dictEnd
-dictPtr
);
4165 if (FSEv07_isError(litlengthHeaderSize
)) return ERROR(dictionary_corrupted
);
4166 if (litlengthLog
> LLFSELog
) return ERROR(dictionary_corrupted
);
4167 { size_t const errorCode
= FSEv07_buildDTable(dctx
->LLTable
, litlengthNCount
, litlengthMaxValue
, litlengthLog
);
4168 if (FSEv07_isError(errorCode
)) return ERROR(dictionary_corrupted
); }
4169 dictPtr
+= litlengthHeaderSize
;
4172 if (dictPtr
+12 > dictEnd
) return ERROR(dictionary_corrupted
);
4173 dctx
->rep
[0] = MEM_readLE32(dictPtr
+0); if (dctx
->rep
[0] == 0 || dctx
->rep
[0] >= dictSize
) return ERROR(dictionary_corrupted
);
4174 dctx
->rep
[1] = MEM_readLE32(dictPtr
+4); if (dctx
->rep
[1] == 0 || dctx
->rep
[1] >= dictSize
) return ERROR(dictionary_corrupted
);
4175 dctx
->rep
[2] = MEM_readLE32(dictPtr
+8); if (dctx
->rep
[2] == 0 || dctx
->rep
[2] >= dictSize
) return ERROR(dictionary_corrupted
);
4178 dctx
->litEntropy
= dctx
->fseEntropy
= 1;
4179 return dictPtr
- (const BYTE
*)dict
;
4182 static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
)
4184 if (dictSize
< 8) return ZSTDv07_refDictContent(dctx
, dict
, dictSize
);
4185 { U32
const magic
= MEM_readLE32(dict
);
4186 if (magic
!= ZSTDv07_DICT_MAGIC
) {
4187 return ZSTDv07_refDictContent(dctx
, dict
, dictSize
); /* pure content mode */
4189 dctx
->dictID
= MEM_readLE32((const char*)dict
+ 4);
4191 /* load entropy tables */
4192 dict
= (const char*)dict
+ 8;
4194 { size_t const eSize
= ZSTDv07_loadEntropy(dctx
, dict
, dictSize
);
4195 if (ZSTDv07_isError(eSize
)) return ERROR(dictionary_corrupted
);
4196 dict
= (const char*)dict
+ eSize
;
4200 /* reference dictionary content */
4201 return ZSTDv07_refDictContent(dctx
, dict
, dictSize
);
4205 size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx
* dctx
, const void* dict
, size_t dictSize
)
4207 { size_t const errorCode
= ZSTDv07_decompressBegin(dctx
);
4208 if (ZSTDv07_isError(errorCode
)) return errorCode
; }
4210 if (dict
&& dictSize
) {
4211 size_t const errorCode
= ZSTDv07_decompress_insertDictionary(dctx
, dict
, dictSize
);
4212 if (ZSTDv07_isError(errorCode
)) return ERROR(dictionary_corrupted
);
4219 struct ZSTDv07_DDict_s
{
4222 ZSTDv07_DCtx
* refContext
;
4223 }; /* typedef'd tp ZSTDv07_CDict within zstd.h */
4225 ZSTDv07_DDict
* ZSTDv07_createDDict_advanced(const void* dict
, size_t dictSize
, ZSTDv07_customMem customMem
)
4227 if (!customMem
.customAlloc
&& !customMem
.customFree
)
4228 customMem
= defaultCustomMem
;
4230 if (!customMem
.customAlloc
|| !customMem
.customFree
)
4233 { ZSTDv07_DDict
* const ddict
= (ZSTDv07_DDict
*) customMem
.customAlloc(customMem
.opaque
, sizeof(*ddict
));
4234 void* const dictContent
= customMem
.customAlloc(customMem
.opaque
, dictSize
);
4235 ZSTDv07_DCtx
* const dctx
= ZSTDv07_createDCtx_advanced(customMem
);
4237 if (!dictContent
|| !ddict
|| !dctx
) {
4238 customMem
.customFree(customMem
.opaque
, dictContent
);
4239 customMem
.customFree(customMem
.opaque
, ddict
);
4240 customMem
.customFree(customMem
.opaque
, dctx
);
4244 memcpy(dictContent
, dict
, dictSize
);
4245 { size_t const errorCode
= ZSTDv07_decompressBegin_usingDict(dctx
, dictContent
, dictSize
);
4246 if (ZSTDv07_isError(errorCode
)) {
4247 customMem
.customFree(customMem
.opaque
, dictContent
);
4248 customMem
.customFree(customMem
.opaque
, ddict
);
4249 customMem
.customFree(customMem
.opaque
, dctx
);
4253 ddict
->dict
= dictContent
;
4254 ddict
->dictSize
= dictSize
;
4255 ddict
->refContext
= dctx
;
4260 /*! ZSTDv07_createDDict() :
4261 * Create a digested dictionary, ready to start decompression without startup delay.
4262 * `dict` can be released after `ZSTDv07_DDict` creation */
4263 ZSTDv07_DDict
* ZSTDv07_createDDict(const void* dict
, size_t dictSize
)
4265 ZSTDv07_customMem
const allocator
= { NULL
, NULL
, NULL
};
4266 return ZSTDv07_createDDict_advanced(dict
, dictSize
, allocator
);
4269 size_t ZSTDv07_freeDDict(ZSTDv07_DDict
* ddict
)
4271 ZSTDv07_freeFunction
const cFree
= ddict
->refContext
->customMem
.customFree
;
4272 void* const opaque
= ddict
->refContext
->customMem
.opaque
;
4273 ZSTDv07_freeDCtx(ddict
->refContext
);
4274 cFree(opaque
, ddict
->dict
);
4275 cFree(opaque
, ddict
);
4279 /*! ZSTDv07_decompress_usingDDict() :
4280 * Decompression using a pre-digested Dictionary
4281 * Use dictionary without significant overhead. */
4282 ZSTDLIBv07_API
size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx
* dctx
,
4283 void* dst
, size_t dstCapacity
,
4284 const void* src
, size_t srcSize
,
4285 const ZSTDv07_DDict
* ddict
)
4287 return ZSTDv07_decompress_usingPreparedDCtx(dctx
, ddict
->refContext
,
4292 Buffered version of Zstd compression library
4293 Copyright (C) 2015-2016, Yann Collet.
4295 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
4297 Redistribution and use in source and binary forms, with or without
4298 modification, are permitted provided that the following conditions are
4300 * Redistributions of source code must retain the above copyright
4301 notice, this list of conditions and the following disclaimer.
4302 * Redistributions in binary form must reproduce the above
4303 copyright notice, this list of conditions and the following disclaimer
4304 in the documentation and/or other materials provided with the
4306 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4307 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
4308 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
4309 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
4310 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4311 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
4312 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
4313 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
4314 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
4315 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
4316 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4318 You can contact the author at :
4319 - zstd homepage : http://www.zstd.net/
4324 /*-***************************************************************************
4325 * Streaming decompression howto
4327 * A ZBUFFv07_DCtx object is required to track streaming operations.
4328 * Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources.
4329 * Use ZBUFFv07_decompressInit() to start a new decompression operation,
4330 * or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary.
4331 * Note that ZBUFFv07_DCtx objects can be re-init multiple times.
4333 * Use ZBUFFv07_decompressContinue() repetitively to consume your input.
4334 * *srcSizePtr and *dstCapacityPtr can be any size.
4335 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
4336 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
4337 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
4338 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
4339 * or 0 when a frame is completely decoded,
4340 * or an error code, which can be tested using ZBUFFv07_isError().
4342 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize()
4343 * output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
4344 * input : ZBUFFv07_recommendedDInSize == 128KB + 3;
4345 * just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
4346 * *******************************************************************************/
4348 typedef enum { ZBUFFds_init
, ZBUFFds_loadHeader
,
4349 ZBUFFds_read
, ZBUFFds_load
, ZBUFFds_flush
} ZBUFFv07_dStage
;
4351 /* *** Resource management *** */
4352 struct ZBUFFv07_DCtx_s
{
4354 ZSTDv07_frameParams fParams
;
4355 ZBUFFv07_dStage stage
;
4364 BYTE headerBuffer
[ZSTDv07_FRAMEHEADERSIZE_MAX
];
4366 ZSTDv07_customMem customMem
;
4367 }; /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */
4369 ZSTDLIBv07_API ZBUFFv07_DCtx
* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem
);
4371 ZBUFFv07_DCtx
* ZBUFFv07_createDCtx(void)
4373 return ZBUFFv07_createDCtx_advanced(defaultCustomMem
);
4376 ZBUFFv07_DCtx
* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem
)
4380 if (!customMem
.customAlloc
&& !customMem
.customFree
)
4381 customMem
= defaultCustomMem
;
4383 if (!customMem
.customAlloc
|| !customMem
.customFree
)
4386 zbd
= (ZBUFFv07_DCtx
*)customMem
.customAlloc(customMem
.opaque
, sizeof(ZBUFFv07_DCtx
));
4387 if (zbd
==NULL
) return NULL
;
4388 memset(zbd
, 0, sizeof(ZBUFFv07_DCtx
));
4389 memcpy(&zbd
->customMem
, &customMem
, sizeof(ZSTDv07_customMem
));
4390 zbd
->zd
= ZSTDv07_createDCtx_advanced(customMem
);
4391 if (zbd
->zd
== NULL
) { ZBUFFv07_freeDCtx(zbd
); return NULL
; }
4392 zbd
->stage
= ZBUFFds_init
;
4396 size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx
* zbd
)
4398 if (zbd
==NULL
) return 0; /* support free on null */
4399 ZSTDv07_freeDCtx(zbd
->zd
);
4400 if (zbd
->inBuff
) zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->inBuff
);
4401 if (zbd
->outBuff
) zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->outBuff
);
4402 zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
);
4407 /* *** Initialization *** */
4409 size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx
* zbd
, const void* dict
, size_t dictSize
)
4411 zbd
->stage
= ZBUFFds_loadHeader
;
4412 zbd
->lhSize
= zbd
->inPos
= zbd
->outStart
= zbd
->outEnd
= 0;
4413 return ZSTDv07_decompressBegin_usingDict(zbd
->zd
, dict
, dictSize
);
4416 size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx
* zbd
)
4418 return ZBUFFv07_decompressInitDictionary(zbd
, NULL
, 0);
4422 /* internal util function */
4423 MEM_STATIC
size_t ZBUFFv07_limitCopy(void* dst
, size_t dstCapacity
, const void* src
, size_t srcSize
)
4425 size_t const length
= MIN(dstCapacity
, srcSize
);
4426 memcpy(dst
, src
, length
);
4431 /* *** Decompression *** */
4433 size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx
* zbd
,
4434 void* dst
, size_t* dstCapacityPtr
,
4435 const void* src
, size_t* srcSizePtr
)
4437 const char* const istart
= (const char*)src
;
4438 const char* const iend
= istart
+ *srcSizePtr
;
4439 const char* ip
= istart
;
4440 char* const ostart
= (char*)dst
;
4441 char* const oend
= ostart
+ *dstCapacityPtr
;
4449 return ERROR(init_missing
);
4451 case ZBUFFds_loadHeader
:
4452 { size_t const hSize
= ZSTDv07_getFrameParams(&(zbd
->fParams
), zbd
->headerBuffer
, zbd
->lhSize
);
4453 if (ZSTDv07_isError(hSize
)) return hSize
;
4455 size_t const toLoad
= hSize
- zbd
->lhSize
; /* if hSize!=0, hSize > zbd->lhSize */
4456 if (toLoad
> (size_t)(iend
-ip
)) { /* not enough input to load full header */
4457 memcpy(zbd
->headerBuffer
+ zbd
->lhSize
, ip
, iend
-ip
);
4458 zbd
->lhSize
+= iend
-ip
;
4459 *dstCapacityPtr
= 0;
4460 return (hSize
- zbd
->lhSize
) + ZSTDv07_blockHeaderSize
; /* remaining header bytes + next block header */
4462 memcpy(zbd
->headerBuffer
+ zbd
->lhSize
, ip
, toLoad
); zbd
->lhSize
= hSize
; ip
+= toLoad
;
4466 /* Consume header */
4467 { size_t const h1Size
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
); /* == ZSTDv07_frameHeaderSize_min */
4468 size_t const h1Result
= ZSTDv07_decompressContinue(zbd
->zd
, NULL
, 0, zbd
->headerBuffer
, h1Size
);
4469 if (ZSTDv07_isError(h1Result
)) return h1Result
;
4470 if (h1Size
< zbd
->lhSize
) { /* long header */
4471 size_t const h2Size
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4472 size_t const h2Result
= ZSTDv07_decompressContinue(zbd
->zd
, NULL
, 0, zbd
->headerBuffer
+h1Size
, h2Size
);
4473 if (ZSTDv07_isError(h2Result
)) return h2Result
;
4476 zbd
->fParams
.windowSize
= MAX(zbd
->fParams
.windowSize
, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN
);
4478 /* Frame header instruct buffer sizes */
4479 { size_t const blockSize
= MIN(zbd
->fParams
.windowSize
, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
);
4480 zbd
->blockSize
= blockSize
;
4481 if (zbd
->inBuffSize
< blockSize
) {
4482 zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->inBuff
);
4483 zbd
->inBuffSize
= blockSize
;
4484 zbd
->inBuff
= (char*)zbd
->customMem
.customAlloc(zbd
->customMem
.opaque
, blockSize
);
4485 if (zbd
->inBuff
== NULL
) return ERROR(memory_allocation
);
4487 { size_t const neededOutSize
= zbd
->fParams
.windowSize
+ blockSize
+ WILDCOPY_OVERLENGTH
* 2;
4488 if (zbd
->outBuffSize
< neededOutSize
) {
4489 zbd
->customMem
.customFree(zbd
->customMem
.opaque
, zbd
->outBuff
);
4490 zbd
->outBuffSize
= neededOutSize
;
4491 zbd
->outBuff
= (char*)zbd
->customMem
.customAlloc(zbd
->customMem
.opaque
, neededOutSize
);
4492 if (zbd
->outBuff
== NULL
) return ERROR(memory_allocation
);
4494 zbd
->stage
= ZBUFFds_read
;
4498 { size_t const neededInSize
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4499 if (neededInSize
==0) { /* end of frame */
4500 zbd
->stage
= ZBUFFds_init
;
4504 if ((size_t)(iend
-ip
) >= neededInSize
) { /* decode directly from src */
4505 const int isSkipFrame
= ZSTDv07_isSkipFrame(zbd
->zd
);
4506 size_t const decodedSize
= ZSTDv07_decompressContinue(zbd
->zd
,
4507 zbd
->outBuff
+ zbd
->outStart
, (isSkipFrame
? 0 : zbd
->outBuffSize
- zbd
->outStart
),
4509 if (ZSTDv07_isError(decodedSize
)) return decodedSize
;
4511 if (!decodedSize
&& !isSkipFrame
) break; /* this was just a header */
4512 zbd
->outEnd
= zbd
->outStart
+ decodedSize
;
4513 zbd
->stage
= ZBUFFds_flush
;
4516 if (ip
==iend
) { notDone
= 0; break; } /* no more input */
4517 zbd
->stage
= ZBUFFds_load
;
4521 { size_t const neededInSize
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4522 size_t const toLoad
= neededInSize
- zbd
->inPos
; /* should always be <= remaining space within inBuff */
4524 if (toLoad
> zbd
->inBuffSize
- zbd
->inPos
) return ERROR(corruption_detected
); /* should never happen */
4525 loadedSize
= ZBUFFv07_limitCopy(zbd
->inBuff
+ zbd
->inPos
, toLoad
, ip
, iend
-ip
);
4527 zbd
->inPos
+= loadedSize
;
4528 if (loadedSize
< toLoad
) { notDone
= 0; break; } /* not enough input, wait for more */
4530 /* decode loaded input */
4531 { const int isSkipFrame
= ZSTDv07_isSkipFrame(zbd
->zd
);
4532 size_t const decodedSize
= ZSTDv07_decompressContinue(zbd
->zd
,
4533 zbd
->outBuff
+ zbd
->outStart
, zbd
->outBuffSize
- zbd
->outStart
,
4534 zbd
->inBuff
, neededInSize
);
4535 if (ZSTDv07_isError(decodedSize
)) return decodedSize
;
4536 zbd
->inPos
= 0; /* input is consumed */
4537 if (!decodedSize
&& !isSkipFrame
) { zbd
->stage
= ZBUFFds_read
; break; } /* this was just a header */
4538 zbd
->outEnd
= zbd
->outStart
+ decodedSize
;
4539 zbd
->stage
= ZBUFFds_flush
;
4546 { size_t const toFlushSize
= zbd
->outEnd
- zbd
->outStart
;
4547 size_t const flushedSize
= ZBUFFv07_limitCopy(op
, oend
-op
, zbd
->outBuff
+ zbd
->outStart
, toFlushSize
);
4549 zbd
->outStart
+= flushedSize
;
4550 if (flushedSize
== toFlushSize
) {
4551 zbd
->stage
= ZBUFFds_read
;
4552 if (zbd
->outStart
+ zbd
->blockSize
> zbd
->outBuffSize
)
4553 zbd
->outStart
= zbd
->outEnd
= 0;
4556 /* cannot flush everything */
4560 default: return ERROR(GENERIC
); /* impossible */
4564 *srcSizePtr
= ip
-istart
;
4565 *dstCapacityPtr
= op
-ostart
;
4566 { size_t nextSrcSizeHint
= ZSTDv07_nextSrcSizeToDecompress(zbd
->zd
);
4567 nextSrcSizeHint
-= zbd
->inPos
; /* already loaded*/
4568 return nextSrcSizeHint
;
4574 /* *************************************
4576 ***************************************/
4577 size_t ZBUFFv07_recommendedDInSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
+ ZSTDv07_blockHeaderSize
/* block header size*/ ; }
4578 size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX
; }