deps/libchdr/deps/zstd-1.5.5/lib/legacy/zstd_v06.c

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