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