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