deps/libchdr/deps/zstd-1.5.6/lib/legacy/zstd_v07.c

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