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