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