1 /*
2 * Copyright (c) 2016-2020, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
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.
9 */
10
11
12 /*- Dependencies -*/
13 #include <stddef.h> /* size_t, ptrdiff_t */
14 #include <string.h> /* memcpy */
15 #include <stdlib.h> /* malloc, free, qsort */
16
17 #ifndef XXH_STATIC_LINKING_ONLY
18 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
19 #endif
20 #include "../common/xxhash.h" /* XXH64_* */
21 #include "zstd_v07.h"
22
23 #define FSEv07_STATIC_LINKING_ONLY /* FSEv07_MIN_TABLELOG */
24 #define HUFv07_STATIC_LINKING_ONLY /* HUFv07_TABLELOG_ABSOLUTEMAX */
25 #define ZSTDv07_STATIC_LINKING_ONLY
26
27 #include "../common/error_private.h"
28
29
30 #ifdef ZSTDv07_STATIC_LINKING_ONLY
31
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 * ==================================================================================== */
38
39 /*--- Constants ---*/
40 #define ZSTDv07_MAGIC_SKIPPABLE_START 0x184D2A50U
41
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
57
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 */
62
63
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;
68
69
70 /*--- Advanced Decompression functions ---*/
71
72 /*! ZSTDv07_estimateDCtxSize() :
73 * Gives the potential amount of memory allocated to create a ZSTDv07_DCtx */
74 ZSTDLIBv07_API size_t ZSTDv07_estimateDCtxSize(void);
75
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);
79
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);
83
84
85 /* ******************************************************************
86 * Buffer-less streaming functions (synchronous mode)
87 ********************************************************************/
88
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);
92
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);
95
96 /*
97 Buffer-less streaming decompression (synchronous mode)
98
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.
102
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()
113
114 Start decompression, with ZSTDv07_decompressBegin() or ZSTDv07_decompressBegin_usingDict().
115 Alternatively, you can copy a prepared context, using ZSTDv07_copyDCtx().
116
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.
120
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.
123
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.
130
131 A frame is fully decoded when ZSTDv07_nextSrcSizeToDecompress() returns zero.
132 Context can then be reset to start a new decompression.
133
134
135 == Special case : skippable frames ==
136
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.
145 */
146
147
148 /* **************************************
149 * Block functions
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.
154
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.
172 */
173
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 */
177
178
179 #endif /* ZSTDv07_STATIC_LINKING_ONLY */
180
181
182 /* ******************************************************************
183 mem.h
184 low-level memory access routines
185 Copyright (C) 2013-2015, Yann Collet.
186
187 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
188
189 Redistribution and use in source and binary forms, with or without
190 modification, are permitted provided that the following conditions are
191 met:
192
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
198 distribution.
199
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.
211
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 ****************************************************************** */
216 #ifndef MEM_H_MODULE
217 #define MEM_H_MODULE
218
219 #if defined (__cplusplus)
220 extern "C" {
221 #endif
222
223 /*-****************************************
224 * Compiler specifics
225 ******************************************/
226 #if defined(_MSC_VER) /* Visual Studio */
227 # include <stdlib.h> /* _byteswap_ulong */
228 # include <intrin.h> /* _byteswap_* */
229 #endif
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
236 #else
237 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
238 #endif
239
240
241 /*-**************************************************************
242 * Basic Types
243 *****************************************************************/
244 #if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
245 # if defined(_AIX)
246 # include <inttypes.h>
247 # else
248 # include <stdint.h> /* intptr_t */
249 # endif
250 typedef uint8_t BYTE;
251 typedef uint16_t U16;
252 typedef int16_t S16;
253 typedef uint32_t U32;
254 typedef int32_t S32;
255 typedef uint64_t U64;
256 typedef int64_t S64;
257 #else
258 typedef unsigned char BYTE;
259 typedef unsigned short U16;
260 typedef signed short S16;
261 typedef unsigned int U32;
262 typedef signed int S32;
263 typedef unsigned long long U64;
264 typedef signed long long S64;
265 #endif
266
267
268 /*-**************************************************************
269 * Memory I/O
270 *****************************************************************/
271 /* MEM_FORCE_MEMORY_ACCESS :
272 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
273 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
274 * The below switch allow to select different access method for improved performance.
275 * Method 0 (default) : use `memcpy()`. Safe and portable.
276 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
277 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
278 * Method 2 : direct access. This method is portable but violate C standard.
279 * It can generate buggy code on targets depending on alignment.
280 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
281 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
282 * Prefer these methods in priority order (0 > 1 > 2)
283 */
284 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
285 # 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__) )
286 # define MEM_FORCE_MEMORY_ACCESS 2
287 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
288 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
289 # define MEM_FORCE_MEMORY_ACCESS 1
290 # endif
291 #endif
292
MEM_32bits(void)293 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
MEM_64bits(void)294 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
295
MEM_isLittleEndian(void)296 MEM_STATIC unsigned MEM_isLittleEndian(void)
297 {
298 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
299 return one.c[0];
300 }
301
302 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
303
304 /* violates C standard, by lying on structure alignment.
305 Only use if no other choice to achieve best performance on target platform */
MEM_read16(const void * memPtr)306 MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
MEM_read32(const void * memPtr)307 MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
MEM_read64(const void * memPtr)308 MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
309
MEM_write16(void * memPtr,U16 value)310 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
311
312 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
313
314 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
315 /* currently only defined for gcc and icc */
316 typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign;
317
MEM_read16(const void * ptr)318 MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
MEM_read32(const void * ptr)319 MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
MEM_read64(const void * ptr)320 MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
321
MEM_write16(void * memPtr,U16 value)322 MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
323
324 #else
325
326 /* default method, safe and standard.
327 can sometimes prove slower */
328
MEM_read16(const void * memPtr)329 MEM_STATIC U16 MEM_read16(const void* memPtr)
330 {
331 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
332 }
333
MEM_read32(const void * memPtr)334 MEM_STATIC U32 MEM_read32(const void* memPtr)
335 {
336 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
337 }
338
MEM_read64(const void * memPtr)339 MEM_STATIC U64 MEM_read64(const void* memPtr)
340 {
341 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
342 }
343
MEM_write16(void * memPtr,U16 value)344 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
345 {
346 memcpy(memPtr, &value, sizeof(value));
347 }
348
349 #endif /* MEM_FORCE_MEMORY_ACCESS */
350
MEM_swap32(U32 in)351 MEM_STATIC U32 MEM_swap32(U32 in)
352 {
353 #if defined(_MSC_VER) /* Visual Studio */
354 return _byteswap_ulong(in);
355 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
356 return __builtin_bswap32(in);
357 #else
358 return ((in << 24) & 0xff000000 ) |
359 ((in << 8) & 0x00ff0000 ) |
360 ((in >> 8) & 0x0000ff00 ) |
361 ((in >> 24) & 0x000000ff );
362 #endif
363 }
364
MEM_swap64(U64 in)365 MEM_STATIC U64 MEM_swap64(U64 in)
366 {
367 #if defined(_MSC_VER) /* Visual Studio */
368 return _byteswap_uint64(in);
369 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
370 return __builtin_bswap64(in);
371 #else
372 return ((in << 56) & 0xff00000000000000ULL) |
373 ((in << 40) & 0x00ff000000000000ULL) |
374 ((in << 24) & 0x0000ff0000000000ULL) |
375 ((in << 8) & 0x000000ff00000000ULL) |
376 ((in >> 8) & 0x00000000ff000000ULL) |
377 ((in >> 24) & 0x0000000000ff0000ULL) |
378 ((in >> 40) & 0x000000000000ff00ULL) |
379 ((in >> 56) & 0x00000000000000ffULL);
380 #endif
381 }
382
383
384 /*=== Little endian r/w ===*/
385
MEM_readLE16(const void * memPtr)386 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
387 {
388 if (MEM_isLittleEndian())
389 return MEM_read16(memPtr);
390 else {
391 const BYTE* p = (const BYTE*)memPtr;
392 return (U16)(p[0] + (p[1]<<8));
393 }
394 }
395
MEM_writeLE16(void * memPtr,U16 val)396 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
397 {
398 if (MEM_isLittleEndian()) {
399 MEM_write16(memPtr, val);
400 } else {
401 BYTE* p = (BYTE*)memPtr;
402 p[0] = (BYTE)val;
403 p[1] = (BYTE)(val>>8);
404 }
405 }
406
MEM_readLE32(const void * memPtr)407 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
408 {
409 if (MEM_isLittleEndian())
410 return MEM_read32(memPtr);
411 else
412 return MEM_swap32(MEM_read32(memPtr));
413 }
414
415
MEM_readLE64(const void * memPtr)416 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
417 {
418 if (MEM_isLittleEndian())
419 return MEM_read64(memPtr);
420 else
421 return MEM_swap64(MEM_read64(memPtr));
422 }
423
MEM_readLEST(const void * memPtr)424 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
425 {
426 if (MEM_32bits())
427 return (size_t)MEM_readLE32(memPtr);
428 else
429 return (size_t)MEM_readLE64(memPtr);
430 }
431
432
433
434 #if defined (__cplusplus)
435 }
436 #endif
437
438 #endif /* MEM_H_MODULE */
439 /* ******************************************************************
440 bitstream
441 Part of FSE library
442 header file (to include)
443 Copyright (C) 2013-2016, Yann Collet.
444
445 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
446
447 Redistribution and use in source and binary forms, with or without
448 modification, are permitted provided that the following conditions are
449 met:
450
451 * Redistributions of source code must retain the above copyright
452 notice, this list of conditions and the following disclaimer.
453 * Redistributions in binary form must reproduce the above
454 copyright notice, this list of conditions and the following disclaimer
455 in the documentation and/or other materials provided with the
456 distribution.
457
458 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
459 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
460 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
461 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
462 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
463 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
464 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
465 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
466 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
467 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
468 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
469
470 You can contact the author at :
471 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
472 ****************************************************************** */
473 #ifndef BITSTREAM_H_MODULE
474 #define BITSTREAM_H_MODULE
475
476 #if defined (__cplusplus)
477 extern "C" {
478 #endif
479
480
481 /*
482 * This API consists of small unitary functions, which must be inlined for best performance.
483 * Since link-time-optimization is not available for all compilers,
484 * these functions are defined into a .h to be included.
485 */
486
487
488 /*=========================================
489 * Target specific
490 =========================================*/
491 #if defined(__BMI__) && defined(__GNUC__)
492 # include <immintrin.h> /* support for bextr (experimental) */
493 #endif
494
495 /*-********************************************
496 * bitStream decoding API (read backward)
497 **********************************************/
498 typedef struct
499 {
500 size_t bitContainer;
501 unsigned bitsConsumed;
502 const char* ptr;
503 const char* start;
504 } BITv07_DStream_t;
505
506 typedef enum { BITv07_DStream_unfinished = 0,
507 BITv07_DStream_endOfBuffer = 1,
508 BITv07_DStream_completed = 2,
509 BITv07_DStream_overflow = 3 } BITv07_DStream_status; /* result of BITv07_reloadDStream() */
510 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
511
512 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
513 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, unsigned nbBits);
514 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD);
515 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* bitD);
516
517
518
519 /*-****************************************
520 * unsafe API
521 ******************************************/
522 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, unsigned nbBits);
523 /* faster, but works only if nbBits >= 1 */
524
525
526
527 /*-**************************************************************
528 * Internal functions
529 ****************************************************************/
BITv07_highbit32(U32 val)530 MEM_STATIC unsigned BITv07_highbit32 (U32 val)
531 {
532 # if defined(_MSC_VER) /* Visual */
533 unsigned long r=0;
534 _BitScanReverse ( &r, val );
535 return (unsigned) r;
536 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
537 return __builtin_clz (val) ^ 31;
538 # else /* Software version */
539 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 };
540 U32 v = val;
541 v |= v >> 1;
542 v |= v >> 2;
543 v |= v >> 4;
544 v |= v >> 8;
545 v |= v >> 16;
546 return DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
547 # endif
548 }
549
550
551
552 /*-********************************************************
553 * bitStream decoding
554 **********************************************************/
555 /*! BITv07_initDStream() :
556 * Initialize a BITv07_DStream_t.
557 * `bitD` : a pointer to an already allocated BITv07_DStream_t structure.
558 * `srcSize` must be the *exact* size of the bitStream, in bytes.
559 * @return : size of stream (== srcSize) or an errorCode if a problem is detected
560 */
BITv07_initDStream(BITv07_DStream_t * bitD,const void * srcBuffer,size_t srcSize)561 MEM_STATIC size_t BITv07_initDStream(BITv07_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
562 {
563 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
564
565 if (srcSize >= sizeof(bitD->bitContainer)) { /* normal case */
566 bitD->start = (const char*)srcBuffer;
567 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
568 bitD->bitContainer = MEM_readLEST(bitD->ptr);
569 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
570 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
571 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
572 } else {
573 bitD->start = (const char*)srcBuffer;
574 bitD->ptr = bitD->start;
575 bitD->bitContainer = *(const BYTE*)(bitD->start);
576 switch(srcSize)
577 {
578 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
579 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
580 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
581 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
582 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
583 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) << 8; /* fall-through */
584 default: break;
585 }
586 { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
587 bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
588 if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
589 bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
590 }
591
592 return srcSize;
593 }
594
595
BITv07_lookBits(const BITv07_DStream_t * bitD,U32 nbBits)596 MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits)
597 {
598 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
599 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
600 }
601
602 /*! BITv07_lookBitsFast() :
603 * unsafe version; only works only if nbBits >= 1 */
BITv07_lookBitsFast(const BITv07_DStream_t * bitD,U32 nbBits)604 MEM_STATIC size_t BITv07_lookBitsFast(const BITv07_DStream_t* bitD, U32 nbBits)
605 {
606 U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
607 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
608 }
609
BITv07_skipBits(BITv07_DStream_t * bitD,U32 nbBits)610 MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits)
611 {
612 bitD->bitsConsumed += nbBits;
613 }
614
BITv07_readBits(BITv07_DStream_t * bitD,U32 nbBits)615 MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits)
616 {
617 size_t const value = BITv07_lookBits(bitD, nbBits);
618 BITv07_skipBits(bitD, nbBits);
619 return value;
620 }
621
622 /*! BITv07_readBitsFast() :
623 * unsafe version; only works only if nbBits >= 1 */
BITv07_readBitsFast(BITv07_DStream_t * bitD,U32 nbBits)624 MEM_STATIC size_t BITv07_readBitsFast(BITv07_DStream_t* bitD, U32 nbBits)
625 {
626 size_t const value = BITv07_lookBitsFast(bitD, nbBits);
627 BITv07_skipBits(bitD, nbBits);
628 return value;
629 }
630
BITv07_reloadDStream(BITv07_DStream_t * bitD)631 MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD)
632 {
633 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should not happen => corruption detected */
634 return BITv07_DStream_overflow;
635
636 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
637 bitD->ptr -= bitD->bitsConsumed >> 3;
638 bitD->bitsConsumed &= 7;
639 bitD->bitContainer = MEM_readLEST(bitD->ptr);
640 return BITv07_DStream_unfinished;
641 }
642 if (bitD->ptr == bitD->start) {
643 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv07_DStream_endOfBuffer;
644 return BITv07_DStream_completed;
645 }
646 { U32 nbBytes = bitD->bitsConsumed >> 3;
647 BITv07_DStream_status result = BITv07_DStream_unfinished;
648 if (bitD->ptr - nbBytes < bitD->start) {
649 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
650 result = BITv07_DStream_endOfBuffer;
651 }
652 bitD->ptr -= nbBytes;
653 bitD->bitsConsumed -= nbBytes*8;
654 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
655 return result;
656 }
657 }
658
659 /*! BITv07_endOfDStream() :
660 * @return Tells if DStream has exactly reached its end (all bits consumed).
661 */
BITv07_endOfDStream(const BITv07_DStream_t * DStream)662 MEM_STATIC unsigned BITv07_endOfDStream(const BITv07_DStream_t* DStream)
663 {
664 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
665 }
666
667 #if defined (__cplusplus)
668 }
669 #endif
670
671 #endif /* BITSTREAM_H_MODULE */
672 /* ******************************************************************
673 FSE : Finite State Entropy codec
674 Public Prototypes declaration
675 Copyright (C) 2013-2016, Yann Collet.
676
677 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
678
679 Redistribution and use in source and binary forms, with or without
680 modification, are permitted provided that the following conditions are
681 met:
682
683 * Redistributions of source code must retain the above copyright
684 notice, this list of conditions and the following disclaimer.
685 * Redistributions in binary form must reproduce the above
686 copyright notice, this list of conditions and the following disclaimer
687 in the documentation and/or other materials provided with the
688 distribution.
689
690 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
691 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
692 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
693 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
694 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
695 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
696 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
697 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
698 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
699 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
700 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
701
702 You can contact the author at :
703 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
704 ****************************************************************** */
705 #ifndef FSEv07_H
706 #define FSEv07_H
707
708 #if defined (__cplusplus)
709 extern "C" {
710 #endif
711
712
713
714 /*-****************************************
715 * FSE simple functions
716 ******************************************/
717
718 /*! FSEv07_decompress():
719 Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
720 into already allocated destination buffer 'dst', of size 'dstCapacity'.
721 @return : size of regenerated data (<= maxDstSize),
722 or an error code, which can be tested using FSEv07_isError() .
723
724 ** Important ** : FSEv07_decompress() does not decompress non-compressible nor RLE data !!!
725 Why ? : making this distinction requires a header.
726 Header management is intentionally delegated to the user layer, which can better manage special cases.
727 */
728 size_t FSEv07_decompress(void* dst, size_t dstCapacity,
729 const void* cSrc, size_t cSrcSize);
730
731
732 /* Error Management */
733 unsigned FSEv07_isError(size_t code); /* tells if a return value is an error code */
734 const char* FSEv07_getErrorName(size_t code); /* provides error code string (useful for debugging) */
735
736
737 /*-*****************************************
738 * FSE detailed API
739 ******************************************/
740 /*!
741 FSEv07_decompress() does the following:
742 1. read normalized counters with readNCount()
743 2. build decoding table 'DTable' from normalized counters
744 3. decode the data stream using decoding table 'DTable'
745
746 The following API allows targeting specific sub-functions for advanced tasks.
747 For example, it's possible to compress several blocks using the same 'CTable',
748 or to save and provide normalized distribution using external method.
749 */
750
751
752 /* *** DECOMPRESSION *** */
753
754 /*! FSEv07_readNCount():
755 Read compactly saved 'normalizedCounter' from 'rBuffer'.
756 @return : size read from 'rBuffer',
757 or an errorCode, which can be tested using FSEv07_isError().
758 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
759 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
760
761 /*! Constructor and Destructor of FSEv07_DTable.
762 Note that its size depends on 'tableLog' */
763 typedef unsigned FSEv07_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
764 FSEv07_DTable* FSEv07_createDTable(unsigned tableLog);
765 void FSEv07_freeDTable(FSEv07_DTable* dt);
766
767 /*! FSEv07_buildDTable():
768 Builds 'dt', which must be already allocated, using FSEv07_createDTable().
769 return : 0, or an errorCode, which can be tested using FSEv07_isError() */
770 size_t FSEv07_buildDTable (FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
771
772 /*! FSEv07_decompress_usingDTable():
773 Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
774 into `dst` which must be already allocated.
775 @return : size of regenerated data (necessarily <= `dstCapacity`),
776 or an errorCode, which can be tested using FSEv07_isError() */
777 size_t FSEv07_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv07_DTable* dt);
778
779 /*!
780 Tutorial :
781 ----------
782 (Note : these functions only decompress FSE-compressed blocks.
783 If block is uncompressed, use memcpy() instead
784 If block is a single repeated byte, use memset() instead )
785
786 The first step is to obtain the normalized frequencies of symbols.
787 This can be performed by FSEv07_readNCount() if it was saved using FSEv07_writeNCount().
788 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
789 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
790 or size the table to handle worst case situations (typically 256).
791 FSEv07_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
792 The result of FSEv07_readNCount() is the number of bytes read from 'rBuffer'.
793 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
794 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
795
796 The next step is to build the decompression tables 'FSEv07_DTable' from 'normalizedCounter'.
797 This is performed by the function FSEv07_buildDTable().
798 The space required by 'FSEv07_DTable' must be already allocated using FSEv07_createDTable().
799 If there is an error, the function will return an error code, which can be tested using FSEv07_isError().
800
801 `FSEv07_DTable` can then be used to decompress `cSrc`, with FSEv07_decompress_usingDTable().
802 `cSrcSize` must be strictly correct, otherwise decompression will fail.
803 FSEv07_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
804 If there is an error, the function will return an error code, which can be tested using FSEv07_isError(). (ex: dst buffer too small)
805 */
806
807
808 #ifdef FSEv07_STATIC_LINKING_ONLY
809
810
811 /* *****************************************
812 * Static allocation
813 *******************************************/
814 /* FSE buffer bounds */
815 #define FSEv07_NCOUNTBOUND 512
816 #define FSEv07_BLOCKBOUND(size) (size + (size>>7))
817
818 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
819 #define FSEv07_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
820
821
822 /* *****************************************
823 * FSE advanced API
824 *******************************************/
825 size_t FSEv07_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
826 /**< same as FSEv07_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr */
827
828 unsigned FSEv07_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus);
829 /**< same as FSEv07_optimalTableLog(), which used `minus==2` */
830
831 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits);
832 /**< build a fake FSEv07_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
833
834 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, unsigned char symbolValue);
835 /**< build a fake FSEv07_DTable, designed to always generate the same symbolValue */
836
837
838
839 /* *****************************************
840 * FSE symbol decompression API
841 *******************************************/
842 typedef struct
843 {
844 size_t state;
845 const void* table; /* precise table may vary, depending on U16 */
846 } FSEv07_DState_t;
847
848
849 static void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt);
850
851 static unsigned char FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
852
853
854
855 /* *****************************************
856 * FSE unsafe API
857 *******************************************/
858 static unsigned char FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD);
859 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
860
861
862 /* ====== Decompression ====== */
863
864 typedef struct {
865 U16 tableLog;
866 U16 fastMode;
867 } FSEv07_DTableHeader; /* sizeof U32 */
868
869 typedef struct
870 {
871 unsigned short newState;
872 unsigned char symbol;
873 unsigned char nbBits;
874 } FSEv07_decode_t; /* size == U32 */
875
FSEv07_initDState(FSEv07_DState_t * DStatePtr,BITv07_DStream_t * bitD,const FSEv07_DTable * dt)876 MEM_STATIC void FSEv07_initDState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD, const FSEv07_DTable* dt)
877 {
878 const void* ptr = dt;
879 const FSEv07_DTableHeader* const DTableH = (const FSEv07_DTableHeader*)ptr;
880 DStatePtr->state = BITv07_readBits(bitD, DTableH->tableLog);
881 BITv07_reloadDStream(bitD);
882 DStatePtr->table = dt + 1;
883 }
884
FSEv07_peekSymbol(const FSEv07_DState_t * DStatePtr)885 MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr)
886 {
887 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
888 return DInfo.symbol;
889 }
890
FSEv07_updateState(FSEv07_DState_t * DStatePtr,BITv07_DStream_t * bitD)891 MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
892 {
893 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
894 U32 const nbBits = DInfo.nbBits;
895 size_t const lowBits = BITv07_readBits(bitD, nbBits);
896 DStatePtr->state = DInfo.newState + lowBits;
897 }
898
FSEv07_decodeSymbol(FSEv07_DState_t * DStatePtr,BITv07_DStream_t * bitD)899 MEM_STATIC BYTE FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
900 {
901 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
902 U32 const nbBits = DInfo.nbBits;
903 BYTE const symbol = DInfo.symbol;
904 size_t const lowBits = BITv07_readBits(bitD, nbBits);
905
906 DStatePtr->state = DInfo.newState + lowBits;
907 return symbol;
908 }
909
910 /*! FSEv07_decodeSymbolFast() :
911 unsafe, only works if no symbol has a probability > 50% */
FSEv07_decodeSymbolFast(FSEv07_DState_t * DStatePtr,BITv07_DStream_t * bitD)912 MEM_STATIC BYTE FSEv07_decodeSymbolFast(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
913 {
914 FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
915 U32 const nbBits = DInfo.nbBits;
916 BYTE const symbol = DInfo.symbol;
917 size_t const lowBits = BITv07_readBitsFast(bitD, nbBits);
918
919 DStatePtr->state = DInfo.newState + lowBits;
920 return symbol;
921 }
922
923
924
925 #ifndef FSEv07_COMMONDEFS_ONLY
926
927 /* **************************************************************
928 * Tuning parameters
929 ****************************************************************/
930 /*!MEMORY_USAGE :
931 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
932 * Increasing memory usage improves compression ratio
933 * Reduced memory usage can improve speed, due to cache effect
934 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
935 #define FSEv07_MAX_MEMORY_USAGE 14
936 #define FSEv07_DEFAULT_MEMORY_USAGE 13
937
938 /*!FSEv07_MAX_SYMBOL_VALUE :
939 * Maximum symbol value authorized.
940 * Required for proper stack allocation */
941 #define FSEv07_MAX_SYMBOL_VALUE 255
942
943
944 /* **************************************************************
945 * template functions type & suffix
946 ****************************************************************/
947 #define FSEv07_FUNCTION_TYPE BYTE
948 #define FSEv07_FUNCTION_EXTENSION
949 #define FSEv07_DECODE_TYPE FSEv07_decode_t
950
951
952 #endif /* !FSEv07_COMMONDEFS_ONLY */
953
954
955 /* ***************************************************************
956 * Constants
957 *****************************************************************/
958 #define FSEv07_MAX_TABLELOG (FSEv07_MAX_MEMORY_USAGE-2)
959 #define FSEv07_MAX_TABLESIZE (1U<<FSEv07_MAX_TABLELOG)
960 #define FSEv07_MAXTABLESIZE_MASK (FSEv07_MAX_TABLESIZE-1)
961 #define FSEv07_DEFAULT_TABLELOG (FSEv07_DEFAULT_MEMORY_USAGE-2)
962 #define FSEv07_MIN_TABLELOG 5
963
964 #define FSEv07_TABLELOG_ABSOLUTE_MAX 15
965 #if FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX
966 # error "FSEv07_MAX_TABLELOG > FSEv07_TABLELOG_ABSOLUTE_MAX is not supported"
967 #endif
968
969 #define FSEv07_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
970
971
972 #endif /* FSEv07_STATIC_LINKING_ONLY */
973
974
975 #if defined (__cplusplus)
976 }
977 #endif
978
979 #endif /* FSEv07_H */
980 /* ******************************************************************
981 Huffman coder, part of New Generation Entropy library
982 header file
983 Copyright (C) 2013-2016, Yann Collet.
984
985 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
986
987 Redistribution and use in source and binary forms, with or without
988 modification, are permitted provided that the following conditions are
989 met:
990
991 * Redistributions of source code must retain the above copyright
992 notice, this list of conditions and the following disclaimer.
993 * Redistributions in binary form must reproduce the above
994 copyright notice, this list of conditions and the following disclaimer
995 in the documentation and/or other materials provided with the
996 distribution.
997
998 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
999 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1000 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1001 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1002 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1003 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1004 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1005 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1006 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1007 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1008 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1009
1010 You can contact the author at :
1011 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1012 ****************************************************************** */
1013 #ifndef HUFv07_H_298734234
1014 #define HUFv07_H_298734234
1015
1016 #if defined (__cplusplus)
1017 extern "C" {
1018 #endif
1019
1020
1021
1022 /* *** simple functions *** */
1023 /**
1024 HUFv07_decompress() :
1025 Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1026 into already allocated buffer 'dst', of minimum size 'dstSize'.
1027 `dstSize` : **must** be the ***exact*** size of original (uncompressed) data.
1028 Note : in contrast with FSE, HUFv07_decompress can regenerate
1029 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1030 because it knows size to regenerate.
1031 @return : size of regenerated data (== dstSize),
1032 or an error code, which can be tested using HUFv07_isError()
1033 */
1034 size_t HUFv07_decompress(void* dst, size_t dstSize,
1035 const void* cSrc, size_t cSrcSize);
1036
1037
1038 /* ****************************************
1039 * Tool functions
1040 ******************************************/
1041 #define HUFv07_BLOCKSIZE_MAX (128 * 1024)
1042
1043 /* Error Management */
1044 unsigned HUFv07_isError(size_t code); /**< tells if a return value is an error code */
1045 const char* HUFv07_getErrorName(size_t code); /**< provides error code string (useful for debugging) */
1046
1047
1048 /* *** Advanced function *** */
1049
1050
1051 #ifdef HUFv07_STATIC_LINKING_ONLY
1052
1053
1054 /* *** Constants *** */
1055 #define HUFv07_TABLELOG_ABSOLUTEMAX 16 /* absolute limit of HUFv07_MAX_TABLELOG. Beyond that value, code does not work */
1056 #define HUFv07_TABLELOG_MAX 12 /* max configured tableLog (for static allocation); can be modified up to HUFv07_ABSOLUTEMAX_TABLELOG */
1057 #define HUFv07_TABLELOG_DEFAULT 11 /* tableLog by default, when not specified */
1058 #define HUFv07_SYMBOLVALUE_MAX 255
1059 #if (HUFv07_TABLELOG_MAX > HUFv07_TABLELOG_ABSOLUTEMAX)
1060 # error "HUFv07_TABLELOG_MAX is too large !"
1061 #endif
1062
1063
1064 /* ****************************************
1065 * Static allocation
1066 ******************************************/
1067 /* HUF buffer bounds */
1068 #define HUFv07_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
1069
1070 /* static allocation of HUF's DTable */
1071 typedef U32 HUFv07_DTable;
1072 #define HUFv07_DTABLE_SIZE(maxTableLog) (1 + (1<<(maxTableLog)))
1073 #define HUFv07_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1074 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE((maxTableLog)-1)] = { ((U32)((maxTableLog)-1)*0x1000001) }
1075 #define HUFv07_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1076 HUFv07_DTable DTable[HUFv07_DTABLE_SIZE(maxTableLog)] = { ((U32)(maxTableLog)*0x1000001) }
1077
1078
1079 /* ****************************************
1080 * Advanced decompression functions
1081 ******************************************/
1082 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1083 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1084
1085 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< decodes RLE and uncompressed */
1086 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 */
1087 size_t HUFv07_decompress4X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1088 size_t HUFv07_decompress4X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1089
1090 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
1091 size_t HUFv07_decompress1X2_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< single-symbol decoder */
1092 size_t HUFv07_decompress1X4_DCtx(HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /**< double-symbols decoder */
1093
1094
1095 /* ****************************************
1096 * HUF detailed API
1097 ******************************************/
1098 /*!
1099 The following API allows targeting specific sub-functions for advanced tasks.
1100 For example, it's possible to compress several blocks using the same 'CTable',
1101 or to save and regenerate 'CTable' using external methods.
1102 */
1103 /* FSEv07_count() : find it within "fse.h" */
1104
1105 /*! HUFv07_readStats() :
1106 Read compact Huffman tree, saved by HUFv07_writeCTable().
1107 `huffWeight` is destination buffer.
1108 @return : size read from `src` , or an error Code .
1109 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() . */
1110 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1111 U32* nbSymbolsPtr, U32* tableLogPtr,
1112 const void* src, size_t srcSize);
1113
1114
1115 /*
1116 HUFv07_decompress() does the following:
1117 1. select the decompression algorithm (X2, X4) based on pre-computed heuristics
1118 2. build Huffman table from save, using HUFv07_readDTableXn()
1119 3. decode 1 or 4 segments in parallel using HUFv07_decompressSXn_usingDTable
1120 */
1121
1122 /** HUFv07_selectDecoder() :
1123 * Tells which decoder is likely to decode faster,
1124 * based on a set of pre-determined metrics.
1125 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
1126 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
1127 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize);
1128
1129 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1130 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize);
1131
1132 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1133 size_t HUFv07_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1134 size_t HUFv07_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1135
1136
1137 /* single stream variants */
1138 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1139 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1140
1141 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1142 size_t HUFv07_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1143 size_t HUFv07_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const HUFv07_DTable* DTable);
1144
1145
1146 #endif /* HUFv07_STATIC_LINKING_ONLY */
1147
1148
1149 #if defined (__cplusplus)
1150 }
1151 #endif
1152
1153 #endif /* HUFv07_H_298734234 */
1154 /*
1155 Common functions of New Generation Entropy library
1156 Copyright (C) 2016, Yann Collet.
1157
1158 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1159
1160 Redistribution and use in source and binary forms, with or without
1161 modification, are permitted provided that the following conditions are
1162 met:
1163
1164 * Redistributions of source code must retain the above copyright
1165 notice, this list of conditions and the following disclaimer.
1166 * Redistributions in binary form must reproduce the above
1167 copyright notice, this list of conditions and the following disclaimer
1168 in the documentation and/or other materials provided with the
1169 distribution.
1170
1171 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1172 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1173 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1174 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1175 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1176 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1177 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1178 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1179 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1180 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1181 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1182
1183 You can contact the author at :
1184 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1185 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1186 *************************************************************************** */
1187
1188
1189
1190 /*-****************************************
1191 * FSE Error Management
1192 ******************************************/
FSEv07_isError(size_t code)1193 unsigned FSEv07_isError(size_t code) { return ERR_isError(code); }
1194
FSEv07_getErrorName(size_t code)1195 const char* FSEv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1196
1197
1198 /* **************************************************************
1199 * HUF Error Management
1200 ****************************************************************/
HUFv07_isError(size_t code)1201 unsigned HUFv07_isError(size_t code) { return ERR_isError(code); }
1202
HUFv07_getErrorName(size_t code)1203 const char* HUFv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
1204
1205
1206 /*-**************************************************************
1207 * FSE NCount encoding-decoding
1208 ****************************************************************/
FSEv07_abs(short a)1209 static short FSEv07_abs(short a) { return (short)(a<0 ? -a : a); }
1210
FSEv07_readNCount(short * normalizedCounter,unsigned * maxSVPtr,unsigned * tableLogPtr,const void * headerBuffer,size_t hbSize)1211 size_t FSEv07_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1212 const void* headerBuffer, size_t hbSize)
1213 {
1214 const BYTE* const istart = (const BYTE*) headerBuffer;
1215 const BYTE* const iend = istart + hbSize;
1216 const BYTE* ip = istart;
1217 int nbBits;
1218 int remaining;
1219 int threshold;
1220 U32 bitStream;
1221 int bitCount;
1222 unsigned charnum = 0;
1223 int previous0 = 0;
1224
1225 if (hbSize < 4) return ERROR(srcSize_wrong);
1226 bitStream = MEM_readLE32(ip);
1227 nbBits = (bitStream & 0xF) + FSEv07_MIN_TABLELOG; /* extract tableLog */
1228 if (nbBits > FSEv07_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1229 bitStream >>= 4;
1230 bitCount = 4;
1231 *tableLogPtr = nbBits;
1232 remaining = (1<<nbBits)+1;
1233 threshold = 1<<nbBits;
1234 nbBits++;
1235
1236 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1237 if (previous0) {
1238 unsigned n0 = charnum;
1239 while ((bitStream & 0xFFFF) == 0xFFFF) {
1240 n0+=24;
1241 if (ip < iend-5) {
1242 ip+=2;
1243 bitStream = MEM_readLE32(ip) >> bitCount;
1244 } else {
1245 bitStream >>= 16;
1246 bitCount+=16;
1247 } }
1248 while ((bitStream & 3) == 3) {
1249 n0+=3;
1250 bitStream>>=2;
1251 bitCount+=2;
1252 }
1253 n0 += bitStream & 3;
1254 bitCount += 2;
1255 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1256 while (charnum < n0) normalizedCounter[charnum++] = 0;
1257 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1258 ip += bitCount>>3;
1259 bitCount &= 7;
1260 bitStream = MEM_readLE32(ip) >> bitCount;
1261 }
1262 else
1263 bitStream >>= 2;
1264 }
1265 { short const max = (short)((2*threshold-1)-remaining);
1266 short count;
1267
1268 if ((bitStream & (threshold-1)) < (U32)max) {
1269 count = (short)(bitStream & (threshold-1));
1270 bitCount += nbBits-1;
1271 } else {
1272 count = (short)(bitStream & (2*threshold-1));
1273 if (count >= threshold) count -= max;
1274 bitCount += nbBits;
1275 }
1276
1277 count--; /* extra accuracy */
1278 remaining -= FSEv07_abs(count);
1279 normalizedCounter[charnum++] = count;
1280 previous0 = !count;
1281 while (remaining < threshold) {
1282 nbBits--;
1283 threshold >>= 1;
1284 }
1285
1286 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1287 ip += bitCount>>3;
1288 bitCount &= 7;
1289 } else {
1290 bitCount -= (int)(8 * (iend - 4 - ip));
1291 ip = iend - 4;
1292 }
1293 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1294 } } /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1295 if (remaining != 1) return ERROR(GENERIC);
1296 *maxSVPtr = charnum-1;
1297
1298 ip += (bitCount+7)>>3;
1299 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1300 return ip-istart;
1301 }
1302
1303
1304 /*! HUFv07_readStats() :
1305 Read compact Huffman tree, saved by HUFv07_writeCTable().
1306 `huffWeight` is destination buffer.
1307 @return : size read from `src` , or an error Code .
1308 Note : Needed by HUFv07_readCTable() and HUFv07_readDTableXn() .
1309 */
HUFv07_readStats(BYTE * huffWeight,size_t hwSize,U32 * rankStats,U32 * nbSymbolsPtr,U32 * tableLogPtr,const void * src,size_t srcSize)1310 size_t HUFv07_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1311 U32* nbSymbolsPtr, U32* tableLogPtr,
1312 const void* src, size_t srcSize)
1313 {
1314 U32 weightTotal;
1315 const BYTE* ip = (const BYTE*) src;
1316 size_t iSize;
1317 size_t oSize;
1318
1319 if (!srcSize) return ERROR(srcSize_wrong);
1320 iSize = ip[0];
1321 /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */
1322
1323 if (iSize >= 128) { /* special header */
1324 if (iSize >= (242)) { /* RLE */
1325 static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1326 oSize = l[iSize-242];
1327 memset(huffWeight, 1, hwSize);
1328 iSize = 0;
1329 }
1330 else { /* Incompressible */
1331 oSize = iSize - 127;
1332 iSize = ((oSize+1)/2);
1333 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1334 if (oSize >= hwSize) return ERROR(corruption_detected);
1335 ip += 1;
1336 { U32 n;
1337 for (n=0; n<oSize; n+=2) {
1338 huffWeight[n] = ip[n/2] >> 4;
1339 huffWeight[n+1] = ip[n/2] & 15;
1340 } } } }
1341 else { /* header compressed with FSE (normal case) */
1342 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1343 oSize = FSEv07_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1344 if (FSEv07_isError(oSize)) return oSize;
1345 }
1346
1347 /* collect weight stats */
1348 memset(rankStats, 0, (HUFv07_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
1349 weightTotal = 0;
1350 { U32 n; for (n=0; n<oSize; n++) {
1351 if (huffWeight[n] >= HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1352 rankStats[huffWeight[n]]++;
1353 weightTotal += (1 << huffWeight[n]) >> 1;
1354 } }
1355 if (weightTotal == 0) return ERROR(corruption_detected);
1356
1357 /* get last non-null symbol weight (implied, total must be 2^n) */
1358 { U32 const tableLog = BITv07_highbit32(weightTotal) + 1;
1359 if (tableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1360 *tableLogPtr = tableLog;
1361 /* determine last weight */
1362 { U32 const total = 1 << tableLog;
1363 U32 const rest = total - weightTotal;
1364 U32 const verif = 1 << BITv07_highbit32(rest);
1365 U32 const lastWeight = BITv07_highbit32(rest) + 1;
1366 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1367 huffWeight[oSize] = (BYTE)lastWeight;
1368 rankStats[lastWeight]++;
1369 } }
1370
1371 /* check tree construction validity */
1372 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1373
1374 /* results */
1375 *nbSymbolsPtr = (U32)(oSize+1);
1376 return iSize+1;
1377 }
1378 /* ******************************************************************
1379 FSE : Finite State Entropy decoder
1380 Copyright (C) 2013-2015, Yann Collet.
1381
1382 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1383
1384 Redistribution and use in source and binary forms, with or without
1385 modification, are permitted provided that the following conditions are
1386 met:
1387
1388 * Redistributions of source code must retain the above copyright
1389 notice, this list of conditions and the following disclaimer.
1390 * Redistributions in binary form must reproduce the above
1391 copyright notice, this list of conditions and the following disclaimer
1392 in the documentation and/or other materials provided with the
1393 distribution.
1394
1395 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1396 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1397 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1398 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1399 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1400 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1401 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1402 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1403 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1404 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1405 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1406
1407 You can contact the author at :
1408 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1409 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1410 ****************************************************************** */
1411
1412
1413 /* **************************************************************
1414 * Compiler specifics
1415 ****************************************************************/
1416 #ifdef _MSC_VER /* Visual Studio */
1417 # define FORCE_INLINE static __forceinline
1418 # include <intrin.h> /* For Visual 2005 */
1419 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1420 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1421 #else
1422 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1423 # ifdef __GNUC__
1424 # define FORCE_INLINE static inline __attribute__((always_inline))
1425 # else
1426 # define FORCE_INLINE static inline
1427 # endif
1428 # else
1429 # define FORCE_INLINE static
1430 # endif /* __STDC_VERSION__ */
1431 #endif
1432
1433
1434 /* **************************************************************
1435 * Error Management
1436 ****************************************************************/
1437 #define FSEv07_isError ERR_isError
1438 #define FSEv07_STATIC_ASSERT(c) { enum { FSEv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1439
1440
1441 /* **************************************************************
1442 * Complex types
1443 ****************************************************************/
1444 typedef U32 DTable_max_t[FSEv07_DTABLE_SIZE_U32(FSEv07_MAX_TABLELOG)];
1445
1446
1447 /* **************************************************************
1448 * Templates
1449 ****************************************************************/
1450 /*
1451 designed to be included
1452 for type-specific functions (template emulation in C)
1453 Objective is to write these functions only once, for improved maintenance
1454 */
1455
1456 /* safety checks */
1457 #ifndef FSEv07_FUNCTION_EXTENSION
1458 # error "FSEv07_FUNCTION_EXTENSION must be defined"
1459 #endif
1460 #ifndef FSEv07_FUNCTION_TYPE
1461 # error "FSEv07_FUNCTION_TYPE must be defined"
1462 #endif
1463
1464 /* Function names */
1465 #define FSEv07_CAT(X,Y) X##Y
1466 #define FSEv07_FUNCTION_NAME(X,Y) FSEv07_CAT(X,Y)
1467 #define FSEv07_TYPE_NAME(X,Y) FSEv07_CAT(X,Y)
1468
1469
1470 /* Function templates */
FSEv07_createDTable(unsigned tableLog)1471 FSEv07_DTable* FSEv07_createDTable (unsigned tableLog)
1472 {
1473 if (tableLog > FSEv07_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv07_TABLELOG_ABSOLUTE_MAX;
1474 return (FSEv07_DTable*)malloc( FSEv07_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1475 }
1476
FSEv07_freeDTable(FSEv07_DTable * dt)1477 void FSEv07_freeDTable (FSEv07_DTable* dt)
1478 {
1479 free(dt);
1480 }
1481
FSEv07_buildDTable(FSEv07_DTable * dt,const short * normalizedCounter,unsigned maxSymbolValue,unsigned tableLog)1482 size_t FSEv07_buildDTable(FSEv07_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1483 {
1484 void* const tdPtr = dt+1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
1485 FSEv07_DECODE_TYPE* const tableDecode = (FSEv07_DECODE_TYPE*) (tdPtr);
1486 U16 symbolNext[FSEv07_MAX_SYMBOL_VALUE+1];
1487
1488 U32 const maxSV1 = maxSymbolValue + 1;
1489 U32 const tableSize = 1 << tableLog;
1490 U32 highThreshold = tableSize-1;
1491
1492 /* Sanity Checks */
1493 if (maxSymbolValue > FSEv07_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1494 if (tableLog > FSEv07_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1495
1496 /* Init, lay down lowprob symbols */
1497 { FSEv07_DTableHeader DTableH;
1498 DTableH.tableLog = (U16)tableLog;
1499 DTableH.fastMode = 1;
1500 { S16 const largeLimit= (S16)(1 << (tableLog-1));
1501 U32 s;
1502 for (s=0; s<maxSV1; s++) {
1503 if (normalizedCounter[s]==-1) {
1504 tableDecode[highThreshold--].symbol = (FSEv07_FUNCTION_TYPE)s;
1505 symbolNext[s] = 1;
1506 } else {
1507 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1508 symbolNext[s] = normalizedCounter[s];
1509 } } }
1510 memcpy(dt, &DTableH, sizeof(DTableH));
1511 }
1512
1513 /* Spread symbols */
1514 { U32 const tableMask = tableSize-1;
1515 U32 const step = FSEv07_TABLESTEP(tableSize);
1516 U32 s, position = 0;
1517 for (s=0; s<maxSV1; s++) {
1518 int i;
1519 for (i=0; i<normalizedCounter[s]; i++) {
1520 tableDecode[position].symbol = (FSEv07_FUNCTION_TYPE)s;
1521 position = (position + step) & tableMask;
1522 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1523 } }
1524
1525 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1526 }
1527
1528 /* Build Decoding table */
1529 { U32 u;
1530 for (u=0; u<tableSize; u++) {
1531 FSEv07_FUNCTION_TYPE const symbol = (FSEv07_FUNCTION_TYPE)(tableDecode[u].symbol);
1532 U16 nextState = symbolNext[symbol]++;
1533 tableDecode[u].nbBits = (BYTE) (tableLog - BITv07_highbit32 ((U32)nextState) );
1534 tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1535 } }
1536
1537 return 0;
1538 }
1539
1540
1541
1542 #ifndef FSEv07_COMMONDEFS_ONLY
1543
1544 /*-*******************************************************
1545 * Decompression (Byte symbols)
1546 *********************************************************/
FSEv07_buildDTable_rle(FSEv07_DTable * dt,BYTE symbolValue)1547 size_t FSEv07_buildDTable_rle (FSEv07_DTable* dt, BYTE symbolValue)
1548 {
1549 void* ptr = dt;
1550 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1551 void* dPtr = dt + 1;
1552 FSEv07_decode_t* const cell = (FSEv07_decode_t*)dPtr;
1553
1554 DTableH->tableLog = 0;
1555 DTableH->fastMode = 0;
1556
1557 cell->newState = 0;
1558 cell->symbol = symbolValue;
1559 cell->nbBits = 0;
1560
1561 return 0;
1562 }
1563
1564
FSEv07_buildDTable_raw(FSEv07_DTable * dt,unsigned nbBits)1565 size_t FSEv07_buildDTable_raw (FSEv07_DTable* dt, unsigned nbBits)
1566 {
1567 void* ptr = dt;
1568 FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1569 void* dPtr = dt + 1;
1570 FSEv07_decode_t* const dinfo = (FSEv07_decode_t*)dPtr;
1571 const unsigned tableSize = 1 << nbBits;
1572 const unsigned tableMask = tableSize - 1;
1573 const unsigned maxSV1 = tableMask+1;
1574 unsigned s;
1575
1576 /* Sanity checks */
1577 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1578
1579 /* Build Decoding Table */
1580 DTableH->tableLog = (U16)nbBits;
1581 DTableH->fastMode = 1;
1582 for (s=0; s<maxSV1; s++) {
1583 dinfo[s].newState = 0;
1584 dinfo[s].symbol = (BYTE)s;
1585 dinfo[s].nbBits = (BYTE)nbBits;
1586 }
1587
1588 return 0;
1589 }
1590
FSEv07_decompress_usingDTable_generic(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const FSEv07_DTable * dt,const unsigned fast)1591 FORCE_INLINE size_t FSEv07_decompress_usingDTable_generic(
1592 void* dst, size_t maxDstSize,
1593 const void* cSrc, size_t cSrcSize,
1594 const FSEv07_DTable* dt, const unsigned fast)
1595 {
1596 BYTE* const ostart = (BYTE*) dst;
1597 BYTE* op = ostart;
1598 BYTE* const omax = op + maxDstSize;
1599 BYTE* const olimit = omax-3;
1600
1601 BITv07_DStream_t bitD;
1602 FSEv07_DState_t state1;
1603 FSEv07_DState_t state2;
1604
1605 /* Init */
1606 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1607 if (FSEv07_isError(errorCode)) return errorCode; }
1608
1609 FSEv07_initDState(&state1, &bitD, dt);
1610 FSEv07_initDState(&state2, &bitD, dt);
1611
1612 #define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1613
1614 /* 4 symbols per loop */
1615 for ( ; (BITv07_reloadDStream(&bitD)==BITv07_DStream_unfinished) && (op<olimit) ; op+=4) {
1616 op[0] = FSEv07_GETSYMBOL(&state1);
1617
1618 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1619 BITv07_reloadDStream(&bitD);
1620
1621 op[1] = FSEv07_GETSYMBOL(&state2);
1622
1623 if (FSEv07_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1624 { if (BITv07_reloadDStream(&bitD) > BITv07_DStream_unfinished) { op+=2; break; } }
1625
1626 op[2] = FSEv07_GETSYMBOL(&state1);
1627
1628 if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1629 BITv07_reloadDStream(&bitD);
1630
1631 op[3] = FSEv07_GETSYMBOL(&state2);
1632 }
1633
1634 /* tail */
1635 /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1636 while (1) {
1637 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1638
1639 *op++ = FSEv07_GETSYMBOL(&state1);
1640
1641 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1642 *op++ = FSEv07_GETSYMBOL(&state2);
1643 break;
1644 }
1645
1646 if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1647
1648 *op++ = FSEv07_GETSYMBOL(&state2);
1649
1650 if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1651 *op++ = FSEv07_GETSYMBOL(&state1);
1652 break;
1653 } }
1654
1655 return op-ostart;
1656 }
1657
1658
FSEv07_decompress_usingDTable(void * dst,size_t originalSize,const void * cSrc,size_t cSrcSize,const FSEv07_DTable * dt)1659 size_t FSEv07_decompress_usingDTable(void* dst, size_t originalSize,
1660 const void* cSrc, size_t cSrcSize,
1661 const FSEv07_DTable* dt)
1662 {
1663 const void* ptr = dt;
1664 const FSEv07_DTableHeader* DTableH = (const FSEv07_DTableHeader*)ptr;
1665 const U32 fastMode = DTableH->fastMode;
1666
1667 /* select fast mode (static) */
1668 if (fastMode) return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1669 return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1670 }
1671
1672
FSEv07_decompress(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize)1673 size_t FSEv07_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1674 {
1675 const BYTE* const istart = (const BYTE*)cSrc;
1676 const BYTE* ip = istart;
1677 short counting[FSEv07_MAX_SYMBOL_VALUE+1];
1678 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1679 unsigned tableLog;
1680 unsigned maxSymbolValue = FSEv07_MAX_SYMBOL_VALUE;
1681
1682 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1683
1684 /* normal FSE decoding mode */
1685 { size_t const NCountLength = FSEv07_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1686 if (FSEv07_isError(NCountLength)) return NCountLength;
1687 if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1688 ip += NCountLength;
1689 cSrcSize -= NCountLength;
1690 }
1691
1692 { size_t const errorCode = FSEv07_buildDTable (dt, counting, maxSymbolValue, tableLog);
1693 if (FSEv07_isError(errorCode)) return errorCode; }
1694
1695 return FSEv07_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt); /* always return, even if it is an error code */
1696 }
1697
1698
1699
1700 #endif /* FSEv07_COMMONDEFS_ONLY */
1701
1702 /* ******************************************************************
1703 Huffman decoder, part of New Generation Entropy library
1704 Copyright (C) 2013-2016, Yann Collet.
1705
1706 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1707
1708 Redistribution and use in source and binary forms, with or without
1709 modification, are permitted provided that the following conditions are
1710 met:
1711
1712 * Redistributions of source code must retain the above copyright
1713 notice, this list of conditions and the following disclaimer.
1714 * Redistributions in binary form must reproduce the above
1715 copyright notice, this list of conditions and the following disclaimer
1716 in the documentation and/or other materials provided with the
1717 distribution.
1718
1719 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1720 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1721 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1722 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1723 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1724 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1725 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1726 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1727 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1728 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1729 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1730
1731 You can contact the author at :
1732 - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1733 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1734 ****************************************************************** */
1735
1736 /* **************************************************************
1737 * Compiler specifics
1738 ****************************************************************/
1739 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1740 /* inline is defined */
1741 #elif defined(_MSC_VER)
1742 # define inline __inline
1743 #else
1744 # define inline /* disable inline */
1745 #endif
1746
1747
1748 #ifdef _MSC_VER /* Visual Studio */
1749 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1750 #endif
1751
1752
1753
1754 /* **************************************************************
1755 * Error Management
1756 ****************************************************************/
1757 #define HUFv07_STATIC_ASSERT(c) { enum { HUFv07_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1758
1759
1760 /*-***************************/
1761 /* generic DTableDesc */
1762 /*-***************************/
1763
1764 typedef struct { BYTE maxTableLog; BYTE tableType; BYTE tableLog; BYTE reserved; } DTableDesc;
1765
HUFv07_getDTableDesc(const HUFv07_DTable * table)1766 static DTableDesc HUFv07_getDTableDesc(const HUFv07_DTable* table)
1767 {
1768 DTableDesc dtd;
1769 memcpy(&dtd, table, sizeof(dtd));
1770 return dtd;
1771 }
1772
1773
1774 /*-***************************/
1775 /* single-symbol decoding */
1776 /*-***************************/
1777
1778 typedef struct { BYTE byte; BYTE nbBits; } HUFv07_DEltX2; /* single-symbol decoding */
1779
HUFv07_readDTableX2(HUFv07_DTable * DTable,const void * src,size_t srcSize)1780 size_t HUFv07_readDTableX2 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
1781 {
1782 BYTE huffWeight[HUFv07_SYMBOLVALUE_MAX + 1];
1783 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1]; /* large enough for values from 0 to 16 */
1784 U32 tableLog = 0;
1785 U32 nbSymbols = 0;
1786 size_t iSize;
1787 void* const dtPtr = DTable + 1;
1788 HUFv07_DEltX2* const dt = (HUFv07_DEltX2*)dtPtr;
1789
1790 HUFv07_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUFv07_DTable));
1791 /* memset(huffWeight, 0, sizeof(huffWeight)); */ /* is not necessary, even though some analyzer complain ... */
1792
1793 iSize = HUFv07_readStats(huffWeight, HUFv07_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1794 if (HUFv07_isError(iSize)) return iSize;
1795
1796 /* Table header */
1797 { DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1798 if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge); /* DTable too small, huffman tree cannot fit in */
1799 dtd.tableType = 0;
1800 dtd.tableLog = (BYTE)tableLog;
1801 memcpy(DTable, &dtd, sizeof(dtd));
1802 }
1803
1804 /* Prepare ranks */
1805 { U32 n, nextRankStart = 0;
1806 for (n=1; n<tableLog+1; n++) {
1807 U32 current = nextRankStart;
1808 nextRankStart += (rankVal[n] << (n-1));
1809 rankVal[n] = current;
1810 } }
1811
1812 /* fill DTable */
1813 { U32 n;
1814 for (n=0; n<nbSymbols; n++) {
1815 U32 const w = huffWeight[n];
1816 U32 const length = (1 << w) >> 1;
1817 U32 i;
1818 HUFv07_DEltX2 D;
1819 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1820 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1821 dt[i] = D;
1822 rankVal[w] += length;
1823 } }
1824
1825 return iSize;
1826 }
1827
1828
HUFv07_decodeSymbolX2(BITv07_DStream_t * Dstream,const HUFv07_DEltX2 * dt,const U32 dtLog)1829 static BYTE HUFv07_decodeSymbolX2(BITv07_DStream_t* Dstream, const HUFv07_DEltX2* dt, const U32 dtLog)
1830 {
1831 size_t const val = BITv07_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1832 BYTE const c = dt[val].byte;
1833 BITv07_skipBits(Dstream, dt[val].nbBits);
1834 return c;
1835 }
1836
1837 #define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1838 *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1839
1840 #define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1841 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1842 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1843
1844 #define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1845 if (MEM_64bits()) \
1846 HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1847
HUFv07_decodeStreamX2(BYTE * p,BITv07_DStream_t * const bitDPtr,BYTE * const pEnd,const HUFv07_DEltX2 * const dt,const U32 dtLog)1848 static inline size_t HUFv07_decodeStreamX2(BYTE* p, BITv07_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv07_DEltX2* const dt, const U32 dtLog)
1849 {
1850 BYTE* const pStart = p;
1851
1852 /* up to 4 symbols at a time */
1853 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-4)) {
1854 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1855 HUFv07_DECODE_SYMBOLX2_1(p, bitDPtr);
1856 HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1857 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1858 }
1859
1860 /* closer to the end */
1861 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd))
1862 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1863
1864 /* no more data to retrieve from bitstream, hence no need to reload */
1865 while (p < pEnd)
1866 HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1867
1868 return pEnd-pStart;
1869 }
1870
HUFv07_decompress1X2_usingDTable_internal(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)1871 static size_t HUFv07_decompress1X2_usingDTable_internal(
1872 void* dst, size_t dstSize,
1873 const void* cSrc, size_t cSrcSize,
1874 const HUFv07_DTable* DTable)
1875 {
1876 BYTE* op = (BYTE*)dst;
1877 BYTE* const oend = op + dstSize;
1878 const void* dtPtr = DTable + 1;
1879 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1880 BITv07_DStream_t bitD;
1881 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1882 U32 const dtLog = dtd.tableLog;
1883
1884 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
1885 if (HUFv07_isError(errorCode)) return errorCode; }
1886
1887 HUFv07_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1888
1889 /* check */
1890 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
1891
1892 return dstSize;
1893 }
1894
HUFv07_decompress1X2_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)1895 size_t HUFv07_decompress1X2_usingDTable(
1896 void* dst, size_t dstSize,
1897 const void* cSrc, size_t cSrcSize,
1898 const HUFv07_DTable* DTable)
1899 {
1900 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1901 if (dtd.tableType != 0) return ERROR(GENERIC);
1902 return HUFv07_decompress1X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
1903 }
1904
HUFv07_decompress1X2_DCtx(HUFv07_DTable * DCtx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)1905 size_t HUFv07_decompress1X2_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1906 {
1907 const BYTE* ip = (const BYTE*) cSrc;
1908
1909 size_t const hSize = HUFv07_readDTableX2 (DCtx, cSrc, cSrcSize);
1910 if (HUFv07_isError(hSize)) return hSize;
1911 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1912 ip += hSize; cSrcSize -= hSize;
1913
1914 return HUFv07_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
1915 }
1916
HUFv07_decompress1X2(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)1917 size_t HUFv07_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1918 {
1919 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
1920 return HUFv07_decompress1X2_DCtx (DTable, dst, dstSize, cSrc, cSrcSize);
1921 }
1922
1923
HUFv07_decompress4X2_usingDTable_internal(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)1924 static size_t HUFv07_decompress4X2_usingDTable_internal(
1925 void* dst, size_t dstSize,
1926 const void* cSrc, size_t cSrcSize,
1927 const HUFv07_DTable* DTable)
1928 {
1929 /* Check */
1930 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1931
1932 { const BYTE* const istart = (const BYTE*) cSrc;
1933 BYTE* const ostart = (BYTE*) dst;
1934 BYTE* const oend = ostart + dstSize;
1935 const void* const dtPtr = DTable + 1;
1936 const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1937
1938 /* Init */
1939 BITv07_DStream_t bitD1;
1940 BITv07_DStream_t bitD2;
1941 BITv07_DStream_t bitD3;
1942 BITv07_DStream_t bitD4;
1943 size_t const length1 = MEM_readLE16(istart);
1944 size_t const length2 = MEM_readLE16(istart+2);
1945 size_t const length3 = MEM_readLE16(istart+4);
1946 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
1947 const BYTE* const istart1 = istart + 6; /* jumpTable */
1948 const BYTE* const istart2 = istart1 + length1;
1949 const BYTE* const istart3 = istart2 + length2;
1950 const BYTE* const istart4 = istart3 + length3;
1951 const size_t segmentSize = (dstSize+3) / 4;
1952 BYTE* const opStart2 = ostart + segmentSize;
1953 BYTE* const opStart3 = opStart2 + segmentSize;
1954 BYTE* const opStart4 = opStart3 + segmentSize;
1955 BYTE* op1 = ostart;
1956 BYTE* op2 = opStart2;
1957 BYTE* op3 = opStart3;
1958 BYTE* op4 = opStart4;
1959 U32 endSignal;
1960 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1961 U32 const dtLog = dtd.tableLog;
1962
1963 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1964 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
1965 if (HUFv07_isError(errorCode)) return errorCode; }
1966 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
1967 if (HUFv07_isError(errorCode)) return errorCode; }
1968 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
1969 if (HUFv07_isError(errorCode)) return errorCode; }
1970 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
1971 if (HUFv07_isError(errorCode)) return errorCode; }
1972
1973 /* 16-32 symbols per loop (4-8 symbols per stream) */
1974 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1975 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
1976 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
1977 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
1978 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
1979 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
1980 HUFv07_DECODE_SYMBOLX2_1(op1, &bitD1);
1981 HUFv07_DECODE_SYMBOLX2_1(op2, &bitD2);
1982 HUFv07_DECODE_SYMBOLX2_1(op3, &bitD3);
1983 HUFv07_DECODE_SYMBOLX2_1(op4, &bitD4);
1984 HUFv07_DECODE_SYMBOLX2_2(op1, &bitD1);
1985 HUFv07_DECODE_SYMBOLX2_2(op2, &bitD2);
1986 HUFv07_DECODE_SYMBOLX2_2(op3, &bitD3);
1987 HUFv07_DECODE_SYMBOLX2_2(op4, &bitD4);
1988 HUFv07_DECODE_SYMBOLX2_0(op1, &bitD1);
1989 HUFv07_DECODE_SYMBOLX2_0(op2, &bitD2);
1990 HUFv07_DECODE_SYMBOLX2_0(op3, &bitD3);
1991 HUFv07_DECODE_SYMBOLX2_0(op4, &bitD4);
1992 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1993 }
1994
1995 /* check corruption */
1996 if (op1 > opStart2) return ERROR(corruption_detected);
1997 if (op2 > opStart3) return ERROR(corruption_detected);
1998 if (op3 > opStart4) return ERROR(corruption_detected);
1999 /* note : op4 supposed already verified within main loop */
2000
2001 /* finish bitStreams one by one */
2002 HUFv07_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2003 HUFv07_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2004 HUFv07_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2005 HUFv07_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2006
2007 /* check */
2008 endSignal = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2009 if (!endSignal) return ERROR(corruption_detected);
2010
2011 /* decoded size */
2012 return dstSize;
2013 }
2014 }
2015
2016
HUFv07_decompress4X2_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)2017 size_t HUFv07_decompress4X2_usingDTable(
2018 void* dst, size_t dstSize,
2019 const void* cSrc, size_t cSrcSize,
2020 const HUFv07_DTable* DTable)
2021 {
2022 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2023 if (dtd.tableType != 0) return ERROR(GENERIC);
2024 return HUFv07_decompress4X2_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2025 }
2026
2027
HUFv07_decompress4X2_DCtx(HUFv07_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2028 size_t HUFv07_decompress4X2_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2029 {
2030 const BYTE* ip = (const BYTE*) cSrc;
2031
2032 size_t const hSize = HUFv07_readDTableX2 (dctx, cSrc, cSrcSize);
2033 if (HUFv07_isError(hSize)) return hSize;
2034 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2035 ip += hSize; cSrcSize -= hSize;
2036
2037 return HUFv07_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx);
2038 }
2039
HUFv07_decompress4X2(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2040 size_t HUFv07_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2041 {
2042 HUFv07_CREATE_STATIC_DTABLEX2(DTable, HUFv07_TABLELOG_MAX);
2043 return HUFv07_decompress4X2_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2044 }
2045
2046
2047 /* *************************/
2048 /* double-symbols decoding */
2049 /* *************************/
2050 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv07_DEltX4; /* double-symbols decoding */
2051
2052 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
2053
HUFv07_fillDTableX4Level2(HUFv07_DEltX4 * DTable,U32 sizeLog,const U32 consumed,const U32 * rankValOrigin,const int minWeight,const sortedSymbol_t * sortedSymbols,const U32 sortedListSize,U32 nbBitsBaseline,U16 baseSeq)2054 static void HUFv07_fillDTableX4Level2(HUFv07_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2055 const U32* rankValOrigin, const int minWeight,
2056 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2057 U32 nbBitsBaseline, U16 baseSeq)
2058 {
2059 HUFv07_DEltX4 DElt;
2060 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2061
2062 /* get pre-calculated rankVal */
2063 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2064
2065 /* fill skipped values */
2066 if (minWeight>1) {
2067 U32 i, skipSize = rankVal[minWeight];
2068 MEM_writeLE16(&(DElt.sequence), baseSeq);
2069 DElt.nbBits = (BYTE)(consumed);
2070 DElt.length = 1;
2071 for (i = 0; i < skipSize; i++)
2072 DTable[i] = DElt;
2073 }
2074
2075 /* fill DTable */
2076 { U32 s; for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2077 const U32 symbol = sortedSymbols[s].symbol;
2078 const U32 weight = sortedSymbols[s].weight;
2079 const U32 nbBits = nbBitsBaseline - weight;
2080 const U32 length = 1 << (sizeLog-nbBits);
2081 const U32 start = rankVal[weight];
2082 U32 i = start;
2083 const U32 end = start + length;
2084
2085 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2086 DElt.nbBits = (BYTE)(nbBits + consumed);
2087 DElt.length = 2;
2088 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2089
2090 rankVal[weight] += length;
2091 }}
2092 }
2093
2094 typedef U32 rankVal_t[HUFv07_TABLELOG_ABSOLUTEMAX][HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2095
HUFv07_fillDTableX4(HUFv07_DEltX4 * DTable,const U32 targetLog,const sortedSymbol_t * sortedList,const U32 sortedListSize,const U32 * rankStart,rankVal_t rankValOrigin,const U32 maxWeight,const U32 nbBitsBaseline)2096 static void HUFv07_fillDTableX4(HUFv07_DEltX4* DTable, const U32 targetLog,
2097 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2098 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2099 const U32 nbBitsBaseline)
2100 {
2101 U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];
2102 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2103 const U32 minBits = nbBitsBaseline - maxWeight;
2104 U32 s;
2105
2106 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2107
2108 /* fill DTable */
2109 for (s=0; s<sortedListSize; s++) {
2110 const U16 symbol = sortedList[s].symbol;
2111 const U32 weight = sortedList[s].weight;
2112 const U32 nbBits = nbBitsBaseline - weight;
2113 const U32 start = rankVal[weight];
2114 const U32 length = 1 << (targetLog-nbBits);
2115
2116 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2117 U32 sortedRank;
2118 int minWeight = nbBits + scaleLog;
2119 if (minWeight < 1) minWeight = 1;
2120 sortedRank = rankStart[minWeight];
2121 HUFv07_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2122 rankValOrigin[nbBits], minWeight,
2123 sortedList+sortedRank, sortedListSize-sortedRank,
2124 nbBitsBaseline, symbol);
2125 } else {
2126 HUFv07_DEltX4 DElt;
2127 MEM_writeLE16(&(DElt.sequence), symbol);
2128 DElt.nbBits = (BYTE)(nbBits);
2129 DElt.length = 1;
2130 { U32 u;
2131 const U32 end = start + length;
2132 for (u = start; u < end; u++) DTable[u] = DElt;
2133 } }
2134 rankVal[weight] += length;
2135 }
2136 }
2137
HUFv07_readDTableX4(HUFv07_DTable * DTable,const void * src,size_t srcSize)2138 size_t HUFv07_readDTableX4 (HUFv07_DTable* DTable, const void* src, size_t srcSize)
2139 {
2140 BYTE weightList[HUFv07_SYMBOLVALUE_MAX + 1];
2141 sortedSymbol_t sortedSymbol[HUFv07_SYMBOLVALUE_MAX + 1];
2142 U32 rankStats[HUFv07_TABLELOG_ABSOLUTEMAX + 1] = { 0 };
2143 U32 rankStart0[HUFv07_TABLELOG_ABSOLUTEMAX + 2] = { 0 };
2144 U32* const rankStart = rankStart0+1;
2145 rankVal_t rankVal;
2146 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2147 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2148 U32 const maxTableLog = dtd.maxTableLog;
2149 size_t iSize;
2150 void* dtPtr = DTable+1; /* force compiler to avoid strict-aliasing */
2151 HUFv07_DEltX4* const dt = (HUFv07_DEltX4*)dtPtr;
2152
2153 HUFv07_STATIC_ASSERT(sizeof(HUFv07_DEltX4) == sizeof(HUFv07_DTable)); /* if compilation fails here, assertion is false */
2154 if (maxTableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(tableLog_tooLarge);
2155 /* memset(weightList, 0, sizeof(weightList)); */ /* is not necessary, even though some analyzer complain ... */
2156
2157 iSize = HUFv07_readStats(weightList, HUFv07_SYMBOLVALUE_MAX + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2158 if (HUFv07_isError(iSize)) return iSize;
2159
2160 /* check result */
2161 if (tableLog > maxTableLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2162
2163 /* find maxWeight */
2164 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2165
2166 /* Get start index of each weight */
2167 { U32 w, nextRankStart = 0;
2168 for (w=1; w<maxW+1; w++) {
2169 U32 current = nextRankStart;
2170 nextRankStart += rankStats[w];
2171 rankStart[w] = current;
2172 }
2173 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2174 sizeOfSort = nextRankStart;
2175 }
2176
2177 /* sort symbols by weight */
2178 { U32 s;
2179 for (s=0; s<nbSymbols; s++) {
2180 U32 const w = weightList[s];
2181 U32 const r = rankStart[w]++;
2182 sortedSymbol[r].symbol = (BYTE)s;
2183 sortedSymbol[r].weight = (BYTE)w;
2184 }
2185 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2186 }
2187
2188 /* Build rankVal */
2189 { U32* const rankVal0 = rankVal[0];
2190 { int const rescale = (maxTableLog-tableLog) - 1; /* tableLog <= maxTableLog */
2191 U32 nextRankVal = 0;
2192 U32 w;
2193 for (w=1; w<maxW+1; w++) {
2194 U32 current = nextRankVal;
2195 nextRankVal += rankStats[w] << (w+rescale);
2196 rankVal0[w] = current;
2197 } }
2198 { U32 const minBits = tableLog+1 - maxW;
2199 U32 consumed;
2200 for (consumed = minBits; consumed < maxTableLog - minBits + 1; consumed++) {
2201 U32* const rankValPtr = rankVal[consumed];
2202 U32 w;
2203 for (w = 1; w < maxW+1; w++) {
2204 rankValPtr[w] = rankVal0[w] >> consumed;
2205 } } } }
2206
2207 HUFv07_fillDTableX4(dt, maxTableLog,
2208 sortedSymbol, sizeOfSort,
2209 rankStart0, rankVal, maxW,
2210 tableLog+1);
2211
2212 dtd.tableLog = (BYTE)maxTableLog;
2213 dtd.tableType = 1;
2214 memcpy(DTable, &dtd, sizeof(dtd));
2215 return iSize;
2216 }
2217
2218
HUFv07_decodeSymbolX4(void * op,BITv07_DStream_t * DStream,const HUFv07_DEltX4 * dt,const U32 dtLog)2219 static U32 HUFv07_decodeSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2220 {
2221 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2222 memcpy(op, dt+val, 2);
2223 BITv07_skipBits(DStream, dt[val].nbBits);
2224 return dt[val].length;
2225 }
2226
HUFv07_decodeLastSymbolX4(void * op,BITv07_DStream_t * DStream,const HUFv07_DEltX4 * dt,const U32 dtLog)2227 static U32 HUFv07_decodeLastSymbolX4(void* op, BITv07_DStream_t* DStream, const HUFv07_DEltX4* dt, const U32 dtLog)
2228 {
2229 const size_t val = BITv07_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2230 memcpy(op, dt+val, 1);
2231 if (dt[val].length==1) BITv07_skipBits(DStream, dt[val].nbBits);
2232 else {
2233 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2234 BITv07_skipBits(DStream, dt[val].nbBits);
2235 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2236 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 */
2237 } }
2238 return 1;
2239 }
2240
2241
2242 #define HUFv07_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2243 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2244
2245 #define HUFv07_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2246 if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
2247 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2248
2249 #define HUFv07_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2250 if (MEM_64bits()) \
2251 ptr += HUFv07_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2252
HUFv07_decodeStreamX4(BYTE * p,BITv07_DStream_t * bitDPtr,BYTE * const pEnd,const HUFv07_DEltX4 * const dt,const U32 dtLog)2253 static inline size_t HUFv07_decodeStreamX4(BYTE* p, BITv07_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv07_DEltX4* const dt, const U32 dtLog)
2254 {
2255 BYTE* const pStart = p;
2256
2257 /* up to 8 symbols at a time */
2258 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p < pEnd-7)) {
2259 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2260 HUFv07_DECODE_SYMBOLX4_1(p, bitDPtr);
2261 HUFv07_DECODE_SYMBOLX4_2(p, bitDPtr);
2262 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2263 }
2264
2265 /* closer to end : up to 2 symbols at a time */
2266 while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-2))
2267 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr);
2268
2269 while (p <= pEnd-2)
2270 HUFv07_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2271
2272 if (p < pEnd)
2273 p += HUFv07_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2274
2275 return p-pStart;
2276 }
2277
2278
HUFv07_decompress1X4_usingDTable_internal(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)2279 static size_t HUFv07_decompress1X4_usingDTable_internal(
2280 void* dst, size_t dstSize,
2281 const void* cSrc, size_t cSrcSize,
2282 const HUFv07_DTable* DTable)
2283 {
2284 BITv07_DStream_t bitD;
2285
2286 /* Init */
2287 { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
2288 if (HUFv07_isError(errorCode)) return errorCode;
2289 }
2290
2291 /* decode */
2292 { BYTE* const ostart = (BYTE*) dst;
2293 BYTE* const oend = ostart + dstSize;
2294 const void* const dtPtr = DTable+1; /* force compiler to not use strict-aliasing */
2295 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2296 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2297 HUFv07_decodeStreamX4(ostart, &bitD, oend, dt, dtd.tableLog);
2298 }
2299
2300 /* check */
2301 if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
2302
2303 /* decoded size */
2304 return dstSize;
2305 }
2306
HUFv07_decompress1X4_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)2307 size_t HUFv07_decompress1X4_usingDTable(
2308 void* dst, size_t dstSize,
2309 const void* cSrc, size_t cSrcSize,
2310 const HUFv07_DTable* DTable)
2311 {
2312 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2313 if (dtd.tableType != 1) return ERROR(GENERIC);
2314 return HUFv07_decompress1X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2315 }
2316
HUFv07_decompress1X4_DCtx(HUFv07_DTable * DCtx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2317 size_t HUFv07_decompress1X4_DCtx (HUFv07_DTable* DCtx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2318 {
2319 const BYTE* ip = (const BYTE*) cSrc;
2320
2321 size_t const hSize = HUFv07_readDTableX4 (DCtx, cSrc, cSrcSize);
2322 if (HUFv07_isError(hSize)) return hSize;
2323 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2324 ip += hSize; cSrcSize -= hSize;
2325
2326 return HUFv07_decompress1X4_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
2327 }
2328
HUFv07_decompress1X4(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2329 size_t HUFv07_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2330 {
2331 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2332 return HUFv07_decompress1X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2333 }
2334
HUFv07_decompress4X4_usingDTable_internal(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)2335 static size_t HUFv07_decompress4X4_usingDTable_internal(
2336 void* dst, size_t dstSize,
2337 const void* cSrc, size_t cSrcSize,
2338 const HUFv07_DTable* DTable)
2339 {
2340 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2341
2342 { const BYTE* const istart = (const BYTE*) cSrc;
2343 BYTE* const ostart = (BYTE*) dst;
2344 BYTE* const oend = ostart + dstSize;
2345 const void* const dtPtr = DTable+1;
2346 const HUFv07_DEltX4* const dt = (const HUFv07_DEltX4*)dtPtr;
2347
2348 /* Init */
2349 BITv07_DStream_t bitD1;
2350 BITv07_DStream_t bitD2;
2351 BITv07_DStream_t bitD3;
2352 BITv07_DStream_t bitD4;
2353 size_t const length1 = MEM_readLE16(istart);
2354 size_t const length2 = MEM_readLE16(istart+2);
2355 size_t const length3 = MEM_readLE16(istart+4);
2356 size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
2357 const BYTE* const istart1 = istart + 6; /* jumpTable */
2358 const BYTE* const istart2 = istart1 + length1;
2359 const BYTE* const istart3 = istart2 + length2;
2360 const BYTE* const istart4 = istart3 + length3;
2361 size_t const segmentSize = (dstSize+3) / 4;
2362 BYTE* const opStart2 = ostart + segmentSize;
2363 BYTE* const opStart3 = opStart2 + segmentSize;
2364 BYTE* const opStart4 = opStart3 + segmentSize;
2365 BYTE* op1 = ostart;
2366 BYTE* op2 = opStart2;
2367 BYTE* op3 = opStart3;
2368 BYTE* op4 = opStart4;
2369 U32 endSignal;
2370 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2371 U32 const dtLog = dtd.tableLog;
2372
2373 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2374 { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
2375 if (HUFv07_isError(errorCode)) return errorCode; }
2376 { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
2377 if (HUFv07_isError(errorCode)) return errorCode; }
2378 { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
2379 if (HUFv07_isError(errorCode)) return errorCode; }
2380 { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
2381 if (HUFv07_isError(errorCode)) return errorCode; }
2382
2383 /* 16-32 symbols per loop (4-8 symbols per stream) */
2384 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2385 for ( ; (endSignal==BITv07_DStream_unfinished) && (op4<(oend-7)) ; ) {
2386 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2387 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2388 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2389 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2390 HUFv07_DECODE_SYMBOLX4_1(op1, &bitD1);
2391 HUFv07_DECODE_SYMBOLX4_1(op2, &bitD2);
2392 HUFv07_DECODE_SYMBOLX4_1(op3, &bitD3);
2393 HUFv07_DECODE_SYMBOLX4_1(op4, &bitD4);
2394 HUFv07_DECODE_SYMBOLX4_2(op1, &bitD1);
2395 HUFv07_DECODE_SYMBOLX4_2(op2, &bitD2);
2396 HUFv07_DECODE_SYMBOLX4_2(op3, &bitD3);
2397 HUFv07_DECODE_SYMBOLX4_2(op4, &bitD4);
2398 HUFv07_DECODE_SYMBOLX4_0(op1, &bitD1);
2399 HUFv07_DECODE_SYMBOLX4_0(op2, &bitD2);
2400 HUFv07_DECODE_SYMBOLX4_0(op3, &bitD3);
2401 HUFv07_DECODE_SYMBOLX4_0(op4, &bitD4);
2402
2403 endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
2404 }
2405
2406 /* check corruption */
2407 if (op1 > opStart2) return ERROR(corruption_detected);
2408 if (op2 > opStart3) return ERROR(corruption_detected);
2409 if (op3 > opStart4) return ERROR(corruption_detected);
2410 /* note : op4 supposed already verified within main loop */
2411
2412 /* finish bitStreams one by one */
2413 HUFv07_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2414 HUFv07_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2415 HUFv07_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2416 HUFv07_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2417
2418 /* check */
2419 { U32 const endCheck = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
2420 if (!endCheck) return ERROR(corruption_detected); }
2421
2422 /* decoded size */
2423 return dstSize;
2424 }
2425 }
2426
2427
HUFv07_decompress4X4_usingDTable(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)2428 size_t HUFv07_decompress4X4_usingDTable(
2429 void* dst, size_t dstSize,
2430 const void* cSrc, size_t cSrcSize,
2431 const HUFv07_DTable* DTable)
2432 {
2433 DTableDesc dtd = HUFv07_getDTableDesc(DTable);
2434 if (dtd.tableType != 1) return ERROR(GENERIC);
2435 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, cSrc, cSrcSize, DTable);
2436 }
2437
2438
HUFv07_decompress4X4_DCtx(HUFv07_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2439 size_t HUFv07_decompress4X4_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2440 {
2441 const BYTE* ip = (const BYTE*) cSrc;
2442
2443 size_t hSize = HUFv07_readDTableX4 (dctx, cSrc, cSrcSize);
2444 if (HUFv07_isError(hSize)) return hSize;
2445 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2446 ip += hSize; cSrcSize -= hSize;
2447
2448 return HUFv07_decompress4X4_usingDTable_internal(dst, dstSize, ip, cSrcSize, dctx);
2449 }
2450
HUFv07_decompress4X4(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2451 size_t HUFv07_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2452 {
2453 HUFv07_CREATE_STATIC_DTABLEX4(DTable, HUFv07_TABLELOG_MAX);
2454 return HUFv07_decompress4X4_DCtx(DTable, dst, dstSize, cSrc, cSrcSize);
2455 }
2456
2457
2458 /* ********************************/
2459 /* Generic decompression selector */
2460 /* ********************************/
2461
HUFv07_decompress1X_usingDTable(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)2462 size_t HUFv07_decompress1X_usingDTable(void* dst, size_t maxDstSize,
2463 const void* cSrc, size_t cSrcSize,
2464 const HUFv07_DTable* DTable)
2465 {
2466 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2467 return dtd.tableType ? HUFv07_decompress1X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2468 HUFv07_decompress1X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2469 }
2470
HUFv07_decompress4X_usingDTable(void * dst,size_t maxDstSize,const void * cSrc,size_t cSrcSize,const HUFv07_DTable * DTable)2471 size_t HUFv07_decompress4X_usingDTable(void* dst, size_t maxDstSize,
2472 const void* cSrc, size_t cSrcSize,
2473 const HUFv07_DTable* DTable)
2474 {
2475 DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
2476 return dtd.tableType ? HUFv07_decompress4X4_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable) :
2477 HUFv07_decompress4X2_usingDTable_internal(dst, maxDstSize, cSrc, cSrcSize, DTable);
2478 }
2479
2480
2481 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2482 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2483 {
2484 /* single, double, quad */
2485 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2486 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2487 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2488 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2489 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2490 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2491 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2492 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2493 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2494 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2495 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2496 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2497 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2498 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2499 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2500 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2501 };
2502
2503 /** HUFv07_selectDecoder() :
2504 * Tells which decoder is likely to decode faster,
2505 * based on a set of pre-determined metrics.
2506 * @return : 0==HUFv07_decompress4X2, 1==HUFv07_decompress4X4 .
2507 * Assumption : 0 < cSrcSize < dstSize <= 128 KB */
HUFv07_selectDecoder(size_t dstSize,size_t cSrcSize)2508 U32 HUFv07_selectDecoder (size_t dstSize, size_t cSrcSize)
2509 {
2510 /* decoder timing evaluation */
2511 U32 const Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2512 U32 const D256 = (U32)(dstSize >> 8);
2513 U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
2514 U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
2515 DTime1 += DTime1 >> 3; /* advantage to algorithm using less memory, for cache eviction */
2516
2517 return DTime1 < DTime0;
2518 }
2519
2520
2521 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2522
HUFv07_decompress(void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2523 size_t HUFv07_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2524 {
2525 static const decompressionAlgo decompress[2] = { HUFv07_decompress4X2, HUFv07_decompress4X4 };
2526
2527 /* validation checks */
2528 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2529 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2530 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2531 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2532
2533 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2534 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2535 }
2536
2537 /* return HUFv07_decompress4X2(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams single-symbol decoding */
2538 /* return HUFv07_decompress4X4(dst, dstSize, cSrc, cSrcSize); */ /* multi-streams double-symbols decoding */
2539 }
2540
HUFv07_decompress4X_DCtx(HUFv07_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2541 size_t HUFv07_decompress4X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2542 {
2543 /* validation checks */
2544 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2545 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2546 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2547 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2548
2549 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2550 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2551 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2552 }
2553 }
2554
HUFv07_decompress4X_hufOnly(HUFv07_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2555 size_t HUFv07_decompress4X_hufOnly (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2556 {
2557 /* validation checks */
2558 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2559 if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected); /* invalid */
2560
2561 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2562 return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2563 HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2564 }
2565 }
2566
HUFv07_decompress1X_DCtx(HUFv07_DTable * dctx,void * dst,size_t dstSize,const void * cSrc,size_t cSrcSize)2567 size_t HUFv07_decompress1X_DCtx (HUFv07_DTable* dctx, void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2568 {
2569 /* validation checks */
2570 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2571 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2572 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2573 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2574
2575 { U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2576 return algoNb ? HUFv07_decompress1X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2577 HUFv07_decompress1X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2578 }
2579 }
2580 /*
2581 Common functions of Zstd compression library
2582 Copyright (C) 2015-2016, Yann Collet.
2583
2584 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2585
2586 Redistribution and use in source and binary forms, with or without
2587 modification, are permitted provided that the following conditions are
2588 met:
2589 * Redistributions of source code must retain the above copyright
2590 notice, this list of conditions and the following disclaimer.
2591 * Redistributions in binary form must reproduce the above
2592 copyright notice, this list of conditions and the following disclaimer
2593 in the documentation and/or other materials provided with the
2594 distribution.
2595 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2596 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2597 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2598 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2599 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2600 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2601 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2602 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2603 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2604 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2605 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2606
2607 You can contact the author at :
2608 - zstd homepage : http://www.zstd.net/
2609 */
2610
2611
2612
2613 /*-****************************************
2614 * ZSTD Error Management
2615 ******************************************/
2616 /*! ZSTDv07_isError() :
2617 * tells if a return value is an error code */
ZSTDv07_isError(size_t code)2618 unsigned ZSTDv07_isError(size_t code) { return ERR_isError(code); }
2619
2620 /*! ZSTDv07_getErrorName() :
2621 * provides error code string from function result (useful for debugging) */
ZSTDv07_getErrorName(size_t code)2622 const char* ZSTDv07_getErrorName(size_t code) { return ERR_getErrorName(code); }
2623
2624
2625
2626 /* **************************************************************
2627 * ZBUFF Error Management
2628 ****************************************************************/
ZBUFFv07_isError(size_t errorCode)2629 unsigned ZBUFFv07_isError(size_t errorCode) { return ERR_isError(errorCode); }
2630
ZBUFFv07_getErrorName(size_t errorCode)2631 const char* ZBUFFv07_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2632
2633
2634
ZSTDv07_defaultAllocFunction(void * opaque,size_t size)2635 static void* ZSTDv07_defaultAllocFunction(void* opaque, size_t size)
2636 {
2637 void* address = malloc(size);
2638 (void)opaque;
2639 /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2640 return address;
2641 }
2642
ZSTDv07_defaultFreeFunction(void * opaque,void * address)2643 static void ZSTDv07_defaultFreeFunction(void* opaque, void* address)
2644 {
2645 (void)opaque;
2646 /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2647 free(address);
2648 }
2649 /*
2650 zstd_internal - common functions to include
2651 Header File for include
2652 Copyright (C) 2014-2016, Yann Collet.
2653
2654 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2655
2656 Redistribution and use in source and binary forms, with or without
2657 modification, are permitted provided that the following conditions are
2658 met:
2659 * Redistributions of source code must retain the above copyright
2660 notice, this list of conditions and the following disclaimer.
2661 * Redistributions in binary form must reproduce the above
2662 copyright notice, this list of conditions and the following disclaimer
2663 in the documentation and/or other materials provided with the
2664 distribution.
2665 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2666 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2667 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2668 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2669 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2670 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2671 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2672 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2673 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2674 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2675 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2676
2677 You can contact the author at :
2678 - zstd homepage : https://www.zstd.net
2679 */
2680 #ifndef ZSTDv07_CCOMMON_H_MODULE
2681 #define ZSTDv07_CCOMMON_H_MODULE
2682
2683
2684 /*-*************************************
2685 * Common macros
2686 ***************************************/
2687 #define MIN(a,b) ((a)<(b) ? (a) : (b))
2688 #define MAX(a,b) ((a)>(b) ? (a) : (b))
2689
2690
2691 /*-*************************************
2692 * Common constants
2693 ***************************************/
2694 #define ZSTDv07_OPT_NUM (1<<12)
2695 #define ZSTDv07_DICT_MAGIC 0xEC30A437 /* v0.7 */
2696
2697 #define ZSTDv07_REP_NUM 3
2698 #define ZSTDv07_REP_INIT ZSTDv07_REP_NUM
2699 #define ZSTDv07_REP_MOVE (ZSTDv07_REP_NUM-1)
2700 static const U32 repStartValue[ZSTDv07_REP_NUM] = { 1, 4, 8 };
2701
2702 #define KB *(1 <<10)
2703 #define MB *(1 <<20)
2704 #define GB *(1U<<30)
2705
2706 #define BIT7 128
2707 #define BIT6 64
2708 #define BIT5 32
2709 #define BIT4 16
2710 #define BIT1 2
2711 #define BIT0 1
2712
2713 #define ZSTDv07_WINDOWLOG_ABSOLUTEMIN 10
2714 static const size_t ZSTDv07_fcs_fieldSize[4] = { 0, 2, 4, 8 };
2715 static const size_t ZSTDv07_did_fieldSize[4] = { 0, 1, 2, 4 };
2716
2717 #define ZSTDv07_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
2718 static const size_t ZSTDv07_blockHeaderSize = ZSTDv07_BLOCKHEADERSIZE;
2719 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2720
2721 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2722 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
2723
2724 #define HufLog 12
2725 typedef enum { lbt_huffman, lbt_repeat, lbt_raw, lbt_rle } litBlockType_t;
2726
2727 #define LONGNBSEQ 0x7F00
2728
2729 #define MINMATCH 3
2730 #define EQUAL_READ32 4
2731
2732 #define Litbits 8
2733 #define MaxLit ((1<<Litbits) - 1)
2734 #define MaxML 52
2735 #define MaxLL 35
2736 #define MaxOff 28
2737 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
2738 #define MLFSELog 9
2739 #define LLFSELog 9
2740 #define OffFSELog 8
2741
2742 #define FSEv07_ENCODING_RAW 0
2743 #define FSEv07_ENCODING_RLE 1
2744 #define FSEv07_ENCODING_STATIC 2
2745 #define FSEv07_ENCODING_DYNAMIC 3
2746
2747 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2748
2749 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2750 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
2751 13,14,15,16 };
2752 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2753 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
2754 -1,-1,-1,-1 };
2755 static const U32 LL_defaultNormLog = 6;
2756
2757 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2758 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2759 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
2760 12,13,14,15,16 };
2761 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2762 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
2763 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
2764 -1,-1,-1,-1,-1 };
2765 static const U32 ML_defaultNormLog = 6;
2766
2767 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
2768 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
2769 static const U32 OF_defaultNormLog = 5;
2770
2771
2772 /*-*******************************************
2773 * Shared functions to include for inlining
2774 *********************************************/
ZSTDv07_copy8(void * dst,const void * src)2775 static void ZSTDv07_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2776 #define COPY8(d,s) { ZSTDv07_copy8(d,s); d+=8; s+=8; }
2777
2778 /*! ZSTDv07_wildcopy() :
2779 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
2780 #define WILDCOPY_OVERLENGTH 8
ZSTDv07_wildcopy(void * dst,const void * src,ptrdiff_t length)2781 MEM_STATIC void ZSTDv07_wildcopy(void* dst, const void* src, ptrdiff_t length)
2782 {
2783 const BYTE* ip = (const BYTE*)src;
2784 BYTE* op = (BYTE*)dst;
2785 BYTE* const oend = op + length;
2786 do
2787 COPY8(op, ip)
2788 while (op < oend);
2789 }
2790
2791
2792 /*-*******************************************
2793 * Private interfaces
2794 *********************************************/
2795 typedef struct ZSTDv07_stats_s ZSTDv07_stats_t;
2796
2797 typedef struct {
2798 U32 off;
2799 U32 len;
2800 } ZSTDv07_match_t;
2801
2802 typedef struct {
2803 U32 price;
2804 U32 off;
2805 U32 mlen;
2806 U32 litlen;
2807 U32 rep[ZSTDv07_REP_INIT];
2808 } ZSTDv07_optimal_t;
2809
2810 struct ZSTDv07_stats_s { U32 unused; };
2811
2812 typedef struct {
2813 void* buffer;
2814 U32* offsetStart;
2815 U32* offset;
2816 BYTE* offCodeStart;
2817 BYTE* litStart;
2818 BYTE* lit;
2819 U16* litLengthStart;
2820 U16* litLength;
2821 BYTE* llCodeStart;
2822 U16* matchLengthStart;
2823 U16* matchLength;
2824 BYTE* mlCodeStart;
2825 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
2826 U32 longLengthPos;
2827 /* opt */
2828 ZSTDv07_optimal_t* priceTable;
2829 ZSTDv07_match_t* matchTable;
2830 U32* matchLengthFreq;
2831 U32* litLengthFreq;
2832 U32* litFreq;
2833 U32* offCodeFreq;
2834 U32 matchLengthSum;
2835 U32 matchSum;
2836 U32 litLengthSum;
2837 U32 litSum;
2838 U32 offCodeSum;
2839 U32 log2matchLengthSum;
2840 U32 log2matchSum;
2841 U32 log2litLengthSum;
2842 U32 log2litSum;
2843 U32 log2offCodeSum;
2844 U32 factor;
2845 U32 cachedPrice;
2846 U32 cachedLitLength;
2847 const BYTE* cachedLiterals;
2848 ZSTDv07_stats_t stats;
2849 } seqStore_t;
2850
2851 void ZSTDv07_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
2852
2853 /* custom memory allocation functions */
2854 static const ZSTDv07_customMem defaultCustomMem = { ZSTDv07_defaultAllocFunction, ZSTDv07_defaultFreeFunction, NULL };
2855
2856 #endif /* ZSTDv07_CCOMMON_H_MODULE */
2857 /*
2858 zstd - standard compression library
2859 Copyright (C) 2014-2016, Yann Collet.
2860
2861 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2862
2863 Redistribution and use in source and binary forms, with or without
2864 modification, are permitted provided that the following conditions are
2865 met:
2866 * Redistributions of source code must retain the above copyright
2867 notice, this list of conditions and the following disclaimer.
2868 * Redistributions in binary form must reproduce the above
2869 copyright notice, this list of conditions and the following disclaimer
2870 in the documentation and/or other materials provided with the
2871 distribution.
2872 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2873 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2874 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2875 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2876 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2877 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2878 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2879 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2880 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2881 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2882 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2883
2884 You can contact the author at :
2885 - zstd homepage : http://www.zstd.net
2886 */
2887
2888 /* ***************************************************************
2889 * Tuning parameters
2890 *****************************************************************/
2891 /*!
2892 * HEAPMODE :
2893 * Select how default decompression function ZSTDv07_decompress() will allocate memory,
2894 * in memory stack (0), or in memory heap (1, requires malloc())
2895 */
2896 #ifndef ZSTDv07_HEAPMODE
2897 # define ZSTDv07_HEAPMODE 1
2898 #endif
2899
2900
2901 /*-*******************************************************
2902 * Compiler specifics
2903 *********************************************************/
2904 #ifdef _MSC_VER /* Visual Studio */
2905 # include <intrin.h> /* For Visual 2005 */
2906 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2907 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2908 # pragma warning(disable : 4100) /* disable: C4100: unreferenced formal parameter */
2909 #endif
2910
2911
2912 /*-*************************************
2913 * Macros
2914 ***************************************/
2915 #define ZSTDv07_isError ERR_isError /* for inlining */
2916 #define FSEv07_isError ERR_isError
2917 #define HUFv07_isError ERR_isError
2918
2919
2920 /*_*******************************************************
2921 * Memory operations
2922 **********************************************************/
ZSTDv07_copy4(void * dst,const void * src)2923 static void ZSTDv07_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2924
2925
2926 /*-*************************************************************
2927 * Context management
2928 ***************************************************************/
2929 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2930 ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
2931 ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTDv07_dStage;
2932
2933 struct ZSTDv07_DCtx_s
2934 {
2935 FSEv07_DTable LLTable[FSEv07_DTABLE_SIZE_U32(LLFSELog)];
2936 FSEv07_DTable OffTable[FSEv07_DTABLE_SIZE_U32(OffFSELog)];
2937 FSEv07_DTable MLTable[FSEv07_DTABLE_SIZE_U32(MLFSELog)];
2938 HUFv07_DTable hufTable[HUFv07_DTABLE_SIZE(HufLog)]; /* can accommodate HUFv07_decompress4X */
2939 const void* previousDstEnd;
2940 const void* base;
2941 const void* vBase;
2942 const void* dictEnd;
2943 size_t expected;
2944 U32 rep[3];
2945 ZSTDv07_frameParams fParams;
2946 blockType_t bType; /* used in ZSTDv07_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2947 ZSTDv07_dStage stage;
2948 U32 litEntropy;
2949 U32 fseEntropy;
2950 XXH64_state_t xxhState;
2951 size_t headerSize;
2952 U32 dictID;
2953 const BYTE* litPtr;
2954 ZSTDv07_customMem customMem;
2955 size_t litSize;
2956 BYTE litBuffer[ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + WILDCOPY_OVERLENGTH];
2957 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
2958 }; /* typedef'd to ZSTDv07_DCtx within "zstd_static.h" */
2959
2960 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx);
2961
ZSTDv07_sizeofDCtx(const ZSTDv07_DCtx * dctx)2962 size_t ZSTDv07_sizeofDCtx (const ZSTDv07_DCtx* dctx) { return sizeof(*dctx); }
2963
ZSTDv07_estimateDCtxSize(void)2964 size_t ZSTDv07_estimateDCtxSize(void) { return sizeof(ZSTDv07_DCtx); }
2965
ZSTDv07_decompressBegin(ZSTDv07_DCtx * dctx)2966 size_t ZSTDv07_decompressBegin(ZSTDv07_DCtx* dctx)
2967 {
2968 dctx->expected = ZSTDv07_frameHeaderSize_min;
2969 dctx->stage = ZSTDds_getFrameHeaderSize;
2970 dctx->previousDstEnd = NULL;
2971 dctx->base = NULL;
2972 dctx->vBase = NULL;
2973 dctx->dictEnd = NULL;
2974 dctx->hufTable[0] = (HUFv07_DTable)((HufLog)*0x1000001);
2975 dctx->litEntropy = dctx->fseEntropy = 0;
2976 dctx->dictID = 0;
2977 { int i; for (i=0; i<ZSTDv07_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; }
2978 return 0;
2979 }
2980
ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem)2981 ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem)
2982 {
2983 ZSTDv07_DCtx* dctx;
2984
2985 if (!customMem.customAlloc && !customMem.customFree)
2986 customMem = defaultCustomMem;
2987
2988 if (!customMem.customAlloc || !customMem.customFree)
2989 return NULL;
2990
2991 dctx = (ZSTDv07_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTDv07_DCtx));
2992 if (!dctx) return NULL;
2993 memcpy(&dctx->customMem, &customMem, sizeof(ZSTDv07_customMem));
2994 ZSTDv07_decompressBegin(dctx);
2995 return dctx;
2996 }
2997
ZSTDv07_createDCtx(void)2998 ZSTDv07_DCtx* ZSTDv07_createDCtx(void)
2999 {
3000 return ZSTDv07_createDCtx_advanced(defaultCustomMem);
3001 }
3002
ZSTDv07_freeDCtx(ZSTDv07_DCtx * dctx)3003 size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx* dctx)
3004 {
3005 if (dctx==NULL) return 0; /* support free on NULL */
3006 dctx->customMem.customFree(dctx->customMem.opaque, dctx);
3007 return 0; /* reserved as a potential error code in the future */
3008 }
3009
ZSTDv07_copyDCtx(ZSTDv07_DCtx * dstDCtx,const ZSTDv07_DCtx * srcDCtx)3010 void ZSTDv07_copyDCtx(ZSTDv07_DCtx* dstDCtx, const ZSTDv07_DCtx* srcDCtx)
3011 {
3012 memcpy(dstDCtx, srcDCtx,
3013 sizeof(ZSTDv07_DCtx) - (ZSTDv07_BLOCKSIZE_ABSOLUTEMAX+WILDCOPY_OVERLENGTH + ZSTDv07_frameHeaderSize_max)); /* no need to copy workspace */
3014 }
3015
3016
3017 /*-*************************************************************
3018 * Decompression section
3019 ***************************************************************/
3020
3021 /* Frame format description
3022 Frame Header - [ Block Header - Block ] - Frame End
3023 1) Frame Header
3024 - 4 bytes - Magic Number : ZSTDv07_MAGICNUMBER (defined within zstd.h)
3025 - 1 byte - Frame Descriptor
3026 2) Block Header
3027 - 3 bytes, starting with a 2-bits descriptor
3028 Uncompressed, Compressed, Frame End, unused
3029 3) Block
3030 See Block Format Description
3031 4) Frame End
3032 - 3 bytes, compatible with Block Header
3033 */
3034
3035
3036 /* Frame Header :
3037
3038 1 byte - FrameHeaderDescription :
3039 bit 0-1 : dictID (0, 1, 2 or 4 bytes)
3040 bit 2 : checksumFlag
3041 bit 3 : reserved (must be zero)
3042 bit 4 : reserved (unused, can be any value)
3043 bit 5 : Single Segment (if 1, WindowLog byte is not present)
3044 bit 6-7 : FrameContentFieldSize (0, 2, 4, or 8)
3045 if (SkippedWindowLog && !FrameContentFieldsize) FrameContentFieldsize=1;
3046
3047 Optional : WindowLog (0 or 1 byte)
3048 bit 0-2 : octal Fractional (1/8th)
3049 bit 3-7 : Power of 2, with 0 = 1 KB (up to 2 TB)
3050
3051 Optional : dictID (0, 1, 2 or 4 bytes)
3052 Automatic adaptation
3053 0 : no dictID
3054 1 : 1 - 255
3055 2 : 256 - 65535
3056 4 : all other values
3057
3058 Optional : content size (0, 1, 2, 4 or 8 bytes)
3059 0 : unknown (fcfs==0 and swl==0)
3060 1 : 0-255 bytes (fcfs==0 and swl==1)
3061 2 : 256 - 65535+256 (fcfs==1)
3062 4 : 0 - 4GB-1 (fcfs==2)
3063 8 : 0 - 16EB-1 (fcfs==3)
3064 */
3065
3066
3067 /* Compressed Block, format description
3068
3069 Block = Literal Section - Sequences Section
3070 Prerequisite : size of (compressed) block, maximum size of regenerated data
3071
3072 1) Literal Section
3073
3074 1.1) Header : 1-5 bytes
3075 flags: 2 bits
3076 00 compressed by Huff0
3077 01 unused
3078 10 is Raw (uncompressed)
3079 11 is Rle
3080 Note : using 01 => Huff0 with precomputed table ?
3081 Note : delta map ? => compressed ?
3082
3083 1.1.1) Huff0-compressed literal block : 3-5 bytes
3084 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3085 srcSize < 1 KB => 3 bytes (2-2-10-10)
3086 srcSize < 16KB => 4 bytes (2-2-14-14)
3087 else => 5 bytes (2-2-18-18)
3088 big endian convention
3089
3090 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
3091 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
3092 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
3093 size&255
3094 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
3095 size>>8&255
3096 size&255
3097
3098 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
3099 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
3100 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
3101 size&255
3102 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
3103 size>>8&255
3104 size&255
3105
3106 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
3107 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
3108 srcSize < 1 KB => 3 bytes (2-2-10-10)
3109 srcSize < 16KB => 4 bytes (2-2-14-14)
3110 else => 5 bytes (2-2-18-18)
3111 big endian convention
3112
3113 1- CTable available (stored into workspace ?)
3114 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
3115
3116
3117 1.2) Literal block content
3118
3119 1.2.1) Huff0 block, using sizes from header
3120 See Huff0 format
3121
3122 1.2.2) Huff0 block, using prepared table
3123
3124 1.2.3) Raw content
3125
3126 1.2.4) single byte
3127
3128
3129 2) Sequences section
3130 TO DO
3131 */
3132
3133 /** ZSTDv07_frameHeaderSize() :
3134 * srcSize must be >= ZSTDv07_frameHeaderSize_min.
3135 * @return : size of the Frame Header */
ZSTDv07_frameHeaderSize(const void * src,size_t srcSize)3136 static size_t ZSTDv07_frameHeaderSize(const void* src, size_t srcSize)
3137 {
3138 if (srcSize < ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);
3139 { BYTE const fhd = ((const BYTE*)src)[4];
3140 U32 const dictID= fhd & 3;
3141 U32 const directMode = (fhd >> 5) & 1;
3142 U32 const fcsId = fhd >> 6;
3143 return ZSTDv07_frameHeaderSize_min + !directMode + ZSTDv07_did_fieldSize[dictID] + ZSTDv07_fcs_fieldSize[fcsId]
3144 + (directMode && !ZSTDv07_fcs_fieldSize[fcsId]);
3145 }
3146 }
3147
3148
3149 /** ZSTDv07_getFrameParams() :
3150 * decode Frame Header, or require larger `srcSize`.
3151 * @return : 0, `fparamsPtr` is correctly filled,
3152 * >0, `srcSize` is too small, result is expected `srcSize`,
3153 * or an error code, which can be tested using ZSTDv07_isError() */
ZSTDv07_getFrameParams(ZSTDv07_frameParams * fparamsPtr,const void * src,size_t srcSize)3154 size_t ZSTDv07_getFrameParams(ZSTDv07_frameParams* fparamsPtr, const void* src, size_t srcSize)
3155 {
3156 const BYTE* ip = (const BYTE*)src;
3157
3158 if (srcSize < ZSTDv07_frameHeaderSize_min) return ZSTDv07_frameHeaderSize_min;
3159 memset(fparamsPtr, 0, sizeof(*fparamsPtr));
3160 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3161 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
3162 if (srcSize < ZSTDv07_skippableHeaderSize) return ZSTDv07_skippableHeaderSize; /* magic number + skippable frame length */
3163 fparamsPtr->frameContentSize = MEM_readLE32((const char *)src + 4);
3164 fparamsPtr->windowSize = 0; /* windowSize==0 means a frame is skippable */
3165 return 0;
3166 }
3167 return ERROR(prefix_unknown);
3168 }
3169
3170 /* ensure there is enough `srcSize` to fully read/decode frame header */
3171 { size_t const fhsize = ZSTDv07_frameHeaderSize(src, srcSize);
3172 if (srcSize < fhsize) return fhsize; }
3173
3174 { BYTE const fhdByte = ip[4];
3175 size_t pos = 5;
3176 U32 const dictIDSizeCode = fhdByte&3;
3177 U32 const checksumFlag = (fhdByte>>2)&1;
3178 U32 const directMode = (fhdByte>>5)&1;
3179 U32 const fcsID = fhdByte>>6;
3180 U32 const windowSizeMax = 1U << ZSTDv07_WINDOWLOG_MAX;
3181 U32 windowSize = 0;
3182 U32 dictID = 0;
3183 U64 frameContentSize = 0;
3184 if ((fhdByte & 0x08) != 0) /* reserved bits, which must be zero */
3185 return ERROR(frameParameter_unsupported);
3186 if (!directMode) {
3187 BYTE const wlByte = ip[pos++];
3188 U32 const windowLog = (wlByte >> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN;
3189 if (windowLog > ZSTDv07_WINDOWLOG_MAX)
3190 return ERROR(frameParameter_unsupported);
3191 windowSize = (1U << windowLog);
3192 windowSize += (windowSize >> 3) * (wlByte&7);
3193 }
3194
3195 switch(dictIDSizeCode)
3196 {
3197 default: /* impossible */
3198 case 0 : break;
3199 case 1 : dictID = ip[pos]; pos++; break;
3200 case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
3201 case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
3202 }
3203 switch(fcsID)
3204 {
3205 default: /* impossible */
3206 case 0 : if (directMode) frameContentSize = ip[pos]; break;
3207 case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
3208 case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
3209 case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
3210 }
3211 if (!windowSize) windowSize = (U32)frameContentSize;
3212 if (windowSize > windowSizeMax)
3213 return ERROR(frameParameter_unsupported);
3214 fparamsPtr->frameContentSize = frameContentSize;
3215 fparamsPtr->windowSize = windowSize;
3216 fparamsPtr->dictID = dictID;
3217 fparamsPtr->checksumFlag = checksumFlag;
3218 }
3219 return 0;
3220 }
3221
3222
3223 /** ZSTDv07_getDecompressedSize() :
3224 * compatible with legacy mode
3225 * @return : decompressed size if known, 0 otherwise
3226 note : 0 can mean any of the following :
3227 - decompressed size is not provided within frame header
3228 - frame header unknown / not supported
3229 - frame header not completely provided (`srcSize` too small) */
ZSTDv07_getDecompressedSize(const void * src,size_t srcSize)3230 unsigned long long ZSTDv07_getDecompressedSize(const void* src, size_t srcSize)
3231 {
3232 ZSTDv07_frameParams fparams;
3233 size_t const frResult = ZSTDv07_getFrameParams(&fparams, src, srcSize);
3234 if (frResult!=0) return 0;
3235 return fparams.frameContentSize;
3236 }
3237
3238
3239 /** ZSTDv07_decodeFrameHeader() :
3240 * `srcSize` must be the size provided by ZSTDv07_frameHeaderSize().
3241 * @return : 0 if success, or an error code, which can be tested using ZSTDv07_isError() */
ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx * dctx,const void * src,size_t srcSize)3242 static size_t ZSTDv07_decodeFrameHeader(ZSTDv07_DCtx* dctx, const void* src, size_t srcSize)
3243 {
3244 size_t const result = ZSTDv07_getFrameParams(&(dctx->fParams), src, srcSize);
3245 if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
3246 if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
3247 return result;
3248 }
3249
3250
3251 typedef struct
3252 {
3253 blockType_t blockType;
3254 U32 origSize;
3255 } blockProperties_t;
3256
3257 /*! ZSTDv07_getcBlockSize() :
3258 * Provides the size of compressed block from block header `src` */
ZSTDv07_getcBlockSize(const void * src,size_t srcSize,blockProperties_t * bpPtr)3259 static size_t ZSTDv07_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
3260 {
3261 const BYTE* const in = (const BYTE* const)src;
3262 U32 cSize;
3263
3264 if (srcSize < ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3265
3266 bpPtr->blockType = (blockType_t)((*in) >> 6);
3267 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
3268 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
3269
3270 if (bpPtr->blockType == bt_end) return 0;
3271 if (bpPtr->blockType == bt_rle) return 1;
3272 return cSize;
3273 }
3274
3275
ZSTDv07_copyRawBlock(void * dst,size_t dstCapacity,const void * src,size_t srcSize)3276 static size_t ZSTDv07_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3277 {
3278 if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
3279 if (srcSize > 0) {
3280 memcpy(dst, src, srcSize);
3281 }
3282 return srcSize;
3283 }
3284
3285
3286 /*! ZSTDv07_decodeLiteralsBlock() :
3287 @return : nb of bytes read from src (< srcSize ) */
ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx * dctx,const void * src,size_t srcSize)3288 static size_t ZSTDv07_decodeLiteralsBlock(ZSTDv07_DCtx* dctx,
3289 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
3290 {
3291 const BYTE* const istart = (const BYTE*) src;
3292
3293 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3294
3295 switch((litBlockType_t)(istart[0]>> 6))
3296 {
3297 case lbt_huffman:
3298 { size_t litSize, litCSize, singleStream=0;
3299 U32 lhSize = (istart[0] >> 4) & 3;
3300 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3301 switch(lhSize)
3302 {
3303 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3304 /* 2 - 2 - 10 - 10 */
3305 lhSize=3;
3306 singleStream = istart[0] & 16;
3307 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3308 litCSize = ((istart[1] & 3) << 8) + istart[2];
3309 break;
3310 case 2:
3311 /* 2 - 2 - 14 - 14 */
3312 lhSize=4;
3313 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3314 litCSize = ((istart[2] & 63) << 8) + istart[3];
3315 break;
3316 case 3:
3317 /* 2 - 2 - 18 - 18 */
3318 lhSize=5;
3319 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3320 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
3321 break;
3322 }
3323 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3324 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3325
3326 if (HUFv07_isError(singleStream ?
3327 HUFv07_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3328 HUFv07_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3329 return ERROR(corruption_detected);
3330
3331 dctx->litPtr = dctx->litBuffer;
3332 dctx->litSize = litSize;
3333 dctx->litEntropy = 1;
3334 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3335 return litCSize + lhSize;
3336 }
3337 case lbt_repeat:
3338 { size_t litSize, litCSize;
3339 U32 lhSize = ((istart[0]) >> 4) & 3;
3340 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
3341 return ERROR(corruption_detected);
3342 if (dctx->litEntropy==0)
3343 return ERROR(dictionary_corrupted);
3344
3345 /* 2 - 2 - 10 - 10 */
3346 lhSize=3;
3347 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3348 litCSize = ((istart[1] & 3) << 8) + istart[2];
3349 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3350
3351 { size_t const errorCode = HUFv07_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTable);
3352 if (HUFv07_isError(errorCode)) return ERROR(corruption_detected);
3353 }
3354 dctx->litPtr = dctx->litBuffer;
3355 dctx->litSize = litSize;
3356 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3357 return litCSize + lhSize;
3358 }
3359 case lbt_raw:
3360 { size_t litSize;
3361 U32 lhSize = ((istart[0]) >> 4) & 3;
3362 switch(lhSize)
3363 {
3364 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3365 lhSize=1;
3366 litSize = istart[0] & 31;
3367 break;
3368 case 2:
3369 litSize = ((istart[0] & 15) << 8) + istart[1];
3370 break;
3371 case 3:
3372 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3373 break;
3374 }
3375
3376 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
3377 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3378 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3379 dctx->litPtr = dctx->litBuffer;
3380 dctx->litSize = litSize;
3381 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3382 return lhSize+litSize;
3383 }
3384 /* direct reference into compressed stream */
3385 dctx->litPtr = istart+lhSize;
3386 dctx->litSize = litSize;
3387 return lhSize+litSize;
3388 }
3389 case lbt_rle:
3390 { size_t litSize;
3391 U32 lhSize = ((istart[0]) >> 4) & 3;
3392 switch(lhSize)
3393 {
3394 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
3395 lhSize = 1;
3396 litSize = istart[0] & 31;
3397 break;
3398 case 2:
3399 litSize = ((istart[0] & 15) << 8) + istart[1];
3400 break;
3401 case 3:
3402 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3403 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3404 break;
3405 }
3406 if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3407 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3408 dctx->litPtr = dctx->litBuffer;
3409 dctx->litSize = litSize;
3410 return lhSize+1;
3411 }
3412 default:
3413 return ERROR(corruption_detected); /* impossible */
3414 }
3415 }
3416
3417
3418 /*! ZSTDv07_buildSeqTable() :
3419 @return : nb bytes read from src,
3420 or an error code if it fails, testable with ZSTDv07_isError()
3421 */
ZSTDv07_buildSeqTable(FSEv07_DTable * DTable,U32 type,U32 max,U32 maxLog,const void * src,size_t srcSize,const S16 * defaultNorm,U32 defaultLog,U32 flagRepeatTable)3422 static size_t ZSTDv07_buildSeqTable(FSEv07_DTable* DTable, U32 type, U32 max, U32 maxLog,
3423 const void* src, size_t srcSize,
3424 const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3425 {
3426 switch(type)
3427 {
3428 case FSEv07_ENCODING_RLE :
3429 if (!srcSize) return ERROR(srcSize_wrong);
3430 if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3431 FSEv07_buildDTable_rle(DTable, *(const BYTE*)src); /* if *src > max, data is corrupted */
3432 return 1;
3433 case FSEv07_ENCODING_RAW :
3434 FSEv07_buildDTable(DTable, defaultNorm, max, defaultLog);
3435 return 0;
3436 case FSEv07_ENCODING_STATIC:
3437 if (!flagRepeatTable) return ERROR(corruption_detected);
3438 return 0;
3439 default : /* impossible */
3440 case FSEv07_ENCODING_DYNAMIC :
3441 { U32 tableLog;
3442 S16 norm[MaxSeq+1];
3443 size_t const headerSize = FSEv07_readNCount(norm, &max, &tableLog, src, srcSize);
3444 if (FSEv07_isError(headerSize)) return ERROR(corruption_detected);
3445 if (tableLog > maxLog) return ERROR(corruption_detected);
3446 FSEv07_buildDTable(DTable, norm, max, tableLog);
3447 return headerSize;
3448 } }
3449 }
3450
3451
ZSTDv07_decodeSeqHeaders(int * nbSeqPtr,FSEv07_DTable * DTableLL,FSEv07_DTable * DTableML,FSEv07_DTable * DTableOffb,U32 flagRepeatTable,const void * src,size_t srcSize)3452 static size_t ZSTDv07_decodeSeqHeaders(int* nbSeqPtr,
3453 FSEv07_DTable* DTableLL, FSEv07_DTable* DTableML, FSEv07_DTable* DTableOffb, U32 flagRepeatTable,
3454 const void* src, size_t srcSize)
3455 {
3456 const BYTE* const istart = (const BYTE* const)src;
3457 const BYTE* const iend = istart + srcSize;
3458 const BYTE* ip = istart;
3459
3460 /* check */
3461 if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3462
3463 /* SeqHead */
3464 { int nbSeq = *ip++;
3465 if (!nbSeq) { *nbSeqPtr=0; return 1; }
3466 if (nbSeq > 0x7F) {
3467 if (nbSeq == 0xFF) {
3468 if (ip+2 > iend) return ERROR(srcSize_wrong);
3469 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3470 } else {
3471 if (ip >= iend) return ERROR(srcSize_wrong);
3472 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3473 }
3474 }
3475 *nbSeqPtr = nbSeq;
3476 }
3477
3478 /* FSE table descriptors */
3479 if (ip + 4 > iend) return ERROR(srcSize_wrong); /* min : header byte + all 3 are "raw", hence no header, but at least xxLog bits per type */
3480 { U32 const LLtype = *ip >> 6;
3481 U32 const OFtype = (*ip >> 4) & 3;
3482 U32 const MLtype = (*ip >> 2) & 3;
3483 ip++;
3484
3485 /* Build DTables */
3486 { size_t const llhSize = ZSTDv07_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3487 if (ZSTDv07_isError(llhSize)) return ERROR(corruption_detected);
3488 ip += llhSize;
3489 }
3490 { size_t const ofhSize = ZSTDv07_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3491 if (ZSTDv07_isError(ofhSize)) return ERROR(corruption_detected);
3492 ip += ofhSize;
3493 }
3494 { size_t const mlhSize = ZSTDv07_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3495 if (ZSTDv07_isError(mlhSize)) return ERROR(corruption_detected);
3496 ip += mlhSize;
3497 } }
3498
3499 return ip-istart;
3500 }
3501
3502
3503 typedef struct {
3504 size_t litLength;
3505 size_t matchLength;
3506 size_t offset;
3507 } seq_t;
3508
3509 typedef struct {
3510 BITv07_DStream_t DStream;
3511 FSEv07_DState_t stateLL;
3512 FSEv07_DState_t stateOffb;
3513 FSEv07_DState_t stateML;
3514 size_t prevOffset[ZSTDv07_REP_INIT];
3515 } seqState_t;
3516
3517
ZSTDv07_decodeSequence(seqState_t * seqState)3518 static seq_t ZSTDv07_decodeSequence(seqState_t* seqState)
3519 {
3520 seq_t seq;
3521
3522 U32 const llCode = FSEv07_peekSymbol(&(seqState->stateLL));
3523 U32 const mlCode = FSEv07_peekSymbol(&(seqState->stateML));
3524 U32 const ofCode = FSEv07_peekSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3525
3526 U32 const llBits = LL_bits[llCode];
3527 U32 const mlBits = ML_bits[mlCode];
3528 U32 const ofBits = ofCode;
3529 U32 const totalBits = llBits+mlBits+ofBits;
3530
3531 static const U32 LL_base[MaxLL+1] = {
3532 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
3533 16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3534 0x2000, 0x4000, 0x8000, 0x10000 };
3535
3536 static const U32 ML_base[MaxML+1] = {
3537 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
3538 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
3539 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3540 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3541
3542 static const U32 OF_base[MaxOff+1] = {
3543 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
3544 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
3545 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3546 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3547
3548 /* sequence */
3549 { size_t offset;
3550 if (!ofCode)
3551 offset = 0;
3552 else {
3553 offset = OF_base[ofCode] + BITv07_readBits(&(seqState->DStream), ofBits); /* <= (ZSTDv07_WINDOWLOG_MAX-1) bits */
3554 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));
3555 }
3556
3557 if (ofCode <= 1) {
3558 if ((llCode == 0) & (offset <= 1)) offset = 1-offset;
3559 if (offset) {
3560 size_t const temp = seqState->prevOffset[offset];
3561 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
3562 seqState->prevOffset[1] = seqState->prevOffset[0];
3563 seqState->prevOffset[0] = offset = temp;
3564 } else {
3565 offset = seqState->prevOffset[0];
3566 }
3567 } else {
3568 seqState->prevOffset[2] = seqState->prevOffset[1];
3569 seqState->prevOffset[1] = seqState->prevOffset[0];
3570 seqState->prevOffset[0] = offset;
3571 }
3572 seq.offset = offset;
3573 }
3574
3575 seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BITv07_readBits(&(seqState->DStream), mlBits) : 0); /* <= 16 bits */
3576 if (MEM_32bits() && (mlBits+llBits>24)) BITv07_reloadDStream(&(seqState->DStream));
3577
3578 seq.litLength = LL_base[llCode] + ((llCode>15) ? BITv07_readBits(&(seqState->DStream), llBits) : 0); /* <= 16 bits */
3579 if (MEM_32bits() ||
3580 (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv07_reloadDStream(&(seqState->DStream));
3581
3582 /* ANS state update */
3583 FSEv07_updateState(&(seqState->stateLL), &(seqState->DStream)); /* <= 9 bits */
3584 FSEv07_updateState(&(seqState->stateML), &(seqState->DStream)); /* <= 9 bits */
3585 if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream)); /* <= 18 bits */
3586 FSEv07_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <= 8 bits */
3587
3588 return seq;
3589 }
3590
3591
3592 static
ZSTDv07_execSequence(BYTE * op,BYTE * const oend,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const base,const BYTE * const vBase,const BYTE * const dictEnd)3593 size_t ZSTDv07_execSequence(BYTE* op,
3594 BYTE* const oend, seq_t sequence,
3595 const BYTE** litPtr, const BYTE* const litLimit,
3596 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3597 {
3598 BYTE* const oLitEnd = op + sequence.litLength;
3599 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3600 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3601 BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH;
3602 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3603 const BYTE* match = oLitEnd - sequence.offset;
3604
3605 /* check */
3606 if ((oLitEnd>oend_w) | (oMatchEnd>oend)) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
3607 if (iLitEnd > litLimit) return ERROR(corruption_detected); /* over-read beyond lit buffer */
3608
3609 /* copy Literals */
3610 ZSTDv07_wildcopy(op, *litPtr, sequence.litLength); /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3611 op = oLitEnd;
3612 *litPtr = iLitEnd; /* update for next sequence */
3613
3614 /* copy Match */
3615 if (sequence.offset > (size_t)(oLitEnd - base)) {
3616 /* offset beyond prefix */
3617 if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3618 match = dictEnd - (base-match);
3619 if (match + sequence.matchLength <= dictEnd) {
3620 memmove(oLitEnd, match, sequence.matchLength);
3621 return sequenceLength;
3622 }
3623 /* span extDict & currentPrefixSegment */
3624 { size_t const length1 = dictEnd - match;
3625 memmove(oLitEnd, match, length1);
3626 op = oLitEnd + length1;
3627 sequence.matchLength -= length1;
3628 match = base;
3629 if (op > oend_w || sequence.matchLength < MINMATCH) {
3630 while (op < oMatchEnd) *op++ = *match++;
3631 return sequenceLength;
3632 }
3633 } }
3634 /* Requirement: op <= oend_w */
3635
3636 /* match within prefix */
3637 if (sequence.offset < 8) {
3638 /* close range match, overlap */
3639 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3640 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
3641 int const sub2 = dec64table[sequence.offset];
3642 op[0] = match[0];
3643 op[1] = match[1];
3644 op[2] = match[2];
3645 op[3] = match[3];
3646 match += dec32table[sequence.offset];
3647 ZSTDv07_copy4(op+4, match);
3648 match -= sub2;
3649 } else {
3650 ZSTDv07_copy8(op, match);
3651 }
3652 op += 8; match += 8;
3653
3654 if (oMatchEnd > oend-(16-MINMATCH)) {
3655 if (op < oend_w) {
3656 ZSTDv07_wildcopy(op, match, oend_w - op);
3657 match += oend_w - op;
3658 op = oend_w;
3659 }
3660 while (op < oMatchEnd) *op++ = *match++;
3661 } else {
3662 ZSTDv07_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3663 }
3664 return sequenceLength;
3665 }
3666
3667
ZSTDv07_decompressSequences(ZSTDv07_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize)3668 static size_t ZSTDv07_decompressSequences(
3669 ZSTDv07_DCtx* dctx,
3670 void* dst, size_t maxDstSize,
3671 const void* seqStart, size_t seqSize)
3672 {
3673 const BYTE* ip = (const BYTE*)seqStart;
3674 const BYTE* const iend = ip + seqSize;
3675 BYTE* const ostart = (BYTE* const)dst;
3676 BYTE* const oend = ostart + maxDstSize;
3677 BYTE* op = ostart;
3678 const BYTE* litPtr = dctx->litPtr;
3679 const BYTE* const litEnd = litPtr + dctx->litSize;
3680 FSEv07_DTable* DTableLL = dctx->LLTable;
3681 FSEv07_DTable* DTableML = dctx->MLTable;
3682 FSEv07_DTable* DTableOffb = dctx->OffTable;
3683 const BYTE* const base = (const BYTE*) (dctx->base);
3684 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3685 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3686 int nbSeq;
3687
3688 /* Build Decoding Tables */
3689 { size_t const seqHSize = ZSTDv07_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize);
3690 if (ZSTDv07_isError(seqHSize)) return seqHSize;
3691 ip += seqHSize;
3692 }
3693
3694 /* Regen sequences */
3695 if (nbSeq) {
3696 seqState_t seqState;
3697 dctx->fseEntropy = 1;
3698 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; }
3699 { size_t const errorCode = BITv07_initDStream(&(seqState.DStream), ip, iend-ip);
3700 if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3701 FSEv07_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3702 FSEv07_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3703 FSEv07_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3704
3705 for ( ; (BITv07_reloadDStream(&(seqState.DStream)) <= BITv07_DStream_completed) && nbSeq ; ) {
3706 nbSeq--;
3707 { seq_t const sequence = ZSTDv07_decodeSequence(&seqState);
3708 size_t const oneSeqSize = ZSTDv07_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3709 if (ZSTDv07_isError(oneSeqSize)) return oneSeqSize;
3710 op += oneSeqSize;
3711 } }
3712
3713 /* check if reached exact end */
3714 if (nbSeq) return ERROR(corruption_detected);
3715 /* save reps for next block */
3716 { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
3717 }
3718
3719 /* last literal segment */
3720 { size_t const lastLLSize = litEnd - litPtr;
3721 /* if (litPtr > litEnd) return ERROR(corruption_detected); */ /* too many literals already used */
3722 if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
3723 if (lastLLSize > 0) {
3724 memcpy(op, litPtr, lastLLSize);
3725 op += lastLLSize;
3726 }
3727 }
3728
3729 return op-ostart;
3730 }
3731
3732
ZSTDv07_checkContinuity(ZSTDv07_DCtx * dctx,const void * dst)3733 static void ZSTDv07_checkContinuity(ZSTDv07_DCtx* dctx, const void* dst)
3734 {
3735 if (dst != dctx->previousDstEnd) { /* not contiguous */
3736 dctx->dictEnd = dctx->previousDstEnd;
3737 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3738 dctx->base = dst;
3739 dctx->previousDstEnd = dst;
3740 }
3741 }
3742
3743
ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)3744 static size_t ZSTDv07_decompressBlock_internal(ZSTDv07_DCtx* dctx,
3745 void* dst, size_t dstCapacity,
3746 const void* src, size_t srcSize)
3747 { /* blockType == blockCompressed */
3748 const BYTE* ip = (const BYTE*)src;
3749
3750 if (srcSize >= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong);
3751
3752 /* Decode literals sub-block */
3753 { size_t const litCSize = ZSTDv07_decodeLiteralsBlock(dctx, src, srcSize);
3754 if (ZSTDv07_isError(litCSize)) return litCSize;
3755 ip += litCSize;
3756 srcSize -= litCSize;
3757 }
3758 return ZSTDv07_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3759 }
3760
3761
ZSTDv07_decompressBlock(ZSTDv07_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)3762 size_t ZSTDv07_decompressBlock(ZSTDv07_DCtx* dctx,
3763 void* dst, size_t dstCapacity,
3764 const void* src, size_t srcSize)
3765 {
3766 size_t dSize;
3767 ZSTDv07_checkContinuity(dctx, dst);
3768 dSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3769 dctx->previousDstEnd = (char*)dst + dSize;
3770 return dSize;
3771 }
3772
3773
3774 /** ZSTDv07_insertBlock() :
3775 insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
ZSTDv07_insertBlock(ZSTDv07_DCtx * dctx,const void * blockStart,size_t blockSize)3776 ZSTDLIBv07_API size_t ZSTDv07_insertBlock(ZSTDv07_DCtx* dctx, const void* blockStart, size_t blockSize)
3777 {
3778 ZSTDv07_checkContinuity(dctx, blockStart);
3779 dctx->previousDstEnd = (const char*)blockStart + blockSize;
3780 return blockSize;
3781 }
3782
3783
ZSTDv07_generateNxBytes(void * dst,size_t dstCapacity,BYTE byte,size_t length)3784 static size_t ZSTDv07_generateNxBytes(void* dst, size_t dstCapacity, BYTE byte, size_t length)
3785 {
3786 if (length > dstCapacity) return ERROR(dstSize_tooSmall);
3787 if (length > 0) {
3788 memset(dst, byte, length);
3789 }
3790 return length;
3791 }
3792
3793
3794 /*! ZSTDv07_decompressFrame() :
3795 * `dctx` must be properly initialized */
ZSTDv07_decompressFrame(ZSTDv07_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)3796 static size_t ZSTDv07_decompressFrame(ZSTDv07_DCtx* dctx,
3797 void* dst, size_t dstCapacity,
3798 const void* src, size_t srcSize)
3799 {
3800 const BYTE* ip = (const BYTE*)src;
3801 const BYTE* const iend = ip + srcSize;
3802 BYTE* const ostart = (BYTE* const)dst;
3803 BYTE* const oend = ostart + dstCapacity;
3804 BYTE* op = ostart;
3805 size_t remainingSize = srcSize;
3806
3807 /* check */
3808 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3809
3810 /* Frame Header */
3811 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3812 if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3813 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3814 if (ZSTDv07_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3815 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3816 }
3817
3818 /* Loop on each block */
3819 while (1) {
3820 size_t decodedSize;
3821 blockProperties_t blockProperties;
3822 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, iend-ip, &blockProperties);
3823 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3824
3825 ip += ZSTDv07_blockHeaderSize;
3826 remainingSize -= ZSTDv07_blockHeaderSize;
3827 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3828
3829 switch(blockProperties.blockType)
3830 {
3831 case bt_compressed:
3832 decodedSize = ZSTDv07_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3833 break;
3834 case bt_raw :
3835 decodedSize = ZSTDv07_copyRawBlock(op, oend-op, ip, cBlockSize);
3836 break;
3837 case bt_rle :
3838 decodedSize = ZSTDv07_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
3839 break;
3840 case bt_end :
3841 /* end of frame */
3842 if (remainingSize) return ERROR(srcSize_wrong);
3843 decodedSize = 0;
3844 break;
3845 default:
3846 return ERROR(GENERIC); /* impossible */
3847 }
3848 if (blockProperties.blockType == bt_end) break; /* bt_end */
3849
3850 if (ZSTDv07_isError(decodedSize)) return decodedSize;
3851 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
3852 op += decodedSize;
3853 ip += cBlockSize;
3854 remainingSize -= cBlockSize;
3855 }
3856
3857 return op-ostart;
3858 }
3859
3860
3861 /*! ZSTDv07_decompress_usingPreparedDCtx() :
3862 * Same as ZSTDv07_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
3863 * It avoids reloading the dictionary each time.
3864 * `preparedDCtx` must have been properly initialized using ZSTDv07_decompressBegin_usingDict().
3865 * Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx * dctx,const ZSTDv07_DCtx * refDCtx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)3866 static size_t ZSTDv07_decompress_usingPreparedDCtx(ZSTDv07_DCtx* dctx, const ZSTDv07_DCtx* refDCtx,
3867 void* dst, size_t dstCapacity,
3868 const void* src, size_t srcSize)
3869 {
3870 ZSTDv07_copyDCtx(dctx, refDCtx);
3871 ZSTDv07_checkContinuity(dctx, dst);
3872 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3873 }
3874
3875
ZSTDv07_decompress_usingDict(ZSTDv07_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const void * dict,size_t dictSize)3876 size_t ZSTDv07_decompress_usingDict(ZSTDv07_DCtx* dctx,
3877 void* dst, size_t dstCapacity,
3878 const void* src, size_t srcSize,
3879 const void* dict, size_t dictSize)
3880 {
3881 ZSTDv07_decompressBegin_usingDict(dctx, dict, dictSize);
3882 ZSTDv07_checkContinuity(dctx, dst);
3883 return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3884 }
3885
3886
ZSTDv07_decompressDCtx(ZSTDv07_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)3887 size_t ZSTDv07_decompressDCtx(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3888 {
3889 return ZSTDv07_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3890 }
3891
3892
ZSTDv07_decompress(void * dst,size_t dstCapacity,const void * src,size_t srcSize)3893 size_t ZSTDv07_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3894 {
3895 #if defined(ZSTDv07_HEAPMODE) && (ZSTDv07_HEAPMODE==1)
3896 size_t regenSize;
3897 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx();
3898 if (dctx==NULL) return ERROR(memory_allocation);
3899 regenSize = ZSTDv07_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3900 ZSTDv07_freeDCtx(dctx);
3901 return regenSize;
3902 #else /* stack mode */
3903 ZSTDv07_DCtx dctx;
3904 return ZSTDv07_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3905 #endif
3906 }
3907
3908 /* ZSTD_errorFrameSizeInfoLegacy() :
3909 assumes `cSize` and `dBound` are _not_ NULL */
ZSTD_errorFrameSizeInfoLegacy(size_t * cSize,unsigned long long * dBound,size_t ret)3910 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3911 {
3912 *cSize = ret;
3913 *dBound = ZSTD_CONTENTSIZE_ERROR;
3914 }
3915
ZSTDv07_findFrameSizeInfoLegacy(const void * src,size_t srcSize,size_t * cSize,unsigned long long * dBound)3916 void ZSTDv07_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3917 {
3918 const BYTE* ip = (const BYTE*)src;
3919 size_t remainingSize = srcSize;
3920 size_t nbBlocks = 0;
3921
3922 /* check */
3923 if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) {
3924 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3925 return;
3926 }
3927
3928 /* Frame Header */
3929 { size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, srcSize);
3930 if (ZSTDv07_isError(frameHeaderSize)) {
3931 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize);
3932 return;
3933 }
3934 if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3935 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3936 return;
3937 }
3938 if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) {
3939 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3940 return;
3941 }
3942 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3943 }
3944
3945 /* Loop on each block */
3946 while (1) {
3947 blockProperties_t blockProperties;
3948 size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, remainingSize, &blockProperties);
3949 if (ZSTDv07_isError(cBlockSize)) {
3950 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3951 return;
3952 }
3953
3954 ip += ZSTDv07_blockHeaderSize;
3955 remainingSize -= ZSTDv07_blockHeaderSize;
3956
3957 if (blockProperties.blockType == bt_end) break;
3958
3959 if (cBlockSize > remainingSize) {
3960 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3961 return;
3962 }
3963
3964 ip += cBlockSize;
3965 remainingSize -= cBlockSize;
3966 nbBlocks++;
3967 }
3968
3969 *cSize = ip - (const BYTE*)src;
3970 *dBound = nbBlocks * ZSTDv07_BLOCKSIZE_ABSOLUTEMAX;
3971 }
3972
3973 /*_******************************
3974 * Streaming Decompression API
3975 ********************************/
ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx * dctx)3976 size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx)
3977 {
3978 return dctx->expected;
3979 }
3980
ZSTDv07_isSkipFrame(ZSTDv07_DCtx * dctx)3981 int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx)
3982 {
3983 return dctx->stage == ZSTDds_skipFrame;
3984 }
3985
3986 /** ZSTDv07_decompressContinue() :
3987 * @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
3988 * or an error code, which can be tested using ZSTDv07_isError() */
ZSTDv07_decompressContinue(ZSTDv07_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)3989 size_t ZSTDv07_decompressContinue(ZSTDv07_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3990 {
3991 /* Sanity check */
3992 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3993 if (dstCapacity) ZSTDv07_checkContinuity(dctx, dst);
3994
3995 switch (dctx->stage)
3996 {
3997 case ZSTDds_getFrameHeaderSize :
3998 if (srcSize != ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3999 if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTDv07_MAGIC_SKIPPABLE_START) {
4000 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
4001 dctx->expected = ZSTDv07_skippableHeaderSize - ZSTDv07_frameHeaderSize_min; /* magic number + skippable frame length */
4002 dctx->stage = ZSTDds_decodeSkippableHeader;
4003 return 0;
4004 }
4005 dctx->headerSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
4006 if (ZSTDv07_isError(dctx->headerSize)) return dctx->headerSize;
4007 memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
4008 if (dctx->headerSize > ZSTDv07_frameHeaderSize_min) {
4009 dctx->expected = dctx->headerSize - ZSTDv07_frameHeaderSize_min;
4010 dctx->stage = ZSTDds_decodeFrameHeader;
4011 return 0;
4012 }
4013 dctx->expected = 0; /* not necessary to copy more */
4014 /* fall-through */
4015 case ZSTDds_decodeFrameHeader:
4016 { size_t result;
4017 memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
4018 result = ZSTDv07_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
4019 if (ZSTDv07_isError(result)) return result;
4020 dctx->expected = ZSTDv07_blockHeaderSize;
4021 dctx->stage = ZSTDds_decodeBlockHeader;
4022 return 0;
4023 }
4024 case ZSTDds_decodeBlockHeader:
4025 { blockProperties_t bp;
4026 size_t const cBlockSize = ZSTDv07_getcBlockSize(src, ZSTDv07_blockHeaderSize, &bp);
4027 if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
4028 if (bp.blockType == bt_end) {
4029 if (dctx->fParams.checksumFlag) {
4030 U64 const h64 = XXH64_digest(&dctx->xxhState);
4031 U32 const h32 = (U32)(h64>>11) & ((1<<22)-1);
4032 const BYTE* const ip = (const BYTE*)src;
4033 U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16);
4034 if (check32 != h32) return ERROR(checksum_wrong);
4035 }
4036 dctx->expected = 0;
4037 dctx->stage = ZSTDds_getFrameHeaderSize;
4038 } else {
4039 dctx->expected = cBlockSize;
4040 dctx->bType = bp.blockType;
4041 dctx->stage = ZSTDds_decompressBlock;
4042 }
4043 return 0;
4044 }
4045 case ZSTDds_decompressBlock:
4046 { size_t rSize;
4047 switch(dctx->bType)
4048 {
4049 case bt_compressed:
4050 rSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
4051 break;
4052 case bt_raw :
4053 rSize = ZSTDv07_copyRawBlock(dst, dstCapacity, src, srcSize);
4054 break;
4055 case bt_rle :
4056 return ERROR(GENERIC); /* not yet handled */
4057 break;
4058 case bt_end : /* should never happen (filtered at phase 1) */
4059 rSize = 0;
4060 break;
4061 default:
4062 return ERROR(GENERIC); /* impossible */
4063 }
4064 dctx->stage = ZSTDds_decodeBlockHeader;
4065 dctx->expected = ZSTDv07_blockHeaderSize;
4066 dctx->previousDstEnd = (char*)dst + rSize;
4067 if (ZSTDv07_isError(rSize)) return rSize;
4068 if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
4069 return rSize;
4070 }
4071 case ZSTDds_decodeSkippableHeader:
4072 { memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
4073 dctx->expected = MEM_readLE32(dctx->headerBuffer + 4);
4074 dctx->stage = ZSTDds_skipFrame;
4075 return 0;
4076 }
4077 case ZSTDds_skipFrame:
4078 { dctx->expected = 0;
4079 dctx->stage = ZSTDds_getFrameHeaderSize;
4080 return 0;
4081 }
4082 default:
4083 return ERROR(GENERIC); /* impossible */
4084 }
4085 }
4086
4087
ZSTDv07_refDictContent(ZSTDv07_DCtx * dctx,const void * dict,size_t dictSize)4088 static size_t ZSTDv07_refDictContent(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4089 {
4090 dctx->dictEnd = dctx->previousDstEnd;
4091 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
4092 dctx->base = dict;
4093 dctx->previousDstEnd = (const char*)dict + dictSize;
4094 return 0;
4095 }
4096
ZSTDv07_loadEntropy(ZSTDv07_DCtx * dctx,const void * const dict,size_t const dictSize)4097 static size_t ZSTDv07_loadEntropy(ZSTDv07_DCtx* dctx, const void* const dict, size_t const dictSize)
4098 {
4099 const BYTE* dictPtr = (const BYTE*)dict;
4100 const BYTE* const dictEnd = dictPtr + dictSize;
4101
4102 { size_t const hSize = HUFv07_readDTableX4(dctx->hufTable, dict, dictSize);
4103 if (HUFv07_isError(hSize)) return ERROR(dictionary_corrupted);
4104 dictPtr += hSize;
4105 }
4106
4107 { short offcodeNCount[MaxOff+1];
4108 U32 offcodeMaxValue=MaxOff, offcodeLog;
4109 size_t const offcodeHeaderSize = FSEv07_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
4110 if (FSEv07_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
4111 if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
4112 { size_t const errorCode = FSEv07_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
4113 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4114 dictPtr += offcodeHeaderSize;
4115 }
4116
4117 { short matchlengthNCount[MaxML+1];
4118 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
4119 size_t const matchlengthHeaderSize = FSEv07_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
4120 if (FSEv07_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
4121 if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
4122 { size_t const errorCode = FSEv07_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
4123 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4124 dictPtr += matchlengthHeaderSize;
4125 }
4126
4127 { short litlengthNCount[MaxLL+1];
4128 unsigned litlengthMaxValue = MaxLL, litlengthLog;
4129 size_t const litlengthHeaderSize = FSEv07_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
4130 if (FSEv07_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
4131 if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
4132 { size_t const errorCode = FSEv07_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
4133 if (FSEv07_isError(errorCode)) return ERROR(dictionary_corrupted); }
4134 dictPtr += litlengthHeaderSize;
4135 }
4136
4137 if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
4138 dctx->rep[0] = MEM_readLE32(dictPtr+0); if (dctx->rep[0] == 0 || dctx->rep[0] >= dictSize) return ERROR(dictionary_corrupted);
4139 dctx->rep[1] = MEM_readLE32(dictPtr+4); if (dctx->rep[1] == 0 || dctx->rep[1] >= dictSize) return ERROR(dictionary_corrupted);
4140 dctx->rep[2] = MEM_readLE32(dictPtr+8); if (dctx->rep[2] == 0 || dctx->rep[2] >= dictSize) return ERROR(dictionary_corrupted);
4141 dictPtr += 12;
4142
4143 dctx->litEntropy = dctx->fseEntropy = 1;
4144 return dictPtr - (const BYTE*)dict;
4145 }
4146
ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx * dctx,const void * dict,size_t dictSize)4147 static size_t ZSTDv07_decompress_insertDictionary(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4148 {
4149 if (dictSize < 8) return ZSTDv07_refDictContent(dctx, dict, dictSize);
4150 { U32 const magic = MEM_readLE32(dict);
4151 if (magic != ZSTDv07_DICT_MAGIC) {
4152 return ZSTDv07_refDictContent(dctx, dict, dictSize); /* pure content mode */
4153 } }
4154 dctx->dictID = MEM_readLE32((const char*)dict + 4);
4155
4156 /* load entropy tables */
4157 dict = (const char*)dict + 8;
4158 dictSize -= 8;
4159 { size_t const eSize = ZSTDv07_loadEntropy(dctx, dict, dictSize);
4160 if (ZSTDv07_isError(eSize)) return ERROR(dictionary_corrupted);
4161 dict = (const char*)dict + eSize;
4162 dictSize -= eSize;
4163 }
4164
4165 /* reference dictionary content */
4166 return ZSTDv07_refDictContent(dctx, dict, dictSize);
4167 }
4168
4169
ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx * dctx,const void * dict,size_t dictSize)4170 size_t ZSTDv07_decompressBegin_usingDict(ZSTDv07_DCtx* dctx, const void* dict, size_t dictSize)
4171 {
4172 { size_t const errorCode = ZSTDv07_decompressBegin(dctx);
4173 if (ZSTDv07_isError(errorCode)) return errorCode; }
4174
4175 if (dict && dictSize) {
4176 size_t const errorCode = ZSTDv07_decompress_insertDictionary(dctx, dict, dictSize);
4177 if (ZSTDv07_isError(errorCode)) return ERROR(dictionary_corrupted);
4178 }
4179
4180 return 0;
4181 }
4182
4183
4184 struct ZSTDv07_DDict_s {
4185 void* dict;
4186 size_t dictSize;
4187 ZSTDv07_DCtx* refContext;
4188 }; /* typedef'd tp ZSTDv07_CDict within zstd.h */
4189
ZSTDv07_createDDict_advanced(const void * dict,size_t dictSize,ZSTDv07_customMem customMem)4190 static ZSTDv07_DDict* ZSTDv07_createDDict_advanced(const void* dict, size_t dictSize, ZSTDv07_customMem customMem)
4191 {
4192 if (!customMem.customAlloc && !customMem.customFree)
4193 customMem = defaultCustomMem;
4194
4195 if (!customMem.customAlloc || !customMem.customFree)
4196 return NULL;
4197
4198 { ZSTDv07_DDict* const ddict = (ZSTDv07_DDict*) customMem.customAlloc(customMem.opaque, sizeof(*ddict));
4199 void* const dictContent = customMem.customAlloc(customMem.opaque, dictSize);
4200 ZSTDv07_DCtx* const dctx = ZSTDv07_createDCtx_advanced(customMem);
4201
4202 if (!dictContent || !ddict || !dctx) {
4203 customMem.customFree(customMem.opaque, dictContent);
4204 customMem.customFree(customMem.opaque, ddict);
4205 customMem.customFree(customMem.opaque, dctx);
4206 return NULL;
4207 }
4208
4209 memcpy(dictContent, dict, dictSize);
4210 { size_t const errorCode = ZSTDv07_decompressBegin_usingDict(dctx, dictContent, dictSize);
4211 if (ZSTDv07_isError(errorCode)) {
4212 customMem.customFree(customMem.opaque, dictContent);
4213 customMem.customFree(customMem.opaque, ddict);
4214 customMem.customFree(customMem.opaque, dctx);
4215 return NULL;
4216 } }
4217
4218 ddict->dict = dictContent;
4219 ddict->dictSize = dictSize;
4220 ddict->refContext = dctx;
4221 return ddict;
4222 }
4223 }
4224
4225 /*! ZSTDv07_createDDict() :
4226 * Create a digested dictionary, ready to start decompression without startup delay.
4227 * `dict` can be released after `ZSTDv07_DDict` creation */
ZSTDv07_createDDict(const void * dict,size_t dictSize)4228 ZSTDv07_DDict* ZSTDv07_createDDict(const void* dict, size_t dictSize)
4229 {
4230 ZSTDv07_customMem const allocator = { NULL, NULL, NULL };
4231 return ZSTDv07_createDDict_advanced(dict, dictSize, allocator);
4232 }
4233
ZSTDv07_freeDDict(ZSTDv07_DDict * ddict)4234 size_t ZSTDv07_freeDDict(ZSTDv07_DDict* ddict)
4235 {
4236 ZSTDv07_freeFunction const cFree = ddict->refContext->customMem.customFree;
4237 void* const opaque = ddict->refContext->customMem.opaque;
4238 ZSTDv07_freeDCtx(ddict->refContext);
4239 cFree(opaque, ddict->dict);
4240 cFree(opaque, ddict);
4241 return 0;
4242 }
4243
4244 /*! ZSTDv07_decompress_usingDDict() :
4245 * Decompression using a pre-digested Dictionary
4246 * Use dictionary without significant overhead. */
ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const ZSTDv07_DDict * ddict)4247 ZSTDLIBv07_API size_t ZSTDv07_decompress_usingDDict(ZSTDv07_DCtx* dctx,
4248 void* dst, size_t dstCapacity,
4249 const void* src, size_t srcSize,
4250 const ZSTDv07_DDict* ddict)
4251 {
4252 return ZSTDv07_decompress_usingPreparedDCtx(dctx, ddict->refContext,
4253 dst, dstCapacity,
4254 src, srcSize);
4255 }
4256 /*
4257 Buffered version of Zstd compression library
4258 Copyright (C) 2015-2016, Yann Collet.
4259
4260 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
4261
4262 Redistribution and use in source and binary forms, with or without
4263 modification, are permitted provided that the following conditions are
4264 met:
4265 * Redistributions of source code must retain the above copyright
4266 notice, this list of conditions and the following disclaimer.
4267 * Redistributions in binary form must reproduce the above
4268 copyright notice, this list of conditions and the following disclaimer
4269 in the documentation and/or other materials provided with the
4270 distribution.
4271 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
4272 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
4273 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
4274 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
4275 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
4276 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
4277 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
4278 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
4279 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
4280 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
4281 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
4282
4283 You can contact the author at :
4284 - zstd homepage : http://www.zstd.net/
4285 */
4286
4287
4288
4289 /*-***************************************************************************
4290 * Streaming decompression howto
4291 *
4292 * A ZBUFFv07_DCtx object is required to track streaming operations.
4293 * Use ZBUFFv07_createDCtx() and ZBUFFv07_freeDCtx() to create/release resources.
4294 * Use ZBUFFv07_decompressInit() to start a new decompression operation,
4295 * or ZBUFFv07_decompressInitDictionary() if decompression requires a dictionary.
4296 * Note that ZBUFFv07_DCtx objects can be re-init multiple times.
4297 *
4298 * Use ZBUFFv07_decompressContinue() repetitively to consume your input.
4299 * *srcSizePtr and *dstCapacityPtr can be any size.
4300 * The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
4301 * Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
4302 * The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
4303 * @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
4304 * or 0 when a frame is completely decoded,
4305 * or an error code, which can be tested using ZBUFFv07_isError().
4306 *
4307 * Hint : recommended buffer sizes (not compulsory) : ZBUFFv07_recommendedDInSize() and ZBUFFv07_recommendedDOutSize()
4308 * output : ZBUFFv07_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
4309 * input : ZBUFFv07_recommendedDInSize == 128KB + 3;
4310 * just follow indications from ZBUFFv07_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
4311 * *******************************************************************************/
4312
4313 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
4314 ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv07_dStage;
4315
4316 /* *** Resource management *** */
4317 struct ZBUFFv07_DCtx_s {
4318 ZSTDv07_DCtx* zd;
4319 ZSTDv07_frameParams fParams;
4320 ZBUFFv07_dStage stage;
4321 char* inBuff;
4322 size_t inBuffSize;
4323 size_t inPos;
4324 char* outBuff;
4325 size_t outBuffSize;
4326 size_t outStart;
4327 size_t outEnd;
4328 size_t blockSize;
4329 BYTE headerBuffer[ZSTDv07_FRAMEHEADERSIZE_MAX];
4330 size_t lhSize;
4331 ZSTDv07_customMem customMem;
4332 }; /* typedef'd to ZBUFFv07_DCtx within "zstd_buffered.h" */
4333
4334 ZSTDLIBv07_API ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem);
4335
ZBUFFv07_createDCtx(void)4336 ZBUFFv07_DCtx* ZBUFFv07_createDCtx(void)
4337 {
4338 return ZBUFFv07_createDCtx_advanced(defaultCustomMem);
4339 }
4340
ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem)4341 ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem)
4342 {
4343 ZBUFFv07_DCtx* zbd;
4344
4345 if (!customMem.customAlloc && !customMem.customFree)
4346 customMem = defaultCustomMem;
4347
4348 if (!customMem.customAlloc || !customMem.customFree)
4349 return NULL;
4350
4351 zbd = (ZBUFFv07_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFFv07_DCtx));
4352 if (zbd==NULL) return NULL;
4353 memset(zbd, 0, sizeof(ZBUFFv07_DCtx));
4354 memcpy(&zbd->customMem, &customMem, sizeof(ZSTDv07_customMem));
4355 zbd->zd = ZSTDv07_createDCtx_advanced(customMem);
4356 if (zbd->zd == NULL) { ZBUFFv07_freeDCtx(zbd); return NULL; }
4357 zbd->stage = ZBUFFds_init;
4358 return zbd;
4359 }
4360
ZBUFFv07_freeDCtx(ZBUFFv07_DCtx * zbd)4361 size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx* zbd)
4362 {
4363 if (zbd==NULL) return 0; /* support free on null */
4364 ZSTDv07_freeDCtx(zbd->zd);
4365 if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4366 if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4367 zbd->customMem.customFree(zbd->customMem.opaque, zbd);
4368 return 0;
4369 }
4370
4371
4372 /* *** Initialization *** */
4373
ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx * zbd,const void * dict,size_t dictSize)4374 size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx* zbd, const void* dict, size_t dictSize)
4375 {
4376 zbd->stage = ZBUFFds_loadHeader;
4377 zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
4378 return ZSTDv07_decompressBegin_usingDict(zbd->zd, dict, dictSize);
4379 }
4380
ZBUFFv07_decompressInit(ZBUFFv07_DCtx * zbd)4381 size_t ZBUFFv07_decompressInit(ZBUFFv07_DCtx* zbd)
4382 {
4383 return ZBUFFv07_decompressInitDictionary(zbd, NULL, 0);
4384 }
4385
4386
4387 /* internal util function */
ZBUFFv07_limitCopy(void * dst,size_t dstCapacity,const void * src,size_t srcSize)4388 MEM_STATIC size_t ZBUFFv07_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
4389 {
4390 size_t const length = MIN(dstCapacity, srcSize);
4391 if (length > 0) {
4392 memcpy(dst, src, length);
4393 }
4394 return length;
4395 }
4396
4397
4398 /* *** Decompression *** */
4399
ZBUFFv07_decompressContinue(ZBUFFv07_DCtx * zbd,void * dst,size_t * dstCapacityPtr,const void * src,size_t * srcSizePtr)4400 size_t ZBUFFv07_decompressContinue(ZBUFFv07_DCtx* zbd,
4401 void* dst, size_t* dstCapacityPtr,
4402 const void* src, size_t* srcSizePtr)
4403 {
4404 const char* const istart = (const char*)src;
4405 const char* const iend = istart + *srcSizePtr;
4406 const char* ip = istart;
4407 char* const ostart = (char*)dst;
4408 char* const oend = ostart + *dstCapacityPtr;
4409 char* op = ostart;
4410 U32 notDone = 1;
4411
4412 while (notDone) {
4413 switch(zbd->stage)
4414 {
4415 case ZBUFFds_init :
4416 return ERROR(init_missing);
4417
4418 case ZBUFFds_loadHeader :
4419 { size_t const hSize = ZSTDv07_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
4420 if (ZSTDv07_isError(hSize)) return hSize;
4421 if (hSize != 0) {
4422 size_t const toLoad = hSize - zbd->lhSize; /* if hSize!=0, hSize > zbd->lhSize */
4423 if (toLoad > (size_t)(iend-ip)) { /* not enough input to load full header */
4424 memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
4425 zbd->lhSize += iend-ip;
4426 *dstCapacityPtr = 0;
4427 return (hSize - zbd->lhSize) + ZSTDv07_blockHeaderSize; /* remaining header bytes + next block header */
4428 }
4429 memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
4430 break;
4431 } }
4432
4433 /* Consume header */
4434 { size_t const h1Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd); /* == ZSTDv07_frameHeaderSize_min */
4435 size_t const h1Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4436 if (ZSTDv07_isError(h1Result)) return h1Result;
4437 if (h1Size < zbd->lhSize) { /* long header */
4438 size_t const h2Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4439 size_t const h2Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4440 if (ZSTDv07_isError(h2Result)) return h2Result;
4441 } }
4442
4443 zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN);
4444
4445 /* Frame header instruct buffer sizes */
4446 { size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX);
4447 zbd->blockSize = blockSize;
4448 if (zbd->inBuffSize < blockSize) {
4449 zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4450 zbd->inBuffSize = blockSize;
4451 zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize);
4452 if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4453 }
4454 { size_t const neededOutSize = zbd->fParams.windowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
4455 if (zbd->outBuffSize < neededOutSize) {
4456 zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4457 zbd->outBuffSize = neededOutSize;
4458 zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize);
4459 if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4460 } } }
4461 zbd->stage = ZBUFFds_read;
4462 /* pass-through */
4463 /* fall-through */
4464 case ZBUFFds_read:
4465 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4466 if (neededInSize==0) { /* end of frame */
4467 zbd->stage = ZBUFFds_init;
4468 notDone = 0;
4469 break;
4470 }
4471 if ((size_t)(iend-ip) >= neededInSize) { /* decode directly from src */
4472 const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4473 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4474 zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart),
4475 ip, neededInSize);
4476 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4477 ip += neededInSize;
4478 if (!decodedSize && !isSkipFrame) break; /* this was just a header */
4479 zbd->outEnd = zbd->outStart + decodedSize;
4480 zbd->stage = ZBUFFds_flush;
4481 break;
4482 }
4483 if (ip==iend) { notDone = 0; break; } /* no more input */
4484 zbd->stage = ZBUFFds_load;
4485 }
4486 /* fall-through */
4487 case ZBUFFds_load:
4488 { size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4489 size_t const toLoad = neededInSize - zbd->inPos; /* should always be <= remaining space within inBuff */
4490 size_t loadedSize;
4491 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected); /* should never happen */
4492 loadedSize = ZBUFFv07_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4493 ip += loadedSize;
4494 zbd->inPos += loadedSize;
4495 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
4496
4497 /* decode loaded input */
4498 { const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4499 size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4500 zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4501 zbd->inBuff, neededInSize);
4502 if (ZSTDv07_isError(decodedSize)) return decodedSize;
4503 zbd->inPos = 0; /* input is consumed */
4504 if (!decodedSize && !isSkipFrame) { zbd->stage = ZBUFFds_read; break; } /* this was just a header */
4505 zbd->outEnd = zbd->outStart + decodedSize;
4506 zbd->stage = ZBUFFds_flush;
4507 /* break; */
4508 /* pass-through */
4509 }
4510 }
4511 /* fall-through */
4512 case ZBUFFds_flush:
4513 { size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4514 size_t const flushedSize = ZBUFFv07_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4515 op += flushedSize;
4516 zbd->outStart += flushedSize;
4517 if (flushedSize == toFlushSize) {
4518 zbd->stage = ZBUFFds_read;
4519 if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4520 zbd->outStart = zbd->outEnd = 0;
4521 break;
4522 }
4523 /* cannot flush everything */
4524 notDone = 0;
4525 break;
4526 }
4527 default: return ERROR(GENERIC); /* impossible */
4528 } }
4529
4530 /* result */
4531 *srcSizePtr = ip-istart;
4532 *dstCapacityPtr = op-ostart;
4533 { size_t nextSrcSizeHint = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4534 nextSrcSizeHint -= zbd->inPos; /* already loaded*/
4535 return nextSrcSizeHint;
4536 }
4537 }
4538
4539
4540
4541 /* *************************************
4542 * Tool functions
4543 ***************************************/
ZBUFFv07_recommendedDInSize(void)4544 size_t ZBUFFv07_recommendedDInSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX + ZSTDv07_blockHeaderSize /* block header size*/ ; }
ZBUFFv07_recommendedDOutSize(void)4545 size_t ZBUFFv07_recommendedDOutSize(void) { return ZSTDv07_BLOCKSIZE_ABSOLUTEMAX; }
4546