Coverage Report

Created: 2026-11-16 07:30

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