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