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