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