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