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