Coverage Report

Created: 2026-11-13 07:26

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