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