Coverage Report

Created: 2024-07-23 06:39

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