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