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