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