contrib/zstd/lib/legacy/zstd_v07.c

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