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