Coverage Report

Created: 2024-09-08 06:26

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