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