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