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