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