Coverage Report

Created: 2026-11-13 07:26

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/work/libzstd-src/lib/legacy/zstd_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
741
#define ZSTDv07_MAGIC_SKIPPABLE_START  0x184D2A50U
42
43
0
#define ZSTDv07_WINDOWLOG_MAX_32  25
44
9.52k
#define ZSTDv07_WINDOWLOG_MAX_64  27
45
9.52k
#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
7.88k
#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
76.7k
MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
265
3.95k
MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
266
267
MEM_STATIC unsigned MEM_isLittleEndian(void)
268
49.2k
{
269
49.2k
    const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
270
49.2k
    return one.c[0];
271
49.2k
}
272
273
MEM_STATIC U16 MEM_read16(const void* memPtr)
274
923
{
275
923
    U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
276
923
}
277
278
MEM_STATIC U32 MEM_read32(const void* memPtr)
279
27.2k
{
280
27.2k
    U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
281
27.2k
}
282
283
MEM_STATIC U64 MEM_read64(const void* memPtr)
284
21.0k
{
285
21.0k
    U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
286
21.0k
}
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
923
{
330
923
    if (MEM_isLittleEndian())
331
923
        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
923
}
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
27.2k
{
351
27.2k
    if (MEM_isLittleEndian())
352
27.2k
        return MEM_read32(memPtr);
353
0
    else
354
0
        return MEM_swap32(MEM_read32(memPtr));
355
27.2k
}
356
357
358
MEM_STATIC U64 MEM_readLE64(const void* memPtr)
359
21.0k
{
360
21.0k
    if (MEM_isLittleEndian())
361
21.0k
        return MEM_read64(memPtr);
362
0
    else
363
0
        return MEM_swap64(MEM_read64(memPtr));
364
21.0k
}
365
366
MEM_STATIC size_t MEM_readLEST(const void* memPtr)
367
20.8k
{
368
20.8k
    if (MEM_32bits())
369
0
        return (size_t)MEM_readLE32(memPtr);
370
20.8k
    else
371
20.8k
        return (size_t)MEM_readLE64(memPtr);
372
20.8k
}
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
461k
{
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
461k
}
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
1.92k
{
504
1.92k
    if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
505
506
1.91k
    if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
507
1.49k
        bitD->start = (const char*)srcBuffer;
508
1.49k
        bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
509
1.49k
        bitD->bitContainer = MEM_readLEST(bitD->ptr);
510
1.49k
        { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
511
1.49k
          bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
512
1.49k
          if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
513
1.49k
    } else {
514
418
        bitD->start = (const char*)srcBuffer;
515
418
        bitD->ptr   = bitD->start;
516
418
        bitD->bitContainer = *(const BYTE*)(bitD->start);
517
418
        switch(srcSize)
518
418
        {
519
66
            case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
520
111
            case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
521
206
            case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
522
288
            case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
523
344
            case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
524
392
            case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8; /* fall-through */
525
418
            default: break;
526
418
        }
527
418
        { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
528
418
          bitD->bitsConsumed = lastByte ? 8 - BITv07_highbit32(lastByte) : 0;
529
418
          if (lastByte == 0) return ERROR(GENERIC); /* endMark not present */ }
530
393
        bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
531
393
    }
532
533
1.87k
    return srcSize;
534
1.91k
}
535
536
537
 MEM_STATIC size_t BITv07_lookBits(const BITv07_DStream_t* bitD, U32 nbBits)
538
64.7k
{
539
64.7k
    U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
540
64.7k
    return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
541
64.7k
}
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
21.5k
{
547
21.5k
    U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
548
21.5k
    return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
549
21.5k
}
550
551
MEM_STATIC void BITv07_skipBits(BITv07_DStream_t* bitD, U32 nbBits)
552
86.2k
{
553
86.2k
    bitD->bitsConsumed += nbBits;
554
86.2k
}
555
556
MEM_STATIC size_t BITv07_readBits(BITv07_DStream_t* bitD, U32 nbBits)
557
64.7k
{
558
64.7k
    size_t const value = BITv07_lookBits(bitD, nbBits);
559
64.7k
    BITv07_skipBits(bitD, nbBits);
560
64.7k
    return value;
561
64.7k
}
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
3.77k
{
567
3.77k
    size_t const value = BITv07_lookBitsFast(bitD, nbBits);
568
3.77k
    BITv07_skipBits(bitD, nbBits);
569
3.77k
    return value;
570
3.77k
}
571
572
MEM_STATIC BITv07_DStream_status BITv07_reloadDStream(BITv07_DStream_t* bitD)
573
25.8k
{
574
25.8k
    if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should not happen => corruption detected */
575
376
        return BITv07_DStream_overflow;
576
577
25.4k
    if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
578
15.4k
        bitD->ptr -= bitD->bitsConsumed >> 3;
579
15.4k
        bitD->bitsConsumed &= 7;
580
15.4k
        bitD->bitContainer = MEM_readLEST(bitD->ptr);
581
15.4k
        return BITv07_DStream_unfinished;
582
15.4k
    }
583
10.0k
    if (bitD->ptr == bitD->start) {
584
6.07k
        if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv07_DStream_endOfBuffer;
585
136
        return BITv07_DStream_completed;
586
6.07k
    }
587
3.94k
    {   U32 nbBytes = bitD->bitsConsumed >> 3;
588
3.94k
        BITv07_DStream_status result = BITv07_DStream_unfinished;
589
3.94k
        if (bitD->ptr - nbBytes < bitD->start) {
590
212
            nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
591
212
            result = BITv07_DStream_endOfBuffer;
592
212
        }
593
3.94k
        bitD->ptr -= nbBytes;
594
3.94k
        bitD->bitsConsumed -= nbBytes*8;
595
3.94k
        bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
596
3.94k
        return result;
597
10.0k
    }
598
10.0k
}
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
50
{
605
50
    return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
606
50
}
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
5.26k
{
819
5.26k
    const void* ptr = dt;
820
5.26k
    const FSEv07_DTableHeader* const DTableH = (const FSEv07_DTableHeader*)ptr;
821
5.26k
    DStatePtr->state = BITv07_readBits(bitD, DTableH->tableLog);
822
5.26k
    BITv07_reloadDStream(bitD);
823
5.26k
    DStatePtr->table = dt + 1;
824
5.26k
}
825
826
MEM_STATIC BYTE FSEv07_peekSymbol(const FSEv07_DState_t* DStatePtr)
827
39.2k
{
828
39.2k
    FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
829
39.2k
    return DInfo.symbol;
830
39.2k
}
831
832
MEM_STATIC void FSEv07_updateState(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
833
39.2k
{
834
39.2k
    FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
835
39.2k
    U32 const nbBits = DInfo.nbBits;
836
39.2k
    size_t const lowBits = BITv07_readBits(bitD, nbBits);
837
39.2k
    DStatePtr->state = DInfo.newState + lowBits;
838
39.2k
}
839
840
MEM_STATIC BYTE FSEv07_decodeSymbol(FSEv07_DState_t* DStatePtr, BITv07_DStream_t* bitD)
841
7.37k
{
842
7.37k
    FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
843
7.37k
    U32 const nbBits = DInfo.nbBits;
844
7.37k
    BYTE const symbol = DInfo.symbol;
845
7.37k
    size_t const lowBits = BITv07_readBits(bitD, nbBits);
846
847
7.37k
    DStatePtr->state = DInfo.newState + lowBits;
848
7.37k
    return symbol;
849
7.37k
}
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
3.77k
{
855
3.77k
    FSEv07_decode_t const DInfo = ((const FSEv07_decode_t*)(DStatePtr->table))[DStatePtr->state];
856
3.77k
    U32 const nbBits = DInfo.nbBits;
857
3.77k
    BYTE const symbol = DInfo.symbol;
858
3.77k
    size_t const lowBits = BITv07_readBitsFast(bitD, nbBits);
859
860
3.77k
    DStatePtr->state = DInfo.newState + lowBits;
861
3.77k
    return symbol;
862
3.77k
}
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
10.0k
#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
4.55k
#define FSEv07_MAX_SYMBOL_VALUE 255
883
884
885
/* **************************************************************
886
*  template functions type & suffix
887
****************************************************************/
888
459k
#define FSEv07_FUNCTION_TYPE BYTE
889
#define FSEv07_FUNCTION_EXTENSION
890
4.33k
#define FSEv07_DECODE_TYPE FSEv07_decode_t
891
892
893
#endif   /* !FSEv07_COMMONDEFS_ONLY */
894
895
896
/* ***************************************************************
897
*  Constants
898
*****************************************************************/
899
10.0k
#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.19k
#define FSEv07_MIN_TABLELOG 5
904
905
1.19k
#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
4.33k
#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
14.6k
#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
322
#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
220
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
732
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
14.2k
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
1.21k
{
1155
1.21k
    const BYTE* const istart = (const BYTE*) headerBuffer;
1156
1.21k
    const BYTE* const iend = istart + hbSize;
1157
1.21k
    const BYTE* ip = istart;
1158
1.21k
    int nbBits;
1159
1.21k
    int remaining;
1160
1.21k
    int threshold;
1161
1.21k
    U32 bitStream;
1162
1.21k
    int bitCount;
1163
1.21k
    unsigned charnum = 0;
1164
1.21k
    int previous0 = 0;
1165
1166
1.21k
    if (hbSize < 4) return ERROR(srcSize_wrong);
1167
1.19k
    bitStream = MEM_readLE32(ip);
1168
1.19k
    nbBits = (bitStream & 0xF) + FSEv07_MIN_TABLELOG;   /* extract tableLog */
1169
1.19k
    if (nbBits > FSEv07_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1170
1.18k
    bitStream >>= 4;
1171
1.18k
    bitCount = 4;
1172
1.18k
    *tableLogPtr = nbBits;
1173
1.18k
    remaining = (1<<nbBits)+1;
1174
1.18k
    threshold = 1<<nbBits;
1175
1.18k
    nbBits++;
1176
1177
15.4k
    while ((remaining>1) && (charnum<=*maxSVPtr)) {
1178
14.2k
        if (previous0) {
1179
2.20k
            unsigned n0 = charnum;
1180
2.46k
            while ((bitStream & 0xFFFF) == 0xFFFF) {
1181
267
                n0+=24;
1182
267
                if (ip < iend-5) {
1183
248
                    ip+=2;
1184
248
                    bitStream = MEM_readLE32(ip) >> bitCount;
1185
248
                } else {
1186
19
                    bitStream >>= 16;
1187
19
                    bitCount+=16;
1188
19
            }   }
1189
2.93k
            while ((bitStream & 3) == 3) {
1190
731
                n0+=3;
1191
731
                bitStream>>=2;
1192
731
                bitCount+=2;
1193
731
            }
1194
2.20k
            n0 += bitStream & 3;
1195
2.20k
            bitCount += 2;
1196
2.20k
            if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1197
6.63k
            while (charnum < n0) normalizedCounter[charnum++] = 0;
1198
2.18k
            if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1199
1.08k
                ip += bitCount>>3;
1200
1.08k
                bitCount &= 7;
1201
1.08k
                bitStream = MEM_readLE32(ip) >> bitCount;
1202
1.08k
            }
1203
1.09k
            else
1204
1.09k
                bitStream >>= 2;
1205
2.18k
        }
1206
14.2k
        {   short const max = (short)((2*threshold-1)-remaining);
1207
14.2k
            short count;
1208
1209
14.2k
            if ((bitStream & (threshold-1)) < (U32)max) {
1210
9.95k
                count = (short)(bitStream & (threshold-1));
1211
9.95k
                bitCount   += nbBits-1;
1212
9.95k
            } else {
1213
4.27k
                count = (short)(bitStream & (2*threshold-1));
1214
4.27k
                if (count >= threshold) count -= max;
1215
4.27k
                bitCount   += nbBits;
1216
4.27k
            }
1217
1218
14.2k
            count--;   /* extra accuracy */
1219
14.2k
            remaining -= FSEv07_abs(count);
1220
14.2k
            normalizedCounter[charnum++] = count;
1221
14.2k
            previous0 = !count;
1222
22.1k
            while (remaining < threshold) {
1223
7.88k
                nbBits--;
1224
7.88k
                threshold >>= 1;
1225
7.88k
            }
1226
1227
14.2k
            if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1228
10.2k
                ip += bitCount>>3;
1229
10.2k
                bitCount &= 7;
1230
10.2k
            } else {
1231
3.97k
                bitCount -= (int)(8 * (iend - 4 - ip));
1232
3.97k
                ip = iend - 4;
1233
3.97k
            }
1234
14.2k
            bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1235
14.2k
    }   }   /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1236
1.16k
    if (remaining != 1) return ERROR(GENERIC);
1237
1.13k
    *maxSVPtr = charnum-1;
1238
1239
1.13k
    ip += (bitCount+7)>>3;
1240
1.13k
    if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1241
1.10k
    return ip-istart;
1242
1.13k
}
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
322
{
1255
322
    U32 weightTotal;
1256
322
    const BYTE* ip = (const BYTE*) src;
1257
322
    size_t iSize;
1258
322
    size_t oSize;
1259
1260
322
    if (!srcSize) return ERROR(srcSize_wrong);
1261
320
    iSize = ip[0];
1262
    /* memset(huffWeight, 0, hwSize); */   /* is not necessary, even though some analyzer complain ... */
1263
1264
320
    if (iSize >= 128)  { /* special header */
1265
97
        if (iSize >= (242)) {  /* RLE */
1266
75
            static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1267
75
            oSize = l[iSize-242];
1268
75
            memset(huffWeight, 1, hwSize);
1269
75
            iSize = 0;
1270
75
        }
1271
22
        else {   /* Incompressible */
1272
22
            oSize = iSize - 127;
1273
22
            iSize = ((oSize+1)/2);
1274
22
            if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1275
17
            if (oSize >= hwSize) return ERROR(corruption_detected);
1276
17
            ip += 1;
1277
17
            {   U32 n;
1278
275
                for (n=0; n<oSize; n+=2) {
1279
258
                    huffWeight[n]   = ip[n/2] >> 4;
1280
258
                    huffWeight[n+1] = ip[n/2] & 15;
1281
258
    }   }   }   }
1282
223
    else  {   /* header compressed with FSE (normal case) */
1283
223
        if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1284
220
        oSize = FSEv07_decompress(huffWeight, hwSize-1, ip+1, iSize);   /* max (hwSize-1) values decoded, as last one is implied */
1285
220
        if (FSEv07_isError(oSize)) return oSize;
1286
220
    }
1287
1288
    /* collect weight stats */
1289
244
    memset(rankStats, 0, (HUFv07_TABLELOG_ABSOLUTEMAX + 1) * sizeof(U32));
1290
244
    weightTotal = 0;
1291
14.3k
    {   U32 n; for (n=0; n<oSize; n++) {
1292
14.1k
            if (huffWeight[n] >= HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1293
14.1k
            rankStats[huffWeight[n]]++;
1294
14.1k
            weightTotal += (1 << huffWeight[n]) >> 1;
1295
14.1k
    }   }
1296
223
    if (weightTotal == 0) return ERROR(corruption_detected);
1297
1298
    /* get last non-null symbol weight (implied, total must be 2^n) */
1299
220
    {   U32 const tableLog = BITv07_highbit32(weightTotal) + 1;
1300
220
        if (tableLog > HUFv07_TABLELOG_ABSOLUTEMAX) return ERROR(corruption_detected);
1301
213
        *tableLogPtr = tableLog;
1302
        /* determine last weight */
1303
213
        {   U32 const total = 1 << tableLog;
1304
213
            U32 const rest = total - weightTotal;
1305
213
            U32 const verif = 1 << BITv07_highbit32(rest);
1306
213
            U32 const lastWeight = BITv07_highbit32(rest) + 1;
1307
213
            if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
1308
135
            huffWeight[oSize] = (BYTE)lastWeight;
1309
135
            rankStats[lastWeight]++;
1310
135
    }   }
1311
1312
    /* check tree construction validity */
1313
135
    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
126
    *nbSymbolsPtr = (U32)(oSize+1);
1317
126
    return iSize+1;
1318
135
}
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
577
#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
4.33k
{
1425
4.33k
    void* const tdPtr = dt+1;   /* because *dt is unsigned, 32-bits aligned on 32-bits */
1426
4.33k
    FSEv07_DECODE_TYPE* const tableDecode = (FSEv07_DECODE_TYPE*) (tdPtr);
1427
4.33k
    U16 symbolNext[FSEv07_MAX_SYMBOL_VALUE+1];
1428
1429
4.33k
    U32 const maxSV1 = maxSymbolValue + 1;
1430
4.33k
    U32 const tableSize = 1 << tableLog;
1431
4.33k
    U32 highThreshold = tableSize-1;
1432
1433
    /* Sanity Checks */
1434
4.33k
    if (maxSymbolValue > FSEv07_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1435
4.33k
    if (tableLog > FSEv07_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1436
1437
    /* Init, lay down lowprob symbols */
1438
4.33k
    {   FSEv07_DTableHeader DTableH;
1439
4.33k
        DTableH.tableLog = (U16)tableLog;
1440
4.33k
        DTableH.fastMode = 1;
1441
4.33k
        {   S16 const largeLimit= (S16)(1 << (tableLog-1));
1442
4.33k
            U32 s;
1443
151k
            for (s=0; s<maxSV1; s++) {
1444
147k
                if (normalizedCounter[s]==-1) {
1445
21.3k
                    tableDecode[highThreshold--].symbol = (FSEv07_FUNCTION_TYPE)s;
1446
21.3k
                    symbolNext[s] = 1;
1447
125k
                } else {
1448
125k
                    if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1449
125k
                    symbolNext[s] = normalizedCounter[s];
1450
125k
        }   }   }
1451
4.33k
        memcpy(dt, &DTableH, sizeof(DTableH));
1452
4.33k
    }
1453
1454
    /* Spread symbols */
1455
4.33k
    {   U32 const tableMask = tableSize-1;
1456
4.33k
        U32 const step = FSEv07_TABLESTEP(tableSize);
1457
4.33k
        U32 s, position = 0;
1458
151k
        for (s=0; s<maxSV1; s++) {
1459
147k
            int i;
1460
585k
            for (i=0; i<normalizedCounter[s]; i++) {
1461
437k
                tableDecode[position].symbol = (FSEv07_FUNCTION_TYPE)s;
1462
437k
                position = (position + step) & tableMask;
1463
459k
                while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
1464
437k
        }   }
1465
1466
4.33k
        if (position!=0) return ERROR(GENERIC);   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1467
4.33k
    }
1468
1469
    /* Build Decoding table */
1470
4.33k
    {   U32 u;
1471
463k
        for (u=0; u<tableSize; u++) {
1472
459k
            FSEv07_FUNCTION_TYPE const symbol = (FSEv07_FUNCTION_TYPE)(tableDecode[u].symbol);
1473
459k
            U16 nextState = symbolNext[symbol]++;
1474
459k
            tableDecode[u].nbBits = (BYTE) (tableLog - BITv07_highbit32 ((U32)nextState) );
1475
459k
            tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1476
459k
    }   }
1477
1478
4.33k
    return 0;
1479
4.33k
}
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.05k
{
1490
1.05k
    void* ptr = dt;
1491
1.05k
    FSEv07_DTableHeader* const DTableH = (FSEv07_DTableHeader*)ptr;
1492
1.05k
    void* dPtr = dt + 1;
1493
1.05k
    FSEv07_decode_t* const cell = (FSEv07_decode_t*)dPtr;
1494
1495
1.05k
    DTableH->tableLog = 0;
1496
1.05k
    DTableH->fastMode = 0;
1497
1498
1.05k
    cell->newState = 0;
1499
1.05k
    cell->symbol = symbolValue;
1500
1.05k
    cell->nbBits = 0;
1501
1502
1.05k
    return 0;
1503
1.05k
}
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
179
{
1537
179
    BYTE* const ostart = (BYTE*) dst;
1538
179
    BYTE* op = ostart;
1539
179
    BYTE* const omax = op + maxDstSize;
1540
179
    BYTE* const olimit = omax-3;
1541
1542
179
    BITv07_DStream_t bitD;
1543
179
    FSEv07_DState_t state1;
1544
179
    FSEv07_DState_t state2;
1545
1546
    /* Init */
1547
179
    { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);   /* replaced last arg by maxCompressed Size */
1548
179
      if (FSEv07_isError(errorCode)) return errorCode; }
1549
1550
168
    FSEv07_initDState(&state1, &bitD, dt);
1551
168
    FSEv07_initDState(&state2, &bitD, dt);
1552
1553
11.1k
#define FSEv07_GETSYMBOL(statePtr) fast ? FSEv07_decodeSymbolFast(statePtr, &bitD) : FSEv07_decodeSymbol(statePtr, &bitD)
1554
1555
    /* 4 symbols per loop */
1556
2.07k
    for ( ; (BITv07_reloadDStream(&bitD)==BITv07_DStream_unfinished) && (op<olimit) ; op+=4) {
1557
1.91k
        op[0] = FSEv07_GETSYMBOL(&state1);
1558
1559
1.91k
        if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1560
0
            BITv07_reloadDStream(&bitD);
1561
1562
1.91k
        op[1] = FSEv07_GETSYMBOL(&state2);
1563
1564
1.91k
        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
1.91k
        op[2] = FSEv07_GETSYMBOL(&state1);
1568
1569
1.91k
        if (FSEv07_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1570
0
            BITv07_reloadDStream(&bitD);
1571
1572
1.91k
        op[3] = FSEv07_GETSYMBOL(&state2);
1573
1.91k
    }
1574
1575
    /* tail */
1576
    /* note : BITv07_reloadDStream(&bitD) >= FSEv07_DStream_partiallyFilled; Ends at exactly BITv07_DStream_completed */
1577
1.72k
    while (1) {
1578
1.72k
        if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1579
1580
1.70k
        *op++ = FSEv07_GETSYMBOL(&state1);
1581
1582
1.70k
        if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1583
68
            *op++ = FSEv07_GETSYMBOL(&state2);
1584
68
            break;
1585
68
        }
1586
1587
1.64k
        if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1588
1589
1.64k
        *op++ = FSEv07_GETSYMBOL(&state2);
1590
1591
1.64k
        if (BITv07_reloadDStream(&bitD)==BITv07_DStream_overflow) {
1592
84
            *op++ = FSEv07_GETSYMBOL(&state1);
1593
84
            break;
1594
84
    }   }
1595
1596
152
    return op-ostart;
1597
168
}
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
179
{
1604
179
    const void* ptr = dt;
1605
179
    const FSEv07_DTableHeader* DTableH = (const FSEv07_DTableHeader*)ptr;
1606
179
    const U32 fastMode = DTableH->fastMode;
1607
1608
    /* select fast mode (static) */
1609
179
    if (fastMode) return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1610
102
    return FSEv07_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1611
179
}
1612
1613
1614
size_t FSEv07_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1615
220
{
1616
220
    const BYTE* const istart = (const BYTE*)cSrc;
1617
220
    const BYTE* ip = istart;
1618
220
    short counting[FSEv07_MAX_SYMBOL_VALUE+1];
1619
220
    DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
1620
220
    unsigned tableLog;
1621
220
    unsigned maxSymbolValue = FSEv07_MAX_SYMBOL_VALUE;
1622
1623
220
    if (cSrcSize<2) return ERROR(srcSize_wrong);   /* too small input size */
1624
1625
    /* normal FSE decoding mode */
1626
215
    {   size_t const NCountLength = FSEv07_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1627
215
        if (FSEv07_isError(NCountLength)) return NCountLength;
1628
186
        if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong);   /* too small input size */
1629
183
        ip += NCountLength;
1630
183
        cSrcSize -= NCountLength;
1631
183
    }
1632
1633
0
    { size_t const errorCode = FSEv07_buildDTable (dt, counting, maxSymbolValue, tableLog);
1634
183
      if (FSEv07_isError(errorCode)) return errorCode; }
1635
1636
179
    return FSEv07_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);   /* always return, even if it is an error code */
1637
183
}
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
322
#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
232
{
1709
232
    DTableDesc dtd;
1710
232
    memcpy(&dtd, table, sizeof(dtd));
1711
232
    return dtd;
1712
232
}
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
322
{
1723
322
    BYTE huffWeight[HUFv07_SYMBOLVALUE_MAX + 1];
1724
322
    U32 rankVal[HUFv07_TABLELOG_ABSOLUTEMAX + 1];   /* large enough for values from 0 to 16 */
1725
322
    U32 tableLog = 0;
1726
322
    U32 nbSymbols = 0;
1727
322
    size_t iSize;
1728
322
    void* const dtPtr = DTable + 1;
1729
322
    HUFv07_DEltX2* const dt = (HUFv07_DEltX2*)dtPtr;
1730
1731
322
    HUFv07_STATIC_ASSERT(sizeof(DTableDesc) == sizeof(HUFv07_DTable));
1732
    /* memset(huffWeight, 0, sizeof(huffWeight)); */   /* is not necessary, even though some analyzer complain ... */
1733
1734
322
    iSize = HUFv07_readStats(huffWeight, HUFv07_SYMBOLVALUE_MAX + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1735
322
    if (HUFv07_isError(iSize)) return iSize;
1736
1737
    /* Table header */
1738
126
    {   DTableDesc dtd = HUFv07_getDTableDesc(DTable);
1739
126
        if (tableLog > (U32)(dtd.maxTableLog+1)) return ERROR(tableLog_tooLarge);   /* DTable too small, huffman tree cannot fit in */
1740
126
        dtd.tableType = 0;
1741
126
        dtd.tableLog = (BYTE)tableLog;
1742
126
        memcpy(DTable, &dtd, sizeof(dtd));
1743
126
    }
1744
1745
    /* Prepare ranks */
1746
0
    {   U32 n, nextRankStart = 0;
1747
879
        for (n=1; n<tableLog+1; n++) {
1748
753
            U32 current = nextRankStart;
1749
753
            nextRankStart += (rankVal[n] << (n-1));
1750
753
            rankVal[n] = current;
1751
753
    }   }
1752
1753
    /* fill DTable */
1754
126
    {   U32 n;
1755
9.86k
        for (n=0; n<nbSymbols; n++) {
1756
9.73k
            U32 const w = huffWeight[n];
1757
9.73k
            U32 const length = (1 << w) >> 1;
1758
9.73k
            U32 i;
1759
9.73k
            HUFv07_DEltX2 D;
1760
9.73k
            D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1761
37.2k
            for (i = rankVal[w]; i < rankVal[w] + length; i++)
1762
27.5k
                dt[i] = D;
1763
9.73k
            rankVal[w] += length;
1764
9.73k
    }   }
1765
1766
126
    return iSize;
1767
126
}
1768
1769
1770
static BYTE HUFv07_decodeSymbolX2(BITv07_DStream_t* Dstream, const HUFv07_DEltX2* dt, const U32 dtLog)
1771
17.7k
{
1772
17.7k
    size_t const val = BITv07_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1773
17.7k
    BYTE const c = dt[val].byte;
1774
17.7k
    BITv07_skipBits(Dstream, dt[val].nbBits);
1775
17.7k
    return c;
1776
17.7k
}
1777
1778
#define HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1779
17.7k
    *ptr++ = HUFv07_decodeSymbolX2(DStreamPtr, dt, dtLog)
1780
1781
#define HUFv07_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1782
1.31k
    if (MEM_64bits() || (HUFv07_TABLELOG_MAX<=12)) \
1783
1.31k
        HUFv07_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1784
1785
#define HUFv07_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1786
2.63k
    if (MEM_64bits()) \
1787
2.63k
        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
50
{
1791
50
    BYTE* const pStart = p;
1792
1793
    /* up to 4 symbols at a time */
1794
1.36k
    while ((BITv07_reloadDStream(bitDPtr) == BITv07_DStream_unfinished) && (p <= pEnd-4)) {
1795
1.31k
        HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1796
1.31k
        HUFv07_DECODE_SYMBOLX2_1(p, bitDPtr);
1797
1.31k
        HUFv07_DECODE_SYMBOLX2_2(p, bitDPtr);
1798
1.31k
        HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1799
1.31k
    }
1800
1801
    /* closer to the end */
1802
62
    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
12.5k
    while (p < pEnd)
1807
12.4k
        HUFv07_DECODE_SYMBOLX2_0(p, bitDPtr);
1808
1809
50
    return pEnd-pStart;
1810
50
}
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
52
{
1817
52
    BYTE* op = (BYTE*)dst;
1818
52
    BYTE* const oend = op + dstSize;
1819
52
    const void* dtPtr = DTable + 1;
1820
52
    const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1821
52
    BITv07_DStream_t bitD;
1822
52
    DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1823
52
    U32 const dtLog = dtd.tableLog;
1824
1825
52
    { size_t const errorCode = BITv07_initDStream(&bitD, cSrc, cSrcSize);
1826
52
      if (HUFv07_isError(errorCode)) return errorCode; }
1827
1828
46
    HUFv07_decodeStreamX2(op, &bitD, oend, dt, dtLog);
1829
1830
    /* check */
1831
46
    if (!BITv07_endOfDStream(&bitD)) return ERROR(corruption_detected);
1832
1833
3
    return dstSize;
1834
46
}
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
71
{
1848
71
    const BYTE* ip = (const BYTE*) cSrc;
1849
1850
71
    size_t const hSize = HUFv07_readDTableX2 (DCtx, cSrc, cSrcSize);
1851
71
    if (HUFv07_isError(hSize)) return hSize;
1852
53
    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1853
52
    ip += hSize; cSrcSize -= hSize;
1854
1855
52
    return HUFv07_decompress1X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, DCtx);
1856
53
}
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
72
{
1870
    /* Check */
1871
72
    if (cSrcSize < 10) return ERROR(corruption_detected);  /* strict minimum : jump table + 1 byte per stream */
1872
1873
54
    {   const BYTE* const istart = (const BYTE*) cSrc;
1874
54
        BYTE* const ostart = (BYTE*) dst;
1875
54
        BYTE* const oend = ostart + dstSize;
1876
54
        const void* const dtPtr = DTable + 1;
1877
54
        const HUFv07_DEltX2* const dt = (const HUFv07_DEltX2*)dtPtr;
1878
1879
        /* Init */
1880
54
        BITv07_DStream_t bitD1;
1881
54
        BITv07_DStream_t bitD2;
1882
54
        BITv07_DStream_t bitD3;
1883
54
        BITv07_DStream_t bitD4;
1884
54
        size_t const length1 = MEM_readLE16(istart);
1885
54
        size_t const length2 = MEM_readLE16(istart+2);
1886
54
        size_t const length3 = MEM_readLE16(istart+4);
1887
54
        size_t const length4 = cSrcSize - (length1 + length2 + length3 + 6);
1888
54
        const BYTE* const istart1 = istart + 6;  /* jumpTable */
1889
54
        const BYTE* const istart2 = istart1 + length1;
1890
54
        const BYTE* const istart3 = istart2 + length2;
1891
54
        const BYTE* const istart4 = istart3 + length3;
1892
54
        const size_t segmentSize = (dstSize+3) / 4;
1893
54
        BYTE* const opStart2 = ostart + segmentSize;
1894
54
        BYTE* const opStart3 = opStart2 + segmentSize;
1895
54
        BYTE* const opStart4 = opStart3 + segmentSize;
1896
54
        BYTE* op1 = ostart;
1897
54
        BYTE* op2 = opStart2;
1898
54
        BYTE* op3 = opStart3;
1899
54
        BYTE* op4 = opStart4;
1900
54
        U32 endSignal;
1901
54
        DTableDesc const dtd = HUFv07_getDTableDesc(DTable);
1902
54
        U32 const dtLog = dtd.tableLog;
1903
1904
54
        if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
1905
18
        { size_t const errorCode = BITv07_initDStream(&bitD1, istart1, length1);
1906
18
          if (HUFv07_isError(errorCode)) return errorCode; }
1907
11
        { size_t const errorCode = BITv07_initDStream(&bitD2, istart2, length2);
1908
11
          if (HUFv07_isError(errorCode)) return errorCode; }
1909
5
        { size_t const errorCode = BITv07_initDStream(&bitD3, istart3, length3);
1910
5
          if (HUFv07_isError(errorCode)) return errorCode; }
1911
2
        { size_t const errorCode = BITv07_initDStream(&bitD4, istart4, length4);
1912
2
          if (HUFv07_isError(errorCode)) return errorCode; }
1913
1914
        /* 16-32 symbols per loop (4-8 symbols per stream) */
1915
1
        endSignal = BITv07_reloadDStream(&bitD1) | BITv07_reloadDStream(&bitD2) | BITv07_reloadDStream(&bitD3) | BITv07_reloadDStream(&bitD4);
1916
1
        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
1
        if (op1 > opStart2) return ERROR(corruption_detected);
1938
1
        if (op2 > opStart3) return ERROR(corruption_detected);
1939
1
        if (op3 > opStart4) return ERROR(corruption_detected);
1940
        /* note : op4 supposed already verified within main loop */
1941
1942
        /* finish bitStreams one by one */
1943
1
        HUFv07_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1944
1
        HUFv07_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1945
1
        HUFv07_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1946
1
        HUFv07_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
1947
1948
        /* check */
1949
1
        endSignal = BITv07_endOfDStream(&bitD1) & BITv07_endOfDStream(&bitD2) & BITv07_endOfDStream(&bitD3) & BITv07_endOfDStream(&bitD4);
1950
1
        if (!endSignal) return ERROR(corruption_detected);
1951
1952
        /* decoded size */
1953
0
        return dstSize;
1954
1
    }
1955
1
}
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
251
{
1971
251
    const BYTE* ip = (const BYTE*) cSrc;
1972
1973
251
    size_t const hSize = HUFv07_readDTableX2 (dctx, cSrc, cSrcSize);
1974
251
    if (HUFv07_isError(hSize)) return hSize;
1975
73
    if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
1976
72
    ip += hSize; cSrcSize -= hSize;
1977
1978
72
    return HUFv07_decompress4X2_usingDTable_internal (dst, dstSize, ip, cSrcSize, dctx);
1979
73
}
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
251
{
2451
    /* decoder timing evaluation */
2452
251
    U32 const Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
2453
251
    U32 const D256 = (U32)(dstSize >> 8);
2454
251
    U32 const DTime0 = algoTime[Q][0].tableTime + (algoTime[Q][0].decode256Time * D256);
2455
251
    U32 DTime1 = algoTime[Q][1].tableTime + (algoTime[Q][1].decode256Time * D256);
2456
251
    DTime1 += DTime1 >> 3;  /* advantage to algorithm using less memory, for cache eviction */
2457
2458
251
    return DTime1 < DTime0;
2459
251
}
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
273
{
2498
    /* validation checks */
2499
273
    if (dstSize == 0) return ERROR(dstSize_tooSmall);
2500
269
    if ((cSrcSize >= dstSize) || (cSrcSize <= 1)) return ERROR(corruption_detected);   /* invalid */
2501
2502
251
    {   U32 const algoNb = HUFv07_selectDecoder(dstSize, cSrcSize);
2503
251
        return algoNb ? HUFv07_decompress4X4_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) :
2504
251
                        HUFv07_decompress4X2_DCtx(dctx, dst, dstSize, cSrc, cSrcSize) ;
2505
269
    }
2506
269
}
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
6.10k
{
2578
6.10k
    void* address = malloc(size);
2579
6.10k
    (void)opaque;
2580
    /* printf("alloc %p, %d opaque=%p \n", address, (int)size, opaque); */
2581
6.10k
    return address;
2582
6.10k
}
2583
2584
static void ZSTDv07_defaultFreeFunction(void* opaque, void* address)
2585
7.39k
{
2586
7.39k
    (void)opaque;
2587
    /* if (address) printf("free %p opaque=%p \n", address, opaque); */
2588
7.39k
    free(address);
2589
7.39k
}
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
803
#define MIN(a,b) ((a)<(b) ? (a) : (b))
2629
705
#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
40.8k
#define ZSTDv07_REP_NUM    3
2639
7.66k
#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
4.31k
#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
5.03k
#define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
2663
2.75k
#define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
2664
2665
8.28k
#define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
2666
typedef enum { lbt_huffman, lbt_repeat, lbt_raw, lbt_rle } litBlockType_t;
2667
2668
177
#define LONGNBSEQ 0x7F00
2669
2670
11.7k
#define MINMATCH 3
2671
#define EQUAL_READ32 4
2672
2673
#define Litbits  8
2674
#define MaxLit ((1<<Litbits) - 1)
2675
1.72k
#define MaxML  52
2676
1.82k
#define MaxLL  35
2677
1.78k
#define MaxOff 28
2678
#define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
2679
14.8k
#define MLFSELog    9
2680
14.9k
#define LLFSELog    9
2681
14.8k
#define OffFSELog   8
2682
2683
3.26k
#define FSEv07_ENCODING_RAW     0
2684
1.06k
#define FSEv07_ENCODING_RLE     1
2685
10
#define FSEv07_ENCODING_STATIC  2
2686
998
#define FSEv07_ENCODING_DYNAMIC 3
2687
2688
36
#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.06M
static void ZSTDv07_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2717
1.06M
#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
29.3k
#define WILDCOPY_OVERLENGTH 8
2722
MEM_STATIC void ZSTDv07_wildcopy(void* dst, const void* src, ptrdiff_t length)
2723
23.5k
{
2724
23.5k
    const BYTE* ip = (const BYTE*)src;
2725
23.5k
    BYTE* op = (BYTE*)dst;
2726
23.5k
    BYTE* const oend = op + length;
2727
23.5k
    do
2728
1.06M
        COPY8(op, ip)
2729
1.06M
    while (op < oend);
2730
23.5k
}
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
73.0k
#define ZSTDv07_isError ERR_isError   /* for inlining */
2857
998
#define FSEv07_isError  ERR_isError
2858
344
#define HUFv07_isError  ERR_isError
2859
2860
2861
/*_*******************************************************
2862
*  Memory operations
2863
**********************************************************/
2864
9.02k
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
8.28k
{
2909
8.28k
    dctx->expected = ZSTDv07_frameHeaderSize_min;
2910
8.28k
    dctx->stage = ZSTDds_getFrameHeaderSize;
2911
8.28k
    dctx->previousDstEnd = NULL;
2912
8.28k
    dctx->base = NULL;
2913
8.28k
    dctx->vBase = NULL;
2914
8.28k
    dctx->dictEnd = NULL;
2915
8.28k
    dctx->hufTable[0] = (HUFv07_DTable)((ZSTD_HUFFDTABLE_CAPACITY_LOG)*0x1000001);
2916
8.28k
    dctx->litEntropy = dctx->fseEntropy = 0;
2917
8.28k
    dctx->dictID = 0;
2918
33.1k
    { int i; for (i=0; i<ZSTDv07_REP_NUM; i++) dctx->rep[i] = repStartValue[i]; }
2919
8.28k
    return 0;
2920
8.28k
}
2921
2922
ZSTDv07_DCtx* ZSTDv07_createDCtx_advanced(ZSTDv07_customMem customMem)
2923
4.11k
{
2924
4.11k
    ZSTDv07_DCtx* dctx;
2925
2926
4.11k
    if (!customMem.customAlloc && !customMem.customFree)
2927
0
        customMem = defaultCustomMem;
2928
2929
4.11k
    if (!customMem.customAlloc || !customMem.customFree)
2930
0
        return NULL;
2931
2932
4.11k
    dctx = (ZSTDv07_DCtx*) customMem.customAlloc(customMem.opaque, sizeof(ZSTDv07_DCtx));
2933
4.11k
    if (!dctx) return NULL;
2934
4.11k
    memcpy(&dctx->customMem, &customMem, sizeof(ZSTDv07_customMem));
2935
4.11k
    ZSTDv07_decompressBegin(dctx);
2936
4.11k
    return dctx;
2937
4.11k
}
2938
2939
ZSTDv07_DCtx* ZSTDv07_createDCtx(void)
2940
3.40k
{
2941
3.40k
    return ZSTDv07_createDCtx_advanced(defaultCustomMem);
2942
3.40k
}
2943
2944
size_t ZSTDv07_freeDCtx(ZSTDv07_DCtx* dctx)
2945
4.11k
{
2946
4.11k
    if (dctx==NULL) return 0;   /* support free on NULL */
2947
4.11k
    dctx->customMem.customFree(dctx->customMem.opaque, dctx);
2948
4.11k
    return 0;   /* reserved as a potential error code in the future */
2949
4.11k
}
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
13.5k
{
3079
13.5k
    if (srcSize < ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);
3080
13.5k
    {   BYTE const fhd = ((const BYTE*)src)[4];
3081
13.5k
        U32 const dictID= fhd & 3;
3082
13.5k
        U32 const directMode = (fhd >> 5) & 1;
3083
13.5k
        U32 const fcsId = fhd >> 6;
3084
13.5k
        return ZSTDv07_frameHeaderSize_min + !directMode + ZSTDv07_did_fieldSize[dictID] + ZSTDv07_fcs_fieldSize[fcsId]
3085
13.5k
                + (directMode && !ZSTDv07_fcs_fieldSize[fcsId]);
3086
13.5k
    }
3087
13.5k
}
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
6.74k
{
3097
6.74k
    const BYTE* ip = (const BYTE*)src;
3098
3099
6.74k
    if (srcSize < ZSTDv07_frameHeaderSize_min) return ZSTDv07_frameHeaderSize_min;
3100
5.97k
    memset(fparamsPtr, 0, sizeof(*fparamsPtr));
3101
5.97k
    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
5.97k
    { size_t const fhsize = ZSTDv07_frameHeaderSize(src, srcSize);
3113
5.97k
      if (srcSize < fhsize) return fhsize; }
3114
3115
5.21k
    {   BYTE const fhdByte = ip[4];
3116
5.21k
        size_t pos = 5;
3117
5.21k
        U32 const dictIDSizeCode = fhdByte&3;
3118
5.21k
        U32 const checksumFlag = (fhdByte>>2)&1;
3119
5.21k
        U32 const directMode = (fhdByte>>5)&1;
3120
5.21k
        U32 const fcsID = fhdByte>>6;
3121
5.21k
        U32 const windowSizeMax = 1U << ZSTDv07_WINDOWLOG_MAX;
3122
5.21k
        U32 windowSize = 0;
3123
5.21k
        U32 dictID = 0;
3124
5.21k
        U64 frameContentSize = 0;
3125
5.21k
        if ((fhdByte & 0x08) != 0)   /* reserved bits, which must be zero */
3126
3
            return ERROR(frameParameter_unsupported);
3127
5.20k
        if (!directMode) {
3128
4.31k
            BYTE const wlByte = ip[pos++];
3129
4.31k
            U32 const windowLog = (wlByte >> 3) + ZSTDv07_WINDOWLOG_ABSOLUTEMIN;
3130
4.31k
            if (windowLog > ZSTDv07_WINDOWLOG_MAX)
3131
3
                return ERROR(frameParameter_unsupported);
3132
4.30k
            windowSize = (1U << windowLog);
3133
4.30k
            windowSize += (windowSize >> 3) * (wlByte&7);
3134
4.30k
        }
3135
3136
5.20k
        switch(dictIDSizeCode)
3137
5.20k
        {
3138
0
            default:   /* impossible */
3139
4.61k
            case 0 : break;
3140
169
            case 1 : dictID = ip[pos]; pos++; break;
3141
245
            case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
3142
172
            case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
3143
5.20k
        }
3144
5.20k
        switch(fcsID)
3145
5.20k
        {
3146
0
            default:   /* impossible */
3147
4.54k
            case 0 : if (directMode) frameContentSize = ip[pos]; break;
3148
339
            case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
3149
169
            case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
3150
152
            case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
3151
5.20k
        }
3152
5.20k
        if (!windowSize) windowSize = (U32)frameContentSize;
3153
5.20k
        if (windowSize > windowSizeMax)
3154
29
            return ERROR(frameParameter_unsupported);
3155
5.17k
        fparamsPtr->frameContentSize = frameContentSize;
3156
5.17k
        fparamsPtr->windowSize = windowSize;
3157
5.17k
        fparamsPtr->dictID = dictID;
3158
5.17k
        fparamsPtr->checksumFlag = checksumFlag;
3159
5.17k
    }
3160
0
    return 0;
3161
5.20k
}
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
4.14k
{
3185
4.14k
    size_t const result = ZSTDv07_getFrameParams(&(dctx->fParams), src, srcSize);
3186
4.14k
    if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID)) return ERROR(dictionary_wrong);
3187
4.07k
    if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
3188
4.07k
    return result;
3189
4.14k
}
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
25.7k
{
3202
25.7k
    const BYTE* const in = (const BYTE*)src;
3203
25.7k
    U32 cSize;
3204
3205
25.7k
    if (srcSize < ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3206
3207
25.7k
    bpPtr->blockType = (blockType_t)((*in) >> 6);
3208
25.7k
    cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
3209
25.7k
    bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
3210
3211
25.7k
    if (bpPtr->blockType == bt_end) return 0;
3212
21.9k
    if (bpPtr->blockType == bt_rle) return 1;
3213
6.79k
    return cSize;
3214
21.9k
}
3215
3216
3217
static size_t ZSTDv07_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3218
328
{
3219
328
    if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
3220
298
    if (srcSize > 0) {
3221
254
        memcpy(dst, src, srcSize);
3222
254
    }
3223
298
    return srcSize;
3224
328
}
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
2.75k
{
3232
2.75k
    const BYTE* const istart = (const BYTE*) src;
3233
3234
2.75k
    if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3235
3236
2.74k
    switch((litBlockType_t)(istart[0]>> 6))
3237
2.74k
    {
3238
393
    case lbt_huffman:
3239
393
        {   size_t litSize, litCSize, singleStream=0;
3240
393
            U32 lhSize = (istart[0] >> 4) & 3;
3241
393
            if (srcSize < 5) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3242
388
            switch(lhSize)
3243
388
            {
3244
337
            case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3245
                /* 2 - 2 - 10 - 10 */
3246
337
                lhSize=3;
3247
337
                singleStream = istart[0] & 16;
3248
337
                litSize  = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3249
337
                litCSize = ((istart[1] &  3) << 8) + istart[2];
3250
337
                break;
3251
16
            case 2:
3252
                /* 2 - 2 - 14 - 14 */
3253
16
                lhSize=4;
3254
16
                litSize  = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3255
16
                litCSize = ((istart[2] & 63) <<  8) + istart[3];
3256
16
                break;
3257
35
            case 3:
3258
                /* 2 - 2 - 18 - 18 */
3259
35
                lhSize=5;
3260
35
                litSize  = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3261
35
                litCSize = ((istart[2] &  3) << 16) + (istart[3] << 8) + istart[4];
3262
35
                break;
3263
388
            }
3264
388
            if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3265
384
            if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3266
3267
344
            if (HUFv07_isError(singleStream ?
3268
71
                            HUFv07_decompress1X2_DCtx(dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3269
344
                            HUFv07_decompress4X_hufOnly (dctx->hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3270
341
                return ERROR(corruption_detected);
3271
3272
3
            dctx->litPtr = dctx->litBuffer;
3273
3
            dctx->litSize = litSize;
3274
3
            dctx->litEntropy = 1;
3275
3
            memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3276
3
            return litCSize + lhSize;
3277
344
        }
3278
8
    case lbt_repeat:
3279
8
        {   size_t litSize, litCSize;
3280
8
            U32 lhSize = ((istart[0]) >> 4) & 3;
3281
8
            if (lhSize != 1)  /* only case supported for now : small litSize, single stream */
3282
5
                return ERROR(corruption_detected);
3283
3
            if (dctx->litEntropy==0)
3284
3
                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.01k
    case lbt_raw:
3301
1.01k
        {   size_t litSize;
3302
1.01k
            U32 lhSize = ((istart[0]) >> 4) & 3;
3303
1.01k
            switch(lhSize)
3304
1.01k
            {
3305
605
            case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3306
605
                lhSize=1;
3307
605
                litSize = istart[0] & 31;
3308
605
                break;
3309
278
            case 2:
3310
278
                litSize = ((istart[0] & 15) << 8) + istart[1];
3311
278
                break;
3312
131
            case 3:
3313
131
                litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3314
131
                break;
3315
1.01k
            }
3316
3317
1.01k
            if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */
3318
167
                if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3319
121
                memcpy(dctx->litBuffer, istart+lhSize, litSize);
3320
121
                dctx->litPtr = dctx->litBuffer;
3321
121
                dctx->litSize = litSize;
3322
121
                memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3323
121
                return lhSize+litSize;
3324
167
            }
3325
            /* direct reference into compressed stream */
3326
847
            dctx->litPtr = istart+lhSize;
3327
847
            dctx->litSize = litSize;
3328
847
            return lhSize+litSize;
3329
1.01k
        }
3330
1.32k
    case lbt_rle:
3331
1.32k
        {   size_t litSize;
3332
1.32k
            U32 lhSize = ((istart[0]) >> 4) & 3;
3333
1.32k
            switch(lhSize)
3334
1.32k
            {
3335
250
            case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3336
250
                lhSize = 1;
3337
250
                litSize = istart[0] & 31;
3338
250
                break;
3339
330
            case 2:
3340
330
                litSize = ((istart[0] & 15) << 8) + istart[1];
3341
330
                break;
3342
746
            case 3:
3343
746
                litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3344
746
                if (srcSize<4) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3345
744
                break;
3346
1.32k
            }
3347
1.32k
            if (litSize > ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(corruption_detected);
3348
1.31k
            memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3349
1.31k
            dctx->litPtr = dctx->litBuffer;
3350
1.31k
            dctx->litSize = litSize;
3351
1.31k
            return lhSize+1;
3352
1.32k
        }
3353
0
    default:
3354
0
        return ERROR(corruption_detected);   /* impossible */
3355
2.74k
    }
3356
2.74k
}
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
5.33k
{
3367
5.33k
    switch(type)
3368
5.33k
    {
3369
1.06k
    case FSEv07_ENCODING_RLE :
3370
1.06k
        if (!srcSize) return ERROR(srcSize_wrong);
3371
1.06k
        if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3372
1.05k
        FSEv07_buildDTable_rle(DTable, *(const BYTE*)src);   /* if *src > max, data is corrupted */
3373
1.05k
        return 1;
3374
3.26k
    case FSEv07_ENCODING_RAW :
3375
3.26k
        FSEv07_buildDTable(DTable, defaultNorm, max, defaultLog);
3376
3.26k
        return 0;
3377
10
    case FSEv07_ENCODING_STATIC:
3378
10
        if (!flagRepeatTable) return ERROR(corruption_detected);
3379
1
        return 0;
3380
0
    default :   /* impossible */
3381
998
    case FSEv07_ENCODING_DYNAMIC :
3382
998
        {   U32 tableLog;
3383
998
            S16 norm[MaxSeq+1];
3384
998
            size_t const headerSize = FSEv07_readNCount(norm, &max, &tableLog, src, srcSize);
3385
998
            if (FSEv07_isError(headerSize)) return ERROR(corruption_detected);
3386
917
            if (tableLog > maxLog) return ERROR(corruption_detected);
3387
892
            FSEv07_buildDTable(DTable, norm, max, tableLog);
3388
892
            return headerSize;
3389
917
    }   }
3390
5.33k
}
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
2.28k
{
3397
2.28k
    const BYTE* const istart = (const BYTE*)src;
3398
2.28k
    const BYTE* const iend = istart + srcSize;
3399
2.28k
    const BYTE* ip = istart;
3400
3401
    /* check */
3402
2.28k
    if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3403
3404
    /* SeqHead */
3405
2.28k
    {   int nbSeq = *ip++;
3406
2.28k
        if (!nbSeq) { *nbSeqPtr=0; return 1; }
3407
1.83k
        if (nbSeq > 0x7F) {
3408
648
            if (nbSeq == 0xFF) {
3409
180
                if (ip+2 > iend) return ERROR(srcSize_wrong);
3410
177
                nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3411
468
            } else {
3412
468
                if (ip >= iend) return ERROR(srcSize_wrong);
3413
466
                nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3414
466
            }
3415
648
        }
3416
1.83k
        *nbSeqPtr = nbSeq;
3417
1.83k
    }
3418
3419
    /* FSE table descriptors */
3420
1.83k
    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
1.82k
    {   U32 const LLtype  = *ip >> 6;
3422
1.82k
        U32 const OFtype = (*ip >> 4) & 3;
3423
1.82k
        U32 const MLtype  = (*ip >> 2) & 3;
3424
1.82k
        ip++;
3425
3426
        /* Build DTables */
3427
1.82k
        {   size_t const llhSize = ZSTDv07_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3428
1.82k
            if (ZSTDv07_isError(llhSize)) return ERROR(corruption_detected);
3429
1.78k
            ip += llhSize;
3430
1.78k
        }
3431
1.78k
        {   size_t const ofhSize = ZSTDv07_buildSeqTable(DTableOffb, OFtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3432
1.78k
            if (ZSTDv07_isError(ofhSize)) return ERROR(corruption_detected);
3433
1.72k
            ip += ofhSize;
3434
1.72k
        }
3435
1.72k
        {   size_t const mlhSize = ZSTDv07_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3436
1.72k
            if (ZSTDv07_isError(mlhSize)) return ERROR(corruption_detected);
3437
1.70k
            ip += mlhSize;
3438
1.70k
    }   }
3439
3440
0
    return ip-istart;
3441
1.72k
}
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
13.0k
{
3461
13.0k
    seq_t seq;
3462
3463
13.0k
    U32 const llCode = FSEv07_peekSymbol(&(seqState->stateLL));
3464
13.0k
    U32 const mlCode = FSEv07_peekSymbol(&(seqState->stateML));
3465
13.0k
    U32 const ofCode = FSEv07_peekSymbol(&(seqState->stateOffb));   /* <= maxOff, by table construction */
3466
3467
13.0k
    U32 const llBits = LL_bits[llCode];
3468
13.0k
    U32 const mlBits = ML_bits[mlCode];
3469
13.0k
    U32 const ofBits = ofCode;
3470
13.0k
    U32 const totalBits = llBits+mlBits+ofBits;
3471
3472
13.0k
    static const U32 LL_base[MaxLL+1] = {
3473
13.0k
                             0,  1,  2,  3,  4,  5,  6,  7,  8,  9,   10,    11,    12,    13,    14,     15,
3474
13.0k
                            16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3475
13.0k
                            0x2000, 0x4000, 0x8000, 0x10000 };
3476
3477
13.0k
    static const U32 ML_base[MaxML+1] = {
3478
13.0k
                             3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13,   14,    15,    16,    17,    18,
3479
13.0k
                            19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,   30,    31,    32,    33,    34,
3480
13.0k
                            35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
3481
13.0k
                            0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
3482
3483
13.0k
    static const U32 OF_base[MaxOff+1] = {
3484
13.0k
                 0,        1,       1,       5,     0xD,     0x1D,     0x3D,     0x7D,
3485
13.0k
                 0xFD,   0x1FD,   0x3FD,   0x7FD,   0xFFD,   0x1FFD,   0x3FFD,   0x7FFD,
3486
13.0k
                 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
3487
13.0k
                 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD };
3488
3489
    /* sequence */
3490
13.0k
    {   size_t offset;
3491
13.0k
        if (!ofCode)
3492
5.97k
            offset = 0;
3493
7.10k
        else {
3494
7.10k
            offset = OF_base[ofCode] + BITv07_readBits(&(seqState->DStream), ofBits);   /* <=  (ZSTDv07_WINDOWLOG_MAX-1) bits */
3495
7.10k
            if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));
3496
7.10k
        }
3497
3498
13.0k
        if (ofCode <= 1) {
3499
11.2k
            if ((llCode == 0) & (offset <= 1)) offset = 1-offset;
3500
11.2k
            if (offset) {
3501
7.51k
                size_t const temp = seqState->prevOffset[offset];
3502
7.51k
                if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
3503
7.51k
                seqState->prevOffset[1] = seqState->prevOffset[0];
3504
7.51k
                seqState->prevOffset[0] = offset = temp;
3505
7.51k
            } else {
3506
3.74k
                offset = seqState->prevOffset[0];
3507
3.74k
            }
3508
11.2k
        } else {
3509
1.82k
            seqState->prevOffset[2] = seqState->prevOffset[1];
3510
1.82k
            seqState->prevOffset[1] = seqState->prevOffset[0];
3511
1.82k
            seqState->prevOffset[0] = offset;
3512
1.82k
        }
3513
13.0k
        seq.offset = offset;
3514
13.0k
    }
3515
3516
13.0k
    seq.matchLength = ML_base[mlCode] + ((mlCode>31) ? BITv07_readBits(&(seqState->DStream), mlBits) : 0);   /* <=  16 bits */
3517
13.0k
    if (MEM_32bits() && (mlBits+llBits>24)) BITv07_reloadDStream(&(seqState->DStream));
3518
3519
13.0k
    seq.litLength = LL_base[llCode] + ((llCode>15) ? BITv07_readBits(&(seqState->DStream), llBits) : 0);   /* <=  16 bits */
3520
13.0k
    if (MEM_32bits() ||
3521
13.0k
       (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv07_reloadDStream(&(seqState->DStream));
3522
3523
    /* ANS state update */
3524
13.0k
    FSEv07_updateState(&(seqState->stateLL), &(seqState->DStream));   /* <=  9 bits */
3525
13.0k
    FSEv07_updateState(&(seqState->stateML), &(seqState->DStream));   /* <=  9 bits */
3526
13.0k
    if (MEM_32bits()) BITv07_reloadDStream(&(seqState->DStream));     /* <= 18 bits */
3527
13.0k
    FSEv07_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <=  8 bits */
3528
3529
13.0k
    return seq;
3530
13.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
13.0k
{
3539
13.0k
    BYTE* const oLitEnd = op + sequence.litLength;
3540
13.0k
    size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3541
13.0k
    BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
3542
13.0k
    BYTE* const oend_w = oend-WILDCOPY_OVERLENGTH;
3543
13.0k
    const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3544
13.0k
    const BYTE* match = oLitEnd - sequence.offset;
3545
3546
    /* check */
3547
13.0k
    assert(oend >= op);
3548
13.0k
    if (sequence.litLength + WILDCOPY_OVERLENGTH > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3549
12.3k
    if (sequenceLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3550
11.9k
    assert(litLimit >= *litPtr);
3551
11.9k
    if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);;
3552
3553
    /* copy Literals */
3554
11.8k
    ZSTDv07_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
3555
11.8k
    op = oLitEnd;
3556
11.8k
    *litPtr = iLitEnd;   /* update for next sequence */
3557
3558
    /* copy Match */
3559
11.8k
    if (sequence.offset > (size_t)(oLitEnd - base)) {
3560
        /* offset beyond prefix */
3561
142
        if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3562
24
        match = dictEnd - (base-match);
3563
24
        if (match + sequence.matchLength <= dictEnd) {
3564
16
            memmove(oLitEnd, match, sequence.matchLength);
3565
16
            return sequenceLength;
3566
16
        }
3567
        /* span extDict & currentPrefixSegment */
3568
8
        {   size_t const length1 = (size_t)(dictEnd - match);
3569
8
            memmove(oLitEnd, match, length1);
3570
8
            op = oLitEnd + length1;
3571
8
            sequence.matchLength -= length1;
3572
8
            match = base;
3573
8
            if (op > oend_w || sequence.matchLength < MINMATCH) {
3574
3
              while (op < oMatchEnd) *op++ = *match++;
3575
1
              return sequenceLength;
3576
1
            }
3577
8
    }   }
3578
    /* Requirement: op <= oend_w */
3579
3580
    /* match within prefix */
3581
11.7k
    if (sequence.offset < 8) {
3582
        /* close range match, overlap */
3583
9.02k
        static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
3584
9.02k
        static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
3585
9.02k
        int const sub2 = dec64table[sequence.offset];
3586
9.02k
        op[0] = match[0];
3587
9.02k
        op[1] = match[1];
3588
9.02k
        op[2] = match[2];
3589
9.02k
        op[3] = match[3];
3590
9.02k
        match += dec32table[sequence.offset];
3591
9.02k
        ZSTDv07_copy4(op+4, match);
3592
9.02k
        match -= sub2;
3593
9.02k
    } else {
3594
2.72k
        ZSTDv07_copy8(op, match);
3595
2.72k
    }
3596
11.7k
    op += 8; match += 8;
3597
3598
11.7k
    if (oMatchEnd > oend-(16-MINMATCH)) {
3599
69
        if (op < oend_w) {
3600
35
            ZSTDv07_wildcopy(op, match, oend_w - op);
3601
35
            match += oend_w - op;
3602
35
            op = oend_w;
3603
35
        }
3604
179
        while (op < oMatchEnd) *op++ = *match++;
3605
11.6k
    } else {
3606
11.6k
        ZSTDv07_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
3607
11.6k
    }
3608
11.7k
    return sequenceLength;
3609
11.8k
}
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
2.28k
{
3617
2.28k
    const BYTE* ip = (const BYTE*)seqStart;
3618
2.28k
    const BYTE* const iend = ip + seqSize;
3619
2.28k
    BYTE* const ostart = (BYTE*)dst;
3620
2.28k
    BYTE* const oend = ostart + maxDstSize;
3621
2.28k
    BYTE* op = ostart;
3622
2.28k
    const BYTE* litPtr = dctx->litPtr;
3623
2.28k
    const BYTE* const litEnd = litPtr + dctx->litSize;
3624
2.28k
    FSEv07_DTable* DTableLL = dctx->LLTable;
3625
2.28k
    FSEv07_DTable* DTableML = dctx->MLTable;
3626
2.28k
    FSEv07_DTable* DTableOffb = dctx->OffTable;
3627
2.28k
    const BYTE* const base = (const BYTE*) (dctx->base);
3628
2.28k
    const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3629
2.28k
    const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3630
2.28k
    int nbSeq;
3631
3632
    /* Build Decoding Tables */
3633
2.28k
    {   size_t const seqHSize = ZSTDv07_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->fseEntropy, ip, seqSize);
3634
2.28k
        if (ZSTDv07_isError(seqHSize)) return seqHSize;
3635
2.14k
        ip += seqHSize;
3636
2.14k
    }
3637
3638
    /* Regen sequences */
3639
2.14k
    if (nbSeq) {
3640
1.66k
        seqState_t seqState;
3641
1.66k
        dctx->fseEntropy = 1;
3642
6.64k
        { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) seqState.prevOffset[i] = dctx->rep[i]; }
3643
1.66k
        { size_t const errorCode = BITv07_initDStream(&(seqState.DStream), ip, iend-ip);
3644
1.66k
          if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3645
1.64k
        FSEv07_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3646
1.64k
        FSEv07_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3647
1.64k
        FSEv07_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3648
3649
13.4k
        for ( ; (BITv07_reloadDStream(&(seqState.DStream)) <= BITv07_DStream_completed) && nbSeq ; ) {
3650
13.0k
            nbSeq--;
3651
13.0k
            {   seq_t const sequence = ZSTDv07_decodeSequence(&seqState);
3652
13.0k
                size_t const oneSeqSize = ZSTDv07_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3653
13.0k
                if (ZSTDv07_isError(oneSeqSize)) return oneSeqSize;
3654
11.7k
                op += oneSeqSize;
3655
11.7k
        }   }
3656
3657
        /* check if reached exact end */
3658
322
        if (nbSeq) return ERROR(corruption_detected);
3659
        /* save reps for next block */
3660
1.01k
        { U32 i; for (i=0; i<ZSTDv07_REP_INIT; i++) dctx->rep[i] = (U32)(seqState.prevOffset[i]); }
3661
253
    }
3662
3663
    /* last literal segment */
3664
737
    {   size_t const lastLLSize = litEnd - litPtr;
3665
        /* if (litPtr > litEnd) return ERROR(corruption_detected); */   /* too many literals already used */
3666
737
        if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
3667
522
        if (lastLLSize > 0) {
3668
409
            memcpy(op, litPtr, lastLLSize);
3669
409
            op += lastLLSize;
3670
409
        }
3671
522
    }
3672
3673
0
    return op-ostart;
3674
737
}
3675
3676
3677
static void ZSTDv07_checkContinuity(ZSTDv07_DCtx* dctx, const void* dst)
3678
4.76k
{
3679
4.76k
    if (dst != dctx->previousDstEnd) {   /* not contiguous */
3680
4.12k
        dctx->dictEnd = dctx->previousDstEnd;
3681
4.12k
        dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3682
4.12k
        dctx->base = dst;
3683
4.12k
        dctx->previousDstEnd = dst;
3684
4.12k
    }
3685
4.76k
}
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
2.75k
{   /* blockType == blockCompressed */
3692
2.75k
    const BYTE* ip = (const BYTE*)src;
3693
3694
2.75k
    if (srcSize >= ZSTDv07_BLOCKSIZE_ABSOLUTEMAX) return ERROR(srcSize_wrong);
3695
3696
    /* Decode literals sub-block */
3697
2.75k
    {   size_t const litCSize = ZSTDv07_decodeLiteralsBlock(dctx, src, srcSize);
3698
2.75k
        if (ZSTDv07_isError(litCSize)) return litCSize;
3699
2.28k
        ip += litCSize;
3700
2.28k
        srcSize -= litCSize;
3701
2.28k
    }
3702
0
    return ZSTDv07_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3703
2.75k
}
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.13k
{
3730
3.13k
    if (length > dstCapacity) return ERROR(dstSize_tooSmall);
3731
1.86k
    if (length > 0) {
3732
1.80k
        memset(dst, byte, length);
3733
1.80k
    }
3734
1.86k
    return length;
3735
3.13k
}
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
3.40k
{
3744
3.40k
    const BYTE* ip = (const BYTE*)src;
3745
3.40k
    const BYTE* const iend = ip + srcSize;
3746
3.40k
    BYTE* const ostart = (BYTE*)dst;
3747
3.40k
    BYTE* const oend = ostart + dstCapacity;
3748
3.40k
    BYTE* op = ostart;
3749
3.40k
    size_t remainingSize = srcSize;
3750
3751
    /* check */
3752
3.40k
    if (srcSize < ZSTDv07_frameHeaderSize_min+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3753
3754
    /* Frame Header */
3755
3.40k
    {   size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3756
3.40k
        if (ZSTDv07_isError(frameHeaderSize)) return frameHeaderSize;
3757
3.40k
        if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) return ERROR(srcSize_wrong);
3758
3.40k
        if (ZSTDv07_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3759
3.35k
        ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3760
3.35k
    }
3761
3762
    /* Loop on each block */
3763
5.94k
    while (1) {
3764
5.94k
        size_t decodedSize;
3765
5.94k
        blockProperties_t blockProperties;
3766
5.94k
        size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, iend-ip, &blockProperties);
3767
5.94k
        if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3768
3769
5.94k
        ip += ZSTDv07_blockHeaderSize;
3770
5.94k
        remainingSize -= ZSTDv07_blockHeaderSize;
3771
5.94k
        if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3772
3773
5.94k
        switch(blockProperties.blockType)
3774
5.94k
        {
3775
2.18k
        case bt_compressed:
3776
2.18k
            decodedSize = ZSTDv07_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3777
2.18k
            break;
3778
323
        case bt_raw :
3779
323
            decodedSize = ZSTDv07_copyRawBlock(op, oend-op, ip, cBlockSize);
3780
323
            break;
3781
3.13k
        case bt_rle :
3782
3.13k
            decodedSize = ZSTDv07_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
3783
3.13k
            break;
3784
301
        case bt_end :
3785
            /* end of frame */
3786
301
            if (remainingSize) return ERROR(srcSize_wrong);
3787
301
            decodedSize = 0;
3788
301
            break;
3789
0
        default:
3790
0
            return ERROR(GENERIC);   /* impossible */
3791
5.94k
        }
3792
5.94k
        if (blockProperties.blockType == bt_end) break;   /* bt_end */
3793
3794
5.64k
        if (ZSTDv07_isError(decodedSize)) return decodedSize;
3795
2.59k
        if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, op, decodedSize);
3796
2.59k
        op += decodedSize;
3797
2.59k
        ip += cBlockSize;
3798
2.59k
        remainingSize -= cBlockSize;
3799
2.59k
    }
3800
3801
301
    return op-ostart;
3802
3.35k
}
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
3.40k
{
3825
3.40k
    ZSTDv07_decompressBegin_usingDict(dctx, dict, dictSize);
3826
3.40k
    ZSTDv07_checkContinuity(dctx, dst);
3827
3.40k
    return ZSTDv07_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3828
3.40k
}
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
36
{
3856
36
    *cSize = ret;
3857
36
    *dBound = ZSTD_CONTENTSIZE_ERROR;
3858
36
}
3859
3860
void ZSTDv07_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3861
3.45k
{
3862
3.45k
    const BYTE* ip = (const BYTE*)src;
3863
3.45k
    size_t remainingSize = srcSize;
3864
3.45k
    size_t nbBlocks = 0;
3865
3866
    /* check */
3867
3.45k
    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
3.45k
    {   size_t const frameHeaderSize = ZSTDv07_frameHeaderSize(src, srcSize);
3874
3.45k
        if (ZSTDv07_isError(frameHeaderSize)) {
3875
0
            ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize);
3876
0
            return;
3877
0
        }
3878
3.45k
        if (MEM_readLE32(src) != ZSTDv07_MAGICNUMBER) {
3879
0
            ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3880
0
            return;
3881
0
        }
3882
3.45k
        if (srcSize < frameHeaderSize+ZSTDv07_blockHeaderSize) {
3883
4
            ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3884
4
            return;
3885
4
        }
3886
3.45k
        ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3887
3.45k
    }
3888
3889
    /* Loop on each block */
3890
19.0k
    while (1) {
3891
19.0k
        blockProperties_t blockProperties;
3892
19.0k
        size_t const cBlockSize = ZSTDv07_getcBlockSize(ip, remainingSize, &blockProperties);
3893
19.0k
        if (ZSTDv07_isError(cBlockSize)) {
3894
4
            ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3895
4
            return;
3896
4
        }
3897
3898
19.0k
        ip += ZSTDv07_blockHeaderSize;
3899
19.0k
        remainingSize -= ZSTDv07_blockHeaderSize;
3900
3901
19.0k
        if (blockProperties.blockType == bt_end) break;
3902
3903
15.6k
        if (cBlockSize > remainingSize) {
3904
26
            ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3905
26
            return;
3906
26
        }
3907
3908
15.5k
        ip += cBlockSize;
3909
15.5k
        remainingSize -= cBlockSize;
3910
15.5k
        nbBlocks++;
3911
15.5k
    }
3912
3913
3.42k
    *cSize = ip - (const BYTE*)src;
3914
3.42k
    *dBound = nbBlocks * ZSTDv07_BLOCKSIZE_ABSOLUTEMAX;
3915
3.42k
}
3916
3917
/*_******************************
3918
*  Streaming Decompression API
3919
********************************/
3920
size_t ZSTDv07_nextSrcSizeToDecompress(ZSTDv07_DCtx* dctx)
3921
3.30k
{
3922
3.30k
    return dctx->expected;
3923
3.30k
}
3924
3925
int ZSTDv07_isSkipFrame(ZSTDv07_DCtx* dctx)
3926
1.35k
{
3927
1.35k
    return dctx->stage == ZSTDds_skipFrame;
3928
1.35k
}
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
2.84k
{
3935
    /* Sanity check */
3936
2.84k
    if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3937
2.84k
    if (dstCapacity) ZSTDv07_checkContinuity(dctx, dst);
3938
3939
2.84k
    switch (dctx->stage)
3940
2.84k
    {
3941
741
    case ZSTDds_getFrameHeaderSize :
3942
741
        if (srcSize != ZSTDv07_frameHeaderSize_min) return ERROR(srcSize_wrong);   /* impossible */
3943
741
        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
741
        dctx->headerSize = ZSTDv07_frameHeaderSize(src, ZSTDv07_frameHeaderSize_min);
3950
741
        if (ZSTDv07_isError(dctx->headerSize)) return dctx->headerSize;
3951
741
        memcpy(dctx->headerBuffer, src, ZSTDv07_frameHeaderSize_min);
3952
741
        if (dctx->headerSize > ZSTDv07_frameHeaderSize_min) {
3953
741
            dctx->expected = dctx->headerSize - ZSTDv07_frameHeaderSize_min;
3954
741
            dctx->stage = ZSTDds_decodeFrameHeader;
3955
741
            return 0;
3956
741
        }
3957
0
        dctx->expected = 0;   /* not necessary to copy more */
3958
  /* fall-through */
3959
741
    case ZSTDds_decodeFrameHeader:
3960
741
        {   size_t result;
3961
741
            memcpy(dctx->headerBuffer + ZSTDv07_frameHeaderSize_min, src, dctx->expected);
3962
741
            result = ZSTDv07_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
3963
741
            if (ZSTDv07_isError(result)) return result;
3964
705
            dctx->expected = ZSTDv07_blockHeaderSize;
3965
705
            dctx->stage = ZSTDds_decodeBlockHeader;
3966
705
            return 0;
3967
741
        }
3968
778
    case ZSTDds_decodeBlockHeader:
3969
778
        {   blockProperties_t bp;
3970
778
            size_t const cBlockSize = ZSTDv07_getcBlockSize(src, ZSTDv07_blockHeaderSize, &bp);
3971
778
            if (ZSTDv07_isError(cBlockSize)) return cBlockSize;
3972
778
            if (bp.blockType == bt_end) {
3973
32
                if (dctx->fParams.checksumFlag) {
3974
12
                    U64 const h64 = XXH64_digest(&dctx->xxhState);
3975
12
                    U32 const h32 = (U32)(h64>>11) & ((1<<22)-1);
3976
12
                    const BYTE* const ip = (const BYTE*)src;
3977
12
                    U32 const check32 = ip[2] + (ip[1] << 8) + ((ip[0] & 0x3F) << 16);
3978
12
                    if (check32 != h32) return ERROR(checksum_wrong);
3979
12
                }
3980
20
                dctx->expected = 0;
3981
20
                dctx->stage = ZSTDds_getFrameHeaderSize;
3982
746
            } else {
3983
746
                dctx->expected = cBlockSize;
3984
746
                dctx->bType = bp.blockType;
3985
746
                dctx->stage = ZSTDds_decompressBlock;
3986
746
            }
3987
766
            return 0;
3988
778
        }
3989
580
    case ZSTDds_decompressBlock:
3990
580
        {   size_t rSize;
3991
580
            switch(dctx->bType)
3992
580
            {
3993
569
            case bt_compressed:
3994
569
                rSize = ZSTDv07_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3995
569
                break;
3996
5
            case bt_raw :
3997
5
                rSize = ZSTDv07_copyRawBlock(dst, dstCapacity, src, srcSize);
3998
5
                break;
3999
6
            case bt_rle :
4000
6
                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
580
            }
4008
574
            dctx->stage = ZSTDds_decodeBlockHeader;
4009
574
            dctx->expected = ZSTDv07_blockHeaderSize;
4010
574
            if (ZSTDv07_isError(rSize)) return rSize;
4011
98
            dctx->previousDstEnd = (char*)dst + rSize;
4012
98
            if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
4013
98
            return rSize;
4014
574
        }
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
574
        }
4021
0
    case ZSTDds_skipFrame:
4022
0
        {   dctx->expected = 0;
4023
0
            dctx->stage = ZSTDds_getFrameHeaderSize;
4024
0
            return 0;
4025
574
        }
4026
0
    default:
4027
0
        return ERROR(GENERIC);   /* impossible */
4028
2.84k
    }
4029
2.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
4.17k
{
4116
4.17k
    { size_t const errorCode = ZSTDv07_decompressBegin(dctx);
4117
4.17k
      if (ZSTDv07_isError(errorCode)) return errorCode; }
4118
4119
4.17k
    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
4.17k
    return 0;
4125
4.17k
}
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
704
{
4282
704
    return ZBUFFv07_createDCtx_advanced(defaultCustomMem);
4283
704
}
4284
4285
ZBUFFv07_DCtx* ZBUFFv07_createDCtx_advanced(ZSTDv07_customMem customMem)
4286
704
{
4287
704
    ZBUFFv07_DCtx* zbd;
4288
4289
704
    if (!customMem.customAlloc && !customMem.customFree)
4290
0
        customMem = defaultCustomMem;
4291
4292
704
    if (!customMem.customAlloc || !customMem.customFree)
4293
0
        return NULL;
4294
4295
704
    zbd = (ZBUFFv07_DCtx*)customMem.customAlloc(customMem.opaque, sizeof(ZBUFFv07_DCtx));
4296
704
    if (zbd==NULL) return NULL;
4297
704
    memset(zbd, 0, sizeof(ZBUFFv07_DCtx));
4298
704
    memcpy(&zbd->customMem, &customMem, sizeof(ZSTDv07_customMem));
4299
704
    zbd->zd = ZSTDv07_createDCtx_advanced(customMem);
4300
704
    if (zbd->zd == NULL) { ZBUFFv07_freeDCtx(zbd); return NULL; }
4301
704
    zbd->stage = ZBUFFds_init;
4302
704
    return zbd;
4303
704
}
4304
4305
size_t ZBUFFv07_freeDCtx(ZBUFFv07_DCtx* zbd)
4306
704
{
4307
704
    if (zbd==NULL) return 0;   /* support free on null */
4308
704
    ZSTDv07_freeDCtx(zbd->zd);
4309
704
    if (zbd->inBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4310
704
    if (zbd->outBuff) zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4311
704
    zbd->customMem.customFree(zbd->customMem.opaque, zbd);
4312
704
    return 0;
4313
704
}
4314
4315
4316
/* *** Initialization *** */
4317
4318
size_t ZBUFFv07_decompressInitDictionary(ZBUFFv07_DCtx* zbd, const void* dict, size_t dictSize)
4319
768
{
4320
768
    zbd->stage = ZBUFFds_loadHeader;
4321
768
    zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
4322
768
    return ZSTDv07_decompressBegin_usingDict(zbd->zd, dict, dictSize);
4323
768
}
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
98
{
4334
98
    size_t const length = MIN(dstCapacity, srcSize);
4335
98
    if (length > 0) {
4336
98
        memcpy(dst, src, length);
4337
98
    }
4338
98
    return length;
4339
98
}
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
768
{
4348
768
    const char* const istart = (const char*)src;
4349
768
    const char* const iend = istart + *srcSizePtr;
4350
768
    const char* ip = istart;
4351
768
    char* const ostart = (char*)dst;
4352
768
    char* const oend = ostart + *dstCapacityPtr;
4353
768
    char* op = ostart;
4354
768
    U32 notDone = 1;
4355
4356
3.37k
    while (notDone) {
4357
3.21k
        switch(zbd->stage)
4358
3.21k
        {
4359
0
        case ZBUFFds_init :
4360
0
            return ERROR(init_missing);
4361
4362
2.29k
        case ZBUFFds_loadHeader :
4363
2.29k
            {   size_t const hSize = ZSTDv07_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
4364
2.29k
                if (ZSTDv07_isError(hSize)) return hSize;
4365
2.27k
                if (hSize != 0) {
4366
1.53k
                    size_t const toLoad = hSize - zbd->lhSize;   /* if hSize!=0, hSize > zbd->lhSize */
4367
1.53k
                    if (toLoad > (size_t)(iend-ip)) {   /* not enough input to load full header */
4368
8
                        if (ip != NULL)
4369
8
                            memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
4370
8
                        zbd->lhSize += iend-ip;
4371
8
                        *dstCapacityPtr = 0;
4372
8
                        return (hSize - zbd->lhSize) + ZSTDv07_blockHeaderSize;   /* remaining header bytes + next block header */
4373
8
                    }
4374
1.52k
                    memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
4375
1.52k
                    break;
4376
1.53k
            }   }
4377
4378
            /* Consume header */
4379
741
            {   size_t const h1Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);  /* == ZSTDv07_frameHeaderSize_min */
4380
741
                size_t const h1Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4381
741
                if (ZSTDv07_isError(h1Result)) return h1Result;
4382
741
                if (h1Size < zbd->lhSize) {   /* long header */
4383
741
                    size_t const h2Size = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4384
741
                    size_t const h2Result = ZSTDv07_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4385
741
                    if (ZSTDv07_isError(h2Result)) return h2Result;
4386
741
            }   }
4387
4388
705
            zbd->fParams.windowSize = MAX(zbd->fParams.windowSize, 1U << ZSTDv07_WINDOWLOG_ABSOLUTEMIN);
4389
4390
            /* Frame header instruct buffer sizes */
4391
705
            {   size_t const blockSize = MIN(zbd->fParams.windowSize, ZSTDv07_BLOCKSIZE_ABSOLUTEMAX);
4392
705
                zbd->blockSize = blockSize;
4393
705
                if (zbd->inBuffSize < blockSize) {
4394
646
                    zbd->customMem.customFree(zbd->customMem.opaque, zbd->inBuff);
4395
646
                    zbd->inBuffSize = blockSize;
4396
646
                    zbd->inBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, blockSize);
4397
646
                    if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4398
646
                }
4399
705
                {   size_t const neededOutSize = zbd->fParams.windowSize + blockSize + WILDCOPY_OVERLENGTH * 2;
4400
705
                    if (zbd->outBuffSize < neededOutSize) {
4401
646
                        zbd->customMem.customFree(zbd->customMem.opaque, zbd->outBuff);
4402
646
                        zbd->outBuffSize = neededOutSize;
4403
646
                        zbd->outBuff = (char*)zbd->customMem.customAlloc(zbd->customMem.opaque, neededOutSize);
4404
646
                        if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4405
646
            }   }   }
4406
705
            zbd->stage = ZBUFFds_read;
4407
            /* pass-through */
4408
      /* fall-through */
4409
1.56k
        case ZBUFFds_read:
4410
1.56k
            {   size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4411
1.56k
                if (neededInSize==0) {  /* end of frame */
4412
99
                    zbd->stage = ZBUFFds_init;
4413
99
                    notDone = 0;
4414
99
                    break;
4415
99
                }
4416
1.47k
                if ((size_t)(iend-ip) >= neededInSize) {  /* decode directly from src */
4417
1.35k
                    const int isSkipFrame = ZSTDv07_isSkipFrame(zbd->zd);
4418
1.35k
                    size_t const decodedSize = ZSTDv07_decompressContinue(zbd->zd,
4419
1.35k
                        zbd->outBuff + zbd->outStart, (isSkipFrame ? 0 : zbd->outBuffSize - zbd->outStart),
4420
1.35k
                        ip, neededInSize);
4421
1.35k
                    if (ZSTDv07_isError(decodedSize)) return decodedSize;
4422
864
                    ip += neededInSize;
4423
864
                    if (!decodedSize && !isSkipFrame) break;   /* this was just a header */
4424
54
                    zbd->outEnd = zbd->outStart +  decodedSize;
4425
54
                    zbd->stage = ZBUFFds_flush;
4426
54
                    break;
4427
864
                }
4428
112
                if (ip==iend) { notDone = 0; break; }   /* no more input */
4429
94
                zbd->stage = ZBUFFds_load;
4430
94
            }
4431
      /* fall-through */
4432
94
        case ZBUFFds_load:
4433
94
            {   size_t const neededInSize = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4434
94
                size_t const toLoad = neededInSize - zbd->inPos;   /* should always be <= remaining space within inBuff */
4435
94
                size_t loadedSize;
4436
94
                if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected);   /* should never happen */
4437
44
                loadedSize = ZBUFFv07_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4438
44
                ip += loadedSize;
4439
44
                zbd->inPos += loadedSize;
4440
44
                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
54
        case ZBUFFds_flush:
4458
54
            {   size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4459
54
                size_t const flushedSize = ZBUFFv07_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4460
54
                op += flushedSize;
4461
54
                zbd->outStart += flushedSize;
4462
54
                if (flushedSize == toFlushSize) {
4463
54
                    zbd->stage = ZBUFFds_read;
4464
54
                    if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4465
31
                        zbd->outStart = zbd->outEnd = 0;
4466
54
                    break;
4467
54
                }
4468
                /* cannot flush everything */
4469
0
                notDone = 0;
4470
0
                break;
4471
54
            }
4472
0
        default: return ERROR(GENERIC);   /* impossible */
4473
3.21k
    }   }
4474
4475
    /* result */
4476
161
    *srcSizePtr = ip-istart;
4477
161
    *dstCapacityPtr = op-ostart;
4478
161
    {   size_t nextSrcSizeHint = ZSTDv07_nextSrcSizeToDecompress(zbd->zd);
4479
161
        nextSrcSizeHint -= zbd->inPos;   /* already loaded*/
4480
161
        return nextSrcSizeHint;
4481
768
    }
4482
768
}
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; }