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