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