2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
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.
12 #include <stddef.h> /* size_t, ptrdiff_t */
14 #include "error_private.h"
17 /******************************************
19 ******************************************/
20 #if defined(_MSC_VER) /* Visual Studio */
21 # include <stdlib.h> /* _byteswap_ulong */
22 # include <intrin.h> /* _byteswap_* */
26 /* ******************************************************************
28 low-level memory access routines
29 Copyright (C) 2013-2015, Yann Collet.
31 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
33 Redistribution and use in source and binary forms, with or without
34 modification, are permitted provided that the following conditions are
37 * Redistributions of source code must retain the above copyright
38 notice, this list of conditions and the following disclaimer.
39 * Redistributions in binary form must reproduce the above
40 copyright notice, this list of conditions and the following disclaimer
41 in the documentation and/or other materials provided with the
44 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
45 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
46 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
47 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
48 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
49 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
50 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
51 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
52 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
53 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
54 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
56 You can contact the author at :
57 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
58 - Public forum : https://groups.google.com/forum/#!forum/lz4c
59 ****************************************************************** */
63 #if defined (__cplusplus)
67 /******************************************
69 ******************************************/
70 #include <stddef.h> /* size_t, ptrdiff_t */
71 #include <string.h> /* memcpy */
74 /******************************************
76 ******************************************/
78 # define MEM_STATIC static __attribute__((unused))
79 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
80 # define MEM_STATIC static inline
81 #elif defined(_MSC_VER)
82 # define MEM_STATIC static __inline
84 # define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
88 /****************************************************************
90 *****************************************************************/
91 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
101 typedef unsigned char BYTE
;
102 typedef unsigned short U16
;
103 typedef signed short S16
;
104 typedef unsigned int U32
;
105 typedef signed int S32
;
106 typedef unsigned long long U64
;
107 typedef signed long long S64
;
111 /****************************************************************
113 *****************************************************************/
114 /* MEM_FORCE_MEMORY_ACCESS
115 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
116 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
117 * The below switch allow to select different access method for improved performance.
118 * Method 0 (default) : use `memcpy()`. Safe and portable.
119 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
120 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
121 * Method 2 : direct access. This method is portable but violate C standard.
122 * It can generate buggy code on targets generating assembly depending on alignment.
123 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
124 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
125 * Prefer these methods in priority order (0 > 1 > 2)
127 #ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
128 # 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__) )
129 # define MEM_FORCE_MEMORY_ACCESS 2
130 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
131 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
132 # define MEM_FORCE_MEMORY_ACCESS 1
136 MEM_STATIC
unsigned MEM_32bits(void) { return sizeof(void*)==4; }
137 MEM_STATIC
unsigned MEM_64bits(void) { return sizeof(void*)==8; }
139 MEM_STATIC
unsigned MEM_isLittleEndian(void)
141 const union { U32 u
; BYTE c
[4]; } one
= { 1 }; /* don't use static : performance detrimental */
145 #if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
147 /* violates C standard on structure alignment.
148 Only use if no other choice to achieve best performance on target platform */
149 MEM_STATIC U16
MEM_read16(const void* memPtr
) { return *(const U16
*) memPtr
; }
150 MEM_STATIC U32
MEM_read32(const void* memPtr
) { return *(const U32
*) memPtr
; }
151 MEM_STATIC U64
MEM_read64(const void* memPtr
) { return *(const U64
*) memPtr
; }
153 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { *(U16
*)memPtr
= value
; }
155 #elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
157 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
158 /* currently only defined for gcc and icc */
159 typedef union { U16 u16
; U32 u32
; U64 u64
; } __attribute__((packed
)) unalign
;
161 MEM_STATIC U16
MEM_read16(const void* ptr
) { return ((const unalign
*)ptr
)->u16
; }
162 MEM_STATIC U32
MEM_read32(const void* ptr
) { return ((const unalign
*)ptr
)->u32
; }
163 MEM_STATIC U64
MEM_read64(const void* ptr
) { return ((const unalign
*)ptr
)->u64
; }
165 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
) { ((unalign
*)memPtr
)->u16
= value
; }
169 /* default method, safe and standard.
170 can sometimes prove slower */
172 MEM_STATIC U16
MEM_read16(const void* memPtr
)
174 U16 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
177 MEM_STATIC U32
MEM_read32(const void* memPtr
)
179 U32 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
182 MEM_STATIC U64
MEM_read64(const void* memPtr
)
184 U64 val
; memcpy(&val
, memPtr
, sizeof(val
)); return val
;
187 MEM_STATIC
void MEM_write16(void* memPtr
, U16 value
)
189 memcpy(memPtr
, &value
, sizeof(value
));
192 #endif // MEM_FORCE_MEMORY_ACCESS
195 MEM_STATIC U16
MEM_readLE16(const void* memPtr
)
197 if (MEM_isLittleEndian())
198 return MEM_read16(memPtr
);
201 const BYTE
* p
= (const BYTE
*)memPtr
;
202 return (U16
)(p
[0] + (p
[1]<<8));
206 MEM_STATIC
void MEM_writeLE16(void* memPtr
, U16 val
)
208 if (MEM_isLittleEndian())
210 MEM_write16(memPtr
, val
);
214 BYTE
* p
= (BYTE
*)memPtr
;
216 p
[1] = (BYTE
)(val
>>8);
220 MEM_STATIC U32
MEM_readLE32(const void* memPtr
)
222 if (MEM_isLittleEndian())
223 return MEM_read32(memPtr
);
226 const BYTE
* p
= (const BYTE
*)memPtr
;
227 return (U32
)((U32
)p
[0] + ((U32
)p
[1]<<8) + ((U32
)p
[2]<<16) + ((U32
)p
[3]<<24));
232 MEM_STATIC U64
MEM_readLE64(const void* memPtr
)
234 if (MEM_isLittleEndian())
235 return MEM_read64(memPtr
);
238 const BYTE
* p
= (const BYTE
*)memPtr
;
239 return (U64
)((U64
)p
[0] + ((U64
)p
[1]<<8) + ((U64
)p
[2]<<16) + ((U64
)p
[3]<<24)
240 + ((U64
)p
[4]<<32) + ((U64
)p
[5]<<40) + ((U64
)p
[6]<<48) + ((U64
)p
[7]<<56));
245 MEM_STATIC
size_t MEM_readLEST(const void* memPtr
)
248 return (size_t)MEM_readLE32(memPtr
);
250 return (size_t)MEM_readLE64(memPtr
);
253 #if defined (__cplusplus)
257 #endif /* MEM_H_MODULE */
260 /* ******************************************************************
262 Part of NewGen Entropy library
263 header file (to include)
264 Copyright (C) 2013-2015, Yann Collet.
266 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
268 Redistribution and use in source and binary forms, with or without
269 modification, are permitted provided that the following conditions are
272 * Redistributions of source code must retain the above copyright
273 notice, this list of conditions and the following disclaimer.
274 * Redistributions in binary form must reproduce the above
275 copyright notice, this list of conditions and the following disclaimer
276 in the documentation and/or other materials provided with the
279 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
280 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
281 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
282 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
283 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
284 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
285 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
286 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
287 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
288 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
289 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
291 You can contact the author at :
292 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
293 - Public forum : https://groups.google.com/forum/#!forum/lz4c
294 ****************************************************************** */
295 #ifndef BITSTREAM_H_MODULE
296 #define BITSTREAM_H_MODULE
298 #if defined (__cplusplus)
304 * This API consists of small unitary functions, which highly benefit from being inlined.
305 * Since link-time-optimization is not available for all compilers,
306 * these functions are defined into a .h to be included.
310 /**********************************************
311 * bitStream decompression API (read backward)
312 **********************************************/
316 unsigned bitsConsumed
;
321 typedef enum { BIT_DStream_unfinished
= 0,
322 BIT_DStream_endOfBuffer
= 1,
323 BIT_DStream_completed
= 2,
324 BIT_DStream_overflow
= 3 } BIT_DStream_status
; /* result of BIT_reloadDStream() */
325 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
327 MEM_STATIC
size_t BIT_initDStream(BIT_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
);
328 MEM_STATIC
size_t BIT_readBits(BIT_DStream_t
* bitD
, unsigned nbBits
);
329 MEM_STATIC BIT_DStream_status
BIT_reloadDStream(BIT_DStream_t
* bitD
);
330 MEM_STATIC
unsigned BIT_endOfDStream(const BIT_DStream_t
* bitD
);
333 /******************************************
335 ******************************************/
336 MEM_STATIC
size_t BIT_readBitsFast(BIT_DStream_t
* bitD
, unsigned nbBits
);
337 /* faster, but works only if nbBits >= 1 */
341 /****************************************************************
343 ****************************************************************/
344 MEM_STATIC
unsigned BIT_highbit32 (U32 val
)
346 # if defined(_MSC_VER) /* Visual */
348 _BitScanReverse ( &r
, val
);
350 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
351 return 31 - __builtin_clz (val
);
352 # else /* Software version */
353 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 };
361 r
= DeBruijnClz
[ (U32
) (v
* 0x07C4ACDDU
) >> 27];
368 /**********************************************************
370 **********************************************************/
373 * Initialize a BIT_DStream_t.
374 * @bitD : a pointer to an already allocated BIT_DStream_t structure
375 * @srcBuffer must point at the beginning of a bitStream
376 * @srcSize must be the exact size of the bitStream
377 * @result : size of stream (== srcSize) or an errorCode if a problem is detected
379 MEM_STATIC
size_t BIT_initDStream(BIT_DStream_t
* bitD
, const void* srcBuffer
, size_t srcSize
)
381 if (srcSize
< 1) { memset(bitD
, 0, sizeof(*bitD
)); return ERROR(srcSize_wrong
); }
383 if (srcSize
>= sizeof(size_t)) /* normal case */
386 bitD
->start
= (const char*)srcBuffer
;
387 bitD
->ptr
= (const char*)srcBuffer
+ srcSize
- sizeof(size_t);
388 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
389 contain32
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
390 if (contain32
== 0) return ERROR(GENERIC
); /* endMark not present */
391 bitD
->bitsConsumed
= 8 - BIT_highbit32(contain32
);
396 bitD
->start
= (const char*)srcBuffer
;
397 bitD
->ptr
= bitD
->start
;
398 bitD
->bitContainer
= *(const BYTE
*)(bitD
->start
);
401 case 7: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[6]) << (sizeof(size_t)*8 - 16);
403 case 6: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[5]) << (sizeof(size_t)*8 - 24);
405 case 5: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[4]) << (sizeof(size_t)*8 - 32);
407 case 4: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[3]) << 24;
409 case 3: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[2]) << 16;
411 case 2: bitD
->bitContainer
+= (size_t)(((const BYTE
*)(bitD
->start
))[1]) << 8;
415 contain32
= ((const BYTE
*)srcBuffer
)[srcSize
-1];
416 if (contain32
== 0) return ERROR(GENERIC
); /* endMark not present */
417 bitD
->bitsConsumed
= 8 - BIT_highbit32(contain32
);
418 bitD
->bitsConsumed
+= (U32
)(sizeof(size_t) - srcSize
)*8;
424 MEM_STATIC
size_t BIT_lookBits(BIT_DStream_t
* bitD
, U32 nbBits
)
426 const U32 bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
427 return ((bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> 1) >> ((bitMask
-nbBits
) & bitMask
);
430 /*! BIT_lookBitsFast :
431 * unsafe version; only works only if nbBits >= 1 */
432 MEM_STATIC
size_t BIT_lookBitsFast(BIT_DStream_t
* bitD
, U32 nbBits
)
434 const U32 bitMask
= sizeof(bitD
->bitContainer
)*8 - 1;
435 return (bitD
->bitContainer
<< (bitD
->bitsConsumed
& bitMask
)) >> (((bitMask
+1)-nbBits
) & bitMask
);
438 MEM_STATIC
void BIT_skipBits(BIT_DStream_t
* bitD
, U32 nbBits
)
440 bitD
->bitsConsumed
+= nbBits
;
443 MEM_STATIC
size_t BIT_readBits(BIT_DStream_t
* bitD
, U32 nbBits
)
445 size_t value
= BIT_lookBits(bitD
, nbBits
);
446 BIT_skipBits(bitD
, nbBits
);
450 /*!BIT_readBitsFast :
451 * unsafe version; only works only if nbBits >= 1 */
452 MEM_STATIC
size_t BIT_readBitsFast(BIT_DStream_t
* bitD
, U32 nbBits
)
454 size_t value
= BIT_lookBitsFast(bitD
, nbBits
);
455 BIT_skipBits(bitD
, nbBits
);
459 MEM_STATIC BIT_DStream_status
BIT_reloadDStream(BIT_DStream_t
* bitD
)
461 if (bitD
->bitsConsumed
> (sizeof(bitD
->bitContainer
)*8)) /* should never happen */
462 return BIT_DStream_overflow
;
464 if (bitD
->ptr
>= bitD
->start
+ sizeof(bitD
->bitContainer
))
466 bitD
->ptr
-= bitD
->bitsConsumed
>> 3;
467 bitD
->bitsConsumed
&= 7;
468 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
);
469 return BIT_DStream_unfinished
;
471 if (bitD
->ptr
== bitD
->start
)
473 if (bitD
->bitsConsumed
< sizeof(bitD
->bitContainer
)*8) return BIT_DStream_endOfBuffer
;
474 return BIT_DStream_completed
;
477 U32 nbBytes
= bitD
->bitsConsumed
>> 3;
478 BIT_DStream_status result
= BIT_DStream_unfinished
;
479 if (bitD
->ptr
- nbBytes
< bitD
->start
)
481 nbBytes
= (U32
)(bitD
->ptr
- bitD
->start
); /* ptr > start */
482 result
= BIT_DStream_endOfBuffer
;
484 bitD
->ptr
-= nbBytes
;
485 bitD
->bitsConsumed
-= nbBytes
*8;
486 bitD
->bitContainer
= MEM_readLEST(bitD
->ptr
); /* reminder : srcSize > sizeof(bitD) */
492 * @return Tells if DStream has reached its exact end
494 MEM_STATIC
unsigned BIT_endOfDStream(const BIT_DStream_t
* DStream
)
496 return ((DStream
->ptr
== DStream
->start
) && (DStream
->bitsConsumed
== sizeof(DStream
->bitContainer
)*8));
499 #if defined (__cplusplus)
503 #endif /* BITSTREAM_H_MODULE */
504 /* ******************************************************************
505 Error codes and messages
506 Copyright (C) 2013-2015, Yann Collet
508 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
510 Redistribution and use in source and binary forms, with or without
511 modification, are permitted provided that the following conditions are
514 * Redistributions of source code must retain the above copyright
515 notice, this list of conditions and the following disclaimer.
516 * Redistributions in binary form must reproduce the above
517 copyright notice, this list of conditions and the following disclaimer
518 in the documentation and/or other materials provided with the
521 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
522 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
523 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
524 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
525 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
526 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
527 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
528 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
529 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
530 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
531 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
533 You can contact the author at :
534 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
535 - Public forum : https://groups.google.com/forum/#!forum/lz4c
536 ****************************************************************** */
537 #ifndef ERROR_H_MODULE
538 #define ERROR_H_MODULE
540 #if defined (__cplusplus)
545 /******************************************
547 ******************************************/
548 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
549 # define ERR_STATIC static inline
550 #elif defined(_MSC_VER)
551 # define ERR_STATIC static __inline
552 #elif defined(__GNUC__)
553 # define ERR_STATIC static __attribute__((unused))
555 # define ERR_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
559 /******************************************
561 ******************************************/
562 #define PREFIX(name) ZSTD_error_##name
564 #define ERROR(name) (size_t)-PREFIX(name)
566 #define ERROR_LIST(ITEM) \
567 ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
568 ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
569 ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
570 ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
571 ITEM(PREFIX(maxCode))
573 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
574 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM
) } ERR_codes
; /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
576 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
577 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
578 static const char* ERR_strings
[] = { ERROR_LIST(ERROR_GENERATE_STRING
) };
580 ERR_STATIC
unsigned ERR_isError(size_t code
) { return (code
> ERROR(maxCode
)); }
582 ERR_STATIC
const char* ERR_getErrorName(size_t code
)
584 static const char* codeError
= "Unspecified error code";
585 if (ERR_isError(code
)) return ERR_strings
[-(int)(code
)];
590 #if defined (__cplusplus)
594 #endif /* ERROR_H_MODULE */
596 Constructor and Destructor of type FSE_CTable
597 Note that its size depends on 'tableLog' and 'maxSymbolValue' */
598 typedef unsigned FSE_CTable
; /* don't allocate that. It's just a way to be more restrictive than void* */
599 typedef unsigned FSE_DTable
; /* don't allocate that. It's just a way to be more restrictive than void* */
602 /* ******************************************************************
603 FSE : Finite State Entropy coder
604 header file for static linking (only)
605 Copyright (C) 2013-2015, Yann Collet
607 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
609 Redistribution and use in source and binary forms, with or without
610 modification, are permitted provided that the following conditions are
613 * Redistributions of source code must retain the above copyright
614 notice, this list of conditions and the following disclaimer.
615 * Redistributions in binary form must reproduce the above
616 copyright notice, this list of conditions and the following disclaimer
617 in the documentation and/or other materials provided with the
620 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
621 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
622 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
623 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
624 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
625 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
626 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
627 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
628 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
629 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
630 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
632 You can contact the author at :
633 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
634 - Public forum : https://groups.google.com/forum/#!forum/lz4c
635 ****************************************************************** */
636 #if defined (__cplusplus)
641 /******************************************
643 ******************************************/
644 /* FSE buffer bounds */
645 #define FSE_NCOUNTBOUND 512
646 #define FSE_BLOCKBOUND(size) (size + (size>>7))
647 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
649 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
650 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue) (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
651 #define FSE_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
654 /******************************************
656 ******************************************/
657 static size_t FSE_buildDTable_raw (FSE_DTable
* dt
, unsigned nbBits
);
658 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
660 static size_t FSE_buildDTable_rle (FSE_DTable
* dt
, unsigned char symbolValue
);
661 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
664 /******************************************
665 * FSE symbol decompression API
666 ******************************************/
670 const void* table
; /* precise table may vary, depending on U16 */
674 static void FSE_initDState(FSE_DState_t
* DStatePtr
, BIT_DStream_t
* bitD
, const FSE_DTable
* dt
);
676 static unsigned char FSE_decodeSymbol(FSE_DState_t
* DStatePtr
, BIT_DStream_t
* bitD
);
678 static unsigned FSE_endOfDState(const FSE_DState_t
* DStatePtr
);
681 /******************************************
683 ******************************************/
684 static unsigned char FSE_decodeSymbolFast(FSE_DState_t
* DStatePtr
, BIT_DStream_t
* bitD
);
685 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
688 /******************************************
689 * Implementation of inline functions
690 ******************************************/
697 } FSE_DTableHeader
; /* sizeof U32 */
701 unsigned short newState
;
702 unsigned char symbol
;
703 unsigned char nbBits
;
704 } FSE_decode_t
; /* size == U32 */
706 MEM_STATIC
void FSE_initDState(FSE_DState_t
* DStatePtr
, BIT_DStream_t
* bitD
, const FSE_DTable
* dt
)
708 FSE_DTableHeader DTableH
;
709 memcpy(&DTableH
, dt
, sizeof(DTableH
));
710 DStatePtr
->state
= BIT_readBits(bitD
, DTableH
.tableLog
);
711 BIT_reloadDStream(bitD
);
712 DStatePtr
->table
= dt
+ 1;
715 MEM_STATIC BYTE
FSE_decodeSymbol(FSE_DState_t
* DStatePtr
, BIT_DStream_t
* bitD
)
717 const FSE_decode_t DInfo
= ((const FSE_decode_t
*)(DStatePtr
->table
))[DStatePtr
->state
];
718 const U32 nbBits
= DInfo
.nbBits
;
719 BYTE symbol
= DInfo
.symbol
;
720 size_t lowBits
= BIT_readBits(bitD
, nbBits
);
722 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
726 MEM_STATIC BYTE
FSE_decodeSymbolFast(FSE_DState_t
* DStatePtr
, BIT_DStream_t
* bitD
)
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_readBitsFast(bitD
, nbBits
);
733 DStatePtr
->state
= DInfo
.newState
+ lowBits
;
737 MEM_STATIC
unsigned FSE_endOfDState(const FSE_DState_t
* DStatePtr
)
739 return DStatePtr
->state
== 0;
743 #if defined (__cplusplus)
746 /* ******************************************************************
747 Huff0 : Huffman coder, part of New Generation Entropy library
748 header file for static linking (only)
749 Copyright (C) 2013-2015, Yann Collet
751 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
753 Redistribution and use in source and binary forms, with or without
754 modification, are permitted provided that the following conditions are
757 * Redistributions of source code must retain the above copyright
758 notice, this list of conditions and the following disclaimer.
759 * Redistributions in binary form must reproduce the above
760 copyright notice, this list of conditions and the following disclaimer
761 in the documentation and/or other materials provided with the
764 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
765 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
766 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
767 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
768 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
769 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
770 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
771 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
772 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
773 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
774 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
776 You can contact the author at :
777 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
778 - Public forum : https://groups.google.com/forum/#!forum/lz4c
779 ****************************************************************** */
781 #if defined (__cplusplus)
785 /******************************************
786 * Static allocation macros
787 ******************************************/
788 /* Huff0 buffer bounds */
789 #define HUF_CTABLEBOUND 129
790 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8) /* only true if incompressible pre-filtered with fast heuristic */
791 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size)) /* Macro version, useful for static allocation */
793 /* static allocation of Huff0's DTable */
794 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog)) /* nb Cells; use unsigned short for X2, unsigned int for X4 */
795 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
796 unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
797 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
798 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
799 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
800 unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
803 /******************************************
805 ******************************************/
806 static size_t HUF_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* single-symbol decoder */
807 static size_t HUF_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* double-symbols decoder */
808 static size_t HUF_decompress4X6 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
); /* quad-symbols decoder */
811 #if defined (__cplusplus)
816 zstd - standard compression library
818 Copyright (C) 2014-2015, Yann Collet.
820 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
822 Redistribution and use in source and binary forms, with or without
823 modification, are permitted provided that the following conditions are
825 * Redistributions of source code must retain the above copyright
826 notice, this list of conditions and the following disclaimer.
827 * Redistributions in binary form must reproduce the above
828 copyright notice, this list of conditions and the following disclaimer
829 in the documentation and/or other materials provided with the
831 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
832 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
833 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
834 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
835 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
836 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
837 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
838 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
839 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
840 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
841 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
843 You can contact the author at :
844 - zstd source repository : https://github.com/Cyan4973/zstd
845 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
848 #if defined (__cplusplus)
852 /* *************************************
854 ***************************************/
855 #include <stddef.h> /* size_t */
858 /* *************************************
860 ***************************************/
861 #define ZSTD_VERSION_MAJOR 0 /* for breaking interface changes */
862 #define ZSTD_VERSION_MINOR 2 /* for new (non-breaking) interface capabilities */
863 #define ZSTD_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */
864 #define ZSTD_VERSION_NUMBER (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
867 /* *************************************
869 ***************************************/
870 typedef struct ZSTD_CCtx_s ZSTD_CCtx
; /* incomplete type */
872 #if defined (__cplusplus)
876 zstd - standard compression library
877 Header File for static linking only
878 Copyright (C) 2014-2015, Yann Collet.
880 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
882 Redistribution and use in source and binary forms, with or without
883 modification, are permitted provided that the following conditions are
885 * Redistributions of source code must retain the above copyright
886 notice, this list of conditions and the following disclaimer.
887 * Redistributions in binary form must reproduce the above
888 copyright notice, this list of conditions and the following disclaimer
889 in the documentation and/or other materials provided with the
891 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
892 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
893 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
894 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
895 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
896 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
897 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
898 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
899 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
900 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
901 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
903 You can contact the author at :
904 - zstd source repository : https://github.com/Cyan4973/zstd
905 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
908 /* The objects defined into this file should be considered experimental.
909 * They are not labelled stable, as their prototype may change in the future.
910 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
913 #if defined (__cplusplus)
917 /* *************************************
918 * Streaming functions
919 ***************************************/
921 typedef struct ZSTD_DCtx_s ZSTD_DCtx
;
924 Use above functions alternatively.
925 ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
926 ZSTD_decompressContinue() will use previous data blocks to improve compression if they are located prior to current block.
927 Result is the number of bytes regenerated within 'dst'.
928 It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
931 /* *************************************
932 * Prefix - version detection
933 ***************************************/
934 #define ZSTD_magicNumber 0xFD2FB522 /* v0.2 (current)*/
937 #if defined (__cplusplus)
940 /* ******************************************************************
941 FSE : Finite State Entropy coder
942 Copyright (C) 2013-2015, Yann Collet.
944 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
946 Redistribution and use in source and binary forms, with or without
947 modification, are permitted provided that the following conditions are
950 * Redistributions of source code must retain the above copyright
951 notice, this list of conditions and the following disclaimer.
952 * Redistributions in binary form must reproduce the above
953 copyright notice, this list of conditions and the following disclaimer
954 in the documentation and/or other materials provided with the
957 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
958 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
959 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
960 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
961 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
962 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
963 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
964 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
965 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
966 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
967 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
969 You can contact the author at :
970 - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
971 - Public forum : https://groups.google.com/forum/#!forum/lz4c
972 ****************************************************************** */
974 #ifndef FSE_COMMONDEFS_ONLY
976 /****************************************************************
978 ****************************************************************/
980 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
981 * Increasing memory usage improves compression ratio
982 * Reduced memory usage can improve speed, due to cache effect
983 * Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
984 #define FSE_MAX_MEMORY_USAGE 14
985 #define FSE_DEFAULT_MEMORY_USAGE 13
987 /* FSE_MAX_SYMBOL_VALUE :
988 * Maximum symbol value authorized.
989 * Required for proper stack allocation */
990 #define FSE_MAX_SYMBOL_VALUE 255
993 /****************************************************************
994 * template functions type & suffix
995 ****************************************************************/
996 #define FSE_FUNCTION_TYPE BYTE
997 #define FSE_FUNCTION_EXTENSION
1000 /****************************************************************
1002 ****************************************************************/
1003 #endif /* !FSE_COMMONDEFS_ONLY */
1006 /****************************************************************
1007 * Compiler specifics
1008 ****************************************************************/
1009 #ifdef _MSC_VER /* Visual Studio */
1010 # define FORCE_INLINE static __forceinline
1011 # include <intrin.h> /* For Visual 2005 */
1012 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1013 # pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1015 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1017 # define FORCE_INLINE static inline __attribute__((always_inline))
1019 # define FORCE_INLINE static inline
1022 # define FORCE_INLINE static
1023 # endif /* __STDC_VERSION__ */
1027 /****************************************************************
1029 ****************************************************************/
1030 #include <stdlib.h> /* malloc, free, qsort */
1031 #include <string.h> /* memcpy, memset */
1032 #include <stdio.h> /* printf (debug) */
1034 /****************************************************************
1036 *****************************************************************/
1037 #define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2)
1038 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
1039 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
1040 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
1041 #define FSE_MIN_TABLELOG 5
1043 #define FSE_TABLELOG_ABSOLUTE_MAX 15
1044 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
1045 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
1049 /****************************************************************
1051 ****************************************************************/
1052 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1055 /****************************************************************
1057 ****************************************************************/
1058 typedef U32 DTable_max_t
[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG
)];
1061 /****************************************************************
1063 ****************************************************************/
1065 designed to be included
1066 for type-specific functions (template emulation in C)
1067 Objective is to write these functions only once, for improved maintenance
1071 #ifndef FSE_FUNCTION_EXTENSION
1072 # error "FSE_FUNCTION_EXTENSION must be defined"
1074 #ifndef FSE_FUNCTION_TYPE
1075 # error "FSE_FUNCTION_TYPE must be defined"
1078 /* Function names */
1079 #define FSE_CAT(X,Y) X##Y
1080 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1081 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1084 /* Function templates */
1086 #define FSE_DECODE_TYPE FSE_decode_t
1088 static U32
FSE_tableStep(U32 tableSize
) { return (tableSize
>>1) + (tableSize
>>3) + 3; }
1090 static size_t FSE_buildDTable
1091 (FSE_DTable
* dt
, const short* normalizedCounter
, unsigned maxSymbolValue
, unsigned tableLog
)
1094 FSE_DECODE_TYPE
* const tableDecode
= (FSE_DECODE_TYPE
*)ptr
;
1095 FSE_DTableHeader DTableH
;
1096 const U32 tableSize
= 1 << tableLog
;
1097 const U32 tableMask
= tableSize
-1;
1098 const U32 step
= FSE_tableStep(tableSize
);
1099 U16 symbolNext
[FSE_MAX_SYMBOL_VALUE
+1];
1101 U32 highThreshold
= tableSize
-1;
1102 const S16 largeLimit
= (S16
)(1 << (tableLog
-1));
1107 if (maxSymbolValue
> FSE_MAX_SYMBOL_VALUE
) return ERROR(maxSymbolValue_tooLarge
);
1108 if (tableLog
> FSE_MAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
1110 /* Init, lay down lowprob symbols */
1111 DTableH
.tableLog
= (U16
)tableLog
;
1112 for (s
=0; s
<=maxSymbolValue
; s
++)
1114 if (normalizedCounter
[s
]==-1)
1116 tableDecode
[highThreshold
--].symbol
= (FSE_FUNCTION_TYPE
)s
;
1121 if (normalizedCounter
[s
] >= largeLimit
) noLarge
=0;
1122 symbolNext
[s
] = normalizedCounter
[s
];
1126 /* Spread symbols */
1127 for (s
=0; s
<=maxSymbolValue
; s
++)
1130 for (i
=0; i
<normalizedCounter
[s
]; i
++)
1132 tableDecode
[position
].symbol
= (FSE_FUNCTION_TYPE
)s
;
1133 position
= (position
+ step
) & tableMask
;
1134 while (position
> highThreshold
) position
= (position
+ step
) & tableMask
; /* lowprob area */
1138 if (position
!=0) return ERROR(GENERIC
); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1140 /* Build Decoding table */
1143 for (i
=0; i
<tableSize
; i
++)
1145 FSE_FUNCTION_TYPE symbol
= (FSE_FUNCTION_TYPE
)(tableDecode
[i
].symbol
);
1146 U16 nextState
= symbolNext
[symbol
]++;
1147 tableDecode
[i
].nbBits
= (BYTE
) (tableLog
- BIT_highbit32 ((U32
)nextState
) );
1148 tableDecode
[i
].newState
= (U16
) ( (nextState
<< tableDecode
[i
].nbBits
) - tableSize
);
1152 DTableH
.fastMode
= (U16
)noLarge
;
1153 memcpy(dt
, &DTableH
, sizeof(DTableH
)); /* memcpy(), to avoid strict aliasing warnings */
1158 #ifndef FSE_COMMONDEFS_ONLY
1159 /******************************************
1160 * FSE helper functions
1161 ******************************************/
1162 static unsigned FSE_isError(size_t code
) { return ERR_isError(code
); }
1165 /****************************************************************
1166 * FSE NCount encoding-decoding
1167 ****************************************************************/
1168 static short FSE_abs(short a
)
1170 return (short)(a
<0 ? -a
: a
);
1173 static size_t FSE_readNCount (short* normalizedCounter
, unsigned* maxSVPtr
, unsigned* tableLogPtr
,
1174 const void* headerBuffer
, size_t hbSize
)
1176 const BYTE
* const istart
= (const BYTE
*) headerBuffer
;
1177 const BYTE
* const iend
= istart
+ hbSize
;
1178 const BYTE
* ip
= istart
;
1184 unsigned charnum
= 0;
1187 if (hbSize
< 4) return ERROR(srcSize_wrong
);
1188 bitStream
= MEM_readLE32(ip
);
1189 nbBits
= (bitStream
& 0xF) + FSE_MIN_TABLELOG
; /* extract tableLog */
1190 if (nbBits
> FSE_TABLELOG_ABSOLUTE_MAX
) return ERROR(tableLog_tooLarge
);
1193 *tableLogPtr
= nbBits
;
1194 remaining
= (1<<nbBits
)+1;
1195 threshold
= 1<<nbBits
;
1198 while ((remaining
>1) && (charnum
<=*maxSVPtr
))
1202 unsigned n0
= charnum
;
1203 while ((bitStream
& 0xFFFF) == 0xFFFF)
1209 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1217 while ((bitStream
& 3) == 3)
1223 n0
+= bitStream
& 3;
1225 if (n0
> *maxSVPtr
) return ERROR(maxSymbolValue_tooSmall
);
1226 while (charnum
< n0
) normalizedCounter
[charnum
++] = 0;
1227 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4))
1231 bitStream
= MEM_readLE32(ip
) >> bitCount
;
1237 const short max
= (short)((2*threshold
-1)-remaining
);
1240 if ((bitStream
& (threshold
-1)) < (U32
)max
)
1242 count
= (short)(bitStream
& (threshold
-1));
1243 bitCount
+= nbBits
-1;
1247 count
= (short)(bitStream
& (2*threshold
-1));
1248 if (count
>= threshold
) count
-= max
;
1252 count
--; /* extra accuracy */
1253 remaining
-= FSE_abs(count
);
1254 normalizedCounter
[charnum
++] = count
;
1256 while (remaining
< threshold
)
1263 if ((ip
<= iend
-7) || (ip
+ (bitCount
>>3) <= iend
-4))
1270 bitCount
-= (int)(8 * (iend
- 4 - ip
));
1273 bitStream
= MEM_readLE32(ip
) >> (bitCount
& 31);
1277 if (remaining
!= 1) return ERROR(GENERIC
);
1278 *maxSVPtr
= charnum
-1;
1280 ip
+= (bitCount
+7)>>3;
1281 if ((size_t)(ip
-istart
) > hbSize
) return ERROR(srcSize_wrong
);
1286 /*********************************************************
1287 * Decompression (Byte symbols)
1288 *********************************************************/
1289 static size_t FSE_buildDTable_rle (FSE_DTable
* dt
, BYTE symbolValue
)
1292 FSE_DTableHeader
* const DTableH
= (FSE_DTableHeader
*)ptr
;
1293 FSE_decode_t
* const cell
= (FSE_decode_t
*)(ptr
) + 1; /* because dt is unsigned */
1295 DTableH
->tableLog
= 0;
1296 DTableH
->fastMode
= 0;
1299 cell
->symbol
= symbolValue
;
1306 static size_t FSE_buildDTable_raw (FSE_DTable
* dt
, unsigned nbBits
)
1309 FSE_DTableHeader
* const DTableH
= (FSE_DTableHeader
*)ptr
;
1310 FSE_decode_t
* const dinfo
= (FSE_decode_t
*)(ptr
) + 1; /* because dt is unsigned */
1311 const unsigned tableSize
= 1 << nbBits
;
1312 const unsigned tableMask
= tableSize
- 1;
1313 const unsigned maxSymbolValue
= tableMask
;
1317 if (nbBits
< 1) return ERROR(GENERIC
); /* min size */
1319 /* Build Decoding Table */
1320 DTableH
->tableLog
= (U16
)nbBits
;
1321 DTableH
->fastMode
= 1;
1322 for (s
=0; s
<=maxSymbolValue
; s
++)
1324 dinfo
[s
].newState
= 0;
1325 dinfo
[s
].symbol
= (BYTE
)s
;
1326 dinfo
[s
].nbBits
= (BYTE
)nbBits
;
1332 FORCE_INLINE
size_t FSE_decompress_usingDTable_generic(
1333 void* dst
, size_t maxDstSize
,
1334 const void* cSrc
, size_t cSrcSize
,
1335 const FSE_DTable
* dt
, const unsigned fast
)
1337 BYTE
* const ostart
= (BYTE
*) dst
;
1339 BYTE
* const omax
= op
+ maxDstSize
;
1340 BYTE
* const olimit
= omax
-3;
1343 FSE_DState_t state1
;
1344 FSE_DState_t state2
;
1348 errorCode
= BIT_initDStream(&bitD
, cSrc
, cSrcSize
); /* replaced last arg by maxCompressed Size */
1349 if (FSE_isError(errorCode
)) return errorCode
;
1351 FSE_initDState(&state1
, &bitD
, dt
);
1352 FSE_initDState(&state2
, &bitD
, dt
);
1354 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1356 /* 4 symbols per loop */
1357 for ( ; (BIT_reloadDStream(&bitD
)==BIT_DStream_unfinished
) && (op
<olimit
) ; op
+=4)
1359 op
[0] = FSE_GETSYMBOL(&state1
);
1361 if (FSE_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1362 BIT_reloadDStream(&bitD
);
1364 op
[1] = FSE_GETSYMBOL(&state2
);
1366 if (FSE_MAX_TABLELOG
*4+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1367 { if (BIT_reloadDStream(&bitD
) > BIT_DStream_unfinished
) { op
+=2; break; } }
1369 op
[2] = FSE_GETSYMBOL(&state1
);
1371 if (FSE_MAX_TABLELOG
*2+7 > sizeof(bitD
.bitContainer
)*8) /* This test must be static */
1372 BIT_reloadDStream(&bitD
);
1374 op
[3] = FSE_GETSYMBOL(&state2
);
1378 /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1381 if ( (BIT_reloadDStream(&bitD
)>BIT_DStream_completed
) || (op
==omax
) || (BIT_endOfDStream(&bitD
) && (fast
|| FSE_endOfDState(&state1
))) )
1384 *op
++ = FSE_GETSYMBOL(&state1
);
1386 if ( (BIT_reloadDStream(&bitD
)>BIT_DStream_completed
) || (op
==omax
) || (BIT_endOfDStream(&bitD
) && (fast
|| FSE_endOfDState(&state2
))) )
1389 *op
++ = FSE_GETSYMBOL(&state2
);
1393 if (BIT_endOfDStream(&bitD
) && FSE_endOfDState(&state1
) && FSE_endOfDState(&state2
))
1396 if (op
==omax
) return ERROR(dstSize_tooSmall
); /* dst buffer is full, but cSrc unfinished */
1398 return ERROR(corruption_detected
);
1402 static size_t FSE_decompress_usingDTable(void* dst
, size_t originalSize
,
1403 const void* cSrc
, size_t cSrcSize
,
1404 const FSE_DTable
* dt
)
1406 FSE_DTableHeader DTableH
;
1407 memcpy(&DTableH
, dt
, sizeof(DTableH
));
1409 /* select fast mode (static) */
1410 if (DTableH
.fastMode
) return FSE_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 1);
1411 return FSE_decompress_usingDTable_generic(dst
, originalSize
, cSrc
, cSrcSize
, dt
, 0);
1415 static size_t FSE_decompress(void* dst
, size_t maxDstSize
, const void* cSrc
, size_t cSrcSize
)
1417 const BYTE
* const istart
= (const BYTE
*)cSrc
;
1418 const BYTE
* ip
= istart
;
1419 short counting
[FSE_MAX_SYMBOL_VALUE
+1];
1420 DTable_max_t dt
; /* Static analyzer seems unable to understand this table will be properly initialized later */
1422 unsigned maxSymbolValue
= FSE_MAX_SYMBOL_VALUE
;
1425 if (cSrcSize
<2) return ERROR(srcSize_wrong
); /* too small input size */
1427 /* normal FSE decoding mode */
1428 errorCode
= FSE_readNCount (counting
, &maxSymbolValue
, &tableLog
, istart
, cSrcSize
);
1429 if (FSE_isError(errorCode
)) return errorCode
;
1430 if (errorCode
>= cSrcSize
) return ERROR(srcSize_wrong
); /* too small input size */
1432 cSrcSize
-= errorCode
;
1434 errorCode
= FSE_buildDTable (dt
, counting
, maxSymbolValue
, tableLog
);
1435 if (FSE_isError(errorCode
)) return errorCode
;
1437 /* always return, even if it is an error code */
1438 return FSE_decompress_usingDTable (dst
, maxDstSize
, ip
, cSrcSize
, dt
);
1443 #endif /* FSE_COMMONDEFS_ONLY */
1444 /* ******************************************************************
1445 Huff0 : Huffman coder, part of New Generation Entropy library
1446 Copyright (C) 2013-2015, Yann Collet.
1448 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1450 Redistribution and use in source and binary forms, with or without
1451 modification, are permitted provided that the following conditions are
1454 * Redistributions of source code must retain the above copyright
1455 notice, this list of conditions and the following disclaimer.
1456 * Redistributions in binary form must reproduce the above
1457 copyright notice, this list of conditions and the following disclaimer
1458 in the documentation and/or other materials provided with the
1461 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1462 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1463 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1464 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1465 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1466 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1467 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1468 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1469 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1470 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1471 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1473 You can contact the author at :
1474 - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1475 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1476 ****************************************************************** */
1478 /****************************************************************
1479 * Compiler specifics
1480 ****************************************************************/
1481 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1482 /* inline is defined */
1483 #elif defined(_MSC_VER)
1484 # define inline __inline
1486 # define inline /* disable inline */
1490 #ifdef _MSC_VER /* Visual Studio */
1491 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1495 /****************************************************************
1497 ****************************************************************/
1498 #include <stdlib.h> /* malloc, free, qsort */
1499 #include <string.h> /* memcpy, memset */
1500 #include <stdio.h> /* printf (debug) */
1502 /****************************************************************
1504 ****************************************************************/
1505 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1508 /******************************************
1510 ******************************************/
1511 static unsigned HUF_isError(size_t code
) { return ERR_isError(code
); }
1513 #define HUF_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1514 #define HUF_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1515 #define HUF_DEFAULT_TABLELOG HUF_MAX_TABLELOG /* tableLog by default, when not specified */
1516 #define HUF_MAX_SYMBOL_VALUE 255
1517 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1518 # error "HUF_MAX_TABLELOG is too large !"
1523 /*********************************************************
1524 * Huff0 : Huffman block decompression
1525 *********************************************************/
1526 typedef struct { BYTE byte
; BYTE nbBits
; } HUF_DEltX2
; /* single-symbol decoding */
1528 typedef struct { U16 sequence
; BYTE nbBits
; BYTE length
; } HUF_DEltX4
; /* double-symbols decoding */
1530 typedef struct { BYTE symbol
; BYTE weight
; } sortedSymbol_t
;
1533 Read compact Huffman tree, saved by HUF_writeCTable
1534 @huffWeight : destination buffer
1535 @return : size read from `src`
1537 static size_t HUF_readStats(BYTE
* huffWeight
, size_t hwSize
, U32
* rankStats
,
1538 U32
* nbSymbolsPtr
, U32
* tableLogPtr
,
1539 const void* src
, size_t srcSize
)
1543 const BYTE
* ip
= (const BYTE
*) src
;
1548 if (!srcSize
) return ERROR(srcSize_wrong
);
1550 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1552 if (iSize
>= 128) /* special header */
1554 if (iSize
>= (242)) /* RLE */
1556 static int l
[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1557 oSize
= l
[iSize
-242];
1558 memset(huffWeight
, 1, hwSize
);
1561 else /* Incompressible */
1563 oSize
= iSize
- 127;
1564 iSize
= ((oSize
+1)/2);
1565 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1566 if (oSize
>= hwSize
) return ERROR(corruption_detected
);
1568 for (n
=0; n
<oSize
; n
+=2)
1570 huffWeight
[n
] = ip
[n
/2] >> 4;
1571 huffWeight
[n
+1] = ip
[n
/2] & 15;
1575 else /* header compressed with FSE (normal case) */
1577 if (iSize
+1 > srcSize
) return ERROR(srcSize_wrong
);
1578 oSize
= FSE_decompress(huffWeight
, hwSize
-1, ip
+1, iSize
); /* max (hwSize-1) values decoded, as last one is implied */
1579 if (FSE_isError(oSize
)) return oSize
;
1582 /* collect weight stats */
1583 memset(rankStats
, 0, (HUF_ABSOLUTEMAX_TABLELOG
+ 1) * sizeof(U32
));
1585 for (n
=0; n
<oSize
; n
++)
1587 if (huffWeight
[n
] >= HUF_ABSOLUTEMAX_TABLELOG
) return ERROR(corruption_detected
);
1588 rankStats
[huffWeight
[n
]]++;
1589 weightTotal
+= (1 << huffWeight
[n
]) >> 1;
1591 if (weightTotal
== 0) return ERROR(corruption_detected
);
1593 /* get last non-null symbol weight (implied, total must be 2^n) */
1594 tableLog
= BIT_highbit32(weightTotal
) + 1;
1595 if (tableLog
> HUF_ABSOLUTEMAX_TABLELOG
) return ERROR(corruption_detected
);
1597 U32 total
= 1 << tableLog
;
1598 U32 rest
= total
- weightTotal
;
1599 U32 verif
= 1 << BIT_highbit32(rest
);
1600 U32 lastWeight
= BIT_highbit32(rest
) + 1;
1601 if (verif
!= rest
) return ERROR(corruption_detected
); /* last value must be a clean power of 2 */
1602 huffWeight
[oSize
] = (BYTE
)lastWeight
;
1603 rankStats
[lastWeight
]++;
1606 /* check tree construction validity */
1607 if ((rankStats
[1] < 2) || (rankStats
[1] & 1)) return ERROR(corruption_detected
); /* by construction : at least 2 elts of rank 1, must be even */
1610 *nbSymbolsPtr
= (U32
)(oSize
+1);
1611 *tableLogPtr
= tableLog
;
1616 /**************************/
1617 /* single-symbol decoding */
1618 /**************************/
1620 static size_t HUF_readDTableX2 (U16
* DTable
, const void* src
, size_t srcSize
)
1622 BYTE huffWeight
[HUF_MAX_SYMBOL_VALUE
+ 1];
1623 U32 rankVal
[HUF_ABSOLUTEMAX_TABLELOG
+ 1]; /* large enough for values from 0 to 16 */
1625 const BYTE
* ip
= (const BYTE
*) src
;
1626 size_t iSize
= ip
[0];
1630 void* ptr
= DTable
+1;
1631 HUF_DEltX2
* const dt
= (HUF_DEltX2
*)ptr
;
1633 HUF_STATIC_ASSERT(sizeof(HUF_DEltX2
) == sizeof(U16
)); /* if compilation fails here, assertion is false */
1634 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1636 iSize
= HUF_readStats(huffWeight
, HUF_MAX_SYMBOL_VALUE
+ 1, rankVal
, &nbSymbols
, &tableLog
, src
, srcSize
);
1637 if (HUF_isError(iSize
)) return iSize
;
1640 if (tableLog
> DTable
[0]) return ERROR(tableLog_tooLarge
); /* DTable is too small */
1641 DTable
[0] = (U16
)tableLog
; /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1645 for (n
=1; n
<=tableLog
; n
++)
1647 U32 current
= nextRankStart
;
1648 nextRankStart
+= (rankVal
[n
] << (n
-1));
1649 rankVal
[n
] = current
;
1653 for (n
=0; n
<nbSymbols
; n
++)
1655 const U32 w
= huffWeight
[n
];
1656 const U32 length
= (1 << w
) >> 1;
1659 D
.byte
= (BYTE
)n
; D
.nbBits
= (BYTE
)(tableLog
+ 1 - w
);
1660 for (i
= rankVal
[w
]; i
< rankVal
[w
] + length
; i
++)
1662 rankVal
[w
] += length
;
1668 static BYTE
HUF_decodeSymbolX2(BIT_DStream_t
* Dstream
, const HUF_DEltX2
* dt
, const U32 dtLog
)
1670 const size_t val
= BIT_lookBitsFast(Dstream
, dtLog
); /* note : dtLog >= 1 */
1671 const BYTE c
= dt
[val
].byte
;
1672 BIT_skipBits(Dstream
, dt
[val
].nbBits
);
1676 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1677 *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1679 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1680 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1681 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1683 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1685 HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1687 static inline size_t HUF_decodeStreamX2(BYTE
* p
, BIT_DStream_t
* const bitDPtr
, BYTE
* const pEnd
, const HUF_DEltX2
* const dt
, const U32 dtLog
)
1689 BYTE
* const pStart
= p
;
1691 /* up to 4 symbols at a time */
1692 while ((BIT_reloadDStream(bitDPtr
) == BIT_DStream_unfinished
) && (p
<= pEnd
-4))
1694 HUF_DECODE_SYMBOLX2_2(p
, bitDPtr
);
1695 HUF_DECODE_SYMBOLX2_1(p
, bitDPtr
);
1696 HUF_DECODE_SYMBOLX2_2(p
, bitDPtr
);
1697 HUF_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1700 /* closer to the end */
1701 while ((BIT_reloadDStream(bitDPtr
) == BIT_DStream_unfinished
) && (p
< pEnd
))
1702 HUF_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1704 /* no more data to retrieve from bitstream, hence no need to reload */
1706 HUF_DECODE_SYMBOLX2_0(p
, bitDPtr
);
1712 static size_t HUF_decompress4X2_usingDTable(
1713 void* dst
, size_t dstSize
,
1714 const void* cSrc
, size_t cSrcSize
,
1717 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
1720 const BYTE
* const istart
= (const BYTE
*) cSrc
;
1721 BYTE
* const ostart
= (BYTE
*) dst
;
1722 BYTE
* const oend
= ostart
+ dstSize
;
1724 const void* ptr
= DTable
;
1725 const HUF_DEltX2
* const dt
= ((const HUF_DEltX2
*)ptr
) +1;
1726 const U32 dtLog
= DTable
[0];
1730 BIT_DStream_t bitD1
;
1731 BIT_DStream_t bitD2
;
1732 BIT_DStream_t bitD3
;
1733 BIT_DStream_t bitD4
;
1734 const size_t length1
= MEM_readLE16(istart
);
1735 const size_t length2
= MEM_readLE16(istart
+2);
1736 const size_t length3
= MEM_readLE16(istart
+4);
1738 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
1739 const BYTE
* const istart2
= istart1
+ length1
;
1740 const BYTE
* const istart3
= istart2
+ length2
;
1741 const BYTE
* const istart4
= istart3
+ length3
;
1742 const size_t segmentSize
= (dstSize
+3) / 4;
1743 BYTE
* const opStart2
= ostart
+ segmentSize
;
1744 BYTE
* const opStart3
= opStart2
+ segmentSize
;
1745 BYTE
* const opStart4
= opStart3
+ segmentSize
;
1747 BYTE
* op2
= opStart2
;
1748 BYTE
* op3
= opStart3
;
1749 BYTE
* op4
= opStart4
;
1752 length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
1753 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
1754 errorCode
= BIT_initDStream(&bitD1
, istart1
, length1
);
1755 if (HUF_isError(errorCode
)) return errorCode
;
1756 errorCode
= BIT_initDStream(&bitD2
, istart2
, length2
);
1757 if (HUF_isError(errorCode
)) return errorCode
;
1758 errorCode
= BIT_initDStream(&bitD3
, istart3
, length3
);
1759 if (HUF_isError(errorCode
)) return errorCode
;
1760 errorCode
= BIT_initDStream(&bitD4
, istart4
, length4
);
1761 if (HUF_isError(errorCode
)) return errorCode
;
1763 /* 16-32 symbols per loop (4-8 symbols per stream) */
1764 endSignal
= BIT_reloadDStream(&bitD1
) | BIT_reloadDStream(&bitD2
) | BIT_reloadDStream(&bitD3
) | BIT_reloadDStream(&bitD4
);
1765 for ( ; (endSignal
==BIT_DStream_unfinished
) && (op4
<(oend
-7)) ; )
1767 HUF_DECODE_SYMBOLX2_2(op1
, &bitD1
);
1768 HUF_DECODE_SYMBOLX2_2(op2
, &bitD2
);
1769 HUF_DECODE_SYMBOLX2_2(op3
, &bitD3
);
1770 HUF_DECODE_SYMBOLX2_2(op4
, &bitD4
);
1771 HUF_DECODE_SYMBOLX2_1(op1
, &bitD1
);
1772 HUF_DECODE_SYMBOLX2_1(op2
, &bitD2
);
1773 HUF_DECODE_SYMBOLX2_1(op3
, &bitD3
);
1774 HUF_DECODE_SYMBOLX2_1(op4
, &bitD4
);
1775 HUF_DECODE_SYMBOLX2_2(op1
, &bitD1
);
1776 HUF_DECODE_SYMBOLX2_2(op2
, &bitD2
);
1777 HUF_DECODE_SYMBOLX2_2(op3
, &bitD3
);
1778 HUF_DECODE_SYMBOLX2_2(op4
, &bitD4
);
1779 HUF_DECODE_SYMBOLX2_0(op1
, &bitD1
);
1780 HUF_DECODE_SYMBOLX2_0(op2
, &bitD2
);
1781 HUF_DECODE_SYMBOLX2_0(op3
, &bitD3
);
1782 HUF_DECODE_SYMBOLX2_0(op4
, &bitD4
);
1784 endSignal
= BIT_reloadDStream(&bitD1
) | BIT_reloadDStream(&bitD2
) | BIT_reloadDStream(&bitD3
) | BIT_reloadDStream(&bitD4
);
1787 /* check corruption */
1788 if (op1
> opStart2
) return ERROR(corruption_detected
);
1789 if (op2
> opStart3
) return ERROR(corruption_detected
);
1790 if (op3
> opStart4
) return ERROR(corruption_detected
);
1791 /* note : op4 supposed already verified within main loop */
1793 /* finish bitStreams one by one */
1794 HUF_decodeStreamX2(op1
, &bitD1
, opStart2
, dt
, dtLog
);
1795 HUF_decodeStreamX2(op2
, &bitD2
, opStart3
, dt
, dtLog
);
1796 HUF_decodeStreamX2(op3
, &bitD3
, opStart4
, dt
, dtLog
);
1797 HUF_decodeStreamX2(op4
, &bitD4
, oend
, dt
, dtLog
);
1800 endSignal
= BIT_endOfDStream(&bitD1
) & BIT_endOfDStream(&bitD2
) & BIT_endOfDStream(&bitD3
) & BIT_endOfDStream(&bitD4
);
1801 if (!endSignal
) return ERROR(corruption_detected
);
1809 static size_t HUF_decompress4X2 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
1811 HUF_CREATE_STATIC_DTABLEX2(DTable
, HUF_MAX_TABLELOG
);
1812 const BYTE
* ip
= (const BYTE
*) cSrc
;
1815 errorCode
= HUF_readDTableX2 (DTable
, cSrc
, cSrcSize
);
1816 if (HUF_isError(errorCode
)) return errorCode
;
1817 if (errorCode
>= cSrcSize
) return ERROR(srcSize_wrong
);
1819 cSrcSize
-= errorCode
;
1821 return HUF_decompress4X2_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
1825 /***************************/
1826 /* double-symbols decoding */
1827 /***************************/
1829 static void HUF_fillDTableX4Level2(HUF_DEltX4
* DTable
, U32 sizeLog
, const U32 consumed
,
1830 const U32
* rankValOrigin
, const int minWeight
,
1831 const sortedSymbol_t
* sortedSymbols
, const U32 sortedListSize
,
1832 U32 nbBitsBaseline
, U16 baseSeq
)
1835 U32 rankVal
[HUF_ABSOLUTEMAX_TABLELOG
+ 1];
1838 /* get pre-calculated rankVal */
1839 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
1841 /* fill skipped values */
1844 U32 i
, skipSize
= rankVal
[minWeight
];
1845 MEM_writeLE16(&(DElt
.sequence
), baseSeq
);
1846 DElt
.nbBits
= (BYTE
)(consumed
);
1848 for (i
= 0; i
< skipSize
; i
++)
1853 for (s
=0; s
<sortedListSize
; s
++) /* note : sortedSymbols already skipped */
1855 const U32 symbol
= sortedSymbols
[s
].symbol
;
1856 const U32 weight
= sortedSymbols
[s
].weight
;
1857 const U32 nbBits
= nbBitsBaseline
- weight
;
1858 const U32 length
= 1 << (sizeLog
-nbBits
);
1859 const U32 start
= rankVal
[weight
];
1861 const U32 end
= start
+ length
;
1863 MEM_writeLE16(&(DElt
.sequence
), (U16
)(baseSeq
+ (symbol
<< 8)));
1864 DElt
.nbBits
= (BYTE
)(nbBits
+ consumed
);
1866 do { DTable
[i
++] = DElt
; } while (i
<end
); /* since length >= 1 */
1868 rankVal
[weight
] += length
;
1872 typedef U32 rankVal_t
[HUF_ABSOLUTEMAX_TABLELOG
][HUF_ABSOLUTEMAX_TABLELOG
+ 1];
1874 static void HUF_fillDTableX4(HUF_DEltX4
* DTable
, const U32 targetLog
,
1875 const sortedSymbol_t
* sortedList
, const U32 sortedListSize
,
1876 const U32
* rankStart
, rankVal_t rankValOrigin
, const U32 maxWeight
,
1877 const U32 nbBitsBaseline
)
1879 U32 rankVal
[HUF_ABSOLUTEMAX_TABLELOG
+ 1];
1880 const int scaleLog
= nbBitsBaseline
- targetLog
; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1881 const U32 minBits
= nbBitsBaseline
- maxWeight
;
1884 memcpy(rankVal
, rankValOrigin
, sizeof(rankVal
));
1887 for (s
=0; s
<sortedListSize
; s
++)
1889 const U16 symbol
= sortedList
[s
].symbol
;
1890 const U32 weight
= sortedList
[s
].weight
;
1891 const U32 nbBits
= nbBitsBaseline
- weight
;
1892 const U32 start
= rankVal
[weight
];
1893 const U32 length
= 1 << (targetLog
-nbBits
);
1895 if (targetLog
-nbBits
>= minBits
) /* enough room for a second symbol */
1898 int minWeight
= nbBits
+ scaleLog
;
1899 if (minWeight
< 1) minWeight
= 1;
1900 sortedRank
= rankStart
[minWeight
];
1901 HUF_fillDTableX4Level2(DTable
+start
, targetLog
-nbBits
, nbBits
,
1902 rankValOrigin
[nbBits
], minWeight
,
1903 sortedList
+sortedRank
, sortedListSize
-sortedRank
,
1904 nbBitsBaseline
, symbol
);
1909 const U32 end
= start
+ length
;
1912 MEM_writeLE16(&(DElt
.sequence
), symbol
);
1913 DElt
.nbBits
= (BYTE
)(nbBits
);
1915 for (i
= start
; i
< end
; i
++)
1918 rankVal
[weight
] += length
;
1922 static size_t HUF_readDTableX4 (U32
* DTable
, const void* src
, size_t srcSize
)
1924 BYTE weightList
[HUF_MAX_SYMBOL_VALUE
+ 1];
1925 sortedSymbol_t sortedSymbol
[HUF_MAX_SYMBOL_VALUE
+ 1];
1926 U32 rankStats
[HUF_ABSOLUTEMAX_TABLELOG
+ 1] = { 0 };
1927 U32 rankStart0
[HUF_ABSOLUTEMAX_TABLELOG
+ 2] = { 0 };
1928 U32
* const rankStart
= rankStart0
+1;
1930 U32 tableLog
, maxW
, sizeOfSort
, nbSymbols
;
1931 const U32 memLog
= DTable
[0];
1932 const BYTE
* ip
= (const BYTE
*) src
;
1933 size_t iSize
= ip
[0];
1935 HUF_DEltX4
* const dt
= ((HUF_DEltX4
*)ptr
) + 1;
1937 HUF_STATIC_ASSERT(sizeof(HUF_DEltX4
) == sizeof(U32
)); /* if compilation fails here, assertion is false */
1938 if (memLog
> HUF_ABSOLUTEMAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
1939 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
1941 iSize
= HUF_readStats(weightList
, HUF_MAX_SYMBOL_VALUE
+ 1, rankStats
, &nbSymbols
, &tableLog
, src
, srcSize
);
1942 if (HUF_isError(iSize
)) return iSize
;
1945 if (tableLog
> memLog
) return ERROR(tableLog_tooLarge
); /* DTable can't fit code depth */
1947 /* find maxWeight */
1948 for (maxW
= tableLog
; rankStats
[maxW
]==0; maxW
--)
1949 {if (!maxW
) return ERROR(GENERIC
); } /* necessarily finds a solution before maxW==0 */
1951 /* Get start index of each weight */
1953 U32 w
, nextRankStart
= 0;
1954 for (w
=1; w
<=maxW
; w
++)
1956 U32 current
= nextRankStart
;
1957 nextRankStart
+= rankStats
[w
];
1958 rankStart
[w
] = current
;
1960 rankStart
[0] = nextRankStart
; /* put all 0w symbols at the end of sorted list*/
1961 sizeOfSort
= nextRankStart
;
1964 /* sort symbols by weight */
1967 for (s
=0; s
<nbSymbols
; s
++)
1969 U32 w
= weightList
[s
];
1970 U32 r
= rankStart
[w
]++;
1971 sortedSymbol
[r
].symbol
= (BYTE
)s
;
1972 sortedSymbol
[r
].weight
= (BYTE
)w
;
1974 rankStart
[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
1979 const U32 minBits
= tableLog
+1 - maxW
;
1980 U32 nextRankVal
= 0;
1982 const int rescale
= (memLog
-tableLog
) - 1; /* tableLog <= memLog */
1983 U32
* rankVal0
= rankVal
[0];
1984 for (w
=1; w
<=maxW
; w
++)
1986 U32 current
= nextRankVal
;
1987 nextRankVal
+= rankStats
[w
] << (w
+rescale
);
1988 rankVal0
[w
] = current
;
1990 for (consumed
= minBits
; consumed
<= memLog
- minBits
; consumed
++)
1992 U32
* rankValPtr
= rankVal
[consumed
];
1993 for (w
= 1; w
<= maxW
; w
++)
1995 rankValPtr
[w
] = rankVal0
[w
] >> consumed
;
2000 HUF_fillDTableX4(dt
, memLog
,
2001 sortedSymbol
, sizeOfSort
,
2002 rankStart0
, rankVal
, maxW
,
2009 static U32
HUF_decodeSymbolX4(void* op
, BIT_DStream_t
* DStream
, const HUF_DEltX4
* dt
, const U32 dtLog
)
2011 const size_t val
= BIT_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2012 memcpy(op
, dt
+val
, 2);
2013 BIT_skipBits(DStream
, dt
[val
].nbBits
);
2014 return dt
[val
].length
;
2017 static U32
HUF_decodeLastSymbolX4(void* op
, BIT_DStream_t
* DStream
, const HUF_DEltX4
* dt
, const U32 dtLog
)
2019 const size_t val
= BIT_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2020 memcpy(op
, dt
+val
, 1);
2021 if (dt
[val
].length
==1) BIT_skipBits(DStream
, dt
[val
].nbBits
);
2024 if (DStream
->bitsConsumed
< (sizeof(DStream
->bitContainer
)*8))
2026 BIT_skipBits(DStream
, dt
[val
].nbBits
);
2027 if (DStream
->bitsConsumed
> (sizeof(DStream
->bitContainer
)*8))
2028 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 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2036 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2038 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2039 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2040 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2042 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2044 ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2046 static inline size_t HUF_decodeStreamX4(BYTE
* p
, BIT_DStream_t
* bitDPtr
, BYTE
* const pEnd
, const HUF_DEltX4
* const dt
, const U32 dtLog
)
2048 BYTE
* const pStart
= p
;
2050 /* up to 8 symbols at a time */
2051 while ((BIT_reloadDStream(bitDPtr
) == BIT_DStream_unfinished
) && (p
< pEnd
-7))
2053 HUF_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2054 HUF_DECODE_SYMBOLX4_1(p
, bitDPtr
);
2055 HUF_DECODE_SYMBOLX4_2(p
, bitDPtr
);
2056 HUF_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2059 /* closer to the end */
2060 while ((BIT_reloadDStream(bitDPtr
) == BIT_DStream_unfinished
) && (p
<= pEnd
-2))
2061 HUF_DECODE_SYMBOLX4_0(p
, bitDPtr
);
2064 HUF_DECODE_SYMBOLX4_0(p
, bitDPtr
); /* no need to reload : reached the end of DStream */
2067 p
+= HUF_decodeLastSymbolX4(p
, bitDPtr
, dt
, dtLog
);
2074 static size_t HUF_decompress4X4_usingDTable(
2075 void* dst
, size_t dstSize
,
2076 const void* cSrc
, size_t cSrcSize
,
2079 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2082 const BYTE
* const istart
= (const BYTE
*) cSrc
;
2083 BYTE
* const ostart
= (BYTE
*) dst
;
2084 BYTE
* const oend
= ostart
+ dstSize
;
2086 const void* ptr
= DTable
;
2087 const HUF_DEltX4
* const dt
= ((const HUF_DEltX4
*)ptr
) +1;
2088 const U32 dtLog
= DTable
[0];
2092 BIT_DStream_t bitD1
;
2093 BIT_DStream_t bitD2
;
2094 BIT_DStream_t bitD3
;
2095 BIT_DStream_t bitD4
;
2096 const size_t length1
= MEM_readLE16(istart
);
2097 const size_t length2
= MEM_readLE16(istart
+2);
2098 const size_t length3
= MEM_readLE16(istart
+4);
2100 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2101 const BYTE
* const istart2
= istart1
+ length1
;
2102 const BYTE
* const istart3
= istart2
+ length2
;
2103 const BYTE
* const istart4
= istart3
+ length3
;
2104 const size_t segmentSize
= (dstSize
+3) / 4;
2105 BYTE
* const opStart2
= ostart
+ segmentSize
;
2106 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2107 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2109 BYTE
* op2
= opStart2
;
2110 BYTE
* op3
= opStart3
;
2111 BYTE
* op4
= opStart4
;
2114 length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2115 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2116 errorCode
= BIT_initDStream(&bitD1
, istart1
, length1
);
2117 if (HUF_isError(errorCode
)) return errorCode
;
2118 errorCode
= BIT_initDStream(&bitD2
, istart2
, length2
);
2119 if (HUF_isError(errorCode
)) return errorCode
;
2120 errorCode
= BIT_initDStream(&bitD3
, istart3
, length3
);
2121 if (HUF_isError(errorCode
)) return errorCode
;
2122 errorCode
= BIT_initDStream(&bitD4
, istart4
, length4
);
2123 if (HUF_isError(errorCode
)) return errorCode
;
2125 /* 16-32 symbols per loop (4-8 symbols per stream) */
2126 endSignal
= BIT_reloadDStream(&bitD1
) | BIT_reloadDStream(&bitD2
) | BIT_reloadDStream(&bitD3
) | BIT_reloadDStream(&bitD4
);
2127 for ( ; (endSignal
==BIT_DStream_unfinished
) && (op4
<(oend
-7)) ; )
2129 HUF_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2130 HUF_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2131 HUF_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2132 HUF_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2133 HUF_DECODE_SYMBOLX4_1(op1
, &bitD1
);
2134 HUF_DECODE_SYMBOLX4_1(op2
, &bitD2
);
2135 HUF_DECODE_SYMBOLX4_1(op3
, &bitD3
);
2136 HUF_DECODE_SYMBOLX4_1(op4
, &bitD4
);
2137 HUF_DECODE_SYMBOLX4_2(op1
, &bitD1
);
2138 HUF_DECODE_SYMBOLX4_2(op2
, &bitD2
);
2139 HUF_DECODE_SYMBOLX4_2(op3
, &bitD3
);
2140 HUF_DECODE_SYMBOLX4_2(op4
, &bitD4
);
2141 HUF_DECODE_SYMBOLX4_0(op1
, &bitD1
);
2142 HUF_DECODE_SYMBOLX4_0(op2
, &bitD2
);
2143 HUF_DECODE_SYMBOLX4_0(op3
, &bitD3
);
2144 HUF_DECODE_SYMBOLX4_0(op4
, &bitD4
);
2146 endSignal
= BIT_reloadDStream(&bitD1
) | BIT_reloadDStream(&bitD2
) | BIT_reloadDStream(&bitD3
) | BIT_reloadDStream(&bitD4
);
2149 /* check corruption */
2150 if (op1
> opStart2
) return ERROR(corruption_detected
);
2151 if (op2
> opStart3
) return ERROR(corruption_detected
);
2152 if (op3
> opStart4
) return ERROR(corruption_detected
);
2153 /* note : op4 supposed already verified within main loop */
2155 /* finish bitStreams one by one */
2156 HUF_decodeStreamX4(op1
, &bitD1
, opStart2
, dt
, dtLog
);
2157 HUF_decodeStreamX4(op2
, &bitD2
, opStart3
, dt
, dtLog
);
2158 HUF_decodeStreamX4(op3
, &bitD3
, opStart4
, dt
, dtLog
);
2159 HUF_decodeStreamX4(op4
, &bitD4
, oend
, dt
, dtLog
);
2162 endSignal
= BIT_endOfDStream(&bitD1
) & BIT_endOfDStream(&bitD2
) & BIT_endOfDStream(&bitD3
) & BIT_endOfDStream(&bitD4
);
2163 if (!endSignal
) return ERROR(corruption_detected
);
2171 static size_t HUF_decompress4X4 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2173 HUF_CREATE_STATIC_DTABLEX4(DTable
, HUF_MAX_TABLELOG
);
2174 const BYTE
* ip
= (const BYTE
*) cSrc
;
2176 size_t hSize
= HUF_readDTableX4 (DTable
, cSrc
, cSrcSize
);
2177 if (HUF_isError(hSize
)) return hSize
;
2178 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2182 return HUF_decompress4X4_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2186 /**********************************/
2187 /* quad-symbol decoding */
2188 /**********************************/
2189 typedef struct { BYTE nbBits
; BYTE nbBytes
; } HUF_DDescX6
;
2190 typedef union { BYTE byte
[4]; U32 sequence
; } HUF_DSeqX6
;
2192 /* recursive, up to level 3; may benefit from <template>-like strategy to nest each level inline */
2193 static void HUF_fillDTableX6LevelN(HUF_DDescX6
* DDescription
, HUF_DSeqX6
* DSequence
, int sizeLog
,
2194 const rankVal_t rankValOrigin
, const U32 consumed
, const int minWeight
, const U32 maxWeight
,
2195 const sortedSymbol_t
* sortedSymbols
, const U32 sortedListSize
, const U32
* rankStart
,
2196 const U32 nbBitsBaseline
, HUF_DSeqX6 baseSeq
, HUF_DDescX6 DDesc
)
2198 const int scaleLog
= nbBitsBaseline
- sizeLog
; /* note : targetLog >= (nbBitsBaseline-1), hence scaleLog <= 1 */
2199 const int minBits
= nbBitsBaseline
- maxWeight
;
2200 const U32 level
= DDesc
.nbBytes
;
2201 U32 rankVal
[HUF_ABSOLUTEMAX_TABLELOG
+ 1];
2202 U32 symbolStartPos
, s
;
2204 /* local rankVal, will be modified */
2205 memcpy(rankVal
, rankValOrigin
[consumed
], sizeof(rankVal
));
2207 /* fill skipped values */
2211 const U32 skipSize
= rankVal
[minWeight
];
2212 for (i
= 0; i
< skipSize
; i
++)
2214 DSequence
[i
] = baseSeq
;
2215 DDescription
[i
] = DDesc
;
2221 symbolStartPos
= rankStart
[minWeight
];
2222 for (s
=symbolStartPos
; s
<sortedListSize
; s
++)
2224 const BYTE symbol
= sortedSymbols
[s
].symbol
;
2225 const U32 weight
= sortedSymbols
[s
].weight
; /* >= 1 (sorted) */
2226 const int nbBits
= nbBitsBaseline
- weight
; /* >= 1 (by construction) */
2227 const int totalBits
= consumed
+nbBits
;
2228 const U32 start
= rankVal
[weight
];
2229 const U32 length
= 1 << (sizeLog
-nbBits
);
2230 baseSeq
.byte
[level
] = symbol
;
2231 DDesc
.nbBits
= (BYTE
)totalBits
;
2233 if ((level
<3) && (sizeLog
-totalBits
>= minBits
)) /* enough room for another symbol */
2235 int nextMinWeight
= totalBits
+ scaleLog
;
2236 if (nextMinWeight
< 1) nextMinWeight
= 1;
2237 HUF_fillDTableX6LevelN(DDescription
+start
, DSequence
+start
, sizeLog
-nbBits
,
2238 rankValOrigin
, totalBits
, nextMinWeight
, maxWeight
,
2239 sortedSymbols
, sortedListSize
, rankStart
,
2240 nbBitsBaseline
, baseSeq
, DDesc
); /* recursive (max : level 3) */
2245 const U32 end
= start
+ length
;
2246 for (i
= start
; i
< end
; i
++)
2248 DDescription
[i
] = DDesc
;
2249 DSequence
[i
] = baseSeq
;
2252 rankVal
[weight
] += length
;
2257 /* note : same preparation as X4 */
2258 static size_t HUF_readDTableX6 (U32
* DTable
, const void* src
, size_t srcSize
)
2260 BYTE weightList
[HUF_MAX_SYMBOL_VALUE
+ 1];
2261 sortedSymbol_t sortedSymbol
[HUF_MAX_SYMBOL_VALUE
+ 1];
2262 U32 rankStats
[HUF_ABSOLUTEMAX_TABLELOG
+ 1] = { 0 };
2263 U32 rankStart0
[HUF_ABSOLUTEMAX_TABLELOG
+ 2] = { 0 };
2264 U32
* const rankStart
= rankStart0
+1;
2265 U32 tableLog
, maxW
, sizeOfSort
, nbSymbols
;
2267 const U32 memLog
= DTable
[0];
2268 const BYTE
* ip
= (const BYTE
*) src
;
2269 size_t iSize
= ip
[0];
2271 if (memLog
> HUF_ABSOLUTEMAX_TABLELOG
) return ERROR(tableLog_tooLarge
);
2272 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2274 iSize
= HUF_readStats(weightList
, HUF_MAX_SYMBOL_VALUE
+ 1, rankStats
, &nbSymbols
, &tableLog
, src
, srcSize
);
2275 if (HUF_isError(iSize
)) return iSize
;
2278 if (tableLog
> memLog
) return ERROR(tableLog_tooLarge
); /* DTable is too small */
2280 /* find maxWeight */
2281 for (maxW
= tableLog
; rankStats
[maxW
]==0; maxW
--)
2282 { if (!maxW
) return ERROR(GENERIC
); } /* necessarily finds a solution before maxW==0 */
2285 /* Get start index of each weight */
2287 U32 w
, nextRankStart
= 0;
2288 for (w
=1; w
<=maxW
; w
++)
2290 U32 current
= nextRankStart
;
2291 nextRankStart
+= rankStats
[w
];
2292 rankStart
[w
] = current
;
2294 rankStart
[0] = nextRankStart
; /* put all 0w symbols at the end of sorted list*/
2295 sizeOfSort
= nextRankStart
;
2298 /* sort symbols by weight */
2301 for (s
=0; s
<nbSymbols
; s
++)
2303 U32 w
= weightList
[s
];
2304 U32 r
= rankStart
[w
]++;
2305 sortedSymbol
[r
].symbol
= (BYTE
)s
;
2306 sortedSymbol
[r
].weight
= (BYTE
)w
;
2308 rankStart
[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2313 const U32 minBits
= tableLog
+1 - maxW
;
2314 U32 nextRankVal
= 0;
2316 const int rescale
= (memLog
-tableLog
) - 1; /* tableLog <= memLog */
2317 U32
* rankVal0
= rankVal
[0];
2318 for (w
=1; w
<=maxW
; w
++)
2320 U32 current
= nextRankVal
;
2321 nextRankVal
+= rankStats
[w
] << (w
+rescale
);
2322 rankVal0
[w
] = current
;
2324 for (consumed
= minBits
; consumed
<= memLog
- minBits
; consumed
++)
2326 U32
* rankValPtr
= rankVal
[consumed
];
2327 for (w
= 1; w
<= maxW
; w
++)
2329 rankValPtr
[w
] = rankVal0
[w
] >> consumed
;
2337 void* ptr
= DTable
+1;
2338 HUF_DDescX6
* DDescription
= (HUF_DDescX6
*)(ptr
);
2339 void* dSeqStart
= DTable
+ 1 + ((size_t)1<<(memLog
-1));
2340 HUF_DSeqX6
* DSequence
= (HUF_DSeqX6
*)(dSeqStart
);
2346 HUF_fillDTableX6LevelN(DDescription
, DSequence
, memLog
,
2347 (const U32 (*)[HUF_ABSOLUTEMAX_TABLELOG
+ 1])rankVal
, 0, 1, maxW
,
2348 sortedSymbol
, sizeOfSort
, rankStart0
,
2349 tableLog
+1, DSeq
, DDesc
);
2356 static U32
HUF_decodeSymbolX6(void* op
, BIT_DStream_t
* DStream
, const HUF_DDescX6
* dd
, const HUF_DSeqX6
* ds
, const U32 dtLog
)
2358 const size_t val
= BIT_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2359 memcpy(op
, ds
+val
, sizeof(HUF_DSeqX6
));
2360 BIT_skipBits(DStream
, dd
[val
].nbBits
);
2361 return dd
[val
].nbBytes
;
2364 static U32
HUF_decodeLastSymbolsX6(void* op
, const U32 maxL
, BIT_DStream_t
* DStream
,
2365 const HUF_DDescX6
* dd
, const HUF_DSeqX6
* ds
, const U32 dtLog
)
2367 const size_t val
= BIT_lookBitsFast(DStream
, dtLog
); /* note : dtLog >= 1 */
2368 U32 length
= dd
[val
].nbBytes
;
2371 memcpy(op
, ds
+val
, length
);
2372 BIT_skipBits(DStream
, dd
[val
].nbBits
);
2375 memcpy(op
, ds
+val
, maxL
);
2376 if (DStream
->bitsConsumed
< (sizeof(DStream
->bitContainer
)*8))
2378 BIT_skipBits(DStream
, dd
[val
].nbBits
);
2379 if (DStream
->bitsConsumed
> (sizeof(DStream
->bitContainer
)*8))
2380 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 */
2386 #define HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr) \
2387 ptr += HUF_decodeSymbolX6(ptr, DStreamPtr, dd, ds, dtLog)
2389 #define HUF_DECODE_SYMBOLX6_1(ptr, DStreamPtr) \
2390 if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2391 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2393 #define HUF_DECODE_SYMBOLX6_2(ptr, DStreamPtr) \
2395 HUF_DECODE_SYMBOLX6_0(ptr, DStreamPtr)
2397 static inline size_t HUF_decodeStreamX6(BYTE
* p
, BIT_DStream_t
* bitDPtr
, BYTE
* const pEnd
, const U32
* DTable
, const U32 dtLog
)
2399 const void* ddPtr
= DTable
+1;
2400 const HUF_DDescX6
* dd
= (const HUF_DDescX6
*)(ddPtr
);
2401 const void* dsPtr
= DTable
+ 1 + ((size_t)1<<(dtLog
-1));
2402 const HUF_DSeqX6
* ds
= (const HUF_DSeqX6
*)(dsPtr
);
2403 BYTE
* const pStart
= p
;
2405 /* up to 16 symbols at a time */
2406 while ((BIT_reloadDStream(bitDPtr
) == BIT_DStream_unfinished
) && (p
<= pEnd
-16))
2408 HUF_DECODE_SYMBOLX6_2(p
, bitDPtr
);
2409 HUF_DECODE_SYMBOLX6_1(p
, bitDPtr
);
2410 HUF_DECODE_SYMBOLX6_2(p
, bitDPtr
);
2411 HUF_DECODE_SYMBOLX6_0(p
, bitDPtr
);
2414 /* closer to the end, up to 4 symbols at a time */
2415 while ((BIT_reloadDStream(bitDPtr
) == BIT_DStream_unfinished
) && (p
<= pEnd
-4))
2416 HUF_DECODE_SYMBOLX6_0(p
, bitDPtr
);
2419 HUF_DECODE_SYMBOLX6_0(p
, bitDPtr
); /* no need to reload : reached the end of DStream */
2422 p
+= HUF_decodeLastSymbolsX6(p
, (U32
)(pEnd
-p
), bitDPtr
, dd
, ds
, dtLog
);
2429 static size_t HUF_decompress4X6_usingDTable(
2430 void* dst
, size_t dstSize
,
2431 const void* cSrc
, size_t cSrcSize
,
2434 if (cSrcSize
< 10) return ERROR(corruption_detected
); /* strict minimum : jump table + 1 byte per stream */
2437 const BYTE
* const istart
= (const BYTE
*) cSrc
;
2438 BYTE
* const ostart
= (BYTE
*) dst
;
2439 BYTE
* const oend
= ostart
+ dstSize
;
2441 const U32 dtLog
= DTable
[0];
2442 const void* ddPtr
= DTable
+1;
2443 const HUF_DDescX6
* dd
= (const HUF_DDescX6
*)(ddPtr
);
2444 const void* dsPtr
= DTable
+ 1 + ((size_t)1<<(dtLog
-1));
2445 const HUF_DSeqX6
* ds
= (const HUF_DSeqX6
*)(dsPtr
);
2449 BIT_DStream_t bitD1
;
2450 BIT_DStream_t bitD2
;
2451 BIT_DStream_t bitD3
;
2452 BIT_DStream_t bitD4
;
2453 const size_t length1
= MEM_readLE16(istart
);
2454 const size_t length2
= MEM_readLE16(istart
+2);
2455 const size_t length3
= MEM_readLE16(istart
+4);
2457 const BYTE
* const istart1
= istart
+ 6; /* jumpTable */
2458 const BYTE
* const istart2
= istart1
+ length1
;
2459 const BYTE
* const istart3
= istart2
+ length2
;
2460 const BYTE
* const istart4
= istart3
+ length3
;
2461 const size_t segmentSize
= (dstSize
+3) / 4;
2462 BYTE
* const opStart2
= ostart
+ segmentSize
;
2463 BYTE
* const opStart3
= opStart2
+ segmentSize
;
2464 BYTE
* const opStart4
= opStart3
+ segmentSize
;
2466 BYTE
* op2
= opStart2
;
2467 BYTE
* op3
= opStart3
;
2468 BYTE
* op4
= opStart4
;
2471 length4
= cSrcSize
- (length1
+ length2
+ length3
+ 6);
2472 if (length4
> cSrcSize
) return ERROR(corruption_detected
); /* overflow */
2473 errorCode
= BIT_initDStream(&bitD1
, istart1
, length1
);
2474 if (HUF_isError(errorCode
)) return errorCode
;
2475 errorCode
= BIT_initDStream(&bitD2
, istart2
, length2
);
2476 if (HUF_isError(errorCode
)) return errorCode
;
2477 errorCode
= BIT_initDStream(&bitD3
, istart3
, length3
);
2478 if (HUF_isError(errorCode
)) return errorCode
;
2479 errorCode
= BIT_initDStream(&bitD4
, istart4
, length4
);
2480 if (HUF_isError(errorCode
)) return errorCode
;
2482 /* 16-64 symbols per loop (4-16 symbols per stream) */
2483 endSignal
= BIT_reloadDStream(&bitD1
) | BIT_reloadDStream(&bitD2
) | BIT_reloadDStream(&bitD3
) | BIT_reloadDStream(&bitD4
);
2484 for ( ; (op3
<= opStart4
) && (endSignal
==BIT_DStream_unfinished
) && (op4
<=(oend
-16)) ; )
2486 HUF_DECODE_SYMBOLX6_2(op1
, &bitD1
);
2487 HUF_DECODE_SYMBOLX6_2(op2
, &bitD2
);
2488 HUF_DECODE_SYMBOLX6_2(op3
, &bitD3
);
2489 HUF_DECODE_SYMBOLX6_2(op4
, &bitD4
);
2490 HUF_DECODE_SYMBOLX6_1(op1
, &bitD1
);
2491 HUF_DECODE_SYMBOLX6_1(op2
, &bitD2
);
2492 HUF_DECODE_SYMBOLX6_1(op3
, &bitD3
);
2493 HUF_DECODE_SYMBOLX6_1(op4
, &bitD4
);
2494 HUF_DECODE_SYMBOLX6_2(op1
, &bitD1
);
2495 HUF_DECODE_SYMBOLX6_2(op2
, &bitD2
);
2496 HUF_DECODE_SYMBOLX6_2(op3
, &bitD3
);
2497 HUF_DECODE_SYMBOLX6_2(op4
, &bitD4
);
2498 HUF_DECODE_SYMBOLX6_0(op1
, &bitD1
);
2499 HUF_DECODE_SYMBOLX6_0(op2
, &bitD2
);
2500 HUF_DECODE_SYMBOLX6_0(op3
, &bitD3
);
2501 HUF_DECODE_SYMBOLX6_0(op4
, &bitD4
);
2503 endSignal
= BIT_reloadDStream(&bitD1
) | BIT_reloadDStream(&bitD2
) | BIT_reloadDStream(&bitD3
) | BIT_reloadDStream(&bitD4
);
2506 /* check corruption */
2507 if (op1
> opStart2
) return ERROR(corruption_detected
);
2508 if (op2
> opStart3
) return ERROR(corruption_detected
);
2509 if (op3
> opStart4
) return ERROR(corruption_detected
);
2510 /* note : op4 supposed already verified within main loop */
2512 /* finish bitStreams one by one */
2513 HUF_decodeStreamX6(op1
, &bitD1
, opStart2
, DTable
, dtLog
);
2514 HUF_decodeStreamX6(op2
, &bitD2
, opStart3
, DTable
, dtLog
);
2515 HUF_decodeStreamX6(op3
, &bitD3
, opStart4
, DTable
, dtLog
);
2516 HUF_decodeStreamX6(op4
, &bitD4
, oend
, DTable
, dtLog
);
2519 endSignal
= BIT_endOfDStream(&bitD1
) & BIT_endOfDStream(&bitD2
) & BIT_endOfDStream(&bitD3
) & BIT_endOfDStream(&bitD4
);
2520 if (!endSignal
) return ERROR(corruption_detected
);
2528 static size_t HUF_decompress4X6 (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2530 HUF_CREATE_STATIC_DTABLEX6(DTable
, HUF_MAX_TABLELOG
);
2531 const BYTE
* ip
= (const BYTE
*) cSrc
;
2533 size_t hSize
= HUF_readDTableX6 (DTable
, cSrc
, cSrcSize
);
2534 if (HUF_isError(hSize
)) return hSize
;
2535 if (hSize
>= cSrcSize
) return ERROR(srcSize_wrong
);
2539 return HUF_decompress4X6_usingDTable (dst
, dstSize
, ip
, cSrcSize
, DTable
);
2543 /**********************************/
2544 /* Generic decompression selector */
2545 /**********************************/
2547 typedef struct { U32 tableTime
; U32 decode256Time
; } algo_time_t
;
2548 static const algo_time_t algoTime
[16 /* Quantization */][3 /* single, double, quad */] =
2550 /* single, double, quad */
2551 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2552 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2553 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2554 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2555 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2556 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2557 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2558 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2559 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2560 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2561 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2562 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2563 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2564 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2565 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2566 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2569 typedef size_t (*decompressionAlgo
)(void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
);
2571 static size_t HUF_decompress (void* dst
, size_t dstSize
, const void* cSrc
, size_t cSrcSize
)
2573 static const decompressionAlgo decompress
[3] = { HUF_decompress4X2
, HUF_decompress4X4
, HUF_decompress4X6
};
2574 /* estimate decompression time */
2576 const U32 D256
= (U32
)(dstSize
>> 8);
2581 /* validation checks */
2582 if (dstSize
== 0) return ERROR(dstSize_tooSmall
);
2583 if (cSrcSize
> dstSize
) return ERROR(corruption_detected
); /* invalid */
2584 if (cSrcSize
== dstSize
) { memcpy(dst
, cSrc
, dstSize
); return dstSize
; } /* not compressed */
2585 if (cSrcSize
== 1) { memset(dst
, *(const BYTE
*)cSrc
, dstSize
); return dstSize
; } /* RLE */
2587 /* decoder timing evaluation */
2588 Q
= (U32
)(cSrcSize
* 16 / dstSize
); /* Q < 16 since dstSize > cSrcSize */
2590 Dtime
[n
] = algoTime
[Q
][n
].tableTime
+ (algoTime
[Q
][n
].decode256Time
* D256
);
2592 Dtime
[1] += Dtime
[1] >> 4; Dtime
[2] += Dtime
[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2594 if (Dtime
[1] < Dtime
[0]) algoNb
= 1;
2595 if (Dtime
[2] < Dtime
[algoNb
]) algoNb
= 2;
2597 return decompress
[algoNb
](dst
, dstSize
, cSrc
, cSrcSize
);
2599 //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2600 //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2601 //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2604 zstd - standard compression library
2605 Copyright (C) 2014-2015, Yann Collet.
2607 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2609 Redistribution and use in source and binary forms, with or without
2610 modification, are permitted provided that the following conditions are
2612 * Redistributions of source code must retain the above copyright
2613 notice, this list of conditions and the following disclaimer.
2614 * Redistributions in binary form must reproduce the above
2615 copyright notice, this list of conditions and the following disclaimer
2616 in the documentation and/or other materials provided with the
2618 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2619 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2620 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2621 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2622 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2623 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2624 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2625 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2626 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2627 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2628 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2630 You can contact the author at :
2631 - zstd source repository : https://github.com/Cyan4973/zstd
2632 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2635 /* ***************************************************************
2637 *****************************************************************/
2640 * Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2641 * Increasing memory usage improves compression ratio
2642 * Reduced memory usage can improve speed, due to cache effect
2644 #define ZSTD_MEMORY_USAGE 17
2648 * Select how default compression functions will allocate memory for their hash table,
2649 * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2650 * Note that compression context is fairly large, as a consequence heap memory is recommended.
2652 #ifndef ZSTD_HEAPMODE
2653 # define ZSTD_HEAPMODE 1
2654 #endif /* ZSTD_HEAPMODE */
2658 * decompressor can decode older formats (starting from Zstd 0.1+)
2660 #ifndef ZSTD_LEGACY_SUPPORT
2661 # define ZSTD_LEGACY_SUPPORT 1
2665 /* *******************************************************
2667 *********************************************************/
2668 #include <stdlib.h> /* calloc */
2669 #include <string.h> /* memcpy, memmove */
2670 #include <stdio.h> /* debug : printf */
2673 /* *******************************************************
2674 * Compiler specifics
2675 *********************************************************/
2677 # include <immintrin.h> /* AVX2 intrinsics */
2680 #ifdef _MSC_VER /* Visual Studio */
2681 # include <intrin.h> /* For Visual 2005 */
2682 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2683 # pragma warning(disable : 4324) /* disable: C4324: padded structure */
2687 /* *******************************************************
2689 *********************************************************/
2690 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2691 #define HASH_TABLESIZE (1 << HASH_LOG)
2692 #define HASH_MASK (HASH_TABLESIZE - 1)
2694 #define KNUTH 2654435761
2703 #define KB *(1 <<10)
2704 #define MB *(1 <<20)
2705 #define GB *(1U<<30)
2707 #define BLOCKSIZE (128 KB) /* define, for static allocation */
2708 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2709 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2713 #define WORKPLACESIZE (BLOCKSIZE*3)
2718 #define MaxML ((1<<MLbits )-1)
2719 #define MaxLL ((1<<LLbits )-1)
2721 #define LitFSELog 11
2725 #define MAX(a,b) ((a)<(b)?(b):(a))
2726 #define MaxSeq MAX(MaxLL, MaxML)
2728 #define LITERAL_NOENTROPY 63
2729 #define COMMAND_NOENTROPY 7 /* to remove */
2731 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
2733 static const size_t ZSTD_blockHeaderSize
= 3;
2734 static const size_t ZSTD_frameHeaderSize
= 4;
2737 /* *******************************************************
2739 **********************************************************/
2740 static void ZSTD_copy4(void* dst
, const void* src
) { memcpy(dst
, src
, 4); }
2742 static void ZSTD_copy8(void* dst
, const void* src
) { memcpy(dst
, src
, 8); }
2744 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2746 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2747 static void ZSTD_wildcopy(void* dst
, const void* src
, ptrdiff_t length
)
2749 const BYTE
* ip
= (const BYTE
*)src
;
2750 BYTE
* op
= (BYTE
*)dst
;
2751 BYTE
* const oend
= op
+ length
;
2752 do COPY8(op
, ip
) while (op
< oend
);
2756 /* **************************************
2758 ****************************************/
2759 typedef enum { bt_compressed
, bt_raw
, bt_rle
, bt_end
} blockType_t
;
2763 blockType_t blockType
;
2765 } blockProperties_t
;
2775 BYTE
* litLengthStart
;
2777 BYTE
* matchLengthStart
;
2784 /* *************************************
2786 ***************************************/
2788 * tells if a return value is an error code */
2789 static unsigned ZSTD_isError(size_t code
) { return ERR_isError(code
); }
2793 /* *************************************************************
2794 * Decompression section
2795 ***************************************************************/
2798 U32 LLTable
[FSE_DTABLE_SIZE_U32(LLFSELog
)];
2799 U32 OffTable
[FSE_DTABLE_SIZE_U32(OffFSELog
)];
2800 U32 MLTable
[FSE_DTABLE_SIZE_U32(MLFSELog
)];
2801 void* previousDstEnd
;
2808 BYTE litBuffer
[BLOCKSIZE
+ 8 /* margin for wildcopy */];
2809 }; /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2812 static size_t ZSTD_getcBlockSize(const void* src
, size_t srcSize
, blockProperties_t
* bpPtr
)
2814 const BYTE
* const in
= (const BYTE
* const)src
;
2818 if (srcSize
< 3) return ERROR(srcSize_wrong
);
2821 cSize
= in
[2] + (in
[1]<<8) + ((in
[0] & 7)<<16);
2823 bpPtr
->blockType
= (blockType_t
)(headerFlags
>> 6);
2824 bpPtr
->origSize
= (bpPtr
->blockType
== bt_rle
) ? cSize
: 0;
2826 if (bpPtr
->blockType
== bt_end
) return 0;
2827 if (bpPtr
->blockType
== bt_rle
) return 1;
2831 static size_t ZSTD_copyUncompressedBlock(void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
2833 if (srcSize
> maxDstSize
) return ERROR(dstSize_tooSmall
);
2834 memcpy(dst
, src
, srcSize
);
2839 /** ZSTD_decompressLiterals
2840 @return : nb of bytes read from src, or an error code*/
2841 static size_t ZSTD_decompressLiterals(void* dst
, size_t* maxDstSizePtr
,
2842 const void* src
, size_t srcSize
)
2844 const BYTE
* ip
= (const BYTE
*)src
;
2846 const size_t litSize
= (MEM_readLE32(src
) & 0x1FFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2847 const size_t litCSize
= (MEM_readLE32(ip
+2) & 0xFFFFFF) >> 5; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2849 if (litSize
> *maxDstSizePtr
) return ERROR(corruption_detected
);
2850 if (litCSize
+ 5 > srcSize
) return ERROR(corruption_detected
);
2852 if (HUF_isError(HUF_decompress(dst
, litSize
, ip
+5, litCSize
))) return ERROR(corruption_detected
);
2854 *maxDstSizePtr
= litSize
;
2855 return litCSize
+ 5;
2859 /** ZSTD_decodeLiteralsBlock
2860 @return : nb of bytes read from src (< srcSize )*/
2861 static size_t ZSTD_decodeLiteralsBlock(void* ctx
,
2862 const void* src
, size_t srcSize
)
2864 ZSTD_DCtx
* dctx
= (ZSTD_DCtx
*)ctx
;
2865 const BYTE
* const istart
= (const BYTE
* const)src
;
2867 /* any compressed block with literals segment must be at least this size */
2868 if (srcSize
< MIN_CBLOCK_SIZE
) return ERROR(corruption_detected
);
2875 size_t litSize
= BLOCKSIZE
;
2876 const size_t readSize
= ZSTD_decompressLiterals(dctx
->litBuffer
, &litSize
, src
, srcSize
);
2877 dctx
->litPtr
= dctx
->litBuffer
;
2878 dctx
->litSize
= litSize
;
2879 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, 8);
2880 return readSize
; /* works if it's an error too */
2884 const size_t litSize
= (MEM_readLE32(istart
) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2885 if (litSize
> srcSize
-11) /* risk of reading too far with wildcopy */
2887 if (litSize
> srcSize
-3) return ERROR(corruption_detected
);
2888 memcpy(dctx
->litBuffer
, istart
, litSize
);
2889 dctx
->litPtr
= dctx
->litBuffer
;
2890 dctx
->litSize
= litSize
;
2891 memset(dctx
->litBuffer
+ dctx
->litSize
, 0, 8);
2894 /* direct reference into compressed stream */
2895 dctx
->litPtr
= istart
+3;
2896 dctx
->litSize
= litSize
;
2901 const size_t litSize
= (MEM_readLE32(istart
) & 0xFFFFFF) >> 2; /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2902 if (litSize
> BLOCKSIZE
) return ERROR(corruption_detected
);
2903 memset(dctx
->litBuffer
, istart
[3], litSize
+ 8);
2904 dctx
->litPtr
= dctx
->litBuffer
;
2905 dctx
->litSize
= litSize
;
2912 static size_t ZSTD_decodeSeqHeaders(int* nbSeq
, const BYTE
** dumpsPtr
, size_t* dumpsLengthPtr
,
2913 FSE_DTable
* DTableLL
, FSE_DTable
* DTableML
, FSE_DTable
* DTableOffb
,
2914 const void* src
, size_t srcSize
)
2916 const BYTE
* const istart
= (const BYTE
* const)src
;
2917 const BYTE
* ip
= istart
;
2918 const BYTE
* const iend
= istart
+ srcSize
;
2919 U32 LLtype
, Offtype
, MLtype
;
2920 U32 LLlog
, Offlog
, MLlog
;
2924 if (srcSize
< 5) return ERROR(srcSize_wrong
);
2927 *nbSeq
= MEM_readLE16(ip
); ip
+=2;
2929 Offtype
= (*ip
>> 4) & 3;
2930 MLtype
= (*ip
>> 2) & 3;
2933 dumpsLength
= ip
[2];
2934 dumpsLength
+= ip
[1] << 8;
2939 dumpsLength
= ip
[1];
2940 dumpsLength
+= (ip
[0] & 1) << 8;
2945 *dumpsLengthPtr
= dumpsLength
;
2948 if (ip
> iend
-3) return ERROR(srcSize_wrong
); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2952 S16 norm
[MaxML
+1]; /* assumption : MaxML >= MaxLL and MaxOff */
2960 FSE_buildDTable_rle(DTableLL
, *ip
++); break;
2963 FSE_buildDTable_raw(DTableLL
, LLbits
); break;
2966 headerSize
= FSE_readNCount(norm
, &max
, &LLlog
, ip
, iend
-ip
);
2967 if (FSE_isError(headerSize
)) return ERROR(GENERIC
);
2968 if (LLlog
> LLFSELog
) return ERROR(corruption_detected
);
2970 FSE_buildDTable(DTableLL
, norm
, max
, LLlog
);
2977 if (ip
> iend
-2) return ERROR(srcSize_wrong
); /* min : "raw", hence no header, but at least xxLog bits */
2978 FSE_buildDTable_rle(DTableOffb
, *ip
++ & MaxOff
); /* if *ip > MaxOff, data is corrupted */
2982 FSE_buildDTable_raw(DTableOffb
, Offbits
); break;
2985 headerSize
= FSE_readNCount(norm
, &max
, &Offlog
, ip
, iend
-ip
);
2986 if (FSE_isError(headerSize
)) return ERROR(GENERIC
);
2987 if (Offlog
> OffFSELog
) return ERROR(corruption_detected
);
2989 FSE_buildDTable(DTableOffb
, norm
, max
, Offlog
);
2996 if (ip
> iend
-2) return ERROR(srcSize_wrong
); /* min : "raw", hence no header, but at least xxLog bits */
2997 FSE_buildDTable_rle(DTableML
, *ip
++); break;
3000 FSE_buildDTable_raw(DTableML
, MLbits
); break;
3003 headerSize
= FSE_readNCount(norm
, &max
, &MLlog
, ip
, iend
-ip
);
3004 if (FSE_isError(headerSize
)) return ERROR(GENERIC
);
3005 if (MLlog
> MLFSELog
) return ERROR(corruption_detected
);
3007 FSE_buildDTable(DTableML
, norm
, max
, MLlog
);
3021 BIT_DStream_t DStream
;
3022 FSE_DState_t stateLL
;
3023 FSE_DState_t stateOffb
;
3024 FSE_DState_t stateML
;
3027 const BYTE
* dumpsEnd
;
3031 static void ZSTD_decodeSequence(seq_t
* seq
, seqState_t
* seqState
)
3037 const BYTE
* dumps
= seqState
->dumps
;
3038 const BYTE
* const de
= seqState
->dumpsEnd
;
3040 /* Literal length */
3041 litLength
= FSE_decodeSymbol(&(seqState
->stateLL
), &(seqState
->DStream
));
3042 prevOffset
= litLength
? seq
->offset
: seqState
->prevOffset
;
3043 seqState
->prevOffset
= seq
->offset
;
3044 if (litLength
== MaxLL
)
3047 if (add
< 255) litLength
+= add
;
3050 litLength
= MEM_readLE32(dumps
) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3053 if (dumps
>= de
) dumps
= de
-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3058 static const size_t offsetPrefix
[MaxOff
+1] = { /* note : size_t faster than U32 */
3059 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3060 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3061 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3062 U32 offsetCode
, nbBits
;
3063 offsetCode
= FSE_decodeSymbol(&(seqState
->stateOffb
), &(seqState
->DStream
)); /* <= maxOff, by table construction */
3064 if (MEM_32bits()) BIT_reloadDStream(&(seqState
->DStream
));
3065 nbBits
= offsetCode
- 1;
3066 if (offsetCode
==0) nbBits
= 0; /* cmove */
3067 offset
= offsetPrefix
[offsetCode
] + BIT_readBits(&(seqState
->DStream
), nbBits
);
3068 if (MEM_32bits()) BIT_reloadDStream(&(seqState
->DStream
));
3069 if (offsetCode
==0) offset
= prevOffset
; /* cmove */
3073 matchLength
= FSE_decodeSymbol(&(seqState
->stateML
), &(seqState
->DStream
));
3074 if (matchLength
== MaxML
)
3077 if (add
< 255) matchLength
+= add
;
3080 matchLength
= MEM_readLE32(dumps
) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3083 if (dumps
>= de
) dumps
= de
-1; /* late correction, to avoid read overflow (data is now corrupted anyway) */
3085 matchLength
+= MINMATCH
;
3088 seq
->litLength
= litLength
;
3089 seq
->offset
= offset
;
3090 seq
->matchLength
= matchLength
;
3091 seqState
->dumps
= dumps
;
3095 static size_t ZSTD_execSequence(BYTE
* op
,
3097 const BYTE
** litPtr
, const BYTE
* const litLimit
,
3098 BYTE
* const base
, BYTE
* const oend
)
3100 static const int dec32table
[] = {0, 1, 2, 1, 4, 4, 4, 4}; /* added */
3101 static const int dec64table
[] = {8, 8, 8, 7, 8, 9,10,11}; /* subtracted */
3102 const BYTE
* const ostart
= op
;
3103 BYTE
* const oLitEnd
= op
+ sequence
.litLength
;
3104 BYTE
* const oMatchEnd
= op
+ sequence
.litLength
+ sequence
.matchLength
; /* risk : address space overflow (32-bits) */
3105 BYTE
* const oend_8
= oend
-8;
3106 const BYTE
* const litEnd
= *litPtr
+ sequence
.litLength
;
3109 if (oLitEnd
> oend_8
) return ERROR(dstSize_tooSmall
); /* last match must start at a minimum distance of 8 from oend */
3110 if (oMatchEnd
> oend
) return ERROR(dstSize_tooSmall
); /* overwrite beyond dst buffer */
3111 if (litEnd
> litLimit
) return ERROR(corruption_detected
); /* overRead beyond lit buffer */
3114 ZSTD_wildcopy(op
, *litPtr
, sequence
.litLength
); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3116 *litPtr
= litEnd
; /* update for next sequence */
3120 const BYTE
* match
= op
- sequence
.offset
;
3123 if (sequence
.offset
> (size_t)op
) return ERROR(corruption_detected
); /* address space overflow test (this test seems kept by clang optimizer) */
3124 //if (match > op) return ERROR(corruption_detected); /* address space overflow test (is clang optimizer removing this test ?) */
3125 if (match
< base
) return ERROR(corruption_detected
);
3127 /* close range match, overlap */
3128 if (sequence
.offset
< 8)
3130 const int dec64
= dec64table
[sequence
.offset
];
3135 match
+= dec32table
[sequence
.offset
];
3136 ZSTD_copy4(op
+4, match
);
3141 ZSTD_copy8(op
, match
);
3143 op
+= 8; match
+= 8;
3145 if (oMatchEnd
> oend
-(16-MINMATCH
))
3149 ZSTD_wildcopy(op
, match
, oend_8
- op
);
3150 match
+= oend_8
- op
;
3153 while (op
< oMatchEnd
) *op
++ = *match
++;
3157 ZSTD_wildcopy(op
, match
, (ptrdiff_t)sequence
.matchLength
-8); /* works even if matchLength < 8 */
3161 return oMatchEnd
- ostart
;
3164 static size_t ZSTD_decompressSequences(
3166 void* dst
, size_t maxDstSize
,
3167 const void* seqStart
, size_t seqSize
)
3169 ZSTD_DCtx
* dctx
= (ZSTD_DCtx
*)ctx
;
3170 const BYTE
* ip
= (const BYTE
*)seqStart
;
3171 const BYTE
* const iend
= ip
+ seqSize
;
3172 BYTE
* const ostart
= (BYTE
* const)dst
;
3174 BYTE
* const oend
= ostart
+ maxDstSize
;
3175 size_t errorCode
, dumpsLength
;
3176 const BYTE
* litPtr
= dctx
->litPtr
;
3177 const BYTE
* const litEnd
= litPtr
+ dctx
->litSize
;
3180 U32
* DTableLL
= dctx
->LLTable
;
3181 U32
* DTableML
= dctx
->MLTable
;
3182 U32
* DTableOffb
= dctx
->OffTable
;
3183 BYTE
* const base
= (BYTE
*) (dctx
->base
);
3185 /* Build Decoding Tables */
3186 errorCode
= ZSTD_decodeSeqHeaders(&nbSeq
, &dumps
, &dumpsLength
,
3187 DTableLL
, DTableML
, DTableOffb
,
3189 if (ZSTD_isError(errorCode
)) return errorCode
;
3192 /* Regen sequences */
3195 seqState_t seqState
;
3197 memset(&sequence
, 0, sizeof(sequence
));
3198 seqState
.dumps
= dumps
;
3199 seqState
.dumpsEnd
= dumps
+ dumpsLength
;
3200 seqState
.prevOffset
= 1;
3201 errorCode
= BIT_initDStream(&(seqState
.DStream
), ip
, iend
-ip
);
3202 if (ERR_isError(errorCode
)) return ERROR(corruption_detected
);
3203 FSE_initDState(&(seqState
.stateLL
), &(seqState
.DStream
), DTableLL
);
3204 FSE_initDState(&(seqState
.stateOffb
), &(seqState
.DStream
), DTableOffb
);
3205 FSE_initDState(&(seqState
.stateML
), &(seqState
.DStream
), DTableML
);
3207 for ( ; (BIT_reloadDStream(&(seqState
.DStream
)) <= BIT_DStream_completed
) && (nbSeq
>0) ; )
3211 ZSTD_decodeSequence(&sequence
, &seqState
);
3212 oneSeqSize
= ZSTD_execSequence(op
, sequence
, &litPtr
, litEnd
, base
, oend
);
3213 if (ZSTD_isError(oneSeqSize
)) return oneSeqSize
;
3217 /* check if reached exact end */
3218 if ( !BIT_endOfDStream(&(seqState
.DStream
)) ) return ERROR(corruption_detected
); /* requested too much : data is corrupted */
3219 if (nbSeq
<0) return ERROR(corruption_detected
); /* requested too many sequences : data is corrupted */
3221 /* last literal segment */
3223 size_t lastLLSize
= litEnd
- litPtr
;
3224 if (litPtr
> litEnd
) return ERROR(corruption_detected
);
3225 if (op
+lastLLSize
> oend
) return ERROR(dstSize_tooSmall
);
3226 if (op
!= litPtr
) memmove(op
, litPtr
, lastLLSize
);
3235 static size_t ZSTD_decompressBlock(
3237 void* dst
, size_t maxDstSize
,
3238 const void* src
, size_t srcSize
)
3240 /* blockType == blockCompressed */
3241 const BYTE
* ip
= (const BYTE
*)src
;
3243 /* Decode literals sub-block */
3244 size_t litCSize
= ZSTD_decodeLiteralsBlock(ctx
, src
, srcSize
);
3245 if (ZSTD_isError(litCSize
)) return litCSize
;
3247 srcSize
-= litCSize
;
3249 return ZSTD_decompressSequences(ctx
, dst
, maxDstSize
, ip
, srcSize
);
3253 static size_t ZSTD_decompressDCtx(void* ctx
, void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3255 const BYTE
* ip
= (const BYTE
*)src
;
3256 const BYTE
* iend
= ip
+ srcSize
;
3257 BYTE
* const ostart
= (BYTE
* const)dst
;
3259 BYTE
* const oend
= ostart
+ maxDstSize
;
3260 size_t remainingSize
= srcSize
;
3262 blockProperties_t blockProperties
;
3265 if (srcSize
< ZSTD_frameHeaderSize
+ZSTD_blockHeaderSize
) return ERROR(srcSize_wrong
);
3266 magicNumber
= MEM_readLE32(src
);
3267 if (magicNumber
!= ZSTD_magicNumber
) return ERROR(prefix_unknown
);
3268 ip
+= ZSTD_frameHeaderSize
; remainingSize
-= ZSTD_frameHeaderSize
;
3270 /* Loop on each block */
3273 size_t decodedSize
=0;
3274 size_t cBlockSize
= ZSTD_getcBlockSize(ip
, iend
-ip
, &blockProperties
);
3275 if (ZSTD_isError(cBlockSize
)) return cBlockSize
;
3277 ip
+= ZSTD_blockHeaderSize
;
3278 remainingSize
-= ZSTD_blockHeaderSize
;
3279 if (cBlockSize
> remainingSize
) return ERROR(srcSize_wrong
);
3281 switch(blockProperties
.blockType
)
3284 decodedSize
= ZSTD_decompressBlock(ctx
, op
, oend
-op
, ip
, cBlockSize
);
3287 decodedSize
= ZSTD_copyUncompressedBlock(op
, oend
-op
, ip
, cBlockSize
);
3290 return ERROR(GENERIC
); /* not yet supported */
3294 if (remainingSize
) return ERROR(srcSize_wrong
);
3297 return ERROR(GENERIC
); /* impossible */
3299 if (cBlockSize
== 0) break; /* bt_end */
3301 if (ZSTD_isError(decodedSize
)) return decodedSize
;
3304 remainingSize
-= cBlockSize
;
3310 static size_t ZSTD_decompress(void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3314 return ZSTD_decompressDCtx(&ctx
, dst
, maxDstSize
, src
, srcSize
);
3317 /* ZSTD_errorFrameSizeInfoLegacy() :
3318 assumes `cSize` and `dBound` are _not_ NULL */
3319 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize
, unsigned long long* dBound
, size_t ret
)
3322 *dBound
= ZSTD_CONTENTSIZE_ERROR
;
3325 void ZSTDv02_findFrameSizeInfoLegacy(const void *src
, size_t srcSize
, size_t* cSize
, unsigned long long* dBound
)
3327 const BYTE
* ip
= (const BYTE
*)src
;
3328 size_t remainingSize
= srcSize
;
3329 size_t nbBlocks
= 0;
3331 blockProperties_t blockProperties
;
3334 if (srcSize
< ZSTD_frameHeaderSize
+ZSTD_blockHeaderSize
) {
3335 ZSTD_errorFrameSizeInfoLegacy(cSize
, dBound
, ERROR(srcSize_wrong
));
3338 magicNumber
= MEM_readLE32(src
);
3339 if (magicNumber
!= ZSTD_magicNumber
) {
3340 ZSTD_errorFrameSizeInfoLegacy(cSize
, dBound
, ERROR(prefix_unknown
));
3343 ip
+= ZSTD_frameHeaderSize
; remainingSize
-= ZSTD_frameHeaderSize
;
3345 /* Loop on each block */
3348 size_t cBlockSize
= ZSTD_getcBlockSize(ip
, remainingSize
, &blockProperties
);
3349 if (ZSTD_isError(cBlockSize
)) {
3350 ZSTD_errorFrameSizeInfoLegacy(cSize
, dBound
, cBlockSize
);
3354 ip
+= ZSTD_blockHeaderSize
;
3355 remainingSize
-= ZSTD_blockHeaderSize
;
3356 if (cBlockSize
> remainingSize
) {
3357 ZSTD_errorFrameSizeInfoLegacy(cSize
, dBound
, ERROR(srcSize_wrong
));
3361 if (cBlockSize
== 0) break; /* bt_end */
3364 remainingSize
-= cBlockSize
;
3368 *cSize
= ip
- (const BYTE
*)src
;
3369 *dBound
= nbBlocks
* BLOCKSIZE
;
3372 /*******************************
3373 * Streaming Decompression API
3374 *******************************/
3376 static size_t ZSTD_resetDCtx(ZSTD_DCtx
* dctx
)
3378 dctx
->expected
= ZSTD_frameHeaderSize
;
3380 dctx
->previousDstEnd
= NULL
;
3385 static ZSTD_DCtx
* ZSTD_createDCtx(void)
3387 ZSTD_DCtx
* dctx
= (ZSTD_DCtx
*)malloc(sizeof(ZSTD_DCtx
));
3388 if (dctx
==NULL
) return NULL
;
3389 ZSTD_resetDCtx(dctx
);
3393 static size_t ZSTD_freeDCtx(ZSTD_DCtx
* dctx
)
3399 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx
* dctx
)
3401 return dctx
->expected
;
3404 static size_t ZSTD_decompressContinue(ZSTD_DCtx
* ctx
, void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3407 if (srcSize
!= ctx
->expected
) return ERROR(srcSize_wrong
);
3408 if (dst
!= ctx
->previousDstEnd
) /* not contiguous */
3411 /* Decompress : frame header */
3412 if (ctx
->phase
== 0)
3414 /* Check frame magic header */
3415 U32 magicNumber
= MEM_readLE32(src
);
3416 if (magicNumber
!= ZSTD_magicNumber
) return ERROR(prefix_unknown
);
3418 ctx
->expected
= ZSTD_blockHeaderSize
;
3422 /* Decompress : block header */
3423 if (ctx
->phase
== 1)
3425 blockProperties_t bp
;
3426 size_t blockSize
= ZSTD_getcBlockSize(src
, ZSTD_blockHeaderSize
, &bp
);
3427 if (ZSTD_isError(blockSize
)) return blockSize
;
3428 if (bp
.blockType
== bt_end
)
3435 ctx
->expected
= blockSize
;
3436 ctx
->bType
= bp
.blockType
;
3443 /* Decompress : block content */
3449 rSize
= ZSTD_decompressBlock(ctx
, dst
, maxDstSize
, src
, srcSize
);
3452 rSize
= ZSTD_copyUncompressedBlock(dst
, maxDstSize
, src
, srcSize
);
3455 return ERROR(GENERIC
); /* not yet handled */
3457 case bt_end
: /* should never happen (filtered at phase 1) */
3461 return ERROR(GENERIC
);
3464 ctx
->expected
= ZSTD_blockHeaderSize
;
3465 ctx
->previousDstEnd
= (void*)( ((char*)dst
) + rSize
);
3474 unsigned ZSTDv02_isError(size_t code
)
3476 return ZSTD_isError(code
);
3479 size_t ZSTDv02_decompress( void* dst
, size_t maxOriginalSize
,
3480 const void* src
, size_t compressedSize
)
3482 return ZSTD_decompress(dst
, maxOriginalSize
, src
, compressedSize
);
3485 ZSTDv02_Dctx
* ZSTDv02_createDCtx(void)
3487 return (ZSTDv02_Dctx
*)ZSTD_createDCtx();
3490 size_t ZSTDv02_freeDCtx(ZSTDv02_Dctx
* dctx
)
3492 return ZSTD_freeDCtx((ZSTD_DCtx
*)dctx
);
3495 size_t ZSTDv02_resetDCtx(ZSTDv02_Dctx
* dctx
)
3497 return ZSTD_resetDCtx((ZSTD_DCtx
*)dctx
);
3500 size_t ZSTDv02_nextSrcSizeToDecompress(ZSTDv02_Dctx
* dctx
)
3502 return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx
*)dctx
);
3505 size_t ZSTDv02_decompressContinue(ZSTDv02_Dctx
* dctx
, void* dst
, size_t maxDstSize
, const void* src
, size_t srcSize
)
3507 return ZSTD_decompressContinue((ZSTD_DCtx
*)dctx
, dst
, maxDstSize
, src
, srcSize
);