1/*
2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under both the BSD-style license (found in the
6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7 * in the COPYING file in the root directory of this source tree).
8 * You may select, at your option, one of the above-listed licenses.
9 */
10
11
12/*- Dependencies -*/
13#include "zstd_v05.h"
14#include "error_private.h"
15
16
17/* ******************************************************************
18 mem.h
19 low-level memory access routines
20 Copyright (C) 2013-2015, Yann Collet.
21
22 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
23
24 Redistribution and use in source and binary forms, with or without
25 modification, are permitted provided that the following conditions are
26 met:
27
28 * Redistributions of source code must retain the above copyright
29 notice, this list of conditions and the following disclaimer.
30 * Redistributions in binary form must reproduce the above
31 copyright notice, this list of conditions and the following disclaimer
32 in the documentation and/or other materials provided with the
33 distribution.
34
35 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
38 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
39 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
42 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
43 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
44 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
45 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
46
47 You can contact the author at :
48 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
49 - Public forum : https://groups.google.com/forum/#!forum/lz4c
50****************************************************************** */
51#ifndef MEM_H_MODULE
52#define MEM_H_MODULE
53
54#if defined (__cplusplus)
55extern "C" {
56#endif
57
58/*-****************************************
59* Dependencies
60******************************************/
61#include <stddef.h> /* size_t, ptrdiff_t */
62#include <string.h> /* memcpy */
63
64
65/*-****************************************
66* Compiler specifics
67******************************************/
68#if defined(__GNUC__)
69# define MEM_STATIC static __attribute__((unused))
70#elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
71# define MEM_STATIC static inline
72#elif defined(_MSC_VER)
73# define MEM_STATIC static __inline
74#else
75# define MEM_STATIC static /* this version may generate warnings for unused static functions; disable the relevant warning */
76#endif
77
78
79/*-**************************************************************
80* Basic Types
81*****************************************************************/
82#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
83# include <stdint.h>
84 typedef uint8_t BYTE;
85 typedef uint16_t U16;
86 typedef int16_t S16;
87 typedef uint32_t U32;
88 typedef int32_t S32;
89 typedef uint64_t U64;
90 typedef int64_t S64;
91#else
92 typedef unsigned char BYTE;
93 typedef unsigned short U16;
94 typedef signed short S16;
95 typedef unsigned int U32;
96 typedef signed int S32;
97 typedef unsigned long long U64;
98 typedef signed long long S64;
99#endif
100
101
102/*-**************************************************************
103* Memory I/O
104*****************************************************************/
105/* MEM_FORCE_MEMORY_ACCESS :
106 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
107 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
108 * The below switch allow to select different access method for improved performance.
109 * Method 0 (default) : use `memcpy()`. Safe and portable.
110 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
111 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
112 * Method 2 : direct access. This method is portable but violate C standard.
113 * It can generate buggy code on targets depending on alignment.
114 * In some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
115 * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
116 * Prefer these methods in priority order (0 > 1 > 2)
117 */
118#ifndef MEM_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
119# 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__) )
120# define MEM_FORCE_MEMORY_ACCESS 2
121# elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
122 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
123# define MEM_FORCE_MEMORY_ACCESS 1
124# endif
125#endif
126
127MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
128MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
129
130MEM_STATIC unsigned MEM_isLittleEndian(void)
131{
132 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
133 return one.c[0];
134}
135
136#if defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==2)
137
138/* violates C standard, by lying on structure alignment.
139Only use if no other choice to achieve best performance on target platform */
140MEM_STATIC U16 MEM_read16(const void* memPtr) { return *(const U16*) memPtr; }
141MEM_STATIC U32 MEM_read32(const void* memPtr) { return *(const U32*) memPtr; }
142MEM_STATIC U64 MEM_read64(const void* memPtr) { return *(const U64*) memPtr; }
143
144MEM_STATIC void MEM_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
145MEM_STATIC void MEM_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
146MEM_STATIC void MEM_write64(void* memPtr, U64 value) { *(U64*)memPtr = value; }
147
148#elif defined(MEM_FORCE_MEMORY_ACCESS) && (MEM_FORCE_MEMORY_ACCESS==1)
149
150/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
151/* currently only defined for gcc and icc */
152typedef union { U16 u16; U32 u32; U64 u64; size_t st; } __attribute__((packed)) unalign;
153
154MEM_STATIC U16 MEM_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
155MEM_STATIC U32 MEM_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
156MEM_STATIC U64 MEM_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
157
158MEM_STATIC void MEM_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
159MEM_STATIC void MEM_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }
160MEM_STATIC void MEM_write64(void* memPtr, U64 value) { ((unalign*)memPtr)->u64 = value; }
161
162#else
163
164/* default method, safe and standard.
165 can sometimes prove slower */
166
167MEM_STATIC U16 MEM_read16(const void* memPtr)
168{
169 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
170}
171
172MEM_STATIC U32 MEM_read32(const void* memPtr)
173{
174 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
175}
176
177MEM_STATIC U64 MEM_read64(const void* memPtr)
178{
179 U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
180}
181
182MEM_STATIC void MEM_write16(void* memPtr, U16 value)
183{
184 memcpy(memPtr, &value, sizeof(value));
185}
186
187MEM_STATIC void MEM_write32(void* memPtr, U32 value)
188{
189 memcpy(memPtr, &value, sizeof(value));
190}
191
192MEM_STATIC void MEM_write64(void* memPtr, U64 value)
193{
194 memcpy(memPtr, &value, sizeof(value));
195}
196
197#endif /* MEM_FORCE_MEMORY_ACCESS */
198
199
200MEM_STATIC U16 MEM_readLE16(const void* memPtr)
201{
202 if (MEM_isLittleEndian())
203 return MEM_read16(memPtr);
204 else {
205 const BYTE* p = (const BYTE*)memPtr;
206 return (U16)(p[0] + (p[1]<<8));
207 }
208}
209
210MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
211{
212 if (MEM_isLittleEndian()) {
213 MEM_write16(memPtr, val);
214 } else {
215 BYTE* p = (BYTE*)memPtr;
216 p[0] = (BYTE)val;
217 p[1] = (BYTE)(val>>8);
218 }
219}
220
221MEM_STATIC U32 MEM_readLE32(const void* memPtr)
222{
223 if (MEM_isLittleEndian())
224 return MEM_read32(memPtr);
225 else {
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));
228 }
229}
230
231
232MEM_STATIC U64 MEM_readLE64(const void* memPtr)
233{
234 if (MEM_isLittleEndian())
235 return MEM_read64(memPtr);
236 else {
237 const BYTE* p = (const BYTE*)memPtr;
238 return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
239 + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
240 }
241}
242
243
244MEM_STATIC size_t MEM_readLEST(const void* memPtr)
245{
246 if (MEM_32bits())
247 return (size_t)MEM_readLE32(memPtr);
248 else
249 return (size_t)MEM_readLE64(memPtr);
250}
251
252
253#if defined (__cplusplus)
254}
255#endif
256
257#endif /* MEM_H_MODULE */
258
259/*
260 zstd - standard compression library
261 Header File for static linking only
262 Copyright (C) 2014-2016, Yann Collet.
263
264 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
265
266 Redistribution and use in source and binary forms, with or without
267 modification, are permitted provided that the following conditions are
268 met:
269 * Redistributions of source code must retain the above copyright
270 notice, this list of conditions and the following disclaimer.
271 * Redistributions in binary form must reproduce the above
272 copyright notice, this list of conditions and the following disclaimer
273 in the documentation and/or other materials provided with the
274 distribution.
275 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
276 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
277 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
278 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
279 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
280 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
281 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
282 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
283 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
284 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
285 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
286
287 You can contact the author at :
288 - zstd homepage : http://www.zstd.net
289*/
290#ifndef ZSTD_STATIC_H
291#define ZSTD_STATIC_H
292
293/* The prototypes defined within this file are considered experimental.
294 * They should not be used in the context DLL as they may change in the future.
295 * Prefer static linking if you need them, to control breaking version changes issues.
296 */
297
298#if defined (__cplusplus)
299extern "C" {
300#endif
301
302
303
304/*-*************************************
305* Types
306***************************************/
307#define ZSTDv05_WINDOWLOG_ABSOLUTEMIN 11
308
309
310/*-*************************************
311* Advanced functions
312***************************************/
313/*- Advanced Decompression functions -*/
314
315/*! ZSTDv05_decompress_usingPreparedDCtx() :
316* Same as ZSTDv05_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
317* It avoids reloading the dictionary each time.
318* `preparedDCtx` must have been properly initialized using ZSTDv05_decompressBegin_usingDict().
319* Requires 2 contexts : 1 for reference, which will not be modified, and 1 to run the decompression operation */
320size_t ZSTDv05_decompress_usingPreparedDCtx(
321 ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* preparedDCtx,
322 void* dst, size_t dstCapacity,
323 const void* src, size_t srcSize);
324
325
326/* **************************************
327* Streaming functions (direct mode)
328****************************************/
329size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx);
330
331/*
332 Streaming decompression, direct mode (bufferless)
333
334 A ZSTDv05_DCtx object is required to track streaming operations.
335 Use ZSTDv05_createDCtx() / ZSTDv05_freeDCtx() to manage it.
336 A ZSTDv05_DCtx object can be re-used multiple times.
337
338 First typical operation is to retrieve frame parameters, using ZSTDv05_getFrameParams().
339 This operation is independent, and just needs enough input data to properly decode the frame header.
340 Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.
341 Result : 0 when successful, it means the ZSTDv05_parameters structure has been filled.
342 >0 : means there is not enough data into src. Provides the expected size to successfully decode header.
343 errorCode, which can be tested using ZSTDv05_isError()
344
345 Start decompression, with ZSTDv05_decompressBegin() or ZSTDv05_decompressBegin_usingDict()
346 Alternatively, you can copy a prepared context, using ZSTDv05_copyDCtx()
347
348 Then use ZSTDv05_nextSrcSizeToDecompress() and ZSTDv05_decompressContinue() alternatively.
349 ZSTDv05_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv05_decompressContinue().
350 ZSTDv05_decompressContinue() requires this exact amount of bytes, or it will fail.
351 ZSTDv05_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
352 They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
353
354 @result of ZSTDv05_decompressContinue() is the number of bytes regenerated within 'dst'.
355 It can be zero, which is not an error; it just means ZSTDv05_decompressContinue() has decoded some header.
356
357 A frame is fully decoded when ZSTDv05_nextSrcSizeToDecompress() returns zero.
358 Context can then be reset to start a new decompression.
359*/
360
361
362/* **************************************
363* Block functions
364****************************************/
365/*! Block functions produce and decode raw zstd blocks, without frame metadata.
366 User will have to take in charge required information to regenerate data, such as block sizes.
367
368 A few rules to respect :
369 - Uncompressed block size must be <= 128 KB
370 - Compressing or decompressing requires a context structure
371 + Use ZSTDv05_createCCtx() and ZSTDv05_createDCtx()
372 - It is necessary to init context before starting
373 + compression : ZSTDv05_compressBegin()
374 + decompression : ZSTDv05_decompressBegin()
375 + variants _usingDict() are also allowed
376 + copyCCtx() and copyDCtx() work too
377 - When a block is considered not compressible enough, ZSTDv05_compressBlock() result will be zero.
378 In which case, nothing is produced into `dst`.
379 + User must test for such outcome and deal directly with uncompressed data
380 + ZSTDv05_decompressBlock() doesn't accept uncompressed data as input !!
381*/
382
383size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
384
385
386
387
388#if defined (__cplusplus)
389}
390#endif
391
392#endif /* ZSTDv05_STATIC_H */
393
394
395/*
396 zstd_internal - common functions to include
397 Header File for include
398 Copyright (C) 2014-2016, Yann Collet.
399
400 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
401
402 Redistribution and use in source and binary forms, with or without
403 modification, are permitted provided that the following conditions are
404 met:
405 * Redistributions of source code must retain the above copyright
406 notice, this list of conditions and the following disclaimer.
407 * Redistributions in binary form must reproduce the above
408 copyright notice, this list of conditions and the following disclaimer
409 in the documentation and/or other materials provided with the
410 distribution.
411 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
412 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
413 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
414 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
415 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
416 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
417 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
418 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
419 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
420 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
421 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
422
423 You can contact the author at :
424 - zstd source repository : https://github.com/Cyan4973/zstd
425*/
426#ifndef ZSTD_CCOMMON_H_MODULE
427#define ZSTD_CCOMMON_H_MODULE
428
429
430
431/*-*************************************
432* Common macros
433***************************************/
434#define MIN(a,b) ((a)<(b) ? (a) : (b))
435#define MAX(a,b) ((a)>(b) ? (a) : (b))
436
437
438/*-*************************************
439* Common constants
440***************************************/
441#define ZSTDv05_DICT_MAGIC 0xEC30A435
442
443#define KB *(1 <<10)
444#define MB *(1 <<20)
445#define GB *(1U<<30)
446
447#define BLOCKSIZE (128 KB) /* define, for static allocation */
448
449static const size_t ZSTDv05_blockHeaderSize = 3;
450static const size_t ZSTDv05_frameHeaderSize_min = 5;
451#define ZSTDv05_frameHeaderSize_max 5 /* define, for static allocation */
452
453#define BITv057 128
454#define BITv056 64
455#define BITv055 32
456#define BITv054 16
457#define BITv051 2
458#define BITv050 1
459
460#define IS_HUFv05 0
461#define IS_PCH 1
462#define IS_RAW 2
463#define IS_RLE 3
464
465#define MINMATCH 4
466#define REPCODE_STARTVALUE 1
467
468#define Litbits 8
469#define MLbits 7
470#define LLbits 6
471#define Offbits 5
472#define MaxLit ((1<<Litbits) - 1)
473#define MaxML ((1<<MLbits) - 1)
474#define MaxLL ((1<<LLbits) - 1)
475#define MaxOff ((1<<Offbits)- 1)
476#define MLFSEv05Log 10
477#define LLFSEv05Log 10
478#define OffFSEv05Log 9
479#define MaxSeq MAX(MaxLL, MaxML)
480
481#define FSEv05_ENCODING_RAW 0
482#define FSEv05_ENCODING_RLE 1
483#define FSEv05_ENCODING_STATIC 2
484#define FSEv05_ENCODING_DYNAMIC 3
485
486
487#define HufLog 12
488
489#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
490#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
491
492#define WILDCOPY_OVERLENGTH 8
493
494typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
495
496
497/*-*******************************************
498* Shared functions to include for inlining
499*********************************************/
500static void ZSTDv05_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
501
502#define COPY8(d,s) { ZSTDv05_copy8(d,s); d+=8; s+=8; }
503
504/*! ZSTDv05_wildcopy() :
505* custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
506MEM_STATIC void ZSTDv05_wildcopy(void* dst, const void* src, ptrdiff_t length)
507{
508 const BYTE* ip = (const BYTE*)src;
509 BYTE* op = (BYTE*)dst;
510 BYTE* const oend = op + length;
511 do
512 COPY8(op, ip)
513 while (op < oend);
514}
515
516
517/*-*******************************************
518* Private interfaces
519*********************************************/
520typedef struct {
521 void* buffer;
522 U32* offsetStart;
523 U32* offset;
524 BYTE* offCodeStart;
525 BYTE* offCode;
526 BYTE* litStart;
527 BYTE* lit;
528 BYTE* litLengthStart;
529 BYTE* litLength;
530 BYTE* matchLengthStart;
531 BYTE* matchLength;
532 BYTE* dumpsStart;
533 BYTE* dumps;
534 /* opt */
535 U32* matchLengthFreq;
536 U32* litLengthFreq;
537 U32* litFreq;
538 U32* offCodeFreq;
539 U32 matchLengthSum;
540 U32 litLengthSum;
541 U32 litSum;
542 U32 offCodeSum;
543} seqStore_t;
544
545
546
547#endif /* ZSTDv05_CCOMMON_H_MODULE */
548/* ******************************************************************
549 FSEv05 : Finite State Entropy coder
550 header file
551 Copyright (C) 2013-2015, Yann Collet.
552
553 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
554
555 Redistribution and use in source and binary forms, with or without
556 modification, are permitted provided that the following conditions are
557 met:
558
559 * Redistributions of source code must retain the above copyright
560 notice, this list of conditions and the following disclaimer.
561 * Redistributions in binary form must reproduce the above
562 copyright notice, this list of conditions and the following disclaimer
563 in the documentation and/or other materials provided with the
564 distribution.
565
566 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
567 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
568 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
569 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
570 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
571 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
572 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
573 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
574 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
575 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
576 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
577
578 You can contact the author at :
579 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
580 - Public forum : https://groups.google.com/forum/#!forum/lz4c
581****************************************************************** */
582#ifndef FSEv05_H
583#define FSEv05_H
584
585#if defined (__cplusplus)
586extern "C" {
587#endif
588
589
590/* *****************************************
591* Includes
592******************************************/
593#include <stddef.h> /* size_t, ptrdiff_t */
594
595
596/*-****************************************
597* FSEv05 simple functions
598******************************************/
599size_t FSEv05_decompress(void* dst, size_t maxDstSize,
600 const void* cSrc, size_t cSrcSize);
601/*!
602FSEv05_decompress():
603 Decompress FSEv05 data from buffer 'cSrc', of size 'cSrcSize',
604 into already allocated destination buffer 'dst', of size 'maxDstSize'.
605 return : size of regenerated data (<= maxDstSize)
606 or an error code, which can be tested using FSEv05_isError()
607
608 ** Important ** : FSEv05_decompress() doesn't decompress non-compressible nor RLE data !!!
609 Why ? : making this distinction requires a header.
610 Header management is intentionally delegated to the user layer, which can better manage special cases.
611*/
612
613
614/* *****************************************
615* Tool functions
616******************************************/
617/* Error Management */
618unsigned FSEv05_isError(size_t code); /* tells if a return value is an error code */
619const char* FSEv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
620
621
622
623
624/* *****************************************
625* FSEv05 detailed API
626******************************************/
627/* *** DECOMPRESSION *** */
628
629/*!
630FSEv05_readNCount():
631 Read compactly saved 'normalizedCounter' from 'rBuffer'.
632 return : size read from 'rBuffer'
633 or an errorCode, which can be tested using FSEv05_isError()
634 maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
635size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
636
637/*!
638Constructor and Destructor of type FSEv05_DTable
639 Note that its size depends on 'tableLog' */
640typedef unsigned FSEv05_DTable; /* don't allocate that. It's just a way to be more restrictive than void* */
641FSEv05_DTable* FSEv05_createDTable(unsigned tableLog);
642void FSEv05_freeDTable(FSEv05_DTable* dt);
643
644/*!
645FSEv05_buildDTable():
646 Builds 'dt', which must be already allocated, using FSEv05_createDTable()
647 @return : 0,
648 or an errorCode, which can be tested using FSEv05_isError() */
649size_t FSEv05_buildDTable (FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
650
651/*!
652FSEv05_decompress_usingDTable():
653 Decompress compressed source @cSrc of size @cSrcSize using `dt`
654 into `dst` which must be already allocated.
655 @return : size of regenerated data (necessarily <= @dstCapacity)
656 or an errorCode, which can be tested using FSEv05_isError() */
657size_t FSEv05_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv05_DTable* dt);
658
659
660
661#if defined (__cplusplus)
662}
663#endif
664
665#endif /* FSEv05_H */
666/* ******************************************************************
667 bitstream
668 Part of FSEv05 library
669 header file (to include)
670 Copyright (C) 2013-2016, Yann Collet.
671
672 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
673
674 Redistribution and use in source and binary forms, with or without
675 modification, are permitted provided that the following conditions are
676 met:
677
678 * Redistributions of source code must retain the above copyright
679 notice, this list of conditions and the following disclaimer.
680 * Redistributions in binary form must reproduce the above
681 copyright notice, this list of conditions and the following disclaimer
682 in the documentation and/or other materials provided with the
683 distribution.
684
685 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
686 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
687 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
688 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
689 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
690 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
691 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
692 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
693 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
694 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
695 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
696
697 You can contact the author at :
698 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
699****************************************************************** */
700#ifndef BITv05STREAM_H_MODULE
701#define BITv05STREAM_H_MODULE
702
703#if defined (__cplusplus)
704extern "C" {
705#endif
706
707
708/*
709* This API consists of small unitary functions, which highly benefit from being inlined.
710* Since link-time-optimization is not available for all compilers,
711* these functions are defined into a .h to be included.
712*/
713
714
715
716/*-********************************************
717* bitStream decoding API (read backward)
718**********************************************/
719typedef struct
720{
721 size_t bitContainer;
722 unsigned bitsConsumed;
723 const char* ptr;
724 const char* start;
725} BITv05_DStream_t;
726
727typedef enum { BITv05_DStream_unfinished = 0,
728 BITv05_DStream_endOfBuffer = 1,
729 BITv05_DStream_completed = 2,
730 BITv05_DStream_overflow = 3 } BITv05_DStream_status; /* result of BITv05_reloadDStream() */
731 /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
732
733MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
734MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, unsigned nbBits);
735MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD);
736MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* bitD);
737
738
739/*-****************************************
740* unsafe API
741******************************************/
742MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, unsigned nbBits);
743/* faster, but works only if nbBits >= 1 */
744
745
746
747/*-**************************************************************
748* Helper functions
749****************************************************************/
750MEM_STATIC unsigned BITv05_highbit32 (U32 val)
751{
752# if defined(_MSC_VER) /* Visual */
753 unsigned long r=0;
754 _BitScanReverse ( &r, val );
755 return (unsigned) r;
756# elif defined(__GNUC__) && (__GNUC__ >= 3) /* Use GCC Intrinsic */
757 return 31 - __builtin_clz (val);
758# else /* Software version */
759 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 };
760 U32 v = val;
761 unsigned r;
762 v |= v >> 1;
763 v |= v >> 2;
764 v |= v >> 4;
765 v |= v >> 8;
766 v |= v >> 16;
767 r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
768 return r;
769# endif
770}
771
772
773
774/*-********************************************************
775* bitStream decoding
776**********************************************************/
777/*!BITv05_initDStream
778* Initialize a BITv05_DStream_t.
779* @bitD : a pointer to an already allocated BITv05_DStream_t structure
780* @srcBuffer must point at the beginning of a bitStream
781* @srcSize must be the exact size of the bitStream
782* @result : size of stream (== srcSize) or an errorCode if a problem is detected
783*/
784MEM_STATIC size_t BITv05_initDStream(BITv05_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
785{
786 if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
787
788 if (srcSize >= sizeof(size_t)) { /* normal case */
789 U32 contain32;
790 bitD->start = (const char*)srcBuffer;
791 bitD->ptr = (const char*)srcBuffer + srcSize - sizeof(size_t);
792 bitD->bitContainer = MEM_readLEST(bitD->ptr);
793 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
794 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
795 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
796 } else {
797 U32 contain32;
798 bitD->start = (const char*)srcBuffer;
799 bitD->ptr = bitD->start;
800 bitD->bitContainer = *(const BYTE*)(bitD->start);
801 switch(srcSize)
802 {
803 case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
804 case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
805 case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
806 case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
807 case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
808 case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) << 8; /* fall-through */
809 default: break;
810 }
811 contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
812 if (contain32 == 0) return ERROR(GENERIC); /* endMark not present */
813 bitD->bitsConsumed = 8 - BITv05_highbit32(contain32);
814 bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
815 }
816
817 return srcSize;
818}
819
820MEM_STATIC size_t BITv05_lookBits(BITv05_DStream_t* bitD, U32 nbBits)
821{
822 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
823 return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
824}
825
826/*! BITv05_lookBitsFast :
827* unsafe version; only works only if nbBits >= 1 */
828MEM_STATIC size_t BITv05_lookBitsFast(BITv05_DStream_t* bitD, U32 nbBits)
829{
830 const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
831 return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
832}
833
834MEM_STATIC void BITv05_skipBits(BITv05_DStream_t* bitD, U32 nbBits)
835{
836 bitD->bitsConsumed += nbBits;
837}
838
839MEM_STATIC size_t BITv05_readBits(BITv05_DStream_t* bitD, U32 nbBits)
840{
841 size_t value = BITv05_lookBits(bitD, nbBits);
842 BITv05_skipBits(bitD, nbBits);
843 return value;
844}
845
846/*!BITv05_readBitsFast :
847* unsafe version; only works only if nbBits >= 1 */
848MEM_STATIC size_t BITv05_readBitsFast(BITv05_DStream_t* bitD, U32 nbBits)
849{
850 size_t value = BITv05_lookBitsFast(bitD, nbBits);
851 BITv05_skipBits(bitD, nbBits);
852 return value;
853}
854
855MEM_STATIC BITv05_DStream_status BITv05_reloadDStream(BITv05_DStream_t* bitD)
856{
857 if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8)) /* should never happen */
858 return BITv05_DStream_overflow;
859
860 if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
861 bitD->ptr -= bitD->bitsConsumed >> 3;
862 bitD->bitsConsumed &= 7;
863 bitD->bitContainer = MEM_readLEST(bitD->ptr);
864 return BITv05_DStream_unfinished;
865 }
866 if (bitD->ptr == bitD->start) {
867 if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv05_DStream_endOfBuffer;
868 return BITv05_DStream_completed;
869 }
870 {
871 U32 nbBytes = bitD->bitsConsumed >> 3;
872 BITv05_DStream_status result = BITv05_DStream_unfinished;
873 if (bitD->ptr - nbBytes < bitD->start) {
874 nbBytes = (U32)(bitD->ptr - bitD->start); /* ptr > start */
875 result = BITv05_DStream_endOfBuffer;
876 }
877 bitD->ptr -= nbBytes;
878 bitD->bitsConsumed -= nbBytes*8;
879 bitD->bitContainer = MEM_readLEST(bitD->ptr); /* reminder : srcSize > sizeof(bitD) */
880 return result;
881 }
882}
883
884/*! BITv05_endOfDStream
885* @return Tells if DStream has reached its exact end
886*/
887MEM_STATIC unsigned BITv05_endOfDStream(const BITv05_DStream_t* DStream)
888{
889 return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
890}
891
892#if defined (__cplusplus)
893}
894#endif
895
896#endif /* BITv05STREAM_H_MODULE */
897/* ******************************************************************
898 FSEv05 : Finite State Entropy coder
899 header file for static linking (only)
900 Copyright (C) 2013-2015, Yann Collet
901
902 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
903
904 Redistribution and use in source and binary forms, with or without
905 modification, are permitted provided that the following conditions are
906 met:
907
908 * Redistributions of source code must retain the above copyright
909 notice, this list of conditions and the following disclaimer.
910 * Redistributions in binary form must reproduce the above
911 copyright notice, this list of conditions and the following disclaimer
912 in the documentation and/or other materials provided with the
913 distribution.
914
915 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
916 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
917 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
918 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
919 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
920 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
921 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
922 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
923 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
924 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
925 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
926
927 You can contact the author at :
928 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
929 - Public forum : https://groups.google.com/forum/#!forum/lz4c
930****************************************************************** */
931#ifndef FSEv05_STATIC_H
932#define FSEv05_STATIC_H
933
934#if defined (__cplusplus)
935extern "C" {
936#endif
937
938
939
940/* *****************************************
941* Static allocation
942*******************************************/
943/* It is possible to statically allocate FSEv05 CTable/DTable as a table of unsigned using below macros */
944#define FSEv05_DTABLE_SIZE_U32(maxTableLog) (1 + (1<<maxTableLog))
945
946
947/* *****************************************
948* FSEv05 advanced API
949*******************************************/
950size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits);
951/* build a fake FSEv05_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
952
953size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, unsigned char symbolValue);
954/* build a fake FSEv05_DTable, designed to always generate the same symbolValue */
955
956
957
958/* *****************************************
959* FSEv05 symbol decompression API
960*******************************************/
961typedef struct
962{
963 size_t state;
964 const void* table; /* precise table may vary, depending on U16 */
965} FSEv05_DState_t;
966
967
968static void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt);
969
970static unsigned char FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
971
972static unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr);
973
974
975
976/* *****************************************
977* FSEv05 unsafe API
978*******************************************/
979static unsigned char FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD);
980/* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
981
982
983/* *****************************************
984* Implementation of inlined functions
985*******************************************/
986/* decompression */
987
988typedef struct {
989 U16 tableLog;
990 U16 fastMode;
991} FSEv05_DTableHeader; /* sizeof U32 */
992
993typedef struct
994{
995 unsigned short newState;
996 unsigned char symbol;
997 unsigned char nbBits;
998} FSEv05_decode_t; /* size == U32 */
999
1000MEM_STATIC void FSEv05_initDState(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD, const FSEv05_DTable* dt)
1001{
1002 const void* ptr = dt;
1003 const FSEv05_DTableHeader* const DTableH = (const FSEv05_DTableHeader*)ptr;
1004 DStatePtr->state = BITv05_readBits(bitD, DTableH->tableLog);
1005 BITv05_reloadDStream(bitD);
1006 DStatePtr->table = dt + 1;
1007}
1008
1009MEM_STATIC BYTE FSEv05_peakSymbol(FSEv05_DState_t* DStatePtr)
1010{
1011 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1012 return DInfo.symbol;
1013}
1014
1015MEM_STATIC BYTE FSEv05_decodeSymbol(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
1016{
1017 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1018 const U32 nbBits = DInfo.nbBits;
1019 BYTE symbol = DInfo.symbol;
1020 size_t lowBits = BITv05_readBits(bitD, nbBits);
1021
1022 DStatePtr->state = DInfo.newState + lowBits;
1023 return symbol;
1024}
1025
1026MEM_STATIC BYTE FSEv05_decodeSymbolFast(FSEv05_DState_t* DStatePtr, BITv05_DStream_t* bitD)
1027{
1028 const FSEv05_decode_t DInfo = ((const FSEv05_decode_t*)(DStatePtr->table))[DStatePtr->state];
1029 const U32 nbBits = DInfo.nbBits;
1030 BYTE symbol = DInfo.symbol;
1031 size_t lowBits = BITv05_readBitsFast(bitD, nbBits);
1032
1033 DStatePtr->state = DInfo.newState + lowBits;
1034 return symbol;
1035}
1036
1037MEM_STATIC unsigned FSEv05_endOfDState(const FSEv05_DState_t* DStatePtr)
1038{
1039 return DStatePtr->state == 0;
1040}
1041
1042
1043#if defined (__cplusplus)
1044}
1045#endif
1046
1047#endif /* FSEv05_STATIC_H */
1048/* ******************************************************************
1049 FSEv05 : Finite State Entropy coder
1050 Copyright (C) 2013-2015, Yann Collet.
1051
1052 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1053
1054 Redistribution and use in source and binary forms, with or without
1055 modification, are permitted provided that the following conditions are
1056 met:
1057
1058 * Redistributions of source code must retain the above copyright
1059 notice, this list of conditions and the following disclaimer.
1060 * Redistributions in binary form must reproduce the above
1061 copyright notice, this list of conditions and the following disclaimer
1062 in the documentation and/or other materials provided with the
1063 distribution.
1064
1065 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1066 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1067 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1068 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1069 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1070 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1071 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1072 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1073 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1074 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1075 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1076
1077 You can contact the author at :
1078 - FSEv05 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1079 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1080****************************************************************** */
1081
1082#ifndef FSEv05_COMMONDEFS_ONLY
1083
1084/* **************************************************************
1085* Tuning parameters
1086****************************************************************/
1087/*!MEMORY_USAGE :
1088* Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1089* Increasing memory usage improves compression ratio
1090* Reduced memory usage can improve speed, due to cache effect
1091* Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1092#define FSEv05_MAX_MEMORY_USAGE 14
1093#define FSEv05_DEFAULT_MEMORY_USAGE 13
1094
1095/*!FSEv05_MAX_SYMBOL_VALUE :
1096* Maximum symbol value authorized.
1097* Required for proper stack allocation */
1098#define FSEv05_MAX_SYMBOL_VALUE 255
1099
1100
1101/* **************************************************************
1102* template functions type & suffix
1103****************************************************************/
1104#define FSEv05_FUNCTION_TYPE BYTE
1105#define FSEv05_FUNCTION_EXTENSION
1106#define FSEv05_DECODE_TYPE FSEv05_decode_t
1107
1108
1109#endif /* !FSEv05_COMMONDEFS_ONLY */
1110
1111/* **************************************************************
1112* Compiler specifics
1113****************************************************************/
1114#ifdef _MSC_VER /* Visual Studio */
1115# define FORCE_INLINE static __forceinline
1116# include <intrin.h> /* For Visual 2005 */
1117# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1118# pragma warning(disable : 4214) /* disable: C4214: non-int bitfields */
1119#else
1120# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
1121# ifdef __GNUC__
1122# define FORCE_INLINE static inline __attribute__((always_inline))
1123# else
1124# define FORCE_INLINE static inline
1125# endif
1126# else
1127# define FORCE_INLINE static
1128# endif /* __STDC_VERSION__ */
1129#endif
1130
1131
1132/* **************************************************************
1133* Includes
1134****************************************************************/
1135#include <stdlib.h> /* malloc, free, qsort */
1136#include <string.h> /* memcpy, memset */
1137#include <stdio.h> /* printf (debug) */
1138
1139
1140
1141/* ***************************************************************
1142* Constants
1143*****************************************************************/
1144#define FSEv05_MAX_TABLELOG (FSEv05_MAX_MEMORY_USAGE-2)
1145#define FSEv05_MAX_TABLESIZE (1U<<FSEv05_MAX_TABLELOG)
1146#define FSEv05_MAXTABLESIZE_MASK (FSEv05_MAX_TABLESIZE-1)
1147#define FSEv05_DEFAULT_TABLELOG (FSEv05_DEFAULT_MEMORY_USAGE-2)
1148#define FSEv05_MIN_TABLELOG 5
1149
1150#define FSEv05_TABLELOG_ABSOLUTE_MAX 15
1151#if FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX
1152#error "FSEv05_MAX_TABLELOG > FSEv05_TABLELOG_ABSOLUTE_MAX is not supported"
1153#endif
1154
1155
1156/* **************************************************************
1157* Error Management
1158****************************************************************/
1159#define FSEv05_STATIC_ASSERT(c) { enum { FSEv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1160
1161
1162/* **************************************************************
1163* Complex types
1164****************************************************************/
1165typedef U32 DTable_max_t[FSEv05_DTABLE_SIZE_U32(FSEv05_MAX_TABLELOG)];
1166
1167
1168/* **************************************************************
1169* Templates
1170****************************************************************/
1171/*
1172 designed to be included
1173 for type-specific functions (template emulation in C)
1174 Objective is to write these functions only once, for improved maintenance
1175*/
1176
1177/* safety checks */
1178#ifndef FSEv05_FUNCTION_EXTENSION
1179# error "FSEv05_FUNCTION_EXTENSION must be defined"
1180#endif
1181#ifndef FSEv05_FUNCTION_TYPE
1182# error "FSEv05_FUNCTION_TYPE must be defined"
1183#endif
1184
1185/* Function names */
1186#define FSEv05_CAT(X,Y) X##Y
1187#define FSEv05_FUNCTION_NAME(X,Y) FSEv05_CAT(X,Y)
1188#define FSEv05_TYPE_NAME(X,Y) FSEv05_CAT(X,Y)
1189
1190
1191/* Function templates */
1192static U32 FSEv05_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1193
1194
1195
1196FSEv05_DTable* FSEv05_createDTable (unsigned tableLog)
1197{
1198 if (tableLog > FSEv05_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv05_TABLELOG_ABSOLUTE_MAX;
1199 return (FSEv05_DTable*)malloc( FSEv05_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1200}
1201
1202void FSEv05_freeDTable (FSEv05_DTable* dt)
1203{
1204 free(dt);
1205}
1206
1207size_t FSEv05_buildDTable(FSEv05_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1208{
1209 FSEv05_DTableHeader DTableH;
1210 void* const tdPtr = dt+1; /* because dt is unsigned, 32-bits aligned on 32-bits */
1211 FSEv05_DECODE_TYPE* const tableDecode = (FSEv05_DECODE_TYPE*) (tdPtr);
1212 const U32 tableSize = 1 << tableLog;
1213 const U32 tableMask = tableSize-1;
1214 const U32 step = FSEv05_tableStep(tableSize);
1215 U16 symbolNext[FSEv05_MAX_SYMBOL_VALUE+1];
1216 U32 position = 0;
1217 U32 highThreshold = tableSize-1;
1218 const S16 largeLimit= (S16)(1 << (tableLog-1));
1219 U32 noLarge = 1;
1220 U32 s;
1221
1222 /* Sanity Checks */
1223 if (maxSymbolValue > FSEv05_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1224 if (tableLog > FSEv05_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1225
1226 /* Init, lay down lowprob symbols */
1227 DTableH.tableLog = (U16)tableLog;
1228 for (s=0; s<=maxSymbolValue; s++) {
1229 if (normalizedCounter[s]==-1) {
1230 tableDecode[highThreshold--].symbol = (FSEv05_FUNCTION_TYPE)s;
1231 symbolNext[s] = 1;
1232 } else {
1233 if (normalizedCounter[s] >= largeLimit) noLarge=0;
1234 symbolNext[s] = normalizedCounter[s];
1235 } }
1236
1237 /* Spread symbols */
1238 for (s=0; s<=maxSymbolValue; s++) {
1239 int i;
1240 for (i=0; i<normalizedCounter[s]; i++) {
1241 tableDecode[position].symbol = (FSEv05_FUNCTION_TYPE)s;
1242 position = (position + step) & tableMask;
1243 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
1244 } }
1245
1246 if (position!=0) return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1247
1248 /* Build Decoding table */
1249 {
1250 U32 i;
1251 for (i=0; i<tableSize; i++) {
1252 FSEv05_FUNCTION_TYPE symbol = (FSEv05_FUNCTION_TYPE)(tableDecode[i].symbol);
1253 U16 nextState = symbolNext[symbol]++;
1254 tableDecode[i].nbBits = (BYTE) (tableLog - BITv05_highbit32 ((U32)nextState) );
1255 tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1256 } }
1257
1258 DTableH.fastMode = (U16)noLarge;
1259 memcpy(dt, &DTableH, sizeof(DTableH));
1260 return 0;
1261}
1262
1263
1264#ifndef FSEv05_COMMONDEFS_ONLY
1265/*-****************************************
1266* FSEv05 helper functions
1267******************************************/
1268unsigned FSEv05_isError(size_t code) { return ERR_isError(code); }
1269
1270const char* FSEv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1271
1272
1273/*-**************************************************************
1274* FSEv05 NCount encoding-decoding
1275****************************************************************/
1276static short FSEv05_abs(short a) { return a<0 ? -a : a; }
1277
1278
1279size_t FSEv05_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1280 const void* headerBuffer, size_t hbSize)
1281{
1282 const BYTE* const istart = (const BYTE*) headerBuffer;
1283 const BYTE* const iend = istart + hbSize;
1284 const BYTE* ip = istart;
1285 int nbBits;
1286 int remaining;
1287 int threshold;
1288 U32 bitStream;
1289 int bitCount;
1290 unsigned charnum = 0;
1291 int previous0 = 0;
1292
1293 if (hbSize < 4) return ERROR(srcSize_wrong);
1294 bitStream = MEM_readLE32(ip);
1295 nbBits = (bitStream & 0xF) + FSEv05_MIN_TABLELOG; /* extract tableLog */
1296 if (nbBits > FSEv05_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1297 bitStream >>= 4;
1298 bitCount = 4;
1299 *tableLogPtr = nbBits;
1300 remaining = (1<<nbBits)+1;
1301 threshold = 1<<nbBits;
1302 nbBits++;
1303
1304 while ((remaining>1) && (charnum<=*maxSVPtr)) {
1305 if (previous0) {
1306 unsigned n0 = charnum;
1307 while ((bitStream & 0xFFFF) == 0xFFFF) {
1308 n0+=24;
1309 if (ip < iend-5) {
1310 ip+=2;
1311 bitStream = MEM_readLE32(ip) >> bitCount;
1312 } else {
1313 bitStream >>= 16;
1314 bitCount+=16;
1315 } }
1316 while ((bitStream & 3) == 3) {
1317 n0+=3;
1318 bitStream>>=2;
1319 bitCount+=2;
1320 }
1321 n0 += bitStream & 3;
1322 bitCount += 2;
1323 if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1324 while (charnum < n0) normalizedCounter[charnum++] = 0;
1325 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1326 ip += bitCount>>3;
1327 bitCount &= 7;
1328 bitStream = MEM_readLE32(ip) >> bitCount;
1329 }
1330 else
1331 bitStream >>= 2;
1332 }
1333 {
1334 const short max = (short)((2*threshold-1)-remaining);
1335 short count;
1336
1337 if ((bitStream & (threshold-1)) < (U32)max) {
1338 count = (short)(bitStream & (threshold-1));
1339 bitCount += nbBits-1;
1340 } else {
1341 count = (short)(bitStream & (2*threshold-1));
1342 if (count >= threshold) count -= max;
1343 bitCount += nbBits;
1344 }
1345
1346 count--; /* extra accuracy */
1347 remaining -= FSEv05_abs(count);
1348 normalizedCounter[charnum++] = count;
1349 previous0 = !count;
1350 while (remaining < threshold) {
1351 nbBits--;
1352 threshold >>= 1;
1353 }
1354
1355 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1356 ip += bitCount>>3;
1357 bitCount &= 7;
1358 } else {
1359 bitCount -= (int)(8 * (iend - 4 - ip));
1360 ip = iend - 4;
1361 }
1362 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1363 } }
1364 if (remaining != 1) return ERROR(GENERIC);
1365 *maxSVPtr = charnum-1;
1366
1367 ip += (bitCount+7)>>3;
1368 if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1369 return ip-istart;
1370}
1371
1372
1373
1374/*-*******************************************************
1375* Decompression (Byte symbols)
1376*********************************************************/
1377size_t FSEv05_buildDTable_rle (FSEv05_DTable* dt, BYTE symbolValue)
1378{
1379 void* ptr = dt;
1380 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1381 void* dPtr = dt + 1;
1382 FSEv05_decode_t* const cell = (FSEv05_decode_t*)dPtr;
1383
1384 DTableH->tableLog = 0;
1385 DTableH->fastMode = 0;
1386
1387 cell->newState = 0;
1388 cell->symbol = symbolValue;
1389 cell->nbBits = 0;
1390
1391 return 0;
1392}
1393
1394
1395size_t FSEv05_buildDTable_raw (FSEv05_DTable* dt, unsigned nbBits)
1396{
1397 void* ptr = dt;
1398 FSEv05_DTableHeader* const DTableH = (FSEv05_DTableHeader*)ptr;
1399 void* dPtr = dt + 1;
1400 FSEv05_decode_t* const dinfo = (FSEv05_decode_t*)dPtr;
1401 const unsigned tableSize = 1 << nbBits;
1402 const unsigned tableMask = tableSize - 1;
1403 const unsigned maxSymbolValue = tableMask;
1404 unsigned s;
1405
1406 /* Sanity checks */
1407 if (nbBits < 1) return ERROR(GENERIC); /* min size */
1408
1409 /* Build Decoding Table */
1410 DTableH->tableLog = (U16)nbBits;
1411 DTableH->fastMode = 1;
1412 for (s=0; s<=maxSymbolValue; s++) {
1413 dinfo[s].newState = 0;
1414 dinfo[s].symbol = (BYTE)s;
1415 dinfo[s].nbBits = (BYTE)nbBits;
1416 }
1417
1418 return 0;
1419}
1420
1421FORCE_INLINE size_t FSEv05_decompress_usingDTable_generic(
1422 void* dst, size_t maxDstSize,
1423 const void* cSrc, size_t cSrcSize,
1424 const FSEv05_DTable* dt, const unsigned fast)
1425{
1426 BYTE* const ostart = (BYTE*) dst;
1427 BYTE* op = ostart;
1428 BYTE* const omax = op + maxDstSize;
1429 BYTE* const olimit = omax-3;
1430
1431 BITv05_DStream_t bitD;
1432 FSEv05_DState_t state1;
1433 FSEv05_DState_t state2;
1434 size_t errorCode;
1435
1436 /* Init */
1437 errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize); /* replaced last arg by maxCompressed Size */
1438 if (FSEv05_isError(errorCode)) return errorCode;
1439
1440 FSEv05_initDState(&state1, &bitD, dt);
1441 FSEv05_initDState(&state2, &bitD, dt);
1442
1443#define FSEv05_GETSYMBOL(statePtr) fast ? FSEv05_decodeSymbolFast(statePtr, &bitD) : FSEv05_decodeSymbol(statePtr, &bitD)
1444
1445 /* 4 symbols per loop */
1446 for ( ; (BITv05_reloadDStream(&bitD)==BITv05_DStream_unfinished) && (op<olimit) ; op+=4) {
1447 op[0] = FSEv05_GETSYMBOL(&state1);
1448
1449 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1450 BITv05_reloadDStream(&bitD);
1451
1452 op[1] = FSEv05_GETSYMBOL(&state2);
1453
1454 if (FSEv05_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1455 { if (BITv05_reloadDStream(&bitD) > BITv05_DStream_unfinished) { op+=2; break; } }
1456
1457 op[2] = FSEv05_GETSYMBOL(&state1);
1458
1459 if (FSEv05_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8) /* This test must be static */
1460 BITv05_reloadDStream(&bitD);
1461
1462 op[3] = FSEv05_GETSYMBOL(&state2);
1463 }
1464
1465 /* tail */
1466 /* note : BITv05_reloadDStream(&bitD) >= FSEv05_DStream_partiallyFilled; Ends at exactly BITv05_DStream_completed */
1467 while (1) {
1468 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state1))) )
1469 break;
1470
1471 *op++ = FSEv05_GETSYMBOL(&state1);
1472
1473 if ( (BITv05_reloadDStream(&bitD)>BITv05_DStream_completed) || (op==omax) || (BITv05_endOfDStream(&bitD) && (fast || FSEv05_endOfDState(&state2))) )
1474 break;
1475
1476 *op++ = FSEv05_GETSYMBOL(&state2);
1477 }
1478
1479 /* end ? */
1480 if (BITv05_endOfDStream(&bitD) && FSEv05_endOfDState(&state1) && FSEv05_endOfDState(&state2))
1481 return op-ostart;
1482
1483 if (op==omax) return ERROR(dstSize_tooSmall); /* dst buffer is full, but cSrc unfinished */
1484
1485 return ERROR(corruption_detected);
1486}
1487
1488
1489size_t FSEv05_decompress_usingDTable(void* dst, size_t originalSize,
1490 const void* cSrc, size_t cSrcSize,
1491 const FSEv05_DTable* dt)
1492{
1493 const void* ptr = dt;
1494 const FSEv05_DTableHeader* DTableH = (const FSEv05_DTableHeader*)ptr;
1495 const U32 fastMode = DTableH->fastMode;
1496
1497 /* select fast mode (static) */
1498 if (fastMode) return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1499 return FSEv05_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1500}
1501
1502
1503size_t FSEv05_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1504{
1505 const BYTE* const istart = (const BYTE*)cSrc;
1506 const BYTE* ip = istart;
1507 short counting[FSEv05_MAX_SYMBOL_VALUE+1];
1508 DTable_max_t dt; /* Static analyzer seems unable to understand this table will be properly initialized later */
1509 unsigned tableLog;
1510 unsigned maxSymbolValue = FSEv05_MAX_SYMBOL_VALUE;
1511 size_t errorCode;
1512
1513 if (cSrcSize<2) return ERROR(srcSize_wrong); /* too small input size */
1514
1515 /* normal FSEv05 decoding mode */
1516 errorCode = FSEv05_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1517 if (FSEv05_isError(errorCode)) return errorCode;
1518 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong); /* too small input size */
1519 ip += errorCode;
1520 cSrcSize -= errorCode;
1521
1522 errorCode = FSEv05_buildDTable (dt, counting, maxSymbolValue, tableLog);
1523 if (FSEv05_isError(errorCode)) return errorCode;
1524
1525 /* always return, even if it is an error code */
1526 return FSEv05_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1527}
1528
1529
1530
1531#endif /* FSEv05_COMMONDEFS_ONLY */
1532/* ******************************************************************
1533 Huff0 : Huffman coder, part of New Generation Entropy library
1534 header file
1535 Copyright (C) 2013-2016, Yann Collet.
1536
1537 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1538
1539 Redistribution and use in source and binary forms, with or without
1540 modification, are permitted provided that the following conditions are
1541 met:
1542
1543 * Redistributions of source code must retain the above copyright
1544 notice, this list of conditions and the following disclaimer.
1545 * Redistributions in binary form must reproduce the above
1546 copyright notice, this list of conditions and the following disclaimer
1547 in the documentation and/or other materials provided with the
1548 distribution.
1549
1550 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1551 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1552 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1553 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1554 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1555 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1556 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1557 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1558 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1559 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1560 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1561
1562 You can contact the author at :
1563 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1564****************************************************************** */
1565#ifndef HUFF0_H
1566#define HUFF0_H
1567
1568#if defined (__cplusplus)
1569extern "C" {
1570#endif
1571
1572
1573
1574/* ****************************************
1575* Huff0 simple functions
1576******************************************/
1577size_t HUFv05_decompress(void* dst, size_t dstSize,
1578 const void* cSrc, size_t cSrcSize);
1579/*!
1580HUFv05_decompress():
1581 Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1582 into already allocated destination buffer 'dst', of size 'dstSize'.
1583 @dstSize : must be the **exact** size of original (uncompressed) data.
1584 Note : in contrast with FSEv05, HUFv05_decompress can regenerate
1585 RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1586 because it knows size to regenerate.
1587 @return : size of regenerated data (== dstSize)
1588 or an error code, which can be tested using HUFv05_isError()
1589*/
1590
1591
1592/* ****************************************
1593* Tool functions
1594******************************************/
1595/* Error Management */
1596unsigned HUFv05_isError(size_t code); /* tells if a return value is an error code */
1597const char* HUFv05_getErrorName(size_t code); /* provides error code string (useful for debugging) */
1598
1599
1600#if defined (__cplusplus)
1601}
1602#endif
1603
1604#endif /* HUF0_H */
1605/* ******************************************************************
1606 Huff0 : Huffman codec, part of New Generation Entropy library
1607 header file, for static linking only
1608 Copyright (C) 2013-2016, Yann Collet
1609
1610 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1611
1612 Redistribution and use in source and binary forms, with or without
1613 modification, are permitted provided that the following conditions are
1614 met:
1615
1616 * Redistributions of source code must retain the above copyright
1617 notice, this list of conditions and the following disclaimer.
1618 * Redistributions in binary form must reproduce the above
1619 copyright notice, this list of conditions and the following disclaimer
1620 in the documentation and/or other materials provided with the
1621 distribution.
1622
1623 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1624 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1625 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1626 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1627 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1628 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1629 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1630 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1631 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1632 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1633 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1634
1635 You can contact the author at :
1636 - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1637****************************************************************** */
1638#ifndef HUF0_STATIC_H
1639#define HUF0_STATIC_H
1640
1641#if defined (__cplusplus)
1642extern "C" {
1643#endif
1644
1645
1646
1647/* ****************************************
1648* Static allocation
1649******************************************/
1650/* static allocation of Huff0's DTable */
1651#define HUFv05_DTABLE_SIZE(maxTableLog) (1 + (1<<maxTableLog))
1652#define HUFv05_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1653 unsigned short DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1654#define HUFv05_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1655 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1656#define HUFv05_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1657 unsigned int DTable[HUFv05_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1658
1659
1660/* ****************************************
1661* Advanced decompression functions
1662******************************************/
1663size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1664size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbols decoder */
1665
1666
1667/* ****************************************
1668* Huff0 detailed API
1669******************************************/
1670/*!
1671HUFv05_decompress() does the following:
16721. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
16732. build Huffman table from save, using HUFv05_readDTableXn()
16743. decode 1 or 4 segments in parallel using HUFv05_decompressSXn_usingDTable
1675*/
1676size_t HUFv05_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1677size_t HUFv05_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1678
1679size_t HUFv05_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1680size_t HUFv05_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1681
1682
1683/* single stream variants */
1684
1685size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* single-symbol decoder */
1686size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize); /* double-symbol decoder */
1687
1688size_t HUFv05_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1689size_t HUFv05_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1690
1691
1692
1693#if defined (__cplusplus)
1694}
1695#endif
1696
1697#endif /* HUF0_STATIC_H */
1698/* ******************************************************************
1699 Huff0 : Huffman coder, part of New Generation Entropy library
1700 Copyright (C) 2013-2015, Yann Collet.
1701
1702 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1703
1704 Redistribution and use in source and binary forms, with or without
1705 modification, are permitted provided that the following conditions are
1706 met:
1707
1708 * Redistributions of source code must retain the above copyright
1709 notice, this list of conditions and the following disclaimer.
1710 * Redistributions in binary form must reproduce the above
1711 copyright notice, this list of conditions and the following disclaimer
1712 in the documentation and/or other materials provided with the
1713 distribution.
1714
1715 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1716 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1717 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1718 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1719 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1720 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1721 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1722 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1723 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1724 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1725 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1726
1727 You can contact the author at :
1728 - FSEv05+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1729 - Public forum : https://groups.google.com/forum/#!forum/lz4c
1730****************************************************************** */
1731
1732/* **************************************************************
1733* Compiler specifics
1734****************************************************************/
1735#if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1736/* inline is defined */
1737#elif defined(_MSC_VER)
1738# define inline __inline
1739#else
1740# define inline /* disable inline */
1741#endif
1742
1743
1744#ifdef _MSC_VER /* Visual Studio */
1745# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1746#endif
1747
1748
1749/* **************************************************************
1750* Includes
1751****************************************************************/
1752#include <stdlib.h> /* malloc, free, qsort */
1753#include <string.h> /* memcpy, memset */
1754#include <stdio.h> /* printf (debug) */
1755
1756
1757/* **************************************************************
1758* Constants
1759****************************************************************/
1760#define HUFv05_ABSOLUTEMAX_TABLELOG 16 /* absolute limit of HUFv05_MAX_TABLELOG. Beyond that value, code does not work */
1761#define HUFv05_MAX_TABLELOG 12 /* max configured tableLog (for static allocation); can be modified up to HUFv05_ABSOLUTEMAX_TABLELOG */
1762#define HUFv05_DEFAULT_TABLELOG HUFv05_MAX_TABLELOG /* tableLog by default, when not specified */
1763#define HUFv05_MAX_SYMBOL_VALUE 255
1764#if (HUFv05_MAX_TABLELOG > HUFv05_ABSOLUTEMAX_TABLELOG)
1765# error "HUFv05_MAX_TABLELOG is too large !"
1766#endif
1767
1768
1769/* **************************************************************
1770* Error Management
1771****************************************************************/
1772unsigned HUFv05_isError(size_t code) { return ERR_isError(code); }
1773const char* HUFv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
1774#define HUFv05_STATIC_ASSERT(c) { enum { HUFv05_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
1775
1776
1777/* *******************************************************
1778* Huff0 : Huffman block decompression
1779*********************************************************/
1780typedef struct { BYTE byte; BYTE nbBits; } HUFv05_DEltX2; /* single-symbol decoding */
1781
1782typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv05_DEltX4; /* double-symbols decoding */
1783
1784typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1785
1786/*! HUFv05_readStats
1787 Read compact Huffman tree, saved by HUFv05_writeCTable
1788 @huffWeight : destination buffer
1789 @return : size read from `src`
1790*/
1791static size_t HUFv05_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1792 U32* nbSymbolsPtr, U32* tableLogPtr,
1793 const void* src, size_t srcSize)
1794{
1795 U32 weightTotal;
1796 U32 tableLog;
1797 const BYTE* ip = (const BYTE*) src;
1798 size_t iSize;
1799 size_t oSize;
1800 U32 n;
1801
1802 if (!srcSize) return ERROR(srcSize_wrong);
1803 iSize = ip[0];
1804 //memset(huffWeight, 0, hwSize); /* is not necessary, even though some analyzer complain ... */
1805
1806 if (iSize >= 128) { /* special header */
1807 if (iSize >= (242)) { /* RLE */
1808 static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1809 oSize = l[iSize-242];
1810 memset(huffWeight, 1, hwSize);
1811 iSize = 0;
1812 }
1813 else { /* Incompressible */
1814 oSize = iSize - 127;
1815 iSize = ((oSize+1)/2);
1816 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1817 if (oSize >= hwSize) return ERROR(corruption_detected);
1818 ip += 1;
1819 for (n=0; n<oSize; n+=2) {
1820 huffWeight[n] = ip[n/2] >> 4;
1821 huffWeight[n+1] = ip[n/2] & 15;
1822 } } }
1823 else { /* header compressed with FSEv05 (normal case) */
1824 if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1825 oSize = FSEv05_decompress(huffWeight, hwSize-1, ip+1, iSize); /* max (hwSize-1) values decoded, as last one is implied */
1826 if (FSEv05_isError(oSize)) return oSize;
1827 }
1828
1829 /* collect weight stats */
1830 memset(rankStats, 0, (HUFv05_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1831 weightTotal = 0;
1832 for (n=0; n<oSize; n++) {
1833 if (huffWeight[n] >= HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1834 rankStats[huffWeight[n]]++;
1835 weightTotal += (1 << huffWeight[n]) >> 1;
1836 }
1837 if (weightTotal == 0) return ERROR(corruption_detected);
1838
1839 /* get last non-null symbol weight (implied, total must be 2^n) */
1840 tableLog = BITv05_highbit32(weightTotal) + 1;
1841 if (tableLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1842 { /* determine last weight */
1843 U32 total = 1 << tableLog;
1844 U32 rest = total - weightTotal;
1845 U32 verif = 1 << BITv05_highbit32(rest);
1846 U32 lastWeight = BITv05_highbit32(rest) + 1;
1847 if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
1848 huffWeight[oSize] = (BYTE)lastWeight;
1849 rankStats[lastWeight]++;
1850 }
1851
1852 /* check tree construction validity */
1853 if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
1854
1855 /* results */
1856 *nbSymbolsPtr = (U32)(oSize+1);
1857 *tableLogPtr = tableLog;
1858 return iSize+1;
1859}
1860
1861
1862/*-***************************/
1863/* single-symbol decoding */
1864/*-***************************/
1865
1866size_t HUFv05_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1867{
1868 BYTE huffWeight[HUFv05_MAX_SYMBOL_VALUE + 1];
1869 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1]; /* large enough for values from 0 to 16 */
1870 U32 tableLog = 0;
1871 size_t iSize;
1872 U32 nbSymbols = 0;
1873 U32 n;
1874 U32 nextRankStart;
1875 void* const dtPtr = DTable + 1;
1876 HUFv05_DEltX2* const dt = (HUFv05_DEltX2*)dtPtr;
1877
1878 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX2) == sizeof(U16)); /* if compilation fails here, assertion is false */
1879 //memset(huffWeight, 0, sizeof(huffWeight)); /* is not necessary, even though some analyzer complain ... */
1880
1881 iSize = HUFv05_readStats(huffWeight, HUFv05_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1882 if (HUFv05_isError(iSize)) return iSize;
1883
1884 /* check result */
1885 if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge); /* DTable is too small */
1886 DTable[0] = (U16)tableLog; /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
1887
1888 /* Prepare ranks */
1889 nextRankStart = 0;
1890 for (n=1; n<=tableLog; n++) {
1891 U32 current = nextRankStart;
1892 nextRankStart += (rankVal[n] << (n-1));
1893 rankVal[n] = current;
1894 }
1895
1896 /* fill DTable */
1897 for (n=0; n<nbSymbols; n++) {
1898 const U32 w = huffWeight[n];
1899 const U32 length = (1 << w) >> 1;
1900 U32 i;
1901 HUFv05_DEltX2 D;
1902 D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1903 for (i = rankVal[w]; i < rankVal[w] + length; i++)
1904 dt[i] = D;
1905 rankVal[w] += length;
1906 }
1907
1908 return iSize;
1909}
1910
1911static BYTE HUFv05_decodeSymbolX2(BITv05_DStream_t* Dstream, const HUFv05_DEltX2* dt, const U32 dtLog)
1912{
1913 const size_t val = BITv05_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1914 const BYTE c = dt[val].byte;
1915 BITv05_skipBits(Dstream, dt[val].nbBits);
1916 return c;
1917}
1918
1919#define HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1920 *ptr++ = HUFv05_decodeSymbolX2(DStreamPtr, dt, dtLog)
1921
1922#define HUFv05_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1923 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
1924 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1925
1926#define HUFv05_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1927 if (MEM_64bits()) \
1928 HUFv05_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1929
1930static inline size_t HUFv05_decodeStreamX2(BYTE* p, BITv05_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv05_DEltX2* const dt, const U32 dtLog)
1931{
1932 BYTE* const pStart = p;
1933
1934 /* up to 4 symbols at a time */
1935 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-4)) {
1936 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1937 HUFv05_DECODE_SYMBOLX2_1(p, bitDPtr);
1938 HUFv05_DECODE_SYMBOLX2_2(p, bitDPtr);
1939 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1940 }
1941
1942 /* closer to the end */
1943 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd))
1944 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1945
1946 /* no more data to retrieve from bitstream, hence no need to reload */
1947 while (p < pEnd)
1948 HUFv05_DECODE_SYMBOLX2_0(p, bitDPtr);
1949
1950 return pEnd-pStart;
1951}
1952
1953size_t HUFv05_decompress1X2_usingDTable(
1954 void* dst, size_t dstSize,
1955 const void* cSrc, size_t cSrcSize,
1956 const U16* DTable)
1957{
1958 BYTE* op = (BYTE*)dst;
1959 BYTE* const oend = op + dstSize;
1960 const U32 dtLog = DTable[0];
1961 const void* dtPtr = DTable;
1962 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr)+1;
1963 BITv05_DStream_t bitD;
1964
1965 if (dstSize <= cSrcSize) return ERROR(dstSize_tooSmall);
1966 { size_t const errorCode = BITv05_initDStream(&bitD, cSrc, cSrcSize);
1967 if (HUFv05_isError(errorCode)) return errorCode; }
1968
1969 HUFv05_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1970
1971 /* check */
1972 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
1973
1974 return dstSize;
1975}
1976
1977size_t HUFv05_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1978{
1979 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
1980 const BYTE* ip = (const BYTE*) cSrc;
1981 size_t errorCode;
1982
1983 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
1984 if (HUFv05_isError(errorCode)) return errorCode;
1985 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1986 ip += errorCode;
1987 cSrcSize -= errorCode;
1988
1989 return HUFv05_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1990}
1991
1992
1993size_t HUFv05_decompress4X2_usingDTable(
1994 void* dst, size_t dstSize,
1995 const void* cSrc, size_t cSrcSize,
1996 const U16* DTable)
1997{
1998 const BYTE* const istart = (const BYTE*) cSrc;
1999 BYTE* const ostart = (BYTE*) dst;
2000 BYTE* const oend = ostart + dstSize;
2001 const void* const dtPtr = DTable;
2002 const HUFv05_DEltX2* const dt = ((const HUFv05_DEltX2*)dtPtr) +1;
2003 const U32 dtLog = DTable[0];
2004 size_t errorCode;
2005
2006 /* Init */
2007 BITv05_DStream_t bitD1;
2008 BITv05_DStream_t bitD2;
2009 BITv05_DStream_t bitD3;
2010 BITv05_DStream_t bitD4;
2011 const size_t length1 = MEM_readLE16(istart);
2012 const size_t length2 = MEM_readLE16(istart+2);
2013 const size_t length3 = MEM_readLE16(istart+4);
2014 size_t length4;
2015 const BYTE* const istart1 = istart + 6; /* jumpTable */
2016 const BYTE* const istart2 = istart1 + length1;
2017 const BYTE* const istart3 = istart2 + length2;
2018 const BYTE* const istart4 = istart3 + length3;
2019 const size_t segmentSize = (dstSize+3) / 4;
2020 BYTE* const opStart2 = ostart + segmentSize;
2021 BYTE* const opStart3 = opStart2 + segmentSize;
2022 BYTE* const opStart4 = opStart3 + segmentSize;
2023 BYTE* op1 = ostart;
2024 BYTE* op2 = opStart2;
2025 BYTE* op3 = opStart3;
2026 BYTE* op4 = opStart4;
2027 U32 endSignal;
2028
2029 /* Check */
2030 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2031
2032 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2033 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2034 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
2035 if (HUFv05_isError(errorCode)) return errorCode;
2036 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
2037 if (HUFv05_isError(errorCode)) return errorCode;
2038 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
2039 if (HUFv05_isError(errorCode)) return errorCode;
2040 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
2041 if (HUFv05_isError(errorCode)) return errorCode;
2042
2043 /* 16-32 symbols per loop (4-8 symbols per stream) */
2044 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2045 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
2046 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
2047 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
2048 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2049 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2050 HUFv05_DECODE_SYMBOLX2_1(op1, &bitD1);
2051 HUFv05_DECODE_SYMBOLX2_1(op2, &bitD2);
2052 HUFv05_DECODE_SYMBOLX2_1(op3, &bitD3);
2053 HUFv05_DECODE_SYMBOLX2_1(op4, &bitD4);
2054 HUFv05_DECODE_SYMBOLX2_2(op1, &bitD1);
2055 HUFv05_DECODE_SYMBOLX2_2(op2, &bitD2);
2056 HUFv05_DECODE_SYMBOLX2_2(op3, &bitD3);
2057 HUFv05_DECODE_SYMBOLX2_2(op4, &bitD4);
2058 HUFv05_DECODE_SYMBOLX2_0(op1, &bitD1);
2059 HUFv05_DECODE_SYMBOLX2_0(op2, &bitD2);
2060 HUFv05_DECODE_SYMBOLX2_0(op3, &bitD3);
2061 HUFv05_DECODE_SYMBOLX2_0(op4, &bitD4);
2062 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2063 }
2064
2065 /* check corruption */
2066 if (op1 > opStart2) return ERROR(corruption_detected);
2067 if (op2 > opStart3) return ERROR(corruption_detected);
2068 if (op3 > opStart4) return ERROR(corruption_detected);
2069 /* note : op4 supposed already verified within main loop */
2070
2071 /* finish bitStreams one by one */
2072 HUFv05_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2073 HUFv05_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2074 HUFv05_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2075 HUFv05_decodeStreamX2(op4, &bitD4, oend, dt, dtLog);
2076
2077 /* check */
2078 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2079 if (!endSignal) return ERROR(corruption_detected);
2080
2081 /* decoded size */
2082 return dstSize;
2083}
2084
2085
2086size_t HUFv05_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2087{
2088 HUFv05_CREATE_STATIC_DTABLEX2(DTable, HUFv05_MAX_TABLELOG);
2089 const BYTE* ip = (const BYTE*) cSrc;
2090 size_t errorCode;
2091
2092 errorCode = HUFv05_readDTableX2 (DTable, cSrc, cSrcSize);
2093 if (HUFv05_isError(errorCode)) return errorCode;
2094 if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2095 ip += errorCode;
2096 cSrcSize -= errorCode;
2097
2098 return HUFv05_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2099}
2100
2101
2102/* *************************/
2103/* double-symbols decoding */
2104/* *************************/
2105
2106static void HUFv05_fillDTableX4Level2(HUFv05_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2107 const U32* rankValOrigin, const int minWeight,
2108 const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2109 U32 nbBitsBaseline, U16 baseSeq)
2110{
2111 HUFv05_DEltX4 DElt;
2112 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2113 U32 s;
2114
2115 /* get pre-calculated rankVal */
2116 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2117
2118 /* fill skipped values */
2119 if (minWeight>1) {
2120 U32 i, skipSize = rankVal[minWeight];
2121 MEM_writeLE16(&(DElt.sequence), baseSeq);
2122 DElt.nbBits = (BYTE)(consumed);
2123 DElt.length = 1;
2124 for (i = 0; i < skipSize; i++)
2125 DTable[i] = DElt;
2126 }
2127
2128 /* fill DTable */
2129 for (s=0; s<sortedListSize; s++) { /* note : sortedSymbols already skipped */
2130 const U32 symbol = sortedSymbols[s].symbol;
2131 const U32 weight = sortedSymbols[s].weight;
2132 const U32 nbBits = nbBitsBaseline - weight;
2133 const U32 length = 1 << (sizeLog-nbBits);
2134 const U32 start = rankVal[weight];
2135 U32 i = start;
2136 const U32 end = start + length;
2137
2138 MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2139 DElt.nbBits = (BYTE)(nbBits + consumed);
2140 DElt.length = 2;
2141 do { DTable[i++] = DElt; } while (i<end); /* since length >= 1 */
2142
2143 rankVal[weight] += length;
2144 }
2145}
2146
2147typedef U32 rankVal_t[HUFv05_ABSOLUTEMAX_TABLELOG][HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2148
2149static void HUFv05_fillDTableX4(HUFv05_DEltX4* DTable, const U32 targetLog,
2150 const sortedSymbol_t* sortedList, const U32 sortedListSize,
2151 const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2152 const U32 nbBitsBaseline)
2153{
2154 U32 rankVal[HUFv05_ABSOLUTEMAX_TABLELOG + 1];
2155 const int scaleLog = nbBitsBaseline - targetLog; /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2156 const U32 minBits = nbBitsBaseline - maxWeight;
2157 U32 s;
2158
2159 memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2160
2161 /* fill DTable */
2162 for (s=0; s<sortedListSize; s++) {
2163 const U16 symbol = sortedList[s].symbol;
2164 const U32 weight = sortedList[s].weight;
2165 const U32 nbBits = nbBitsBaseline - weight;
2166 const U32 start = rankVal[weight];
2167 const U32 length = 1 << (targetLog-nbBits);
2168
2169 if (targetLog-nbBits >= minBits) { /* enough room for a second symbol */
2170 U32 sortedRank;
2171 int minWeight = nbBits + scaleLog;
2172 if (minWeight < 1) minWeight = 1;
2173 sortedRank = rankStart[minWeight];
2174 HUFv05_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2175 rankValOrigin[nbBits], minWeight,
2176 sortedList+sortedRank, sortedListSize-sortedRank,
2177 nbBitsBaseline, symbol);
2178 } else {
2179 U32 i;
2180 const U32 end = start + length;
2181 HUFv05_DEltX4 DElt;
2182
2183 MEM_writeLE16(&(DElt.sequence), symbol);
2184 DElt.nbBits = (BYTE)(nbBits);
2185 DElt.length = 1;
2186 for (i = start; i < end; i++)
2187 DTable[i] = DElt;
2188 }
2189 rankVal[weight] += length;
2190 }
2191}
2192
2193size_t HUFv05_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2194{
2195 BYTE weightList[HUFv05_MAX_SYMBOL_VALUE + 1];
2196 sortedSymbol_t sortedSymbol[HUFv05_MAX_SYMBOL_VALUE + 1];
2197 U32 rankStats[HUFv05_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2198 U32 rankStart0[HUFv05_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2199 U32* const rankStart = rankStart0+1;
2200 rankVal_t rankVal;
2201 U32 tableLog, maxW, sizeOfSort, nbSymbols;
2202 const U32 memLog = DTable[0];
2203 size_t iSize;
2204 void* dtPtr = DTable;
2205 HUFv05_DEltX4* const dt = ((HUFv05_DEltX4*)dtPtr) + 1;
2206
2207 HUFv05_STATIC_ASSERT(sizeof(HUFv05_DEltX4) == sizeof(U32)); /* if compilation fails here, assertion is false */
2208 if (memLog > HUFv05_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2209 //memset(weightList, 0, sizeof(weightList)); /* is not necessary, even though some analyzer complain ... */
2210
2211 iSize = HUFv05_readStats(weightList, HUFv05_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2212 if (HUFv05_isError(iSize)) return iSize;
2213
2214 /* check result */
2215 if (tableLog > memLog) return ERROR(tableLog_tooLarge); /* DTable can't fit code depth */
2216
2217 /* find maxWeight */
2218 for (maxW = tableLog; rankStats[maxW]==0; maxW--) {} /* necessarily finds a solution before 0 */
2219
2220 /* Get start index of each weight */
2221 {
2222 U32 w, nextRankStart = 0;
2223 for (w=1; w<=maxW; w++) {
2224 U32 current = nextRankStart;
2225 nextRankStart += rankStats[w];
2226 rankStart[w] = current;
2227 }
2228 rankStart[0] = nextRankStart; /* put all 0w symbols at the end of sorted list*/
2229 sizeOfSort = nextRankStart;
2230 }
2231
2232 /* sort symbols by weight */
2233 {
2234 U32 s;
2235 for (s=0; s<nbSymbols; s++) {
2236 U32 w = weightList[s];
2237 U32 r = rankStart[w]++;
2238 sortedSymbol[r].symbol = (BYTE)s;
2239 sortedSymbol[r].weight = (BYTE)w;
2240 }
2241 rankStart[0] = 0; /* forget 0w symbols; this is beginning of weight(1) */
2242 }
2243
2244 /* Build rankVal */
2245 {
2246 const U32 minBits = tableLog+1 - maxW;
2247 U32 nextRankVal = 0;
2248 U32 w, consumed;
2249 const int rescale = (memLog-tableLog) - 1; /* tableLog <= memLog */
2250 U32* rankVal0 = rankVal[0];
2251 for (w=1; w<=maxW; w++) {
2252 U32 current = nextRankVal;
2253 nextRankVal += rankStats[w] << (w+rescale);
2254 rankVal0[w] = current;
2255 }
2256 for (consumed = minBits; consumed <= memLog - minBits; consumed++) {
2257 U32* rankValPtr = rankVal[consumed];
2258 for (w = 1; w <= maxW; w++) {
2259 rankValPtr[w] = rankVal0[w] >> consumed;
2260 } } }
2261
2262 HUFv05_fillDTableX4(dt, memLog,
2263 sortedSymbol, sizeOfSort,
2264 rankStart0, rankVal, maxW,
2265 tableLog+1);
2266
2267 return iSize;
2268}
2269
2270
2271static U32 HUFv05_decodeSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2272{
2273 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2274 memcpy(op, dt+val, 2);
2275 BITv05_skipBits(DStream, dt[val].nbBits);
2276 return dt[val].length;
2277}
2278
2279static U32 HUFv05_decodeLastSymbolX4(void* op, BITv05_DStream_t* DStream, const HUFv05_DEltX4* dt, const U32 dtLog)
2280{
2281 const size_t val = BITv05_lookBitsFast(DStream, dtLog); /* note : dtLog >= 1 */
2282 memcpy(op, dt+val, 1);
2283 if (dt[val].length==1) BITv05_skipBits(DStream, dt[val].nbBits);
2284 else {
2285 if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2286 BITv05_skipBits(DStream, dt[val].nbBits);
2287 if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2288 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 */
2289 } }
2290 return 1;
2291}
2292
2293
2294#define HUFv05_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2295 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2296
2297#define HUFv05_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2298 if (MEM_64bits() || (HUFv05_MAX_TABLELOG<=12)) \
2299 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2300
2301#define HUFv05_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2302 if (MEM_64bits()) \
2303 ptr += HUFv05_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2304
2305static inline size_t HUFv05_decodeStreamX4(BYTE* p, BITv05_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv05_DEltX4* const dt, const U32 dtLog)
2306{
2307 BYTE* const pStart = p;
2308
2309 /* up to 8 symbols at a time */
2310 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p < pEnd-7)) {
2311 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2312 HUFv05_DECODE_SYMBOLX4_1(p, bitDPtr);
2313 HUFv05_DECODE_SYMBOLX4_2(p, bitDPtr);
2314 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2315 }
2316
2317 /* closer to the end */
2318 while ((BITv05_reloadDStream(bitDPtr) == BITv05_DStream_unfinished) && (p <= pEnd-2))
2319 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr);
2320
2321 while (p <= pEnd-2)
2322 HUFv05_DECODE_SYMBOLX4_0(p, bitDPtr); /* no need to reload : reached the end of DStream */
2323
2324 if (p < pEnd)
2325 p += HUFv05_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2326
2327 return p-pStart;
2328}
2329
2330
2331size_t HUFv05_decompress1X4_usingDTable(
2332 void* dst, size_t dstSize,
2333 const void* cSrc, size_t cSrcSize,
2334 const U32* DTable)
2335{
2336 const BYTE* const istart = (const BYTE*) cSrc;
2337 BYTE* const ostart = (BYTE*) dst;
2338 BYTE* const oend = ostart + dstSize;
2339
2340 const U32 dtLog = DTable[0];
2341 const void* const dtPtr = DTable;
2342 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2343 size_t errorCode;
2344
2345 /* Init */
2346 BITv05_DStream_t bitD;
2347 errorCode = BITv05_initDStream(&bitD, istart, cSrcSize);
2348 if (HUFv05_isError(errorCode)) return errorCode;
2349
2350 /* finish bitStreams one by one */
2351 HUFv05_decodeStreamX4(ostart, &bitD, oend, dt, dtLog);
2352
2353 /* check */
2354 if (!BITv05_endOfDStream(&bitD)) return ERROR(corruption_detected);
2355
2356 /* decoded size */
2357 return dstSize;
2358}
2359
2360size_t HUFv05_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2361{
2362 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2363 const BYTE* ip = (const BYTE*) cSrc;
2364
2365 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2366 if (HUFv05_isError(hSize)) return hSize;
2367 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2368 ip += hSize;
2369 cSrcSize -= hSize;
2370
2371 return HUFv05_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2372}
2373
2374size_t HUFv05_decompress4X4_usingDTable(
2375 void* dst, size_t dstSize,
2376 const void* cSrc, size_t cSrcSize,
2377 const U32* DTable)
2378{
2379 if (cSrcSize < 10) return ERROR(corruption_detected); /* strict minimum : jump table + 1 byte per stream */
2380
2381 {
2382 const BYTE* const istart = (const BYTE*) cSrc;
2383 BYTE* const ostart = (BYTE*) dst;
2384 BYTE* const oend = ostart + dstSize;
2385 const void* const dtPtr = DTable;
2386 const HUFv05_DEltX4* const dt = ((const HUFv05_DEltX4*)dtPtr) +1;
2387 const U32 dtLog = DTable[0];
2388 size_t errorCode;
2389
2390 /* Init */
2391 BITv05_DStream_t bitD1;
2392 BITv05_DStream_t bitD2;
2393 BITv05_DStream_t bitD3;
2394 BITv05_DStream_t bitD4;
2395 const size_t length1 = MEM_readLE16(istart);
2396 const size_t length2 = MEM_readLE16(istart+2);
2397 const size_t length3 = MEM_readLE16(istart+4);
2398 size_t length4;
2399 const BYTE* const istart1 = istart + 6; /* jumpTable */
2400 const BYTE* const istart2 = istart1 + length1;
2401 const BYTE* const istart3 = istart2 + length2;
2402 const BYTE* const istart4 = istart3 + length3;
2403 const size_t segmentSize = (dstSize+3) / 4;
2404 BYTE* const opStart2 = ostart + segmentSize;
2405 BYTE* const opStart3 = opStart2 + segmentSize;
2406 BYTE* const opStart4 = opStart3 + segmentSize;
2407 BYTE* op1 = ostart;
2408 BYTE* op2 = opStart2;
2409 BYTE* op3 = opStart3;
2410 BYTE* op4 = opStart4;
2411 U32 endSignal;
2412
2413 length4 = cSrcSize - (length1 + length2 + length3 + 6);
2414 if (length4 > cSrcSize) return ERROR(corruption_detected); /* overflow */
2415 errorCode = BITv05_initDStream(&bitD1, istart1, length1);
2416 if (HUFv05_isError(errorCode)) return errorCode;
2417 errorCode = BITv05_initDStream(&bitD2, istart2, length2);
2418 if (HUFv05_isError(errorCode)) return errorCode;
2419 errorCode = BITv05_initDStream(&bitD3, istart3, length3);
2420 if (HUFv05_isError(errorCode)) return errorCode;
2421 errorCode = BITv05_initDStream(&bitD4, istart4, length4);
2422 if (HUFv05_isError(errorCode)) return errorCode;
2423
2424 /* 16-32 symbols per loop (4-8 symbols per stream) */
2425 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2426 for ( ; (endSignal==BITv05_DStream_unfinished) && (op4<(oend-7)) ; ) {
2427 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2428 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2429 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2430 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2431 HUFv05_DECODE_SYMBOLX4_1(op1, &bitD1);
2432 HUFv05_DECODE_SYMBOLX4_1(op2, &bitD2);
2433 HUFv05_DECODE_SYMBOLX4_1(op3, &bitD3);
2434 HUFv05_DECODE_SYMBOLX4_1(op4, &bitD4);
2435 HUFv05_DECODE_SYMBOLX4_2(op1, &bitD1);
2436 HUFv05_DECODE_SYMBOLX4_2(op2, &bitD2);
2437 HUFv05_DECODE_SYMBOLX4_2(op3, &bitD3);
2438 HUFv05_DECODE_SYMBOLX4_2(op4, &bitD4);
2439 HUFv05_DECODE_SYMBOLX4_0(op1, &bitD1);
2440 HUFv05_DECODE_SYMBOLX4_0(op2, &bitD2);
2441 HUFv05_DECODE_SYMBOLX4_0(op3, &bitD3);
2442 HUFv05_DECODE_SYMBOLX4_0(op4, &bitD4);
2443
2444 endSignal = BITv05_reloadDStream(&bitD1) | BITv05_reloadDStream(&bitD2) | BITv05_reloadDStream(&bitD3) | BITv05_reloadDStream(&bitD4);
2445 }
2446
2447 /* check corruption */
2448 if (op1 > opStart2) return ERROR(corruption_detected);
2449 if (op2 > opStart3) return ERROR(corruption_detected);
2450 if (op3 > opStart4) return ERROR(corruption_detected);
2451 /* note : op4 supposed already verified within main loop */
2452
2453 /* finish bitStreams one by one */
2454 HUFv05_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2455 HUFv05_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2456 HUFv05_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2457 HUFv05_decodeStreamX4(op4, &bitD4, oend, dt, dtLog);
2458
2459 /* check */
2460 endSignal = BITv05_endOfDStream(&bitD1) & BITv05_endOfDStream(&bitD2) & BITv05_endOfDStream(&bitD3) & BITv05_endOfDStream(&bitD4);
2461 if (!endSignal) return ERROR(corruption_detected);
2462
2463 /* decoded size */
2464 return dstSize;
2465 }
2466}
2467
2468
2469size_t HUFv05_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2470{
2471 HUFv05_CREATE_STATIC_DTABLEX4(DTable, HUFv05_MAX_TABLELOG);
2472 const BYTE* ip = (const BYTE*) cSrc;
2473
2474 size_t hSize = HUFv05_readDTableX4 (DTable, cSrc, cSrcSize);
2475 if (HUFv05_isError(hSize)) return hSize;
2476 if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2477 ip += hSize;
2478 cSrcSize -= hSize;
2479
2480 return HUFv05_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2481}
2482
2483
2484/* ********************************/
2485/* Generic decompression selector */
2486/* ********************************/
2487
2488typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2489static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2490{
2491 /* single, double, quad */
2492 {{0,0}, {1,1}, {2,2}}, /* Q==0 : impossible */
2493 {{0,0}, {1,1}, {2,2}}, /* Q==1 : impossible */
2494 {{ 38,130}, {1313, 74}, {2151, 38}}, /* Q == 2 : 12-18% */
2495 {{ 448,128}, {1353, 74}, {2238, 41}}, /* Q == 3 : 18-25% */
2496 {{ 556,128}, {1353, 74}, {2238, 47}}, /* Q == 4 : 25-32% */
2497 {{ 714,128}, {1418, 74}, {2436, 53}}, /* Q == 5 : 32-38% */
2498 {{ 883,128}, {1437, 74}, {2464, 61}}, /* Q == 6 : 38-44% */
2499 {{ 897,128}, {1515, 75}, {2622, 68}}, /* Q == 7 : 44-50% */
2500 {{ 926,128}, {1613, 75}, {2730, 75}}, /* Q == 8 : 50-56% */
2501 {{ 947,128}, {1729, 77}, {3359, 77}}, /* Q == 9 : 56-62% */
2502 {{1107,128}, {2083, 81}, {4006, 84}}, /* Q ==10 : 62-69% */
2503 {{1177,128}, {2379, 87}, {4785, 88}}, /* Q ==11 : 69-75% */
2504 {{1242,128}, {2415, 93}, {5155, 84}}, /* Q ==12 : 75-81% */
2505 {{1349,128}, {2644,106}, {5260,106}}, /* Q ==13 : 81-87% */
2506 {{1455,128}, {2422,124}, {4174,124}}, /* Q ==14 : 87-93% */
2507 {{ 722,128}, {1891,145}, {1936,146}}, /* Q ==15 : 93-99% */
2508};
2509
2510typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2511
2512size_t HUFv05_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2513{
2514 static const decompressionAlgo decompress[3] = { HUFv05_decompress4X2, HUFv05_decompress4X4, NULL };
2515 /* estimate decompression time */
2516 U32 Q;
2517 const U32 D256 = (U32)(dstSize >> 8);
2518 U32 Dtime[3];
2519 U32 algoNb = 0;
2520 int n;
2521
2522 /* validation checks */
2523 if (dstSize == 0) return ERROR(dstSize_tooSmall);
2524 if (cSrcSize >= dstSize) return ERROR(corruption_detected); /* invalid, or not compressed, but not compressed already dealt with */
2525 if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; } /* RLE */
2526
2527 /* decoder timing evaluation */
2528 Q = (U32)(cSrcSize * 16 / dstSize); /* Q < 16 since dstSize > cSrcSize */
2529 for (n=0; n<3; n++)
2530 Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2531
2532 Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2533
2534 if (Dtime[1] < Dtime[0]) algoNb = 1;
2535
2536 return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2537
2538 //return HUFv05_decompress4X2(dst, dstSize, cSrc, cSrcSize); /* multi-streams single-symbol decoding */
2539 //return HUFv05_decompress4X4(dst, dstSize, cSrc, cSrcSize); /* multi-streams double-symbols decoding */
2540 //return HUFv05_decompress4X6(dst, dstSize, cSrc, cSrcSize); /* multi-streams quad-symbols decoding */
2541}
2542/*
2543 zstd - standard compression library
2544 Copyright (C) 2014-2016, Yann Collet.
2545
2546 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
2547
2548 Redistribution and use in source and binary forms, with or without
2549 modification, are permitted provided that the following conditions are
2550 met:
2551 * Redistributions of source code must retain the above copyright
2552 notice, this list of conditions and the following disclaimer.
2553 * Redistributions in binary form must reproduce the above
2554 copyright notice, this list of conditions and the following disclaimer
2555 in the documentation and/or other materials provided with the
2556 distribution.
2557 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2558 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2559 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2560 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2561 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2562 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2563 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2564 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2565 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2566 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2567 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2568
2569 You can contact the author at :
2570 - zstd source repository : https://github.com/Cyan4973/zstd
2571*/
2572
2573/* ***************************************************************
2574* Tuning parameters
2575*****************************************************************/
2576/*!
2577 * HEAPMODE :
2578 * Select how default decompression function ZSTDv05_decompress() will allocate memory,
2579 * in memory stack (0), or in memory heap (1, requires malloc())
2580 */
2581#ifndef ZSTDv05_HEAPMODE
2582# define ZSTDv05_HEAPMODE 1
2583#endif
2584
2585
2586/*-*******************************************************
2587* Dependencies
2588*********************************************************/
2589#include <stdlib.h> /* calloc */
2590#include <string.h> /* memcpy, memmove */
2591#include <stdio.h> /* debug only : printf */
2592
2593
2594/*-*******************************************************
2595* Compiler specifics
2596*********************************************************/
2597#ifdef _MSC_VER /* Visual Studio */
2598# include <intrin.h> /* For Visual 2005 */
2599# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
2600# pragma warning(disable : 4324) /* disable: C4324: padded structure */
2601#endif
2602
2603
2604/*-*************************************
2605* Local types
2606***************************************/
2607typedef struct
2608{
2609 blockType_t blockType;
2610 U32 origSize;
2611} blockProperties_t;
2612
2613
2614/* *******************************************************
2615* Memory operations
2616**********************************************************/
2617static void ZSTDv05_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2618
2619
2620/* *************************************
2621* Error Management
2622***************************************/
2623/*! ZSTDv05_isError() :
2624* tells if a return value is an error code */
2625unsigned ZSTDv05_isError(size_t code) { return ERR_isError(code); }
2626
2627
2628/*! ZSTDv05_getErrorName() :
2629* provides error code string (useful for debugging) */
2630const char* ZSTDv05_getErrorName(size_t code) { return ERR_getErrorName(code); }
2631
2632
2633/* *************************************************************
2634* Context management
2635***************************************************************/
2636typedef enum { ZSTDv05ds_getFrameHeaderSize, ZSTDv05ds_decodeFrameHeader,
2637 ZSTDv05ds_decodeBlockHeader, ZSTDv05ds_decompressBlock } ZSTDv05_dStage;
2638
2639struct ZSTDv05_DCtx_s
2640{
2641 FSEv05_DTable LLTable[FSEv05_DTABLE_SIZE_U32(LLFSEv05Log)];
2642 FSEv05_DTable OffTable[FSEv05_DTABLE_SIZE_U32(OffFSEv05Log)];
2643 FSEv05_DTable MLTable[FSEv05_DTABLE_SIZE_U32(MLFSEv05Log)];
2644 unsigned hufTableX4[HUFv05_DTABLE_SIZE(HufLog)];
2645 const void* previousDstEnd;
2646 const void* base;
2647 const void* vBase;
2648 const void* dictEnd;
2649 size_t expected;
2650 size_t headerSize;
2651 ZSTDv05_parameters params;
2652 blockType_t bType; /* used in ZSTDv05_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2653 ZSTDv05_dStage stage;
2654 U32 flagStaticTables;
2655 const BYTE* litPtr;
2656 size_t litSize;
2657 BYTE litBuffer[BLOCKSIZE + WILDCOPY_OVERLENGTH];
2658 BYTE headerBuffer[ZSTDv05_frameHeaderSize_max];
2659}; /* typedef'd to ZSTDv05_DCtx within "zstd_static.h" */
2660
2661size_t ZSTDv05_sizeofDCtx (void) { return sizeof(ZSTDv05_DCtx); }
2662
2663size_t ZSTDv05_decompressBegin(ZSTDv05_DCtx* dctx)
2664{
2665 dctx->expected = ZSTDv05_frameHeaderSize_min;
2666 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
2667 dctx->previousDstEnd = NULL;
2668 dctx->base = NULL;
2669 dctx->vBase = NULL;
2670 dctx->dictEnd = NULL;
2671 dctx->hufTableX4[0] = HufLog;
2672 dctx->flagStaticTables = 0;
2673 return 0;
2674}
2675
2676ZSTDv05_DCtx* ZSTDv05_createDCtx(void)
2677{
2678 ZSTDv05_DCtx* dctx = (ZSTDv05_DCtx*)malloc(sizeof(ZSTDv05_DCtx));
2679 if (dctx==NULL) return NULL;
2680 ZSTDv05_decompressBegin(dctx);
2681 return dctx;
2682}
2683
2684size_t ZSTDv05_freeDCtx(ZSTDv05_DCtx* dctx)
2685{
2686 free(dctx);
2687 return 0; /* reserved as a potential error code in the future */
2688}
2689
2690void ZSTDv05_copyDCtx(ZSTDv05_DCtx* dstDCtx, const ZSTDv05_DCtx* srcDCtx)
2691{
2692 memcpy(dstDCtx, srcDCtx,
2693 sizeof(ZSTDv05_DCtx) - (BLOCKSIZE+WILDCOPY_OVERLENGTH + ZSTDv05_frameHeaderSize_max)); /* no need to copy workspace */
2694}
2695
2696
2697/* *************************************************************
2698* Decompression section
2699***************************************************************/
2700
2701/* Frame format description
2702 Frame Header - [ Block Header - Block ] - Frame End
2703 1) Frame Header
2704 - 4 bytes - Magic Number : ZSTDv05_MAGICNUMBER (defined within zstd_internal.h)
2705 - 1 byte - Window Descriptor
2706 2) Block Header
2707 - 3 bytes, starting with a 2-bits descriptor
2708 Uncompressed, Compressed, Frame End, unused
2709 3) Block
2710 See Block Format Description
2711 4) Frame End
2712 - 3 bytes, compatible with Block Header
2713*/
2714
2715/* Block format description
2716
2717 Block = Literal Section - Sequences Section
2718 Prerequisite : size of (compressed) block, maximum size of regenerated data
2719
2720 1) Literal Section
2721
2722 1.1) Header : 1-5 bytes
2723 flags: 2 bits
2724 00 compressed by Huff0
2725 01 unused
2726 10 is Raw (uncompressed)
2727 11 is Rle
2728 Note : using 01 => Huff0 with precomputed table ?
2729 Note : delta map ? => compressed ?
2730
2731 1.1.1) Huff0-compressed literal block : 3-5 bytes
2732 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2733 srcSize < 1 KB => 3 bytes (2-2-10-10)
2734 srcSize < 16KB => 4 bytes (2-2-14-14)
2735 else => 5 bytes (2-2-18-18)
2736 big endian convention
2737
2738 1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2739 size : 5 bits: (IS_RAW<<6) + (0<<4) + size
2740 12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2741 size&255
2742 20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2743 size>>8&255
2744 size&255
2745
2746 1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2747 size : 5 bits: (IS_RLE<<6) + (0<<4) + size
2748 12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2749 size&255
2750 20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2751 size>>8&255
2752 size&255
2753
2754 1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2755 srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2756 srcSize < 1 KB => 3 bytes (2-2-10-10)
2757 srcSize < 16KB => 4 bytes (2-2-14-14)
2758 else => 5 bytes (2-2-18-18)
2759 big endian convention
2760
2761 1- CTable available (stored into workspace ?)
2762 2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2763
2764
2765 1.2) Literal block content
2766
2767 1.2.1) Huff0 block, using sizes from header
2768 See Huff0 format
2769
2770 1.2.2) Huff0 block, using prepared table
2771
2772 1.2.3) Raw content
2773
2774 1.2.4) single byte
2775
2776
2777 2) Sequences section
2778 TO DO
2779*/
2780
2781
2782/** ZSTDv05_decodeFrameHeader_Part1() :
2783* decode the 1st part of the Frame Header, which tells Frame Header size.
2784* srcSize must be == ZSTDv05_frameHeaderSize_min.
2785* @return : the full size of the Frame Header */
2786static size_t ZSTDv05_decodeFrameHeader_Part1(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2787{
2788 U32 magicNumber;
2789 if (srcSize != ZSTDv05_frameHeaderSize_min)
2790 return ERROR(srcSize_wrong);
2791 magicNumber = MEM_readLE32(src);
2792 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2793 zc->headerSize = ZSTDv05_frameHeaderSize_min;
2794 return zc->headerSize;
2795}
2796
2797
2798size_t ZSTDv05_getFrameParams(ZSTDv05_parameters* params, const void* src, size_t srcSize)
2799{
2800 U32 magicNumber;
2801 if (srcSize < ZSTDv05_frameHeaderSize_min) return ZSTDv05_frameHeaderSize_max;
2802 magicNumber = MEM_readLE32(src);
2803 if (magicNumber != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
2804 memset(params, 0, sizeof(*params));
2805 params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTDv05_WINDOWLOG_ABSOLUTEMIN;
2806 if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported); /* reserved bits */
2807 return 0;
2808}
2809
2810/** ZSTDv05_decodeFrameHeader_Part2() :
2811* decode the full Frame Header.
2812* srcSize must be the size provided by ZSTDv05_decodeFrameHeader_Part1().
2813* @return : 0, or an error code, which can be tested using ZSTDv05_isError() */
2814static size_t ZSTDv05_decodeFrameHeader_Part2(ZSTDv05_DCtx* zc, const void* src, size_t srcSize)
2815{
2816 size_t result;
2817 if (srcSize != zc->headerSize)
2818 return ERROR(srcSize_wrong);
2819 result = ZSTDv05_getFrameParams(&(zc->params), src, srcSize);
2820 if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported);
2821 return result;
2822}
2823
2824
2825size_t ZSTDv05_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2826{
2827 const BYTE* const in = (const BYTE* const)src;
2828 BYTE headerFlags;
2829 U32 cSize;
2830
2831 if (srcSize < 3)
2832 return ERROR(srcSize_wrong);
2833
2834 headerFlags = *in;
2835 cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2836
2837 bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2838 bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2839
2840 if (bpPtr->blockType == bt_end) return 0;
2841 if (bpPtr->blockType == bt_rle) return 1;
2842 return cSize;
2843}
2844
2845
2846static size_t ZSTDv05_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2847{
2848 if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2849 memcpy(dst, src, srcSize);
2850 return srcSize;
2851}
2852
2853
2854/*! ZSTDv05_decodeLiteralsBlock() :
2855 @return : nb of bytes read from src (< srcSize ) */
2856size_t ZSTDv05_decodeLiteralsBlock(ZSTDv05_DCtx* dctx,
2857 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
2858{
2859 const BYTE* const istart = (const BYTE*) src;
2860
2861 /* any compressed block with literals segment must be at least this size */
2862 if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2863
2864 switch(istart[0]>> 6)
2865 {
2866 case IS_HUFv05:
2867 {
2868 size_t litSize, litCSize, singleStream=0;
2869 U32 lhSize = ((istart[0]) >> 4) & 3;
2870 if (srcSize < 5) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
2871 switch(lhSize)
2872 {
2873 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2874 /* 2 - 2 - 10 - 10 */
2875 lhSize=3;
2876 singleStream = istart[0] & 16;
2877 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2878 litCSize = ((istart[1] & 3) << 8) + istart[2];
2879 break;
2880 case 2:
2881 /* 2 - 2 - 14 - 14 */
2882 lhSize=4;
2883 litSize = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
2884 litCSize = ((istart[2] & 63) << 8) + istart[3];
2885 break;
2886 case 3:
2887 /* 2 - 2 - 18 - 18 */
2888 lhSize=5;
2889 litSize = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
2890 litCSize = ((istart[2] & 3) << 16) + (istart[3] << 8) + istart[4];
2891 break;
2892 }
2893 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2894 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2895
2896 if (HUFv05_isError(singleStream ?
2897 HUFv05_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) :
2898 HUFv05_decompress (dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
2899 return ERROR(corruption_detected);
2900
2901 dctx->litPtr = dctx->litBuffer;
2902 dctx->litSize = litSize;
2903 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2904 return litCSize + lhSize;
2905 }
2906 case IS_PCH:
2907 {
2908 size_t errorCode;
2909 size_t litSize, litCSize;
2910 U32 lhSize = ((istart[0]) >> 4) & 3;
2911 if (lhSize != 1) /* only case supported for now : small litSize, single stream */
2912 return ERROR(corruption_detected);
2913 if (!dctx->flagStaticTables)
2914 return ERROR(dictionary_corrupted);
2915
2916 /* 2 - 2 - 10 - 10 */
2917 lhSize=3;
2918 litSize = ((istart[0] & 15) << 6) + (istart[1] >> 2);
2919 litCSize = ((istart[1] & 3) << 8) + istart[2];
2920 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
2921
2922 errorCode = HUFv05_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4);
2923 if (HUFv05_isError(errorCode)) return ERROR(corruption_detected);
2924
2925 dctx->litPtr = dctx->litBuffer;
2926 dctx->litSize = litSize;
2927 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2928 return litCSize + lhSize;
2929 }
2930 case IS_RAW:
2931 {
2932 size_t litSize;
2933 U32 lhSize = ((istart[0]) >> 4) & 3;
2934 switch(lhSize)
2935 {
2936 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2937 lhSize=1;
2938 litSize = istart[0] & 31;
2939 break;
2940 case 2:
2941 litSize = ((istart[0] & 15) << 8) + istart[1];
2942 break;
2943 case 3:
2944 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2945 break;
2946 }
2947
2948 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
2949 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
2950 memcpy(dctx->litBuffer, istart+lhSize, litSize);
2951 dctx->litPtr = dctx->litBuffer;
2952 dctx->litSize = litSize;
2953 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
2954 return lhSize+litSize;
2955 }
2956 /* direct reference into compressed stream */
2957 dctx->litPtr = istart+lhSize;
2958 dctx->litSize = litSize;
2959 return lhSize+litSize;
2960 }
2961 case IS_RLE:
2962 {
2963 size_t litSize;
2964 U32 lhSize = ((istart[0]) >> 4) & 3;
2965 switch(lhSize)
2966 {
2967 case 0: case 1: default: /* note : default is impossible, since lhSize into [0..3] */
2968 lhSize = 1;
2969 litSize = istart[0] & 31;
2970 break;
2971 case 2:
2972 litSize = ((istart[0] & 15) << 8) + istart[1];
2973 break;
2974 case 3:
2975 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
2976 if (srcSize<4) return ERROR(corruption_detected); /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
2977 break;
2978 }
2979 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2980 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
2981 dctx->litPtr = dctx->litBuffer;
2982 dctx->litSize = litSize;
2983 return lhSize+1;
2984 }
2985 default:
2986 return ERROR(corruption_detected); /* impossible */
2987 }
2988}
2989
2990
2991size_t ZSTDv05_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2992 FSEv05_DTable* DTableLL, FSEv05_DTable* DTableML, FSEv05_DTable* DTableOffb,
2993 const void* src, size_t srcSize, U32 flagStaticTable)
2994{
2995 const BYTE* const istart = (const BYTE* const)src;
2996 const BYTE* ip = istart;
2997 const BYTE* const iend = istart + srcSize;
2998 U32 LLtype, Offtype, MLtype;
2999 U32 LLlog, Offlog, MLlog;
3000 size_t dumpsLength;
3001
3002 /* check */
3003 if (srcSize < MIN_SEQUENCES_SIZE)
3004 return ERROR(srcSize_wrong);
3005
3006 /* SeqHead */
3007 *nbSeq = *ip++;
3008 if (*nbSeq==0) return 1;
3009 if (*nbSeq >= 128) {
3010 if (ip >= iend) return ERROR(srcSize_wrong);
3011 *nbSeq = ((nbSeq[0]-128)<<8) + *ip++;
3012 }
3013
3014 if (ip >= iend) return ERROR(srcSize_wrong);
3015 LLtype = *ip >> 6;
3016 Offtype = (*ip >> 4) & 3;
3017 MLtype = (*ip >> 2) & 3;
3018 if (*ip & 2) {
3019 if (ip+3 > iend) return ERROR(srcSize_wrong);
3020 dumpsLength = ip[2];
3021 dumpsLength += ip[1] << 8;
3022 ip += 3;
3023 } else {
3024 if (ip+2 > iend) return ERROR(srcSize_wrong);
3025 dumpsLength = ip[1];
3026 dumpsLength += (ip[0] & 1) << 8;
3027 ip += 2;
3028 }
3029 *dumpsPtr = ip;
3030 ip += dumpsLength;
3031 *dumpsLengthPtr = dumpsLength;
3032
3033 /* check */
3034 if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
3035
3036 /* sequences */
3037 {
3038 S16 norm[MaxML+1]; /* assumption : MaxML >= MaxLL >= MaxOff */
3039 size_t headerSize;
3040
3041 /* Build DTables */
3042 switch(LLtype)
3043 {
3044 case FSEv05_ENCODING_RLE :
3045 LLlog = 0;
3046 FSEv05_buildDTable_rle(DTableLL, *ip++);
3047 break;
3048 case FSEv05_ENCODING_RAW :
3049 LLlog = LLbits;
3050 FSEv05_buildDTable_raw(DTableLL, LLbits);
3051 break;
3052 case FSEv05_ENCODING_STATIC:
3053 if (!flagStaticTable) return ERROR(corruption_detected);
3054 break;
3055 case FSEv05_ENCODING_DYNAMIC :
3056 default : /* impossible */
3057 { U32 max = MaxLL;
3058 headerSize = FSEv05_readNCount(norm, &max, &LLlog, ip, iend-ip);
3059 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3060 if (LLlog > LLFSEv05Log) return ERROR(corruption_detected);
3061 ip += headerSize;
3062 FSEv05_buildDTable(DTableLL, norm, max, LLlog);
3063 } }
3064
3065 switch(Offtype)
3066 {
3067 case FSEv05_ENCODING_RLE :
3068 Offlog = 0;
3069 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3070 FSEv05_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
3071 break;
3072 case FSEv05_ENCODING_RAW :
3073 Offlog = Offbits;
3074 FSEv05_buildDTable_raw(DTableOffb, Offbits);
3075 break;
3076 case FSEv05_ENCODING_STATIC:
3077 if (!flagStaticTable) return ERROR(corruption_detected);
3078 break;
3079 case FSEv05_ENCODING_DYNAMIC :
3080 default : /* impossible */
3081 { U32 max = MaxOff;
3082 headerSize = FSEv05_readNCount(norm, &max, &Offlog, ip, iend-ip);
3083 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3084 if (Offlog > OffFSEv05Log) return ERROR(corruption_detected);
3085 ip += headerSize;
3086 FSEv05_buildDTable(DTableOffb, norm, max, Offlog);
3087 } }
3088
3089 switch(MLtype)
3090 {
3091 case FSEv05_ENCODING_RLE :
3092 MLlog = 0;
3093 if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
3094 FSEv05_buildDTable_rle(DTableML, *ip++);
3095 break;
3096 case FSEv05_ENCODING_RAW :
3097 MLlog = MLbits;
3098 FSEv05_buildDTable_raw(DTableML, MLbits);
3099 break;
3100 case FSEv05_ENCODING_STATIC:
3101 if (!flagStaticTable) return ERROR(corruption_detected);
3102 break;
3103 case FSEv05_ENCODING_DYNAMIC :
3104 default : /* impossible */
3105 { U32 max = MaxML;
3106 headerSize = FSEv05_readNCount(norm, &max, &MLlog, ip, iend-ip);
3107 if (FSEv05_isError(headerSize)) return ERROR(GENERIC);
3108 if (MLlog > MLFSEv05Log) return ERROR(corruption_detected);
3109 ip += headerSize;
3110 FSEv05_buildDTable(DTableML, norm, max, MLlog);
3111 } } }
3112
3113 return ip-istart;
3114}
3115
3116
3117typedef struct {
3118 size_t litLength;
3119 size_t matchLength;
3120 size_t offset;
3121} seq_t;
3122
3123typedef struct {
3124 BITv05_DStream_t DStream;
3125 FSEv05_DState_t stateLL;
3126 FSEv05_DState_t stateOffb;
3127 FSEv05_DState_t stateML;
3128 size_t prevOffset;
3129 const BYTE* dumps;
3130 const BYTE* dumpsEnd;
3131} seqState_t;
3132
3133
3134
3135static void ZSTDv05_decodeSequence(seq_t* seq, seqState_t* seqState)
3136{
3137 size_t litLength;
3138 size_t prevOffset;
3139 size_t offset;
3140 size_t matchLength;
3141 const BYTE* dumps = seqState->dumps;
3142 const BYTE* const de = seqState->dumpsEnd;
3143
3144 /* Literal length */
3145 litLength = FSEv05_peakSymbol(&(seqState->stateLL));
3146 prevOffset = litLength ? seq->offset : seqState->prevOffset;
3147 if (litLength == MaxLL) {
3148 U32 add = *dumps++;
3149 if (add < 255) litLength += add;
3150 else {
3151 litLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no risk : dumps is always followed by seq tables > 1 byte */
3152 if (litLength&1) litLength>>=1, dumps += 3;
3153 else litLength = (U16)(litLength)>>1, dumps += 2;
3154 }
3155 if (dumps > de) { litLength = MaxLL+255; } /* late correction, to avoid using uninitialized memory */
3156 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3157 }
3158
3159 /* Offset */
3160 {
3161 static const U32 offsetPrefix[MaxOff+1] = {
3162 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
3163 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
3164 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
3165 U32 offsetCode = FSEv05_peakSymbol(&(seqState->stateOffb)); /* <= maxOff, by table construction */
3166 U32 nbBits = offsetCode - 1;
3167 if (offsetCode==0) nbBits = 0; /* cmove */
3168 offset = offsetPrefix[offsetCode] + BITv05_readBits(&(seqState->DStream), nbBits);
3169 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3170 if (offsetCode==0) offset = prevOffset; /* repcode, cmove */
3171 if (offsetCode | !litLength) seqState->prevOffset = seq->offset; /* cmove */
3172 FSEv05_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream)); /* update */
3173 }
3174
3175 /* Literal length update */
3176 FSEv05_decodeSymbol(&(seqState->stateLL), &(seqState->DStream)); /* update */
3177 if (MEM_32bits()) BITv05_reloadDStream(&(seqState->DStream));
3178
3179 /* MatchLength */
3180 matchLength = FSEv05_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
3181 if (matchLength == MaxML) {
3182 U32 add = *dumps++;
3183 if (add < 255) matchLength += add;
3184 else {
3185 matchLength = MEM_readLE32(dumps) & 0xFFFFFF; /* no pb : dumps is always followed by seq tables > 1 byte */
3186 if (matchLength&1) matchLength>>=1, dumps += 3;
3187 else matchLength = (U16)(matchLength)>>1, dumps += 2;
3188 }
3189 if (dumps > de) { matchLength = MaxML+255; } /* late correction, to avoid using uninitialized memory */
3190 if (dumps >= de) { dumps = de-1; } /* late correction, to avoid read overflow (data is now corrupted anyway) */
3191 }
3192 matchLength += MINMATCH;
3193
3194 /* save result */
3195 seq->litLength = litLength;
3196 seq->offset = offset;
3197 seq->matchLength = matchLength;
3198 seqState->dumps = dumps;
3199
3200#if 0 /* debug */
3201 {
3202 static U64 totalDecoded = 0;
3203 printf("pos %6u : %3u literals & match %3u bytes at distance %6u \n",
3204 (U32)(totalDecoded), (U32)litLength, (U32)matchLength, (U32)offset);
3205 totalDecoded += litLength + matchLength;
3206 }
3207#endif
3208}
3209
3210
3211static size_t ZSTDv05_execSequence(BYTE* op,
3212 BYTE* const oend, seq_t sequence,
3213 const BYTE** litPtr, const BYTE* const litLimit,
3214 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3215{
3216 static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
3217 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* substracted */
3218 BYTE* const oLitEnd = op + sequence.litLength;
3219 const size_t sequenceLength = sequence.litLength + sequence.matchLength;
3220 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
3221 BYTE* const oend_8 = oend-8;
3222 const BYTE* const litEnd = *litPtr + sequence.litLength;
3223 const BYTE* match = oLitEnd - sequence.offset;
3224
3225 /* check */
3226 if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of 8 from oend */
3227 if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* overwrite beyond dst buffer */
3228 if (litEnd > litLimit) return ERROR(corruption_detected); /* risk read beyond lit buffer */
3229
3230 /* copy Literals */
3231 ZSTDv05_wildcopy(op, *litPtr, sequence.litLength); /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3232 op = oLitEnd;
3233 *litPtr = litEnd; /* update for next sequence */
3234
3235 /* copy Match */
3236 if (sequence.offset > (size_t)(oLitEnd - base)) {
3237 /* offset beyond prefix */
3238 if (sequence.offset > (size_t)(oLitEnd - vBase))
3239 return ERROR(corruption_detected);
3240 match = dictEnd - (base-match);
3241 if (match + sequence.matchLength <= dictEnd) {
3242 memmove(oLitEnd, match, sequence.matchLength);
3243 return sequenceLength;
3244 }
3245 /* span extDict & currentPrefixSegment */
3246 {
3247 size_t length1 = dictEnd - match;
3248 memmove(oLitEnd, match, length1);
3249 op = oLitEnd + length1;
3250 sequence.matchLength -= length1;
3251 match = base;
3252 if (op > oend_8 || sequence.matchLength < MINMATCH) {
3253 while (op < oMatchEnd) *op++ = *match++;
3254 return sequenceLength;
3255 }
3256 } }
3257 /* Requirement: op <= oend_8 */
3258
3259 /* match within prefix */
3260 if (sequence.offset < 8) {
3261 /* close range match, overlap */
3262 const int sub2 = dec64table[sequence.offset];
3263 op[0] = match[0];
3264 op[1] = match[1];
3265 op[2] = match[2];
3266 op[3] = match[3];
3267 match += dec32table[sequence.offset];
3268 ZSTDv05_copy4(op+4, match);
3269 match -= sub2;
3270 } else {
3271 ZSTDv05_copy8(op, match);
3272 }
3273 op += 8; match += 8;
3274
3275 if (oMatchEnd > oend-(16-MINMATCH)) {
3276 if (op < oend_8) {
3277 ZSTDv05_wildcopy(op, match, oend_8 - op);
3278 match += oend_8 - op;
3279 op = oend_8;
3280 }
3281 while (op < oMatchEnd)
3282 *op++ = *match++;
3283 } else {
3284 ZSTDv05_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8); /* works even if matchLength < 8 */
3285 }
3286 return sequenceLength;
3287}
3288
3289
3290static size_t ZSTDv05_decompressSequences(
3291 ZSTDv05_DCtx* dctx,
3292 void* dst, size_t maxDstSize,
3293 const void* seqStart, size_t seqSize)
3294{
3295 const BYTE* ip = (const BYTE*)seqStart;
3296 const BYTE* const iend = ip + seqSize;
3297 BYTE* const ostart = (BYTE* const)dst;
3298 BYTE* op = ostart;
3299 BYTE* const oend = ostart + maxDstSize;
3300 size_t errorCode, dumpsLength;
3301 const BYTE* litPtr = dctx->litPtr;
3302 const BYTE* const litEnd = litPtr + dctx->litSize;
3303 int nbSeq;
3304 const BYTE* dumps;
3305 U32* DTableLL = dctx->LLTable;
3306 U32* DTableML = dctx->MLTable;
3307 U32* DTableOffb = dctx->OffTable;
3308 const BYTE* const base = (const BYTE*) (dctx->base);
3309 const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3310 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3311
3312 /* Build Decoding Tables */
3313 errorCode = ZSTDv05_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
3314 DTableLL, DTableML, DTableOffb,
3315 ip, seqSize, dctx->flagStaticTables);
3316 if (ZSTDv05_isError(errorCode)) return errorCode;
3317 ip += errorCode;
3318
3319 /* Regen sequences */
3320 if (nbSeq) {
3321 seq_t sequence;
3322 seqState_t seqState;
3323
3324 memset(&sequence, 0, sizeof(sequence));
3325 sequence.offset = REPCODE_STARTVALUE;
3326 seqState.dumps = dumps;
3327 seqState.dumpsEnd = dumps + dumpsLength;
3328 seqState.prevOffset = REPCODE_STARTVALUE;
3329 errorCode = BITv05_initDStream(&(seqState.DStream), ip, iend-ip);
3330 if (ERR_isError(errorCode)) return ERROR(corruption_detected);
3331 FSEv05_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3332 FSEv05_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3333 FSEv05_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3334
3335 for ( ; (BITv05_reloadDStream(&(seqState.DStream)) <= BITv05_DStream_completed) && nbSeq ; ) {
3336 size_t oneSeqSize;
3337 nbSeq--;
3338 ZSTDv05_decodeSequence(&sequence, &seqState);
3339 oneSeqSize = ZSTDv05_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3340 if (ZSTDv05_isError(oneSeqSize)) return oneSeqSize;
3341 op += oneSeqSize;
3342 }
3343
3344 /* check if reached exact end */
3345 if (nbSeq) return ERROR(corruption_detected);
3346 }
3347
3348 /* last literal segment */
3349 {
3350 size_t lastLLSize = litEnd - litPtr;
3351 if (litPtr > litEnd) return ERROR(corruption_detected); /* too many literals already used */
3352 if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3353 memcpy(op, litPtr, lastLLSize);
3354 op += lastLLSize;
3355 }
3356
3357 return op-ostart;
3358}
3359
3360
3361static void ZSTDv05_checkContinuity(ZSTDv05_DCtx* dctx, const void* dst)
3362{
3363 if (dst != dctx->previousDstEnd) { /* not contiguous */
3364 dctx->dictEnd = dctx->previousDstEnd;
3365 dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3366 dctx->base = dst;
3367 dctx->previousDstEnd = dst;
3368 }
3369}
3370
3371
3372static size_t ZSTDv05_decompressBlock_internal(ZSTDv05_DCtx* dctx,
3373 void* dst, size_t dstCapacity,
3374 const void* src, size_t srcSize)
3375{ /* blockType == blockCompressed */
3376 const BYTE* ip = (const BYTE*)src;
3377 size_t litCSize;
3378
3379 if (srcSize >= BLOCKSIZE) return ERROR(srcSize_wrong);
3380
3381 /* Decode literals sub-block */
3382 litCSize = ZSTDv05_decodeLiteralsBlock(dctx, src, srcSize);
3383 if (ZSTDv05_isError(litCSize)) return litCSize;
3384 ip += litCSize;
3385 srcSize -= litCSize;
3386
3387 return ZSTDv05_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3388}
3389
3390
3391size_t ZSTDv05_decompressBlock(ZSTDv05_DCtx* dctx,
3392 void* dst, size_t dstCapacity,
3393 const void* src, size_t srcSize)
3394{
3395 ZSTDv05_checkContinuity(dctx, dst);
3396 return ZSTDv05_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3397}
3398
3399
3400/*! ZSTDv05_decompress_continueDCtx
3401* dctx must have been properly initialized */
3402static size_t ZSTDv05_decompress_continueDCtx(ZSTDv05_DCtx* dctx,
3403 void* dst, size_t maxDstSize,
3404 const void* src, size_t srcSize)
3405{
3406 const BYTE* ip = (const BYTE*)src;
3407 const BYTE* iend = ip + srcSize;
3408 BYTE* const ostart = (BYTE* const)dst;
3409 BYTE* op = ostart;
3410 BYTE* const oend = ostart + maxDstSize;
3411 size_t remainingSize = srcSize;
3412 blockProperties_t blockProperties;
3413
3414 /* Frame Header */
3415 {
3416 size_t frameHeaderSize;
3417 if (srcSize < ZSTDv05_frameHeaderSize_min+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3418 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3419 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3420 if (srcSize < frameHeaderSize+ZSTDv05_blockHeaderSize) return ERROR(srcSize_wrong);
3421 ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3422 frameHeaderSize = ZSTDv05_decodeFrameHeader_Part2(dctx, src, frameHeaderSize);
3423 if (ZSTDv05_isError(frameHeaderSize)) return frameHeaderSize;
3424 }
3425
3426 /* Loop on each block */
3427 while (1)
3428 {
3429 size_t decodedSize=0;
3430 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, iend-ip, &blockProperties);
3431 if (ZSTDv05_isError(cBlockSize)) return cBlockSize;
3432
3433 ip += ZSTDv05_blockHeaderSize;
3434 remainingSize -= ZSTDv05_blockHeaderSize;
3435 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3436
3437 switch(blockProperties.blockType)
3438 {
3439 case bt_compressed:
3440 decodedSize = ZSTDv05_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3441 break;
3442 case bt_raw :
3443 decodedSize = ZSTDv05_copyRawBlock(op, oend-op, ip, cBlockSize);
3444 break;
3445 case bt_rle :
3446 return ERROR(GENERIC); /* not yet supported */
3447 break;
3448 case bt_end :
3449 /* end of frame */
3450 if (remainingSize) return ERROR(srcSize_wrong);
3451 break;
3452 default:
3453 return ERROR(GENERIC); /* impossible */
3454 }
3455 if (cBlockSize == 0) break; /* bt_end */
3456
3457 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3458 op += decodedSize;
3459 ip += cBlockSize;
3460 remainingSize -= cBlockSize;
3461 }
3462
3463 return op-ostart;
3464}
3465
3466
3467size_t ZSTDv05_decompress_usingPreparedDCtx(ZSTDv05_DCtx* dctx, const ZSTDv05_DCtx* refDCtx,
3468 void* dst, size_t maxDstSize,
3469 const void* src, size_t srcSize)
3470{
3471 ZSTDv05_copyDCtx(dctx, refDCtx);
3472 ZSTDv05_checkContinuity(dctx, dst);
3473 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3474}
3475
3476
3477size_t ZSTDv05_decompress_usingDict(ZSTDv05_DCtx* dctx,
3478 void* dst, size_t maxDstSize,
3479 const void* src, size_t srcSize,
3480 const void* dict, size_t dictSize)
3481{
3482 ZSTDv05_decompressBegin_usingDict(dctx, dict, dictSize);
3483 ZSTDv05_checkContinuity(dctx, dst);
3484 return ZSTDv05_decompress_continueDCtx(dctx, dst, maxDstSize, src, srcSize);
3485}
3486
3487
3488size_t ZSTDv05_decompressDCtx(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3489{
3490 return ZSTDv05_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
3491}
3492
3493size_t ZSTDv05_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3494{
3495#if defined(ZSTDv05_HEAPMODE) && (ZSTDv05_HEAPMODE==1)
3496 size_t regenSize;
3497 ZSTDv05_DCtx* dctx = ZSTDv05_createDCtx();
3498 if (dctx==NULL) return ERROR(memory_allocation);
3499 regenSize = ZSTDv05_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
3500 ZSTDv05_freeDCtx(dctx);
3501 return regenSize;
3502#else
3503 ZSTDv05_DCtx dctx;
3504 return ZSTDv05_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
3505#endif
3506}
3507
3508size_t ZSTDv05_findFrameCompressedSize(const void *src, size_t srcSize)
3509{
3510 const BYTE* ip = (const BYTE*)src;
3511 size_t remainingSize = srcSize;
3512 blockProperties_t blockProperties;
3513
3514 /* Frame Header */
3515 if (srcSize < ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong);
3516 if (MEM_readLE32(src) != ZSTDv05_MAGICNUMBER) return ERROR(prefix_unknown);
3517 ip += ZSTDv05_frameHeaderSize_min; remainingSize -= ZSTDv05_frameHeaderSize_min;
3518
3519 /* Loop on each block */
3520 while (1)
3521 {
3522 size_t cBlockSize = ZSTDv05_getcBlockSize(ip, remainingSize, &blockProperties);
3523 if (ZSTDv05_isError(cBlockSize)) return cBlockSize;
3524
3525 ip += ZSTDv05_blockHeaderSize;
3526 remainingSize -= ZSTDv05_blockHeaderSize;
3527 if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3528
3529 if (cBlockSize == 0) break; /* bt_end */
3530
3531 ip += cBlockSize;
3532 remainingSize -= cBlockSize;
3533 }
3534
3535 return ip - (const BYTE*)src;
3536}
3537
3538/* ******************************
3539* Streaming Decompression API
3540********************************/
3541size_t ZSTDv05_nextSrcSizeToDecompress(ZSTDv05_DCtx* dctx)
3542{
3543 return dctx->expected;
3544}
3545
3546size_t ZSTDv05_decompressContinue(ZSTDv05_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3547{
3548 /* Sanity check */
3549 if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3550 ZSTDv05_checkContinuity(dctx, dst);
3551
3552 /* Decompress : frame header; part 1 */
3553 switch (dctx->stage)
3554 {
3555 case ZSTDv05ds_getFrameHeaderSize :
3556 /* get frame header size */
3557 if (srcSize != ZSTDv05_frameHeaderSize_min) return ERROR(srcSize_wrong); /* impossible */
3558 dctx->headerSize = ZSTDv05_decodeFrameHeader_Part1(dctx, src, ZSTDv05_frameHeaderSize_min);
3559 if (ZSTDv05_isError(dctx->headerSize)) return dctx->headerSize;
3560 memcpy(dctx->headerBuffer, src, ZSTDv05_frameHeaderSize_min);
3561 if (dctx->headerSize > ZSTDv05_frameHeaderSize_min) return ERROR(GENERIC); /* should never happen */
3562 dctx->expected = 0; /* not necessary to copy more */
3563 /* fallthrough */
3564 case ZSTDv05ds_decodeFrameHeader:
3565 /* get frame header */
3566 { size_t const result = ZSTDv05_decodeFrameHeader_Part2(dctx, dctx->headerBuffer, dctx->headerSize);
3567 if (ZSTDv05_isError(result)) return result;
3568 dctx->expected = ZSTDv05_blockHeaderSize;
3569 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3570 return 0;
3571 }
3572 case ZSTDv05ds_decodeBlockHeader:
3573 {
3574 /* Decode block header */
3575 blockProperties_t bp;
3576 size_t blockSize = ZSTDv05_getcBlockSize(src, ZSTDv05_blockHeaderSize, &bp);
3577 if (ZSTDv05_isError(blockSize)) return blockSize;
3578 if (bp.blockType == bt_end) {
3579 dctx->expected = 0;
3580 dctx->stage = ZSTDv05ds_getFrameHeaderSize;
3581 }
3582 else {
3583 dctx->expected = blockSize;
3584 dctx->bType = bp.blockType;
3585 dctx->stage = ZSTDv05ds_decompressBlock;
3586 }
3587 return 0;
3588 }
3589 case ZSTDv05ds_decompressBlock:
3590 {
3591 /* Decompress : block content */
3592 size_t rSize;
3593 switch(dctx->bType)
3594 {
3595 case bt_compressed:
3596 rSize = ZSTDv05_decompressBlock_internal(dctx, dst, maxDstSize, src, srcSize);
3597 break;
3598 case bt_raw :
3599 rSize = ZSTDv05_copyRawBlock(dst, maxDstSize, src, srcSize);
3600 break;
3601 case bt_rle :
3602 return ERROR(GENERIC); /* not yet handled */
3603 break;
3604 case bt_end : /* should never happen (filtered at phase 1) */
3605 rSize = 0;
3606 break;
3607 default:
3608 return ERROR(GENERIC); /* impossible */
3609 }
3610 dctx->stage = ZSTDv05ds_decodeBlockHeader;
3611 dctx->expected = ZSTDv05_blockHeaderSize;
3612 dctx->previousDstEnd = (char*)dst + rSize;
3613 return rSize;
3614 }
3615 default:
3616 return ERROR(GENERIC); /* impossible */
3617 }
3618}
3619
3620
3621static void ZSTDv05_refDictContent(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3622{
3623 dctx->dictEnd = dctx->previousDstEnd;
3624 dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3625 dctx->base = dict;
3626 dctx->previousDstEnd = (const char*)dict + dictSize;
3627}
3628
3629static size_t ZSTDv05_loadEntropy(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3630{
3631 size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, errorCode, litlengthHeaderSize;
3632 short offcodeNCount[MaxOff+1];
3633 U32 offcodeMaxValue=MaxOff, offcodeLog;
3634 short matchlengthNCount[MaxML+1];
3635 unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3636 short litlengthNCount[MaxLL+1];
3637 unsigned litlengthMaxValue = MaxLL, litlengthLog;
3638
3639 hSize = HUFv05_readDTableX4(dctx->hufTableX4, dict, dictSize);
3640 if (HUFv05_isError(hSize)) return ERROR(dictionary_corrupted);
3641 dict = (const char*)dict + hSize;
3642 dictSize -= hSize;
3643
3644 offcodeHeaderSize = FSEv05_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize);
3645 if (FSEv05_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3646 if (offcodeLog > OffFSEv05Log) return ERROR(dictionary_corrupted);
3647 errorCode = FSEv05_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
3648 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3649 dict = (const char*)dict + offcodeHeaderSize;
3650 dictSize -= offcodeHeaderSize;
3651
3652 matchlengthHeaderSize = FSEv05_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize);
3653 if (FSEv05_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3654 if (matchlengthLog > MLFSEv05Log) return ERROR(dictionary_corrupted);
3655 errorCode = FSEv05_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
3656 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3657 dict = (const char*)dict + matchlengthHeaderSize;
3658 dictSize -= matchlengthHeaderSize;
3659
3660 litlengthHeaderSize = FSEv05_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize);
3661 if (litlengthLog > LLFSEv05Log) return ERROR(dictionary_corrupted);
3662 if (FSEv05_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3663 errorCode = FSEv05_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
3664 if (FSEv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3665
3666 dctx->flagStaticTables = 1;
3667 return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize;
3668}
3669
3670static size_t ZSTDv05_decompress_insertDictionary(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3671{
3672 size_t eSize;
3673 U32 magic = MEM_readLE32(dict);
3674 if (magic != ZSTDv05_DICT_MAGIC) {
3675 /* pure content mode */
3676 ZSTDv05_refDictContent(dctx, dict, dictSize);
3677 return 0;
3678 }
3679 /* load entropy tables */
3680 dict = (const char*)dict + 4;
3681 dictSize -= 4;
3682 eSize = ZSTDv05_loadEntropy(dctx, dict, dictSize);
3683 if (ZSTDv05_isError(eSize)) return ERROR(dictionary_corrupted);
3684
3685 /* reference dictionary content */
3686 dict = (const char*)dict + eSize;
3687 dictSize -= eSize;
3688 ZSTDv05_refDictContent(dctx, dict, dictSize);
3689
3690 return 0;
3691}
3692
3693
3694size_t ZSTDv05_decompressBegin_usingDict(ZSTDv05_DCtx* dctx, const void* dict, size_t dictSize)
3695{
3696 size_t errorCode;
3697 errorCode = ZSTDv05_decompressBegin(dctx);
3698 if (ZSTDv05_isError(errorCode)) return errorCode;
3699
3700 if (dict && dictSize) {
3701 errorCode = ZSTDv05_decompress_insertDictionary(dctx, dict, dictSize);
3702 if (ZSTDv05_isError(errorCode)) return ERROR(dictionary_corrupted);
3703 }
3704
3705 return 0;
3706}
3707
3708/*
3709 Buffered version of Zstd compression library
3710 Copyright (C) 2015-2016, Yann Collet.
3711
3712 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
3713
3714 Redistribution and use in source and binary forms, with or without
3715 modification, are permitted provided that the following conditions are
3716 met:
3717 * Redistributions of source code must retain the above copyright
3718 notice, this list of conditions and the following disclaimer.
3719 * Redistributions in binary form must reproduce the above
3720 copyright notice, this list of conditions and the following disclaimer
3721 in the documentation and/or other materials provided with the
3722 distribution.
3723 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3724 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3725 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3726 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3727 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3728 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3729 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3730 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3731 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3732 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3733 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3734
3735 You can contact the author at :
3736 - zstd source repository : https://github.com/Cyan4973/zstd
3737 - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3738*/
3739
3740/* The objects defined into this file should be considered experimental.
3741 * They are not labelled stable, as their prototype may change in the future.
3742 * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3743 */
3744
3745
3746
3747/* *************************************
3748* Constants
3749***************************************/
3750static size_t ZBUFFv05_blockHeaderSize = 3;
3751
3752
3753
3754/* *** Compression *** */
3755
3756static size_t ZBUFFv05_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3757{
3758 size_t length = MIN(maxDstSize, srcSize);
3759 memcpy(dst, src, length);
3760 return length;
3761}
3762
3763
3764
3765
3766/** ************************************************
3767* Streaming decompression
3768*
3769* A ZBUFFv05_DCtx object is required to track streaming operation.
3770* Use ZBUFFv05_createDCtx() and ZBUFFv05_freeDCtx() to create/release resources.
3771* Use ZBUFFv05_decompressInit() to start a new decompression operation.
3772* ZBUFFv05_DCtx objects can be reused multiple times.
3773*
3774* Use ZBUFFv05_decompressContinue() repetitively to consume your input.
3775* *srcSizePtr and *maxDstSizePtr can be any size.
3776* The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3777* Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input.
3778* The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3779* return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3780* or 0 when a frame is completely decoded
3781* or an error code, which can be tested using ZBUFFv05_isError().
3782*
3783* Hint : recommended buffer sizes (not compulsory)
3784* output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3785* input : just follow indications from ZBUFFv05_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3786* **************************************************/
3787
3788typedef enum { ZBUFFv05ds_init, ZBUFFv05ds_readHeader, ZBUFFv05ds_loadHeader, ZBUFFv05ds_decodeHeader,
3789 ZBUFFv05ds_read, ZBUFFv05ds_load, ZBUFFv05ds_flush } ZBUFFv05_dStage;
3790
3791/* *** Resource management *** */
3792
3793#define ZSTDv05_frameHeaderSize_max 5 /* too magical, should come from reference */
3794struct ZBUFFv05_DCtx_s {
3795 ZSTDv05_DCtx* zc;
3796 ZSTDv05_parameters params;
3797 char* inBuff;
3798 size_t inBuffSize;
3799 size_t inPos;
3800 char* outBuff;
3801 size_t outBuffSize;
3802 size_t outStart;
3803 size_t outEnd;
3804 size_t hPos;
3805 ZBUFFv05_dStage stage;
3806 unsigned char headerBuffer[ZSTDv05_frameHeaderSize_max];
3807}; /* typedef'd to ZBUFFv05_DCtx within "zstd_buffered.h" */
3808
3809
3810ZBUFFv05_DCtx* ZBUFFv05_createDCtx(void)
3811{
3812 ZBUFFv05_DCtx* zbc = (ZBUFFv05_DCtx*)malloc(sizeof(ZBUFFv05_DCtx));
3813 if (zbc==NULL) return NULL;
3814 memset(zbc, 0, sizeof(*zbc));
3815 zbc->zc = ZSTDv05_createDCtx();
3816 zbc->stage = ZBUFFv05ds_init;
3817 return zbc;
3818}
3819
3820size_t ZBUFFv05_freeDCtx(ZBUFFv05_DCtx* zbc)
3821{
3822 if (zbc==NULL) return 0; /* support free on null */
3823 ZSTDv05_freeDCtx(zbc->zc);
3824 free(zbc->inBuff);
3825 free(zbc->outBuff);
3826 free(zbc);
3827 return 0;
3828}
3829
3830
3831/* *** Initialization *** */
3832
3833size_t ZBUFFv05_decompressInitDictionary(ZBUFFv05_DCtx* zbc, const void* dict, size_t dictSize)
3834{
3835 zbc->stage = ZBUFFv05ds_readHeader;
3836 zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = 0;
3837 return ZSTDv05_decompressBegin_usingDict(zbc->zc, dict, dictSize);
3838}
3839
3840size_t ZBUFFv05_decompressInit(ZBUFFv05_DCtx* zbc)
3841{
3842 return ZBUFFv05_decompressInitDictionary(zbc, NULL, 0);
3843}
3844
3845
3846/* *** Decompression *** */
3847
3848size_t ZBUFFv05_decompressContinue(ZBUFFv05_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3849{
3850 const char* const istart = (const char*)src;
3851 const char* ip = istart;
3852 const char* const iend = istart + *srcSizePtr;
3853 char* const ostart = (char*)dst;
3854 char* op = ostart;
3855 char* const oend = ostart + *maxDstSizePtr;
3856 U32 notDone = 1;
3857
3858 while (notDone) {
3859 switch(zbc->stage)
3860 {
3861 case ZBUFFv05ds_init :
3862 return ERROR(init_missing);
3863
3864 case ZBUFFv05ds_readHeader :
3865 /* read header from src */
3866 {
3867 size_t headerSize = ZSTDv05_getFrameParams(&(zbc->params), src, *srcSizePtr);
3868 if (ZSTDv05_isError(headerSize)) return headerSize;
3869 if (headerSize) {
3870 /* not enough input to decode header : tell how many bytes would be necessary */
3871 memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
3872 zbc->hPos += *srcSizePtr;
3873 *maxDstSizePtr = 0;
3874 zbc->stage = ZBUFFv05ds_loadHeader;
3875 return headerSize - zbc->hPos;
3876 }
3877 zbc->stage = ZBUFFv05ds_decodeHeader;
3878 break;
3879 }
3880 /* fall-through */
3881 case ZBUFFv05ds_loadHeader:
3882 /* complete header from src */
3883 {
3884 size_t headerSize = ZBUFFv05_limitCopy(
3885 zbc->headerBuffer + zbc->hPos, ZSTDv05_frameHeaderSize_max - zbc->hPos,
3886 src, *srcSizePtr);
3887 zbc->hPos += headerSize;
3888 ip += headerSize;
3889 headerSize = ZSTDv05_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
3890 if (ZSTDv05_isError(headerSize)) return headerSize;
3891 if (headerSize) {
3892 /* not enough input to decode header : tell how many bytes would be necessary */
3893 *maxDstSizePtr = 0;
3894 return headerSize - zbc->hPos;
3895 }
3896 // zbc->stage = ZBUFFv05ds_decodeHeader; break; /* useless : stage follows */
3897 }
3898 /* fall-through */
3899 case ZBUFFv05ds_decodeHeader:
3900 /* apply header to create / resize buffers */
3901 {
3902 size_t neededOutSize = (size_t)1 << zbc->params.windowLog;
3903 size_t neededInSize = BLOCKSIZE; /* a block is never > BLOCKSIZE */
3904 if (zbc->inBuffSize < neededInSize) {
3905 free(zbc->inBuff);
3906 zbc->inBuffSize = neededInSize;
3907 zbc->inBuff = (char*)malloc(neededInSize);
3908 if (zbc->inBuff == NULL) return ERROR(memory_allocation);
3909 }
3910 if (zbc->outBuffSize < neededOutSize) {
3911 free(zbc->outBuff);
3912 zbc->outBuffSize = neededOutSize;
3913 zbc->outBuff = (char*)malloc(neededOutSize);
3914 if (zbc->outBuff == NULL) return ERROR(memory_allocation);
3915 } }
3916 if (zbc->hPos) {
3917 /* some data already loaded into headerBuffer : transfer into inBuff */
3918 memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
3919 zbc->inPos = zbc->hPos;
3920 zbc->hPos = 0;
3921 zbc->stage = ZBUFFv05ds_load;
3922 break;
3923 }
3924 zbc->stage = ZBUFFv05ds_read;
3925 /* fall-through */
3926 case ZBUFFv05ds_read:
3927 {
3928 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3929 if (neededInSize==0) { /* end of frame */
3930 zbc->stage = ZBUFFv05ds_init;
3931 notDone = 0;
3932 break;
3933 }
3934 if ((size_t)(iend-ip) >= neededInSize) {
3935 /* directly decode from src */
3936 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3937 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3938 ip, neededInSize);
3939 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3940 ip += neededInSize;
3941 if (!decodedSize) break; /* this was just a header */
3942 zbc->outEnd = zbc->outStart + decodedSize;
3943 zbc->stage = ZBUFFv05ds_flush;
3944 break;
3945 }
3946 if (ip==iend) { notDone = 0; break; } /* no more input */
3947 zbc->stage = ZBUFFv05ds_load;
3948 }
3949 /* fall-through */
3950 case ZBUFFv05ds_load:
3951 {
3952 size_t neededInSize = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3953 size_t toLoad = neededInSize - zbc->inPos; /* should always be <= remaining space within inBuff */
3954 size_t loadedSize;
3955 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected); /* should never happen */
3956 loadedSize = ZBUFFv05_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
3957 ip += loadedSize;
3958 zbc->inPos += loadedSize;
3959 if (loadedSize < toLoad) { notDone = 0; break; } /* not enough input, wait for more */
3960 {
3961 size_t decodedSize = ZSTDv05_decompressContinue(zbc->zc,
3962 zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3963 zbc->inBuff, neededInSize);
3964 if (ZSTDv05_isError(decodedSize)) return decodedSize;
3965 zbc->inPos = 0; /* input is consumed */
3966 if (!decodedSize) { zbc->stage = ZBUFFv05ds_read; break; } /* this was just a header */
3967 zbc->outEnd = zbc->outStart + decodedSize;
3968 zbc->stage = ZBUFFv05ds_flush;
3969 // break; /* ZBUFFv05ds_flush follows */
3970 }
3971 }
3972 /* fall-through */
3973 case ZBUFFv05ds_flush:
3974 {
3975 size_t toFlushSize = zbc->outEnd - zbc->outStart;
3976 size_t flushedSize = ZBUFFv05_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
3977 op += flushedSize;
3978 zbc->outStart += flushedSize;
3979 if (flushedSize == toFlushSize) {
3980 zbc->stage = ZBUFFv05ds_read;
3981 if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
3982 zbc->outStart = zbc->outEnd = 0;
3983 break;
3984 }
3985 /* cannot flush everything */
3986 notDone = 0;
3987 break;
3988 }
3989 default: return ERROR(GENERIC); /* impossible */
3990 } }
3991
3992 *srcSizePtr = ip-istart;
3993 *maxDstSizePtr = op-ostart;
3994
3995 { size_t nextSrcSizeHint = ZSTDv05_nextSrcSizeToDecompress(zbc->zc);
3996 if (nextSrcSizeHint > ZBUFFv05_blockHeaderSize) nextSrcSizeHint+= ZBUFFv05_blockHeaderSize; /* get next block header too */
3997 nextSrcSizeHint -= zbc->inPos; /* already loaded*/
3998 return nextSrcSizeHint;
3999 }
4000}
4001
4002
4003
4004/* *************************************
4005* Tool functions
4006***************************************/
4007unsigned ZBUFFv05_isError(size_t errorCode) { return ERR_isError(errorCode); }
4008const char* ZBUFFv05_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
4009
4010size_t ZBUFFv05_recommendedDInSize(void) { return BLOCKSIZE + ZBUFFv05_blockHeaderSize /* block header size*/ ; }
4011size_t ZBUFFv05_recommendedDOutSize(void) { return BLOCKSIZE; }
4012