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