blob: 7a0e7c9b69fb0b41439cdc4907207d470bd7f3fb [file] [log] [blame]
khenaidooac637102019-01-14 15:44:34 -05001/*
2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
9 */
10
11
12#include <stddef.h> /* size_t, ptrdiff_t */
13#include "zstd_v03.h"
14#include "error_private.h"
15
16
17/******************************************
18* Compiler-specific
19******************************************/
20#if defined(_MSC_VER) /* Visual Studio */
21# include <stdlib.h> /* _byteswap_ulong */
22# include <intrin.h> /* _byteswap_* */
23#endif
24
25
26
27/* ******************************************************************
28 mem.h
29 low-level memory access routines
30 Copyright (C) 2013-2015, Yann Collet.
31
32 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
33
34 Redistribution and use in source and binary forms, with or without
35 modification, are permitted provided that the following conditions are
36 met:
37
38 * Redistributions of source code must retain the above copyright
39 notice, this list of conditions and the following disclaimer.
40 * Redistributions in binary form must reproduce the above
41 copyright notice, this list of conditions and the following disclaimer
42 in the documentation and/or other materials provided with the
43 distribution.
44
45 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
46 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
47 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
48 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
49 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
50 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
51 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
52 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
53 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
54 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
55 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
56
57 You can contact the author at :
58 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
59 - Public forum : https://groups.google.com/forum/#!forum/lz4c
60****************************************************************** */
61#ifndef MEM_H_MODULE
62#define MEM_H_MODULE
63
64#if defined (__cplusplus)
65extern "C" {
66#endif
67
68/******************************************
69* Includes
70******************************************/
71#include <stddef.h> /* size_t, ptrdiff_t */
72#include <string.h> /* memcpy */
73
74
75/******************************************
76* Compiler-specific
77******************************************/
78#if defined(__GNUC__)
79# define MEM_STATIC static __attribute__((unused))
80#elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
81# define MEM_STATIC static inline
82#elif defined(_MSC_VER)
83# define MEM_STATIC static __inline
84#else
85# define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
86#endif
87
88
89/****************************************************************
90* Basic Types
91*****************************************************************/
92#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
93# include <stdint.h>
94 typedef uint8_t BYTE;
95 typedef uint16_t U16;
96 typedef int16_t S16;
97 typedef uint32_t U32;
98 typedef int32_t S32;
99 typedef uint64_t U64;
100 typedef int64_t S64;
101#else
102 typedef unsigned char BYTE;
103 typedef unsigned short U16;
104 typedef signed short S16;
105 typedef unsigned int U32;
106 typedef signed int S32;
107 typedef unsigned long long U64;
108 typedef signed long long S64;
109#endif
110
111
112/****************************************************************
113* Memory I/O
114*****************************************************************/
115/* MEM_FORCE_MEMORY_ACCESS
116 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
117 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
118 * The below switch allow to select different access method for improved performance.
119 * Method 0 (default) : use `memcpy()`. Safe and portable.
120 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
121 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
122 * Method 2 : direct access. This method is portable but violate C standard.
123 * It can generate buggy code on targets generating assembly depending on alignment.
124 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
125 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
126 * Prefer these methods in priority order (0 > 1 > 2)
127 */
128#ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
129# 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__) )
130# define MEM_FORCE_MEMORY_ACCESS 2
131# elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
132 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
133# define MEM_FORCE_MEMORY_ACCESS 1
134# endif
135#endif
136
137MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
138MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
139
140MEM_STATIC unsigned MEM_isLittleEndian(void)
141{
142 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
143 return one.c[0];
144}
145
146#if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
147
148/* violates C standard on structure alignment.
149Only use if no other choice to achieve best performance on target platform */
150MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
151MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
152MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
153
154MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
155
156#elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
157
158/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
159/* currently only defined for gcc and icc */
160typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;
161
162MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
163MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
164MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
165
166MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
167
168#else
169
170/* default method, safe and standard.
171 can sometimes prove slower */
172
173MEM_STATIC U16 MEM_read16(const void* memPtr)
174{
175 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
176}
177
178MEM_STATIC U32 MEM_read32(const void* memPtr)
179{
180 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
181}
182
183MEM_STATIC U64 MEM_read64(const void* memPtr)
184{
185 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
186}
187
188MEM_STATIC void MEM_write16(void* memPtr, U16 value)
189{
190 memcpy(memPtr, &value, sizeof(value));
191}
192
193
194#endif // MEM_FORCE_MEMORY_ACCESS
195
196
197MEM_STATIC U16 MEM_readLE16(const void* memPtr)
198{
199 if (MEM_isLittleEndian())
200 return MEM_read16(memPtr);
201 else
202 {
203 const BYTE* p = (const BYTE*)memPtr;
204 return (U16)(p[0] + (p[1]<<8));
205 }
206}
207
208MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
209{
210 if (MEM_isLittleEndian())
211 {
212 MEM_write16(memPtr, val);
213 }
214 else
215 {
216 BYTE* p = (BYTE*)memPtr;
217 p[0] = (BYTE)val;
218 p[1] = (BYTE)(val>>8);
219 }
220}
221
Scott Baker8461e152019-10-01 14:44:30 -0700222MEM_STATIC U32 MEM_readLE24(const void* memPtr)
223{
224 return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
225}
226
khenaidooac637102019-01-14 15:44:34 -0500227MEM_STATIC U32 MEM_readLE32(const void* memPtr)
228{
229 if (MEM_isLittleEndian())
230 return MEM_read32(memPtr);
231 else
232 {
233 const BYTE* p = (const BYTE*)memPtr;
234 return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
235 }
236}
237
238MEM_STATIC U64 MEM_readLE64(const void* memPtr)
239{
240 if (MEM_isLittleEndian())
241 return MEM_read64(memPtr);
242 else
243 {
244 const BYTE* p = (const BYTE*)memPtr;
245 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
246 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
247 }
248}
249
250
251MEM_STATIC size_t MEM_readLEST(const void* memPtr)
252{
253 if (MEM_32bits())
254 return (size_t)MEM_readLE32(memPtr);
255 else
256 return (size_t)MEM_readLE64(memPtr);
257}
258
259
260#if defined (__cplusplus)
261}
262#endif
263
264#endif /* MEM_H_MODULE */
265
266
267/* ******************************************************************
268 bitstream
269 Part of NewGen Entropy library
270 header file (to include)
271 Copyright (C) 2013-2015, Yann Collet.
272
273 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
274
275 Redistribution and use in source and binary forms, with or without
276 modification, are permitted provided that the following conditions are
277 met:
278
279 * Redistributions of source code must retain the above copyright
280 notice, this list of conditions and the following disclaimer.
281 * Redistributions in binary form must reproduce the above
282 copyright notice, this list of conditions and the following disclaimer
283 in the documentation and/or other materials provided with the
284 distribution.
285
286 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
287 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
288 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
289 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
290 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
291 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
292 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
293 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
294 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
295 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
296 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
297
298 You can contact the author at :
299 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
300 - Public forum : https://groups.google.com/forum/#!forum/lz4c
301****************************************************************** */
302#ifndef BITSTREAM_H_MODULE
303#define BITSTREAM_H_MODULE
304
305#if defined (__cplusplus)
306extern "C" {
307#endif
308
309
310/*
311* This API consists of small unitary functions, which highly benefit from being inlined.
312* Since link-time-optimization is not available for all compilers,
313* these functions are defined into a .h to be included.
314*/
315
316
317/**********************************************
318* bitStream decompression API (read backward)
319**********************************************/
320typedef struct
321{
322 size_t bitContainer;
323 unsigned bitsConsumed;
324 const char* ptr;
325 const char* start;
326} BIT_DStream_t;
327
328typedef enum { BIT_DStream_unfinished = 0,
329 BIT_DStream_endOfBuffer = 1,
330 BIT_DStream_completed = 2,
331 BIT_DStream_overflow = 3 } BIT_DStream_status; /* result of BIT_reloadDStream() */
332 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
333
334MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
335MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
336MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
337MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
338
339
340
341/******************************************
342* unsafe API
343******************************************/
344MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
345/* faster, but works only if nbBits >= 1 */
346
347
348
349/****************************************************************
350* Helper functions
351****************************************************************/
352MEM_STATIC unsigned BIT_highbit32 (U32 val)
353{
354# if defined(_MSC_VER) /* Visual */
355 unsigned long r=0;
356 _BitScanReverse ( &r, val );
357 return (unsigned) r;
358# elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
359 return 31 - __builtin_clz (val);
360# else /* Software version */
361 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 };
362 U32 v = val;
363 unsigned r;
364 v |= v >> 1;
365 v |= v >> 2;
366 v |= v >> 4;
367 v |= v >> 8;
368 v |= v >> 16;
369 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
370 return r;
371# endif
372}
373
374
375
376/**********************************************************
377* bitStream decoding
378**********************************************************/
379
380/*!BIT_initDStream
381* Initialize a BIT_DStream_t.
382* @bitD : a pointer to an already allocated BIT_DStream_t structure
383* @srcBuffer must point at the beginning of a bitStream
384* @srcSize must be the exact size of the bitStream
385* @result : size of stream (== srcSize) or an errorCode if a problem is detected
386*/
387MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
388{
389 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
390
391 if (srcSize >= sizeof(size_t)) /* normal case */
392 {
393 U32 contain32;
394 bitD->start = (const char*)srcBuffer;
395 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
396 bitD->bitContainer = MEM_readLEST(bitD->ptr);
397 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
398 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
399 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
400 }
401 else
402 {
403 U32 contain32;
404 bitD->start = (const char*)srcBuffer;
405 bitD->ptr = bitD->start;
406 bitD->bitContainer = *(const BYTE*)(bitD->start);
407 switch(srcSize)
408 {
409 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
Scott Baker8461e152019-10-01 14:44:30 -0700410 /* fallthrough */
khenaidooac637102019-01-14 15:44:34 -0500411 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
Scott Baker8461e152019-10-01 14:44:30 -0700412 /* fallthrough */
khenaidooac637102019-01-14 15:44:34 -0500413 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
Scott Baker8461e152019-10-01 14:44:30 -0700414 /* fallthrough */
khenaidooac637102019-01-14 15:44:34 -0500415 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
Scott Baker8461e152019-10-01 14:44:30 -0700416 /* fallthrough */
khenaidooac637102019-01-14 15:44:34 -0500417 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
Scott Baker8461e152019-10-01 14:44:30 -0700418 /* fallthrough */
khenaidooac637102019-01-14 15:44:34 -0500419 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8;
Scott Baker8461e152019-10-01 14:44:30 -0700420 /* fallthrough */
khenaidooac637102019-01-14 15:44:34 -0500421 default:;
422 }
423 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
424 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
425 bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
426 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
427 }
428
429 return srcSize;
430}
431MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
432{
433 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
434 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
435}
436
437/*! BIT_lookBitsFast :
438* unsafe version; only works only if nbBits >= 1 */
439MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
440{
441 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
442 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
443}
444
445MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
446{
447 bitD->bitsConsumed += nbBits;
448}
449
450MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
451{
452 size_t value = BIT_lookBits(bitD, nbBits);
453 BIT_skipBits(bitD, nbBits);
454 return value;
455}
456
457/*!BIT_readBitsFast :
458* unsafe version; only works only if nbBits >= 1 */
459MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
460{
461 size_t value = BIT_lookBitsFast(bitD, nbBits);
462 BIT_skipBits(bitD, nbBits);
463 return value;
464}
465
466MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
467{
468 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
469 return BIT_DStream_overflow;
470
471 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
472 {
473 bitD->ptr -= bitD->bitsConsumed >> 3;
474 bitD->bitsConsumed &= 7;
475 bitD->bitContainer = MEM_readLEST(bitD->ptr);
476 return BIT_DStream_unfinished;
477 }
478 if (bitD->ptr == bitD->start)
479 {
480 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
481 return BIT_DStream_completed;
482 }
483 {
484 U32 nbBytes = bitD->bitsConsumed >> 3;
485 BIT_DStream_status result = BIT_DStream_unfinished;
486 if (bitD->ptr - nbBytes < bitD->start)
487 {
488 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
489 result = BIT_DStream_endOfBuffer;
490 }
491 bitD->ptr -= nbBytes;
492 bitD->bitsConsumed -= nbBytes*8;
493 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
494 return result;
495 }
496}
497
498/*! BIT_endOfDStream
499* @return Tells if DStream has reached its exact end
500*/
501MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
502{
503 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
504}
505
506#if defined (__cplusplus)
507}
508#endif
509
510#endif /* BITSTREAM_H_MODULE */
511/* ******************************************************************
512 Error codes and messages
513 Copyright (C) 2013-2015, Yann Collet
514
515 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
516
517 Redistribution and use in source and binary forms, with or without
518 modification, are permitted provided that the following conditions are
519 met:
520
521 * Redistributions of source code must retain the above copyright
522 notice, this list of conditions and the following disclaimer.
523 * Redistributions in binary form must reproduce the above
524 copyright notice, this list of conditions and the following disclaimer
525 in the documentation and/or other materials provided with the
526 distribution.
527
528 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
529 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
530 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
531 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
532 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
533 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
534 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
535 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
536 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
537 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
538 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
539
540 You can contact the author at :
541 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
542 - Public forum : https://groups.google.com/forum/#!forum/lz4c
543****************************************************************** */
544#ifndef ERROR_H_MODULE
545#define ERROR_H_MODULE
546
547#if defined (__cplusplus)
548extern "C" {
549#endif
550
551
552/******************************************
553* Compiler-specific
554******************************************/
555#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
556# define ERR_STATIC static inline
557#elif defined(_MSC_VER)
558# define ERR_STATIC static __inline
559#elif defined(__GNUC__)
560# define ERR_STATIC static __attribute__((unused))
561#else
562# define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
563#endif
564
565
566/******************************************
567* Error Management
568******************************************/
569#define PREFIX(name) ZSTD_error_##name
570
571#define ERROR(name) (size_t)-PREFIX(name)
572
573#define ERROR_LIST(ITEM) \
574 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
575 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
576 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
577 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
578 ITEM(PREFIX(maxCode))
579
580#define ERROR_GENERATE_ENUM(ENUM) ENUM,
581typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
582
583#define ERROR_CONVERTTOSTRING(STRING) #STRING,
584#define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
585static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
586
587ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
588
589ERR_STATIC const char* ERR_getErrorName(size_t code)
590{
591 static const char* codeError = "Unspecified error code";
592 if (ERR_isError(code)) return ERR_strings[-(int)(code)];
593 return codeError;
594}
595
596
597#if defined (__cplusplus)
598}
599#endif
600
601#endif /* ERROR_H_MODULE */
602/*
603Constructor and Destructor of type FSE_CTable
604 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
605typedef unsigned FSE_CTable; /* don't allocate that. It's just a way to be more restrictive than void* */
606typedef unsigned FSE_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
607
608
609/* ******************************************************************
610 FSE : Finite State Entropy coder
611 header file for static linking (only)
612 Copyright (C) 2013-2015, Yann Collet
613
614 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
615
616 Redistribution and use in source and binary forms, with or without
617 modification, are permitted provided that the following conditions are
618 met:
619
620 * Redistributions of source code must retain the above copyright
621 notice, this list of conditions and the following disclaimer.
622 * Redistributions in binary form must reproduce the above
623 copyright notice, this list of conditions and the following disclaimer
624 in the documentation and/or other materials provided with the
625 distribution.
626
627 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
628 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
629 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
630 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
631 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
632 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
633 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
634 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
635 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
636 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
637 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
638
639 You can contact the author at :
640 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
641 - Public forum : https://groups.google.com/forum/#!forum/lz4c
642****************************************************************** */
643#if defined (__cplusplus)
644extern "C" {
645#endif
646
647
648/******************************************
649* Static allocation
650******************************************/
651/* FSE buffer bounds */
652#define FSE_NCOUNTBOUND 512
653#define FSE_BLOCKBOUND(size) (size + (size>>7))
654#define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
655
656/* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
657#define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
658#define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
659
660
661/******************************************
662* FSE advanced API
663******************************************/
664static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
665/* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
666
667static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
668/* build a fake FSE_DTable, designed to always generate the same symbolValue */
669
670
671/******************************************
672* FSE symbol decompression API
673******************************************/
674typedef struct
675{
676 size_t state;
677 const void* table; /* precise table may vary, depending on U16 */
678} FSE_DState_t;
679
680
681static void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
682
683static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
684
685static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
686
687
688/******************************************
689* FSE unsafe API
690******************************************/
691static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
692/* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
693
694
695/******************************************
696* Implementation of inline functions
697******************************************/
698
699/* decompression */
700
701typedef struct {
702 U16 tableLog;
703 U16 fastMode;
704} FSE_DTableHeader; /* sizeof U32 */
705
706typedef struct
707{
708 unsigned short newState;
709 unsigned char symbol;
710 unsigned char nbBits;
711} FSE_decode_t; /* size == U32 */
712
713MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
714{
715 FSE_DTableHeader DTableH;
716 memcpy(&DTableH, dt, sizeof(DTableH));
717 DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
718 BIT_reloadDStream(bitD);
719 DStatePtr->table = dt + 1;
720}
721
722MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
723{
724 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
725 const U32 nbBits = DInfo.nbBits;
726 BYTE symbol = DInfo.symbol;
727 size_t lowBits = BIT_readBits(bitD, nbBits);
728
729 DStatePtr->state = DInfo.newState + lowBits;
730 return symbol;
731}
732
733MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
734{
735 const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
736 const U32 nbBits = DInfo.nbBits;
737 BYTE symbol = DInfo.symbol;
738 size_t lowBits = BIT_readBitsFast(bitD, nbBits);
739
740 DStatePtr->state = DInfo.newState + lowBits;
741 return symbol;
742}
743
744MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
745{
746 return DStatePtr->state == 0;
747}
748
749
750#if defined (__cplusplus)
751}
752#endif
753/* ******************************************************************
754 Huff0 : Huffman coder, part of New Generation Entropy library
755 header file for static linking (only)
756 Copyright (C) 2013-2015, Yann Collet
757
758 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
759
760 Redistribution and use in source and binary forms, with or without
761 modification, are permitted provided that the following conditions are
762 met:
763
764 * Redistributions of source code must retain the above copyright
765 notice, this list of conditions and the following disclaimer.
766 * Redistributions in binary form must reproduce the above
767 copyright notice, this list of conditions and the following disclaimer
768 in the documentation and/or other materials provided with the
769 distribution.
770
771 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
772 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
773 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
774 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
775 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
776 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
777 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
778 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
779 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
780 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
781 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
782
783 You can contact the author at :
784 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
785 - Public forum : https://groups.google.com/forum/#!forum/lz4c
786****************************************************************** */
787
788#if defined (__cplusplus)
789extern "C" {
790#endif
791
792/******************************************
793* Static allocation macros
794******************************************/
795/* Huff0 buffer bounds */
796#define HUF_CTABLEBOUND 129
797#define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
798#define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
799
800/* static allocation of Huff0's DTable */
801#define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
802#define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
803 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
804#define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
805 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
806#define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
807 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
808
809
810/******************************************
811* Advanced functions
812******************************************/
813static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
814static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
815
816
817#if defined (__cplusplus)
818}
819#endif
820
821/*
822 zstd - standard compression library
823 Header File
824 Copyright (C) 2014-2015, Yann Collet.
825
826 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
827
828 Redistribution and use in source and binary forms, with or without
829 modification, are permitted provided that the following conditions are
830 met:
831 * Redistributions of source code must retain the above copyright
832 notice, this list of conditions and the following disclaimer.
833 * Redistributions in binary form must reproduce the above
834 copyright notice, this list of conditions and the following disclaimer
835 in the documentation and/or other materials provided with the
836 distribution.
837 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
838 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
839 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
840 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
841 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
842 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
843 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
844 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
845 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
846 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
847 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
848
849 You can contact the author at :
850 - zstd source repository : https://github.com/Cyan4973/zstd
851 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
852*/
853
854#if defined (__cplusplus)
855extern "C" {
856#endif
857
858/* *************************************
859* Includes
860***************************************/
861#include <stddef.h> /* size_t */
862
863
864/* *************************************
865* Version
866***************************************/
867#define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
868#define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
869#define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
870#define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
871
872
873/* *************************************
874* Advanced functions
875***************************************/
876typedef struct ZSTD_CCtx_s ZSTD_CCtx; /* incomplete type */
877
878#if defined (__cplusplus)
879}
880#endif
881/*
882 zstd - standard compression library
883 Header File for static linking only
884 Copyright (C) 2014-2015, Yann Collet.
885
886 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
887
888 Redistribution and use in source and binary forms, with or without
889 modification, are permitted provided that the following conditions are
890 met:
891 * Redistributions of source code must retain the above copyright
892 notice, this list of conditions and the following disclaimer.
893 * Redistributions in binary form must reproduce the above
894 copyright notice, this list of conditions and the following disclaimer
895 in the documentation and/or other materials provided with the
896 distribution.
897 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
898 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
899 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
900 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
901 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
902 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
903 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
904 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
905 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
906 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
907 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
908
909 You can contact the author at :
910 - zstd source repository : https://github.com/Cyan4973/zstd
911 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
912*/
913
914/* The objects defined into this file should be considered experimental.
915 * They are not labelled stable, as their prototype may change in the future.
916 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
917 */
918
919#if defined (__cplusplus)
920extern "C" {
921#endif
922
923/* *************************************
924* Streaming functions
925***************************************/
926
927typedef struct ZSTD_DCtx_s ZSTD_DCtx;
928
929/*
930 Use above functions alternatively.
931 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
932 ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
933 Result is the number of bytes regenerated within 'dst'.
934 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
935*/
936
937/* *************************************
938* Prefix - version detection
939***************************************/
940#define ZSTD_magicNumber 0xFD2FB523 /* v0.3 */
941
942
943#if defined (__cplusplus)
944}
945#endif
946/* ******************************************************************
947 FSE : Finite State Entropy coder
948 Copyright (C) 2013-2015, Yann Collet.
949
950 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
951
952 Redistribution and use in source and binary forms, with or without
953 modification, are permitted provided that the following conditions are
954 met:
955
956 * Redistributions of source code must retain the above copyright
957 notice, this list of conditions and the following disclaimer.
958 * Redistributions in binary form must reproduce the above
959 copyright notice, this list of conditions and the following disclaimer
960 in the documentation and/or other materials provided with the
961 distribution.
962
963 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
964 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
965 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
966 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
967 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
968 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
969 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
970 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
971 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
972 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
973 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
974
975 You can contact the author at :
976 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
977 - Public forum : https://groups.google.com/forum/#!forum/lz4c
978****************************************************************** */
979
980#ifndef FSE_COMMONDEFS_ONLY
981
982/****************************************************************
983* Tuning parameters
984****************************************************************/
985/* MEMORY_USAGE :
986* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
987* Increasing memory usage improves compression ratio
988* Reduced memory usage can improve speed, due to cache effect
989* Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
990#define FSE_MAX_MEMORY_USAGE 14
991#define FSE_DEFAULT_MEMORY_USAGE 13
992
993/* FSE_MAX_SYMBOL_VALUE :
994* Maximum symbol value authorized.
995* Required for proper stack allocation */
996#define FSE_MAX_SYMBOL_VALUE 255
997
998
999/****************************************************************
1000* template functions type & suffix
1001****************************************************************/
1002#define FSE_FUNCTION_TYPE BYTE
1003#define FSE_FUNCTION_EXTENSION
1004
1005
1006/****************************************************************
1007* Byte symbol type
1008****************************************************************/
1009#endif /* !FSE_COMMONDEFS_ONLY */
1010
1011
1012/****************************************************************
1013* Compiler specifics
1014****************************************************************/
1015#ifdef _MSC_VER /* Visual Studio */
1016# define FORCE_INLINE static __forceinline
1017# include <intrin.h> /* For Visual 2005 */
1018# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1019# pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1020#else
1021# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1022# ifdef __GNUC__
1023# define FORCE_INLINE static inline __attribute__((always_inline))
1024# else
1025# define FORCE_INLINE static inline
1026# endif
1027# else
1028# define FORCE_INLINE static
1029# endif /* __STDC_VERSION__ */
1030#endif
1031
1032
1033/****************************************************************
1034* Includes
1035****************************************************************/
1036#include <stdlib.h> /* malloc, free, qsort */
1037#include <string.h> /* memcpy, memset */
1038#include <stdio.h> /* printf (debug) */
1039
1040/****************************************************************
1041* Constants
1042*****************************************************************/
1043#define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
1044#define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
1045#define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
1046#define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
1047#define FSE_MIN_TABLELOG 5
1048
1049#define FSE_TABLELOG_ABSOLUTE_MAX 15
1050#if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1051#error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1052#endif
1053
1054
1055/****************************************************************
1056* Error Management
1057****************************************************************/
1058#define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1059
1060
1061/****************************************************************
1062* Complex types
1063****************************************************************/
1064typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
1065
1066
1067/****************************************************************
1068* Templates
1069****************************************************************/
1070/*
1071 designed to be included
1072 for type-specific functions (template emulation in C)
1073 Objective is to write these functions only once, for improved maintenance
1074*/
1075
1076/* safety checks */
1077#ifndef FSE_FUNCTION_EXTENSION
1078# error "FSE_FUNCTION_EXTENSION must be defined"
1079#endif
1080#ifndef FSE_FUNCTION_TYPE
1081# error "FSE_FUNCTION_TYPE must be defined"
1082#endif
1083
1084/* Function names */
1085#define FSE_CAT(X,Y) X##Y
1086#define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1087#define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1088
1089
1090/* Function templates */
1091
1092#define FSE_DECODE_TYPE FSE_decode_t
1093
1094static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1095
1096static size_t FSE_buildDTable
1097(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1098{
1099 void* ptr = dt+1;
1100 FSE_DTableHeader DTableH;
1101 FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
1102 const U32 tableSize = 1 << tableLog;
1103 const U32 tableMask = tableSize-1;
1104 const U32 step = FSE_tableStep(tableSize);
1105 U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1106 U32 position = 0;
1107 U32 highThreshold = tableSize-1;
1108 const S16 largeLimit= (S16)(1 << (tableLog-1));
1109 U32 noLarge = 1;
1110 U32 s;
1111
1112 /* Sanity Checks */
1113 if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1114 if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1115
1116 /* Init, lay down lowprob symbols */
1117 DTableH.tableLog = (U16)tableLog;
1118 for (s=0; s<=maxSymbolValue; s++)
1119 {
1120 if (normalizedCounter[s]==-1)
1121 {
1122 tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1123 symbolNext[s] = 1;
1124 }
1125 else
1126 {
1127 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1128 symbolNext[s] = normalizedCounter[s];
1129 }
1130 }
1131
1132 /* Spread symbols */
1133 for (s=0; s<=maxSymbolValue; s++)
1134 {
1135 int i;
1136 for (i=0; i<normalizedCounter[s]; i++)
1137 {
1138 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1139 position = (position + step) & tableMask;
1140 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1141 }
1142 }
1143
1144 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1145
1146 /* Build Decoding table */
1147 {
1148 U32 i;
1149 for (i=0; i<tableSize; i++)
1150 {
1151 FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1152 U16 nextState = symbolNext[symbol]++;
1153 tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1154 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1155 }
1156 }
1157
1158 DTableH.fastMode = (U16)noLarge;
1159 memcpy(dt, &DTableH, sizeof(DTableH));
1160 return 0;
1161}
1162
1163
1164#ifndef FSE_COMMONDEFS_ONLY
1165/******************************************
1166* FSE helper functions
1167******************************************/
1168static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1169
1170
1171/****************************************************************
1172* FSE NCount encoding-decoding
1173****************************************************************/
1174static short FSE_abs(short a)
1175{
1176 return a<0 ? -a : a;
1177}
1178
1179static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1180 const void* headerBuffer, size_t hbSize)
1181{
1182 const BYTE* const istart = (const BYTE*) headerBuffer;
1183 const BYTE* const iend = istart + hbSize;
1184 const BYTE* ip = istart;
1185 int nbBits;
1186 int remaining;
1187 int threshold;
1188 U32 bitStream;
1189 int bitCount;
1190 unsigned charnum = 0;
1191 int previous0 = 0;
1192
1193 if (hbSize < 4) return ERROR(srcSize_wrong);
1194 bitStream = MEM_readLE32(ip);
1195 nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
1196 if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1197 bitStream >>= 4;
1198 bitCount = 4;
1199 *tableLogPtr = nbBits;
1200 remaining = (1<<nbBits)+1;
1201 threshold = 1<<nbBits;
1202 nbBits++;
1203
1204 while ((remaining>1) && (charnum<=*maxSVPtr))
1205 {
1206 if (previous0)
1207 {
1208 unsigned n0 = charnum;
1209 while ((bitStream & 0xFFFF) == 0xFFFF)
1210 {
1211 n0+=24;
1212 if (ip < iend-5)
1213 {
1214 ip+=2;
1215 bitStream = MEM_readLE32(ip) >> bitCount;
1216 }
1217 else
1218 {
1219 bitStream >>= 16;
1220 bitCount+=16;
1221 }
1222 }
1223 while ((bitStream & 3) == 3)
1224 {
1225 n0+=3;
1226 bitStream>>=2;
1227 bitCount+=2;
1228 }
1229 n0 += bitStream & 3;
1230 bitCount += 2;
1231 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1232 while (charnum < n0) normalizedCounter[charnum++] = 0;
1233 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1234 {
1235 ip += bitCount>>3;
1236 bitCount &= 7;
1237 bitStream = MEM_readLE32(ip) >> bitCount;
1238 }
1239 else
1240 bitStream >>= 2;
1241 }
1242 {
1243 const short max = (short)((2*threshold-1)-remaining);
1244 short count;
1245
1246 if ((bitStream & (threshold-1)) < (U32)max)
1247 {
1248 count = (short)(bitStream & (threshold-1));
1249 bitCount += nbBits-1;
1250 }
1251 else
1252 {
1253 count = (short)(bitStream & (2*threshold-1));
1254 if (count >= threshold) count -= max;
1255 bitCount += nbBits;
1256 }
1257
1258 count--; /* extra accuracy */
1259 remaining -= FSE_abs(count);
1260 normalizedCounter[charnum++] = count;
1261 previous0 = !count;
1262 while (remaining < threshold)
1263 {
1264 nbBits--;
1265 threshold >>= 1;
1266 }
1267
1268 {
1269 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1270 {
1271 ip += bitCount>>3;
1272 bitCount &= 7;
1273 }
1274 else
1275 {
1276 bitCount -= (int)(8 * (iend - 4 - ip));
1277 ip = iend - 4;
1278 }
1279 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1280 }
1281 }
1282 }
1283 if (remaining != 1) return ERROR(GENERIC);
1284 *maxSVPtr = charnum-1;
1285
1286 ip += (bitCount+7)>>3;
1287 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1288 return ip-istart;
1289}
1290
1291
1292/*********************************************************
1293* Decompression (Byte symbols)
1294*********************************************************/
1295static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1296{
1297 void* ptr = dt;
1298 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1299 FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1;
1300
1301 DTableH->tableLog = 0;
1302 DTableH->fastMode = 0;
1303
1304 cell->newState = 0;
1305 cell->symbol = symbolValue;
1306 cell->nbBits = 0;
1307
1308 return 0;
1309}
1310
1311
1312static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1313{
1314 void* ptr = dt;
1315 FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1316 FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1;
1317 const unsigned tableSize = 1 << nbBits;
1318 const unsigned tableMask = tableSize - 1;
1319 const unsigned maxSymbolValue = tableMask;
1320 unsigned s;
1321
1322 /* Sanity checks */
1323 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1324
1325 /* Build Decoding Table */
1326 DTableH->tableLog = (U16)nbBits;
1327 DTableH->fastMode = 1;
1328 for (s=0; s<=maxSymbolValue; s++)
1329 {
1330 dinfo[s].newState = 0;
1331 dinfo[s].symbol = (BYTE)s;
1332 dinfo[s].nbBits = (BYTE)nbBits;
1333 }
1334
1335 return 0;
1336}
1337
1338FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1339 void* dst, size_t maxDstSize,
1340 const void* cSrc, size_t cSrcSize,
1341 const FSE_DTable* dt, const unsigned fast)
1342{
1343 BYTE* const ostart = (BYTE*) dst;
1344 BYTE* op = ostart;
1345 BYTE* const omax = op + maxDstSize;
1346 BYTE* const olimit = omax-3;
1347
1348 BIT_DStream_t bitD;
1349 FSE_DState_t state1;
1350 FSE_DState_t state2;
1351 size_t errorCode;
1352
1353 /* Init */
1354 errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1355 if (FSE_isError(errorCode)) return errorCode;
1356
1357 FSE_initDState(&state1, &bitD, dt);
1358 FSE_initDState(&state2, &bitD, dt);
1359
1360#define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1361
1362 /* 4 symbols per loop */
1363 for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1364 {
1365 op[0] = FSE_GETSYMBOL(&state1);
1366
1367 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1368 BIT_reloadDStream(&bitD);
1369
1370 op[1] = FSE_GETSYMBOL(&state2);
1371
1372 if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1373 { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1374
1375 op[2] = FSE_GETSYMBOL(&state1);
1376
1377 if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1378 BIT_reloadDStream(&bitD);
1379
1380 op[3] = FSE_GETSYMBOL(&state2);
1381 }
1382
1383 /* tail */
1384 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1385 while (1)
1386 {
1387 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1388 break;
1389
1390 *op++ = FSE_GETSYMBOL(&state1);
1391
1392 if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1393 break;
1394
1395 *op++ = FSE_GETSYMBOL(&state2);
1396 }
1397
1398 /* end ? */
1399 if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1400 return op-ostart;
1401
1402 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1403
1404 return ERROR(corruption_detected);
1405}
1406
1407
1408static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1409 const void* cSrc, size_t cSrcSize,
1410 const FSE_DTable* dt)
1411{
1412 FSE_DTableHeader DTableH;
1413 memcpy(&DTableH, dt, sizeof(DTableH));
1414
1415 /* select fast mode (static) */
1416 if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1417 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1418}
1419
1420
1421static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1422{
1423 const BYTE* const istart = (const BYTE*)cSrc;
1424 const BYTE* ip = istart;
1425 short counting[FSE_MAX_SYMBOL_VALUE+1];
1426 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1427 unsigned tableLog;
1428 unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1429 size_t errorCode;
1430
1431 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1432
1433 /* normal FSE decoding mode */
1434 errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1435 if (FSE_isError(errorCode)) return errorCode;
1436 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1437 ip += errorCode;
1438 cSrcSize -= errorCode;
1439
1440 errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1441 if (FSE_isError(errorCode)) return errorCode;
1442
1443 /* always return, even if it is an error code */
1444 return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1445}
1446
1447
1448
1449#endif /* FSE_COMMONDEFS_ONLY */
1450/* ******************************************************************
1451 Huff0 : Huffman coder, part of New Generation Entropy library
1452 Copyright (C) 2013-2015, Yann Collet.
1453
1454 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1455
1456 Redistribution and use in source and binary forms, with or without
1457 modification, are permitted provided that the following conditions are
1458 met:
1459
1460 * Redistributions of source code must retain the above copyright
1461 notice, this list of conditions and the following disclaimer.
1462 * Redistributions in binary form must reproduce the above
1463 copyright notice, this list of conditions and the following disclaimer
1464 in the documentation and/or other materials provided with the
1465 distribution.
1466
1467 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1468 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1469 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1470 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1471 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1472 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1473 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1474 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1475 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1476 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1477 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1478
1479 You can contact the author at :
1480 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1481 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1482****************************************************************** */
1483
1484/****************************************************************
1485* Compiler specifics
1486****************************************************************/
1487#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1488/* inline is defined */
1489#elif defined(_MSC_VER)
1490# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1491# define inline __inline
1492#else
1493# define inline /* disable inline */
1494#endif
1495
1496
1497/****************************************************************
1498* Includes
1499****************************************************************/
1500#include <stdlib.h> /* malloc, free, qsort */
1501#include <string.h> /* memcpy, memset */
1502#include <stdio.h> /* printf (debug) */
1503
1504/****************************************************************
1505* Error Management
1506****************************************************************/
1507#define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1508
1509
1510/******************************************
1511* Helper functions
1512******************************************/
1513static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1514
1515#define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1516#define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1517#define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1518#define HUF_MAX_SYMBOL_VALUE 255
1519#if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1520# error "HUF_MAX_TABLELOG is too large !"
1521#endif
1522
1523
1524
1525/*********************************************************
1526* Huff0 : Huffman block decompression
1527*********************************************************/
1528typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2; /* single-symbol decoding */
1529
1530typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4; /* double-symbols decoding */
1531
1532typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1533
1534/*! HUF_readStats
1535 Read compact Huffman tree, saved by HUF_writeCTable
1536 @huffWeight : destination buffer
1537 @return : size read from `src`
1538*/
1539static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1540 U32* nbSymbolsPtr, U32* tableLogPtr,
1541 const void* src, size_t srcSize)
1542{
1543 U32 weightTotal;
1544 U32 tableLog;
1545 const BYTE* ip = (const BYTE*) src;
1546 size_t iSize;
1547 size_t oSize;
1548 U32 n;
1549
1550 if (!srcSize) return ERROR(srcSize_wrong);
1551 iSize = ip[0];
1552 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1553
1554 if (iSize >= 128) /* special header */
1555 {
1556 if (iSize >= (242)) /* RLE */
1557 {
1558 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1559 oSize = l[iSize-242];
1560 memset(huffWeight, 1, hwSize);
1561 iSize = 0;
1562 }
1563 else /* Incompressible */
1564 {
1565 oSize = iSize - 127;
1566 iSize = ((oSize+1)/2);
1567 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1568 if (oSize >= hwSize) return ERROR(corruption_detected);
1569 ip += 1;
1570 for (n=0; n<oSize; n+=2)
1571 {
1572 huffWeight[n] = ip[n/2] >> 4;
1573 huffWeight[n+1] = ip[n/2] & 15;
1574 }
1575 }
1576 }
1577 else /* header compressed with FSE (normal case) */
1578 {
1579 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1580 oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1581 if (FSE_isError(oSize)) return oSize;
1582 }
1583
1584 /* collect weight stats */
1585 memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1586 weightTotal = 0;
1587 for (n=0; n<oSize; n++)
1588 {
1589 if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1590 rankStats[huffWeight[n]]++;
1591 weightTotal += (1 << huffWeight[n]) >> 1;
1592 }
1593 if (weightTotal == 0) return ERROR(corruption_detected);
1594
1595 /* get last non-null symbol weight (implied, total must be 2^n) */
1596 tableLog = BIT_highbit32(weightTotal) + 1;
1597 if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1598 {
1599 U32 total = 1 << tableLog;
1600 U32 rest = total - weightTotal;
1601 U32 verif = 1 << BIT_highbit32(rest);
1602 U32 lastWeight = BIT_highbit32(rest) + 1;
1603 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1604 huffWeight[oSize] = (BYTE)lastWeight;
1605 rankStats[lastWeight]++;
1606 }
1607
1608 /* check tree construction validity */
1609 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1610
1611 /* results */
1612 *nbSymbolsPtr = (U32)(oSize+1);
1613 *tableLogPtr = tableLog;
1614 return iSize+1;
1615}
1616
1617
1618/**************************/
1619/* single-symbol decoding */
1620/**************************/
1621
1622static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1623{
1624 BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1625 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1626 U32 tableLog = 0;
1627 const BYTE* ip = (const BYTE*) src;
1628 size_t iSize = ip[0];
1629 U32 nbSymbols = 0;
1630 U32 n;
1631 U32 nextRankStart;
1632 void* ptr = DTable+1;
1633 HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr);
1634
1635 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1636 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1637
1638 iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1639 if (HUF_isError(iSize)) return iSize;
1640
1641 /* check result */
1642 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1643 DTable[0] = (U16)tableLog; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1644
1645 /* Prepare ranks */
1646 nextRankStart = 0;
1647 for (n=1; n<=tableLog; n++)
1648 {
1649 U32 current = nextRankStart;
1650 nextRankStart += (rankVal[n] << (n-1));
1651 rankVal[n] = current;
1652 }
1653
1654 /* fill DTable */
1655 for (n=0; n<nbSymbols; n++)
1656 {
1657 const U32 w = huffWeight[n];
1658 const U32 length = (1 << w) >> 1;
1659 U32 i;
1660 HUF_DEltX2 D;
1661 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1662 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1663 dt[i] = D;
1664 rankVal[w] += length;
1665 }
1666
1667 return iSize;
1668}
1669
1670static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1671{
1672 const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1673 const BYTE c = dt[val].byte;
1674 BIT_skipBits(Dstream, dt[val].nbBits);
1675 return c;
1676}
1677
1678#define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1679 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1680
1681#define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1682 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1683 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1684
1685#define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1686 if (MEM_64bits()) \
1687 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1688
1689static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1690{
1691 BYTE* const pStart = p;
1692
1693 /* up to 4 symbols at a time */
1694 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1695 {
1696 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1697 HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1698 HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1699 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1700 }
1701
1702 /* closer to the end */
1703 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1704 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1705
1706 /* no more data to retrieve from bitstream, hence no need to reload */
1707 while (p < pEnd)
1708 HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1709
1710 return pEnd-pStart;
1711}
1712
1713
1714static size_t HUF_decompress4X2_usingDTable(
1715 void* dst, size_t dstSize,
1716 const void* cSrc, size_t cSrcSize,
1717 const U16* DTable)
1718{
1719 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
1720
1721 {
1722 const BYTE* const istart = (const BYTE*) cSrc;
1723 BYTE* const ostart = (BYTE*) dst;
1724 BYTE* const oend = ostart + dstSize;
1725
1726 const void* ptr = DTable;
1727 const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1728 const U32 dtLog = DTable[0];
1729 size_t errorCode;
1730
1731 /* Init */
1732 BIT_DStream_t bitD1;
1733 BIT_DStream_t bitD2;
1734 BIT_DStream_t bitD3;
1735 BIT_DStream_t bitD4;
1736 const size_t length1 = MEM_readLE16(istart);
1737 const size_t length2 = MEM_readLE16(istart+2);
1738 const size_t length3 = MEM_readLE16(istart+4);
1739 size_t length4;
1740 const BYTE* const istart1 = istart + 6; /* jumpTable */
1741 const BYTE* const istart2 = istart1 + length1;
1742 const BYTE* const istart3 = istart2 + length2;
1743 const BYTE* const istart4 = istart3 + length3;
1744 const size_t segmentSize = (dstSize+3) / 4;
1745 BYTE* const opStart2 = ostart + segmentSize;
1746 BYTE* const opStart3 = opStart2 + segmentSize;
1747 BYTE* const opStart4 = opStart3 + segmentSize;
1748 BYTE* op1 = ostart;
1749 BYTE* op2 = opStart2;
1750 BYTE* op3 = opStart3;
1751 BYTE* op4 = opStart4;
1752 U32 endSignal;
1753
1754 length4 = cSrcSize - (length1 + length2 + length3 + 6);
1755 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
1756 errorCode = BIT_initDStream(&bitD1, istart1, length1);
1757 if (HUF_isError(errorCode)) return errorCode;
1758 errorCode = BIT_initDStream(&bitD2, istart2, length2);
1759 if (HUF_isError(errorCode)) return errorCode;
1760 errorCode = BIT_initDStream(&bitD3, istart3, length3);
1761 if (HUF_isError(errorCode)) return errorCode;
1762 errorCode = BIT_initDStream(&bitD4, istart4, length4);
1763 if (HUF_isError(errorCode)) return errorCode;
1764
1765 /* 16-32 symbols per loop (4-8 symbols per stream) */
1766 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1767 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1768 {
1769 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1770 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1771 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1772 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1773 HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1774 HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1775 HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1776 HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1777 HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1778 HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1779 HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1780 HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1781 HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1782 HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1783 HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1784 HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1785
1786 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1787 }
1788
1789 /* check corruption */
1790 if (op1 > opStart2) return ERROR(corruption_detected);
1791 if (op2 > opStart3) return ERROR(corruption_detected);
1792 if (op3 > opStart4) return ERROR(corruption_detected);
1793 /* note : op4 supposed already verified within main loop */
1794
1795 /* finish bitStreams one by one */
1796 HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1797 HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1798 HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1799 HUF_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
1800
1801 /* check */
1802 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1803 if (!endSignal) return ERROR(corruption_detected);
1804
1805 /* decoded size */
1806 return dstSize;
1807 }
1808}
1809
1810
1811static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1812{
1813 HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1814 const BYTE* ip = (const BYTE*) cSrc;
1815 size_t errorCode;
1816
1817 errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1818 if (HUF_isError(errorCode)) return errorCode;
1819 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1820 ip += errorCode;
1821 cSrcSize -= errorCode;
1822
1823 return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1824}
1825
1826
1827/***************************/
1828/* double-symbols decoding */
1829/***************************/
1830
1831static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1832 const U32* rankValOrigin, const int minWeight,
1833 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1834 U32 nbBitsBaseline, U16 baseSeq)
1835{
1836 HUF_DEltX4 DElt;
1837 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1838 U32 s;
1839
1840 /* get pre-calculated rankVal */
1841 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1842
1843 /* fill skipped values */
1844 if (minWeight>1)
1845 {
1846 U32 i, skipSize = rankVal[minWeight];
1847 MEM_writeLE16(&(DElt.sequence), baseSeq);
1848 DElt.nbBits = (BYTE)(consumed);
1849 DElt.length = 1;
1850 for (i = 0; i < skipSize; i++)
1851 DTable[i] = DElt;
1852 }
1853
1854 /* fill DTable */
1855 for (s=0; s<sortedListSize; s++) /* note : sortedSymbols already skipped */
1856 {
1857 const U32 symbol = sortedSymbols[s].symbol;
1858 const U32 weight = sortedSymbols[s].weight;
1859 const U32 nbBits = nbBitsBaseline - weight;
1860 const U32 length = 1 << (sizeLog-nbBits);
1861 const U32 start = rankVal[weight];
1862 U32 i = start;
1863 const U32 end = start + length;
1864
1865 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1866 DElt.nbBits = (BYTE)(nbBits + consumed);
1867 DElt.length = 2;
1868 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
1869
1870 rankVal[weight] += length;
1871 }
1872}
1873
1874typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1875
1876static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1877 const sortedSymbol_t* sortedList, const U32 sortedListSize,
1878 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1879 const U32 nbBitsBaseline)
1880{
1881 U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1882 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1883 const U32 minBits = nbBitsBaseline - maxWeight;
1884 U32 s;
1885
1886 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1887
1888 /* fill DTable */
1889 for (s=0; s<sortedListSize; s++)
1890 {
1891 const U16 symbol = sortedList[s].symbol;
1892 const U32 weight = sortedList[s].weight;
1893 const U32 nbBits = nbBitsBaseline - weight;
1894 const U32 start = rankVal[weight];
1895 const U32 length = 1 << (targetLog-nbBits);
1896
1897 if (targetLog-nbBits >= minBits) /* enough room for a second symbol */
1898 {
1899 U32 sortedRank;
1900 int minWeight = nbBits + scaleLog;
1901 if (minWeight < 1) minWeight = 1;
1902 sortedRank = rankStart[minWeight];
1903 HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1904 rankValOrigin[nbBits], minWeight,
1905 sortedList+sortedRank, sortedListSize-sortedRank,
1906 nbBitsBaseline, symbol);
1907 }
1908 else
1909 {
1910 U32 i;
1911 const U32 end = start + length;
1912 HUF_DEltX4 DElt;
1913
1914 MEM_writeLE16(&(DElt.sequence), symbol);
1915 DElt.nbBits = (BYTE)(nbBits);
1916 DElt.length = 1;
1917 for (i = start; i < end; i++)
1918 DTable[i] = DElt;
1919 }
1920 rankVal[weight] += length;
1921 }
1922}
1923
1924static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1925{
1926 BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1927 sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1928 U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1929 U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1930 U32* const rankStart = rankStart0+1;
1931 rankVal_t rankVal;
1932 U32 tableLog, maxW, sizeOfSort, nbSymbols;
1933 const U32 memLog = DTable[0];
1934 const BYTE* ip = (const BYTE*) src;
1935 size_t iSize = ip[0];
1936 void* ptr = DTable;
1937 HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1938
1939 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
1940 if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1941 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1942
1943 iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1944 if (HUF_isError(iSize)) return iSize;
1945
1946 /* check result */
1947 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
1948
1949 /* find maxWeight */
1950 for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1951 { if (!maxW) return ERROR(GENERIC); } /* necessarily finds a solution before maxW==0 */
1952
1953 /* Get start index of each weight */
1954 {
1955 U32 w, nextRankStart = 0;
1956 for (w=1; w<=maxW; w++)
1957 {
1958 U32 current = nextRankStart;
1959 nextRankStart += rankStats[w];
1960 rankStart[w] = current;
1961 }
1962 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
1963 sizeOfSort = nextRankStart;
1964 }
1965
1966 /* sort symbols by weight */
1967 {
1968 U32 s;
1969 for (s=0; s<nbSymbols; s++)
1970 {
1971 U32 w = weightList[s];
1972 U32 r = rankStart[w]++;
1973 sortedSymbol[r].symbol = (BYTE)s;
1974 sortedSymbol[r].weight = (BYTE)w;
1975 }
1976 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1977 }
1978
1979 /* Build rankVal */
1980 {
1981 const U32 minBits = tableLog+1 - maxW;
1982 U32 nextRankVal = 0;
1983 U32 w, consumed;
1984 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
1985 U32* rankVal0 = rankVal[0];
1986 for (w=1; w<=maxW; w++)
1987 {
1988 U32 current = nextRankVal;
1989 nextRankVal += rankStats[w] << (w+rescale);
1990 rankVal0[w] = current;
1991 }
1992 for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1993 {
1994 U32* rankValPtr = rankVal[consumed];
1995 for (w = 1; w <= maxW; w++)
1996 {
1997 rankValPtr[w] = rankVal0[w] >> consumed;
1998 }
1999 }
2000 }
2001
2002 HUF_fillDTableX4(dt, memLog,
2003 sortedSymbol, sizeOfSort,
2004 rankStart0, rankVal, maxW,
2005 tableLog+1);
2006
2007 return iSize;
2008}
2009
2010
2011static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2012{
2013 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2014 memcpy(op, dt+val, 2);
2015 BIT_skipBits(DStream, dt[val].nbBits);
2016 return dt[val].length;
2017}
2018
2019static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2020{
2021 const size_t val = BIT_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2022 memcpy(op, dt+val, 1);
2023 if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2024 else
2025 {
2026 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2027 {
2028 BIT_skipBits(DStream, dt[val].nbBits);
2029 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2030 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 */
2031 }
2032 }
2033 return 1;
2034}
2035
2036
2037#define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2038 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2039
2040#define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2041 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2042 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2043
2044#define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2045 if (MEM_64bits()) \
2046 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2047
2048static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2049{
2050 BYTE* const pStart = p;
2051
2052 /* up to 8 symbols at a time */
2053 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2054 {
2055 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2056 HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2057 HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2058 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2059 }
2060
2061 /* closer to the end */
2062 while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2063 HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2064
2065 while (p <= pEnd-2)
2066 HUF_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2067
2068 if (p < pEnd)
2069 p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2070
2071 return p-pStart;
2072}
2073
2074
2075
2076static size_t HUF_decompress4X4_usingDTable(
2077 void* dst, size_t dstSize,
2078 const void* cSrc, size_t cSrcSize,
2079 const U32* DTable)
2080{
2081 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2082
2083 {
2084 const BYTE* const istart = (const BYTE*) cSrc;
2085 BYTE* const ostart = (BYTE*) dst;
2086 BYTE* const oend = ostart + dstSize;
2087
2088 const void* ptr = DTable;
2089 const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2090 const U32 dtLog = DTable[0];
2091 size_t errorCode;
2092
2093 /* Init */
2094 BIT_DStream_t bitD1;
2095 BIT_DStream_t bitD2;
2096 BIT_DStream_t bitD3;
2097 BIT_DStream_t bitD4;
2098 const size_t length1 = MEM_readLE16(istart);
2099 const size_t length2 = MEM_readLE16(istart+2);
2100 const size_t length3 = MEM_readLE16(istart+4);
2101 size_t length4;
2102 const BYTE* const istart1 = istart + 6; /* jumpTable */
2103 const BYTE* const istart2 = istart1 + length1;
2104 const BYTE* const istart3 = istart2 + length2;
2105 const BYTE* const istart4 = istart3 + length3;
2106 const size_t segmentSize = (dstSize+3) / 4;
2107 BYTE* const opStart2 = ostart + segmentSize;
2108 BYTE* const opStart3 = opStart2 + segmentSize;
2109 BYTE* const opStart4 = opStart3 + segmentSize;
2110 BYTE* op1 = ostart;
2111 BYTE* op2 = opStart2;
2112 BYTE* op3 = opStart3;
2113 BYTE* op4 = opStart4;
2114 U32 endSignal;
2115
2116 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2117 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2118 errorCode = BIT_initDStream(&bitD1, istart1, length1);
2119 if (HUF_isError(errorCode)) return errorCode;
2120 errorCode = BIT_initDStream(&bitD2, istart2, length2);
2121 if (HUF_isError(errorCode)) return errorCode;
2122 errorCode = BIT_initDStream(&bitD3, istart3, length3);
2123 if (HUF_isError(errorCode)) return errorCode;
2124 errorCode = BIT_initDStream(&bitD4, istart4, length4);
2125 if (HUF_isError(errorCode)) return errorCode;
2126
2127 /* 16-32 symbols per loop (4-8 symbols per stream) */
2128 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2129 for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2130 {
2131 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2132 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2133 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2134 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2135 HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2136 HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2137 HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2138 HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2139 HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2140 HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2141 HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2142 HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2143 HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2144 HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2145 HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2146 HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2147
2148 endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2149 }
2150
2151 /* check corruption */
2152 if (op1 > opStart2) return ERROR(corruption_detected);
2153 if (op2 > opStart3) return ERROR(corruption_detected);
2154 if (op3 > opStart4) return ERROR(corruption_detected);
2155 /* note : op4 supposed already verified within main loop */
2156
2157 /* finish bitStreams one by one */
2158 HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2159 HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2160 HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2161 HUF_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2162
2163 /* check */
2164 endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2165 if (!endSignal) return ERROR(corruption_detected);
2166
2167 /* decoded size */
2168 return dstSize;
2169 }
2170}
2171
2172
2173static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2174{
2175 HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2176 const BYTE* ip = (const BYTE*) cSrc;
2177
2178 size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2179 if (HUF_isError(hSize)) return hSize;
2180 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2181 ip += hSize;
2182 cSrcSize -= hSize;
2183
2184 return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2185}
2186
2187
2188/**********************************/
2189/* Generic decompression selector */
2190/**********************************/
2191
2192typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2193static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2194{
2195 /* single, double, quad */
2196 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2197 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2198 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2199 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2200 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2201 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2202 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2203 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2204 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2205 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2206 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2207 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2208 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2209 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2210 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2211 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2212};
2213
2214typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2215
2216static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2217{
2218 static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2219 /* estimate decompression time */
2220 U32 Q;
2221 const U32 D256 = (U32)(dstSize >> 8);
2222 U32 Dtime[3];
2223 U32 algoNb = 0;
2224 int n;
2225
2226 /* validation checks */
2227 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2228 if (cSrcSize > dstSize) return ERROR(corruption_detected); /* invalid */
2229 if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; } /* not compressed */
2230 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2231
2232 /* decoder timing evaluation */
2233 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2234 for (n=0; n<3; n++)
2235 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2236
2237 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2238
2239 if (Dtime[1] < Dtime[0]) algoNb = 1;
2240
2241 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2242
2243 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2244 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2245 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2246}
2247/*
2248 zstd - standard compression library
2249 Copyright (C) 2014-2015, Yann Collet.
2250
2251 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2252
2253 Redistribution and use in source and binary forms, with or without
2254 modification, are permitted provided that the following conditions are
2255 met:
2256 * Redistributions of source code must retain the above copyright
2257 notice, this list of conditions and the following disclaimer.
2258 * Redistributions in binary form must reproduce the above
2259 copyright notice, this list of conditions and the following disclaimer
2260 in the documentation and/or other materials provided with the
2261 distribution.
2262 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2263 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2264 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2265 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2266 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2267 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2268 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2269 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2270 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2271 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2272 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2273
2274 You can contact the author at :
2275 - zstd source repository : https://github.com/Cyan4973/zstd
2276 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2277*/
2278
2279/* ***************************************************************
2280* Tuning parameters
2281*****************************************************************/
2282/*!
2283* MEMORY_USAGE :
2284* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2285* Increasing memory usage improves compression ratio
2286* Reduced memory usage can improve speed, due to cache effect
2287*/
2288#define ZSTD_MEMORY_USAGE 17
2289
2290/*!
2291 * HEAPMODE :
2292 * Select how default compression functions will allocate memory for their hash table,
2293 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2294 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2295 */
2296#ifndef ZSTD_HEAPMODE
2297# define ZSTD_HEAPMODE 1
2298#endif /* ZSTD_HEAPMODE */
2299
2300/*!
2301* LEGACY_SUPPORT :
2302* decompressor can decode older formats (starting from Zstd 0.1+)
2303*/
2304#ifndef ZSTD_LEGACY_SUPPORT
2305# define ZSTD_LEGACY_SUPPORT 1
2306#endif
2307
2308
2309/* *******************************************************
2310* Includes
2311*********************************************************/
2312#include <stdlib.h> /* calloc */
2313#include <string.h> /* memcpy, memmove */
2314#include <stdio.h> /* debug : printf */
2315
2316
2317/* *******************************************************
2318* Compiler specifics
2319*********************************************************/
2320#ifdef __AVX2__
2321# include <immintrin.h> /* AVX2 intrinsics */
2322#endif
2323
2324#ifdef _MSC_VER /* Visual Studio */
2325# include <intrin.h> /* For Visual 2005 */
2326# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2327# pragma warning(disable : 4324) /* disable: C4324: padded structure */
2328#else
2329# define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
2330#endif
2331
2332
2333/* *******************************************************
2334* Constants
2335*********************************************************/
2336#define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2337#define HASH_TABLESIZE (1 << HASH_LOG)
2338#define HASH_MASK (HASH_TABLESIZE - 1)
2339
2340#define KNUTH 2654435761
2341
2342#define BIT7 128
2343#define BIT6 64
2344#define BIT5 32
2345#define BIT4 16
2346#define BIT1 2
2347#define BIT0 1
2348
2349#define KB *(1 <<10)
2350#define MB *(1 <<20)
2351#define GB *(1U<<30)
2352
2353#define BLOCKSIZE (128 KB) /* define, for static allocation */
2354#define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2355#define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2356#define IS_RAW BIT0
2357#define IS_RLE BIT1
2358
2359#define WORKPLACESIZE (BLOCKSIZE*3)
2360#define MINMATCH 4
2361#define MLbits 7
2362#define LLbits 6
2363#define Offbits 5
2364#define MaxML ((1<<MLbits )-1)
2365#define MaxLL ((1<<LLbits )-1)
2366#define MaxOff 31
2367#define LitFSELog 11
2368#define MLFSELog 10
2369#define LLFSELog 10
2370#define OffFSELog 9
2371#define MAX(a,b) ((a)<(b)?(b):(a))
2372#define MaxSeq MAX(MaxLL, MaxML)
2373
2374#define LITERAL_NOENTROPY 63
2375#define COMMAND_NOENTROPY 7 /* to remove */
2376
Scott Baker8461e152019-10-01 14:44:30 -07002377#define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2378
khenaidooac637102019-01-14 15:44:34 -05002379static const size_t ZSTD_blockHeaderSize = 3;
2380static const size_t ZSTD_frameHeaderSize = 4;
2381
2382
2383/* *******************************************************
2384* Memory operations
2385**********************************************************/
2386static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2387
2388static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2389
2390#define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2391
2392/*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2393static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2394{
2395 const BYTE* ip = (const BYTE*)src;
2396 BYTE* op = (BYTE*)dst;
2397 BYTE* const oend = op + length;
2398 do COPY8(op, ip) while (op < oend);
2399}
2400
2401
2402/* **************************************
2403* Local structures
2404****************************************/
2405typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2406
2407typedef struct
2408{
2409 blockType_t blockType;
2410 U32 origSize;
2411} blockProperties_t;
2412
2413typedef struct {
2414 void* buffer;
2415 U32* offsetStart;
2416 U32* offset;
2417 BYTE* offCodeStart;
2418 BYTE* offCode;
2419 BYTE* litStart;
2420 BYTE* lit;
2421 BYTE* litLengthStart;
2422 BYTE* litLength;
2423 BYTE* matchLengthStart;
2424 BYTE* matchLength;
2425 BYTE* dumpsStart;
2426 BYTE* dumps;
2427} seqStore_t;
2428
2429
2430/* *************************************
2431* Error Management
2432***************************************/
2433/*! ZSTD_isError
2434* tells if a return value is an error code */
2435static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2436
2437
2438
2439/* *************************************************************
2440* Decompression section
2441***************************************************************/
2442struct ZSTD_DCtx_s
2443{
2444 U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2445 U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2446 U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2447 void* previousDstEnd;
2448 void* base;
2449 size_t expected;
2450 blockType_t bType;
2451 U32 phase;
2452 const BYTE* litPtr;
2453 size_t litSize;
2454 BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2455}; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2456
2457
2458static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2459{
2460 const BYTE* const in = (const BYTE* const)src;
2461 BYTE headerFlags;
2462 U32 cSize;
2463
2464 if (srcSize < 3) return ERROR(srcSize_wrong);
2465
2466 headerFlags = *in;
2467 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2468
2469 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2470 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2471
2472 if (bpPtr->blockType == bt_end) return 0;
2473 if (bpPtr->blockType == bt_rle) return 1;
2474 return cSize;
2475}
2476
2477static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2478{
2479 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2480 memcpy(dst, src, srcSize);
2481 return srcSize;
2482}
2483
2484
2485/** ZSTD_decompressLiterals
2486 @return : nb of bytes read from src, or an error code*/
2487static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2488 const void* src, size_t srcSize)
2489{
2490 const BYTE* ip = (const BYTE*)src;
2491
2492 const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2493 const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2494
2495 if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2496 if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2497
2498 if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2499
2500 *maxDstSizePtr = litSize;
2501 return litCSize + 5;
2502}
2503
2504
2505/** ZSTD_decodeLiteralsBlock
2506 @return : nb of bytes read from src (< srcSize )*/
2507static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2508 const void* src, size_t srcSize)
2509{
2510 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2511 const BYTE* const istart = (const BYTE* const)src;
2512
2513 /* any compressed block with literals segment must be at least this size */
2514 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2515
2516 switch(*istart & 3)
2517 {
2518 default:
2519 case 0:
2520 {
2521 size_t litSize = BLOCKSIZE;
2522 const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2523 dctx->litPtr = dctx->litBuffer;
2524 dctx->litSize = litSize;
2525 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2526 return readSize; /* works if it's an error too */
2527 }
2528 case IS_RAW:
2529 {
2530 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2531 if (litSize > srcSize-11) /* risk of reading too far with wildcopy */
2532 {
2533 if (litSize > srcSize-3) return ERROR(corruption_detected);
2534 memcpy(dctx->litBuffer, istart, litSize);
2535 dctx->litPtr = dctx->litBuffer;
2536 dctx->litSize = litSize;
2537 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2538 return litSize+3;
2539 }
2540 /* direct reference into compressed stream */
2541 dctx->litPtr = istart+3;
2542 dctx->litSize = litSize;
2543 return litSize+3;
2544 }
2545 case IS_RLE:
2546 {
2547 const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2548 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2549 memset(dctx->litBuffer, istart[3], litSize + 8);
2550 dctx->litPtr = dctx->litBuffer;
2551 dctx->litSize = litSize;
2552 return 4;
2553 }
2554 }
2555}
2556
2557
2558static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2559 FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2560 const void* src, size_t srcSize)
2561{
2562 const BYTE* const istart = (const BYTE* const)src;
2563 const BYTE* ip = istart;
2564 const BYTE* const iend = istart + srcSize;
2565 U32 LLtype, Offtype, MLtype;
2566 U32 LLlog, Offlog, MLlog;
2567 size_t dumpsLength;
2568
2569 /* check */
2570 if (srcSize < 5) return ERROR(srcSize_wrong);
2571
2572 /* SeqHead */
2573 *nbSeq = MEM_readLE16(ip); ip+=2;
2574 LLtype = *ip >> 6;
2575 Offtype = (*ip >> 4) & 3;
2576 MLtype = (*ip >> 2) & 3;
2577 if (*ip & 2)
2578 {
2579 dumpsLength = ip[2];
2580 dumpsLength += ip[1] << 8;
2581 ip += 3;
2582 }
2583 else
2584 {
2585 dumpsLength = ip[1];
2586 dumpsLength += (ip[0] & 1) << 8;
2587 ip += 2;
2588 }
2589 *dumpsPtr = ip;
2590 ip += dumpsLength;
2591 *dumpsLengthPtr = dumpsLength;
2592
2593 /* check */
2594 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2595
2596 /* sequences */
2597 {
2598 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2599 size_t headerSize;
2600
2601 /* Build DTables */
2602 switch(LLtype)
2603 {
2604 case bt_rle :
2605 LLlog = 0;
2606 FSE_buildDTable_rle(DTableLL, *ip++); break;
2607 case bt_raw :
2608 LLlog = LLbits;
2609 FSE_buildDTable_raw(DTableLL, LLbits); break;
2610 default :
2611 { U32 max = MaxLL;
2612 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2613 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2614 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2615 ip += headerSize;
2616 FSE_buildDTable(DTableLL, norm, max, LLlog);
2617 } }
2618
2619 switch(Offtype)
2620 {
2621 case bt_rle :
2622 Offlog = 0;
2623 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2624 FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2625 break;
2626 case bt_raw :
2627 Offlog = Offbits;
2628 FSE_buildDTable_raw(DTableOffb, Offbits); break;
2629 default :
2630 { U32 max = MaxOff;
2631 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2632 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2633 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2634 ip += headerSize;
2635 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2636 } }
2637
2638 switch(MLtype)
2639 {
2640 case bt_rle :
2641 MLlog = 0;
2642 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2643 FSE_buildDTable_rle(DTableML, *ip++); break;
2644 case bt_raw :
2645 MLlog = MLbits;
2646 FSE_buildDTable_raw(DTableML, MLbits); break;
2647 default :
2648 { U32 max = MaxML;
2649 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2650 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2651 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2652 ip += headerSize;
2653 FSE_buildDTable(DTableML, norm, max, MLlog);
2654 } } }
2655
2656 return ip-istart;
2657}
2658
2659
2660typedef struct {
2661 size_t litLength;
2662 size_t offset;
2663 size_t matchLength;
2664} seq_t;
2665
2666typedef struct {
2667 BIT_DStream_t DStream;
2668 FSE_DState_t stateLL;
2669 FSE_DState_t stateOffb;
2670 FSE_DState_t stateML;
2671 size_t prevOffset;
2672 const BYTE* dumps;
2673 const BYTE* dumpsEnd;
2674} seqState_t;
2675
2676
2677static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2678{
2679 size_t litLength;
2680 size_t prevOffset;
2681 size_t offset;
2682 size_t matchLength;
2683 const BYTE* dumps = seqState->dumps;
2684 const BYTE* const de = seqState->dumpsEnd;
2685
2686 /* Literal length */
2687 litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2688 prevOffset = litLength ? seq->offset : seqState->prevOffset;
2689 seqState->prevOffset = seq->offset;
2690 if (litLength == MaxLL)
2691 {
Scott Baker8461e152019-10-01 14:44:30 -07002692 const U32 add = dumps<de ? *dumps++ : 0;
khenaidooac637102019-01-14 15:44:34 -05002693 if (add < 255) litLength += add;
Scott Baker8461e152019-10-01 14:44:30 -07002694 else if (dumps + 3 <= de)
khenaidooac637102019-01-14 15:44:34 -05002695 {
Scott Baker8461e152019-10-01 14:44:30 -07002696 litLength = MEM_readLE24(dumps);
khenaidooac637102019-01-14 15:44:34 -05002697 dumps += 3;
2698 }
2699 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2700 }
2701
2702 /* Offset */
2703 {
2704 static const size_t offsetPrefix[MaxOff+1] = { /* note : size_t faster than U32 */
2705 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2706 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2707 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2708 U32 offsetCode, nbBits;
2709 offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* <= maxOff, by table construction */
2710 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2711 nbBits = offsetCode - 1;
2712 if (offsetCode==0) nbBits = 0; /* cmove */
2713 offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2714 if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2715 if (offsetCode==0) offset = prevOffset; /* cmove */
2716 }
2717
2718 /* MatchLength */
2719 matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2720 if (matchLength == MaxML)
2721 {
Scott Baker8461e152019-10-01 14:44:30 -07002722 const U32 add = dumps<de ? *dumps++ : 0;
khenaidooac637102019-01-14 15:44:34 -05002723 if (add < 255) matchLength += add;
Scott Baker8461e152019-10-01 14:44:30 -07002724 else if (dumps + 3 <= de)
khenaidooac637102019-01-14 15:44:34 -05002725 {
Scott Baker8461e152019-10-01 14:44:30 -07002726 matchLength = MEM_readLE24(dumps);
khenaidooac637102019-01-14 15:44:34 -05002727 dumps += 3;
2728 }
2729 if (dumps >= de) dumps = de-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
2730 }
2731 matchLength += MINMATCH;
2732
2733 /* save result */
2734 seq->litLength = litLength;
2735 seq->offset = offset;
2736 seq->matchLength = matchLength;
2737 seqState->dumps = dumps;
2738}
2739
2740
2741static size_t ZSTD_execSequence(BYTE* op,
2742 seq_t sequence,
2743 const BYTE** litPtr, const BYTE* const litLimit,
2744 BYTE* const base, BYTE* const oend)
2745{
2746 static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
Scott Baker8461e152019-10-01 14:44:30 -07002747 static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */
khenaidooac637102019-01-14 15:44:34 -05002748 const BYTE* const ostart = op;
2749 BYTE* const oLitEnd = op + sequence.litLength;
2750 BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength; /* risk : address space overflow (32-bits) */
2751 BYTE* const oend_8 = oend-8;
2752 const BYTE* const litEnd = *litPtr + sequence.litLength;
2753
2754 /* checks */
2755 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
2756 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
2757 if (litEnd > litLimit) return ERROR(corruption_detected); /* overRead beyond lit buffer */
2758
2759 /* copy Literals */
2760 ZSTD_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2761 op = oLitEnd;
2762 *litPtr = litEnd; /* update for next sequence */
2763
2764 /* copy Match */
2765 {
2766 const BYTE* match = op - sequence.offset;
2767
2768 /* check */
2769 if (sequence.offset > (size_t)op) return ERROR(corruption_detected); /* address space overflow test (this test seems kept by clang optimizer) */
2770 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
2771 if (match < base) return ERROR(corruption_detected);
2772
2773 /* close range match, overlap */
2774 if (sequence.offset < 8)
2775 {
2776 const int dec64 = dec64table[sequence.offset];
2777 op[0] = match[0];
2778 op[1] = match[1];
2779 op[2] = match[2];
2780 op[3] = match[3];
2781 match += dec32table[sequence.offset];
2782 ZSTD_copy4(op+4, match);
2783 match -= dec64;
2784 }
2785 else
2786 {
2787 ZSTD_copy8(op, match);
2788 }
2789 op += 8; match += 8;
2790
2791 if (oMatchEnd > oend-(16-MINMATCH))
2792 {
2793 if (op < oend_8)
2794 {
2795 ZSTD_wildcopy(op, match, oend_8 - op);
2796 match += oend_8 - op;
2797 op = oend_8;
2798 }
2799 while (op < oMatchEnd) *op++ = *match++;
2800 }
2801 else
2802 {
2803 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
2804 }
2805 }
2806
2807 return oMatchEnd - ostart;
2808}
2809
2810static size_t ZSTD_decompressSequences(
2811 void* ctx,
2812 void* dst, size_t maxDstSize,
2813 const void* seqStart, size_t seqSize)
2814{
2815 ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2816 const BYTE* ip = (const BYTE*)seqStart;
2817 const BYTE* const iend = ip + seqSize;
2818 BYTE* const ostart = (BYTE* const)dst;
2819 BYTE* op = ostart;
2820 BYTE* const oend = ostart + maxDstSize;
2821 size_t errorCode, dumpsLength;
2822 const BYTE* litPtr = dctx->litPtr;
2823 const BYTE* const litEnd = litPtr + dctx->litSize;
2824 int nbSeq;
2825 const BYTE* dumps;
2826 U32* DTableLL = dctx->LLTable;
2827 U32* DTableML = dctx->MLTable;
2828 U32* DTableOffb = dctx->OffTable;
2829 BYTE* const base = (BYTE*) (dctx->base);
2830
2831 /* Build Decoding Tables */
2832 errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2833 DTableLL, DTableML, DTableOffb,
2834 ip, iend-ip);
2835 if (ZSTD_isError(errorCode)) return errorCode;
2836 ip += errorCode;
2837
2838 /* Regen sequences */
2839 {
2840 seq_t sequence;
2841 seqState_t seqState;
2842
2843 memset(&sequence, 0, sizeof(sequence));
2844 seqState.dumps = dumps;
2845 seqState.dumpsEnd = dumps + dumpsLength;
2846 seqState.prevOffset = sequence.offset = 4;
2847 errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2848 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2849 FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2850 FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2851 FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2852
2853 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
2854 {
2855 size_t oneSeqSize;
2856 nbSeq--;
2857 ZSTD_decodeSequence(&sequence, &seqState);
2858 oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
2859 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2860 op += oneSeqSize;
2861 }
2862
2863 /* check if reached exact end */
2864 if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected); /* requested too much : data is corrupted */
2865 if (nbSeq<0) return ERROR(corruption_detected); /* requested too many sequences : data is corrupted */
2866
2867 /* last literal segment */
2868 {
2869 size_t lastLLSize = litEnd - litPtr;
2870 if (litPtr > litEnd) return ERROR(corruption_detected);
2871 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2872 if (op != litPtr) memmove(op, litPtr, lastLLSize);
2873 op += lastLLSize;
2874 }
2875 }
2876
2877 return op-ostart;
2878}
2879
2880
2881static size_t ZSTD_decompressBlock(
2882 void* ctx,
2883 void* dst, size_t maxDstSize,
2884 const void* src, size_t srcSize)
2885{
2886 /* blockType == blockCompressed */
2887 const BYTE* ip = (const BYTE*)src;
2888
2889 /* Decode literals sub-block */
2890 size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
2891 if (ZSTD_isError(litCSize)) return litCSize;
2892 ip += litCSize;
2893 srcSize -= litCSize;
2894
2895 return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
2896}
2897
2898
2899static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2900{
2901 const BYTE* ip = (const BYTE*)src;
2902 const BYTE* iend = ip + srcSize;
2903 BYTE* const ostart = (BYTE* const)dst;
2904 BYTE* op = ostart;
2905 BYTE* const oend = ostart + maxDstSize;
2906 size_t remainingSize = srcSize;
2907 U32 magicNumber;
2908 blockProperties_t blockProperties;
2909
2910 /* Frame Header */
2911 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2912 magicNumber = MEM_readLE32(src);
2913 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2914 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2915
2916 /* Loop on each block */
2917 while (1)
2918 {
2919 size_t decodedSize=0;
2920 size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
2921 if (ZSTD_isError(cBlockSize)) return cBlockSize;
2922
2923 ip += ZSTD_blockHeaderSize;
2924 remainingSize -= ZSTD_blockHeaderSize;
2925 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2926
2927 switch(blockProperties.blockType)
2928 {
2929 case bt_compressed:
2930 decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
2931 break;
2932 case bt_raw :
2933 decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
2934 break;
2935 case bt_rle :
2936 return ERROR(GENERIC); /* not yet supported */
2937 break;
2938 case bt_end :
2939 /* end of frame */
2940 if (remainingSize) return ERROR(srcSize_wrong);
2941 break;
2942 default:
2943 return ERROR(GENERIC); /* impossible */
2944 }
2945 if (cBlockSize == 0) break; /* bt_end */
2946
2947 if (ZSTD_isError(decodedSize)) return decodedSize;
2948 op += decodedSize;
2949 ip += cBlockSize;
2950 remainingSize -= cBlockSize;
2951 }
2952
2953 return op-ostart;
2954}
2955
2956static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2957{
2958 ZSTD_DCtx ctx;
2959 ctx.base = dst;
2960 return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
2961}
2962
Scott Baker8461e152019-10-01 14:44:30 -07002963/* ZSTD_errorFrameSizeInfoLegacy() :
2964 assumes `cSize` and `dBound` are _not_ NULL */
2965MEM_STATIC void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
2966{
2967 *cSize = ret;
2968 *dBound = ZSTD_CONTENTSIZE_ERROR;
2969}
2970
2971void ZSTDv03_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
khenaidooac637102019-01-14 15:44:34 -05002972{
2973 const BYTE* ip = (const BYTE*)src;
2974 size_t remainingSize = srcSize;
Scott Baker8461e152019-10-01 14:44:30 -07002975 size_t nbBlocks = 0;
khenaidooac637102019-01-14 15:44:34 -05002976 U32 magicNumber;
2977 blockProperties_t blockProperties;
2978
2979 /* Frame Header */
Scott Baker8461e152019-10-01 14:44:30 -07002980 if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
2981 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2982 return;
2983 }
khenaidooac637102019-01-14 15:44:34 -05002984 magicNumber = MEM_readLE32(src);
Scott Baker8461e152019-10-01 14:44:30 -07002985 if (magicNumber != ZSTD_magicNumber) {
2986 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
2987 return;
2988 }
khenaidooac637102019-01-14 15:44:34 -05002989 ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2990
2991 /* Loop on each block */
2992 while (1)
2993 {
2994 size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
Scott Baker8461e152019-10-01 14:44:30 -07002995 if (ZSTD_isError(cBlockSize)) {
2996 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
2997 return;
2998 }
khenaidooac637102019-01-14 15:44:34 -05002999
3000 ip += ZSTD_blockHeaderSize;
3001 remainingSize -= ZSTD_blockHeaderSize;
Scott Baker8461e152019-10-01 14:44:30 -07003002 if (cBlockSize > remainingSize) {
3003 ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3004 return;
3005 }
khenaidooac637102019-01-14 15:44:34 -05003006
3007 if (cBlockSize == 0) break; /* bt_end */
3008
3009 ip += cBlockSize;
3010 remainingSize -= cBlockSize;
Scott Baker8461e152019-10-01 14:44:30 -07003011 nbBlocks++;
khenaidooac637102019-01-14 15:44:34 -05003012 }
3013
Scott Baker8461e152019-10-01 14:44:30 -07003014 *cSize = ip - (const BYTE*)src;
3015 *dBound = nbBlocks * BLOCKSIZE;
khenaidooac637102019-01-14 15:44:34 -05003016}
3017
3018
3019/*******************************
3020* Streaming Decompression API
3021*******************************/
3022
3023static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
3024{
3025 dctx->expected = ZSTD_frameHeaderSize;
3026 dctx->phase = 0;
3027 dctx->previousDstEnd = NULL;
3028 dctx->base = NULL;
3029 return 0;
3030}
3031
3032static ZSTD_DCtx* ZSTD_createDCtx(void)
3033{
3034 ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
3035 if (dctx==NULL) return NULL;
3036 ZSTD_resetDCtx(dctx);
3037 return dctx;
3038}
3039
3040static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3041{
3042 free(dctx);
3043 return 0;
3044}
3045
3046static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3047{
3048 return dctx->expected;
3049}
3050
3051static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3052{
3053 /* Sanity check */
3054 if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3055 if (dst != ctx->previousDstEnd) /* not contiguous */
3056 ctx->base = dst;
3057
3058 /* Decompress : frame header */
3059 if (ctx->phase == 0)
3060 {
3061 /* Check frame magic header */
3062 U32 magicNumber = MEM_readLE32(src);
3063 if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3064 ctx->phase = 1;
3065 ctx->expected = ZSTD_blockHeaderSize;
3066 return 0;
3067 }
3068
3069 /* Decompress : block header */
3070 if (ctx->phase == 1)
3071 {
3072 blockProperties_t bp;
3073 size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3074 if (ZSTD_isError(blockSize)) return blockSize;
3075 if (bp.blockType == bt_end)
3076 {
3077 ctx->expected = 0;
3078 ctx->phase = 0;
3079 }
3080 else
3081 {
3082 ctx->expected = blockSize;
3083 ctx->bType = bp.blockType;
3084 ctx->phase = 2;
3085 }
3086
3087 return 0;
3088 }
3089
3090 /* Decompress : block content */
3091 {
3092 size_t rSize;
3093 switch(ctx->bType)
3094 {
3095 case bt_compressed:
3096 rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3097 break;
3098 case bt_raw :
3099 rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3100 break;
3101 case bt_rle :
3102 return ERROR(GENERIC); /* not yet handled */
3103 break;
3104 case bt_end : /* should never happen (filtered at phase 1) */
3105 rSize = 0;
3106 break;
3107 default:
3108 return ERROR(GENERIC);
3109 }
3110 ctx->phase = 1;
3111 ctx->expected = ZSTD_blockHeaderSize;
3112 ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3113 return rSize;
3114 }
3115
3116}
3117
3118
3119/* wrapper layer */
3120
3121unsigned ZSTDv03_isError(size_t code)
3122{
3123 return ZSTD_isError(code);
3124}
3125
3126size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3127 const void* src, size_t compressedSize)
3128{
3129 return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3130}
3131
khenaidooac637102019-01-14 15:44:34 -05003132ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3133{
3134 return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3135}
3136
3137size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3138{
3139 return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3140}
3141
3142size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3143{
3144 return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3145}
3146
3147size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3148{
3149 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3150}
3151
3152size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3153{
3154 return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);
3155}