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