deps/libchdr/deps/zstd-1.5.5/lib/legacy/zstd_v04.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  /******************************************
  13  *  Includes
  14  ******************************************/
  15 #include <stddef.h>    /* size_t, ptrdiff_t */
  16 #include <string.h>    /* memcpy */
  17
  18 #include "zstd_v04.h"
  19 #include "../common/error_private.h"
  20
  21
  22 /* ******************************************************************
  23  *   mem.h
  24  *******************************************************************/
  25 #ifndef MEM_H_MODULE
  26 #define MEM_H_MODULE
  27
  28 #if defined (__cplusplus)
  29 extern "C" {
  30 #endif
  31
  32
  33 /******************************************
  34 *  Compiler-specific
  35 ******************************************/
  36 #if defined(_MSC_VER)   /* Visual Studio */
  37 #   include <stdlib.h>  /* _byteswap_ulong */
  38 #   include <intrin.h>  /* _byteswap_* */
  39 #endif
  40 #if defined(__GNUC__)
  41 #  define MEM_STATIC static __attribute__((unused))
  42 #elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
  43 #  define MEM_STATIC static inline
  44 #elif defined(_MSC_VER)
  45 #  define MEM_STATIC static __inline
  46 #else
  47 #  define MEM_STATIC static  /* this version may generate warnings for unused static functions; disable the relevant warning */
  48 #endif
  49
  50
  51 /****************************************************************
  52 *  Basic Types
  53 *****************************************************************/
  54 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
  55 # if defined(_AIX)
  56 #  include <inttypes.h>
  57 # else
  58 #  include <stdint.h> /* intptr_t */
  59 # endif
  60   typedef  uint8_t BYTE;
  61   typedef uint16_t U16;
  62   typedef  int16_t S16;
  63   typedef uint32_t U32;
  64   typedef  int32_t S32;
  65   typedef uint64_t U64;
  66   typedef  int64_t S64;
  67 #else
  68   typedef unsigned char       BYTE;
  69   typedef unsigned short      U16;
  70   typedef   signed short      S16;
  71   typedef unsigned int        U32;
  72   typedef   signed int        S32;
  73   typedef unsigned long long  U64;
  74   typedef   signed long long  S64;
  75 #endif
  76
  77
  78 /*-*************************************
  79 *  Debug
  80 ***************************************/
  81 #include "../common/debug.h"
  82 #ifndef assert
  83 #  define assert(condition) ((void)0)
  84 #endif
  85
  86
  87 /****************************************************************
  88 *  Memory I/O
  89 *****************************************************************/
  90
  91 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
  92 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
  93
  94 MEM_STATIC unsigned MEM_isLittleEndian(void)
  95 {
  96     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
  97     return one.c[0];
  98 }
  99
 100 MEM_STATIC U16 MEM_read16(const void* memPtr)
 101 {
 102     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
 103 }
 104
 105 MEM_STATIC U32 MEM_read32(const void* memPtr)
 106 {
 107     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
 108 }
 109
 110 MEM_STATIC U64 MEM_read64(const void* memPtr)
 111 {
 112     U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
 113 }
 114
 115 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
 116 {
 117     memcpy(memPtr, &value, sizeof(value));
 118 }
 119
 120 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
 121 {
 122     if (MEM_isLittleEndian())
 123         return MEM_read16(memPtr);
 124     else
 125     {
 126         const BYTE* p = (const BYTE*)memPtr;
 127         return (U16)(p[0] + (p[1]<<8));
 128     }
 129 }
 130
 131 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
 132 {
 133     if (MEM_isLittleEndian())
 134     {
 135         MEM_write16(memPtr, val);
 136     }
 137     else
 138     {
 139         BYTE* p = (BYTE*)memPtr;
 140         p[0] = (BYTE)val;
 141         p[1] = (BYTE)(val>>8);
 142     }
 143 }
 144
 145 MEM_STATIC U32 MEM_readLE24(const void* memPtr)
 146 {
 147     return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
 148 }
 149
 150 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
 151 {
 152     if (MEM_isLittleEndian())
 153         return MEM_read32(memPtr);
 154     else
 155     {
 156         const BYTE* p = (const BYTE*)memPtr;
 157         return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
 158     }
 159 }
 160
 161
 162 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
 163 {
 164     if (MEM_isLittleEndian())
 165         return MEM_read64(memPtr);
 166     else
 167     {
 168         const BYTE* p = (const BYTE*)memPtr;
 169         return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
 170                      + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
 171     }
 172 }
 173
 174
 175 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
 176 {
 177     if (MEM_32bits())
 178         return (size_t)MEM_readLE32(memPtr);
 179     else
 180         return (size_t)MEM_readLE64(memPtr);
 181 }
 182
 183
 184 #if defined (__cplusplus)
 185 }
 186 #endif
 187
 188 #endif /* MEM_H_MODULE */
 189
 190 /*
 191     zstd - standard compression library
 192     Header File for static linking only
 193 */
 194 #ifndef ZSTD_STATIC_H
 195 #define ZSTD_STATIC_H
 196
 197
 198 /* *************************************
 199 *  Types
 200 ***************************************/
 201 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 11
 202
 203 /** from faster to stronger */
 204 typedef enum { ZSTD_fast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2 } ZSTD_strategy;
 205
 206 typedef struct
 207 {
 208     U64 srcSize;       /* optional : tells how much bytes are present in the frame. Use 0 if not known. */
 209     U32 windowLog;     /* largest match distance : larger == more compression, more memory needed during decompression */
 210     U32 contentLog;    /* full search segment : larger == more compression, slower, more memory (useless for fast) */
 211     U32 hashLog;       /* dispatch table : larger == more memory, faster */
 212     U32 searchLog;     /* nb of searches : larger == more compression, slower */
 213     U32 searchLength;  /* size of matches : larger == faster decompression, sometimes less compression */
 214     ZSTD_strategy strategy;
 215 } ZSTD_parameters;
 216
 217 typedef ZSTDv04_Dctx ZSTD_DCtx;
 218
 219 /* *************************************
 220 *  Advanced functions
 221 ***************************************/
 222 /** ZSTD_decompress_usingDict
 223 *   Same as ZSTD_decompressDCtx, using a Dictionary content as prefix
 224 *   Note : dict can be NULL, in which case, it's equivalent to ZSTD_decompressDCtx() */
 225 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
 226                                              void* dst, size_t maxDstSize,
 227                                        const void* src, size_t srcSize,
 228                                        const void* dict,size_t dictSize);
 229
 230
 231 /* **************************************
 232 *  Streaming functions (direct mode)
 233 ****************************************/
 234 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx);
 235 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize);
 236 static void   ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* src, size_t srcSize);
 237
 238 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx);
 239 static size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize);
 240
 241 /**
 242   Streaming decompression, bufferless mode
 243
 244   A ZSTD_DCtx object is required to track streaming operations.
 245   Use ZSTD_createDCtx() / ZSTD_freeDCtx() to manage it.
 246   A ZSTD_DCtx object can be re-used multiple times. Use ZSTD_resetDCtx() to return to fresh status.
 247
 248   First operation is to retrieve frame parameters, using ZSTD_getFrameParams().
 249   This function doesn't consume its input. It needs enough input data to properly decode the frame header.
 250   Objective is to retrieve *params.windowlog, to know minimum amount of memory required during decoding.
 251   Result : 0 when successful, it means the ZSTD_parameters structure has been filled.
 252            >0 : means there is not enough data into src. Provides the expected size to successfully decode header.
 253            errorCode, which can be tested using ZSTD_isError() (For example, if it's not a ZSTD header)
 254
 255   Then, you can optionally insert a dictionary.
 256   This operation must mimic the compressor behavior, otherwise decompression will fail or be corrupted.
 257
 258   Then it's possible to start decompression.
 259   Use ZSTD_nextSrcSizeToDecompress() and ZSTD_decompressContinue() alternatively.
 260   ZSTD_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTD_decompressContinue().
 261   ZSTD_decompressContinue() requires this exact amount of bytes, or it will fail.
 262   ZSTD_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
 263   They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
 264
 265   @result of ZSTD_decompressContinue() is the number of bytes regenerated within 'dst'.
 266   It can be zero, which is not an error; it just means ZSTD_decompressContinue() has decoded some header.
 267
 268   A frame is fully decoded when ZSTD_nextSrcSizeToDecompress() returns zero.
 269   Context can then be reset to start a new decompression.
 270 */
 271
 272
 273
 274
 275 #endif  /* ZSTD_STATIC_H */
 276
 277
 278 /*
 279     zstd_internal - common functions to include
 280     Header File for include
 281 */
 282 #ifndef ZSTD_CCOMMON_H_MODULE
 283 #define ZSTD_CCOMMON_H_MODULE
 284
 285 /* *************************************
 286 *  Common macros
 287 ***************************************/
 288 #define MIN(a,b) ((a)<(b) ? (a) : (b))
 289 #define MAX(a,b) ((a)>(b) ? (a) : (b))
 290
 291
 292 /* *************************************
 293 *  Common constants
 294 ***************************************/
 295 #define ZSTD_MAGICNUMBER 0xFD2FB524   /* v0.4 */
 296
 297 #define KB *(1 <<10)
 298 #define MB *(1 <<20)
 299 #define GB *(1U<<30)
 300
 301 #define BLOCKSIZE (128 KB)                 /* define, for static allocation */
 302
 303 static const size_t ZSTD_blockHeaderSize = 3;
 304 static const size_t ZSTD_frameHeaderSize_min = 5;
 305 #define ZSTD_frameHeaderSize_max 5         /* define, for static allocation */
 306
 307 #define BIT7 128
 308 #define BIT6  64
 309 #define BIT5  32
 310 #define BIT4  16
 311 #define BIT1   2
 312 #define BIT0   1
 313
 314 #define IS_RAW BIT0
 315 #define IS_RLE BIT1
 316
 317 #define MINMATCH 4
 318 #define REPCODE_STARTVALUE 4
 319
 320 #define MLbits   7
 321 #define LLbits   6
 322 #define Offbits  5
 323 #define MaxML  ((1<<MLbits) - 1)
 324 #define MaxLL  ((1<<LLbits) - 1)
 325 #define MaxOff ((1<<Offbits)- 1)
 326 #define MLFSELog   10
 327 #define LLFSELog   10
 328 #define OffFSELog   9
 329 #define MaxSeq MAX(MaxLL, MaxML)
 330
 331 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
 332 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
 333
 334 #define ZSTD_CONTENTSIZE_ERROR   (0ULL - 2)
 335
 336 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
 337
 338
 339 /* ******************************************
 340 *  Shared functions to include for inlining
 341 ********************************************/
 342 static void ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
 343
 344 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
 345
 346 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
 347 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
 348 {
 349     const BYTE* ip = (const BYTE*)src;
 350     BYTE* op = (BYTE*)dst;
 351     BYTE* const oend = op + length;
 352     do
 353         COPY8(op, ip)
 354     while (op < oend);
 355 }
 356
 357
 358
 359 /* ******************************************************************
 360    FSE : Finite State Entropy coder
 361    header file
 362 ****************************************************************** */
 363 #ifndef FSE_H
 364 #define FSE_H
 365
 366 #if defined (__cplusplus)
 367 extern "C" {
 368 #endif
 369
 370
 371 /* *****************************************
 372 *  Includes
 373 ******************************************/
 374 #include <stddef.h>    /* size_t, ptrdiff_t */
 375
 376
 377 /* *****************************************
 378 *  FSE simple functions
 379 ******************************************/
 380 static size_t FSE_decompress(void* dst,  size_t maxDstSize,
 381                 const void* cSrc, size_t cSrcSize);
 382 /*!
 383 FSE_decompress():
 384     Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
 385     into already allocated destination buffer 'dst', of size 'maxDstSize'.
 386     return : size of regenerated data (<= maxDstSize)
 387              or an error code, which can be tested using FSE_isError()
 388
 389     ** Important ** : FSE_decompress() doesn't decompress non-compressible nor RLE data !!!
 390     Why ? : making this distinction requires a header.
 391     Header management is intentionally delegated to the user layer, which can better manage special cases.
 392 */
 393
 394
 395 /* *****************************************
 396 *  Tool functions
 397 ******************************************/
 398 /* Error Management */
 399 static unsigned    FSE_isError(size_t code);        /* tells if a return value is an error code */
 400
 401
 402
 403 /* *****************************************
 404 *  FSE detailed API
 405 ******************************************/
 406 /*!
 407 FSE_compress() does the following:
 408 1. count symbol occurrence from source[] into table count[]
 409 2. normalize counters so that sum(count[]) == Power_of_2 (2^tableLog)
 410 3. save normalized counters to memory buffer using writeNCount()
 411 4. build encoding table 'CTable' from normalized counters
 412 5. encode the data stream using encoding table 'CTable'
 413
 414 FSE_decompress() does the following:
 415 1. read normalized counters with readNCount()
 416 2. build decoding table 'DTable' from normalized counters
 417 3. decode the data stream using decoding table 'DTable'
 418
 419 The following API allows targeting specific sub-functions for advanced tasks.
 420 For example, it's possible to compress several blocks using the same 'CTable',
 421 or to save and provide normalized distribution using external method.
 422 */
 423
 424
 425 /* *** DECOMPRESSION *** */
 426
 427 /*!
 428 FSE_readNCount():
 429    Read compactly saved 'normalizedCounter' from 'rBuffer'.
 430    return : size read from 'rBuffer'
 431             or an errorCode, which can be tested using FSE_isError()
 432             maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
 433 static  size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
 434
 435 /*!
 436 Constructor and Destructor of type FSE_DTable
 437     Note that its size depends on 'tableLog' */
 438 typedef unsigned FSE_DTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
 439
 440 /*!
 441 FSE_buildDTable():
 442    Builds 'dt', which must be already allocated, using FSE_createDTable()
 443    return : 0,
 444             or an errorCode, which can be tested using FSE_isError() */
 445 static size_t FSE_buildDTable ( FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
 446
 447 /*!
 448 FSE_decompress_usingDTable():
 449    Decompress compressed source 'cSrc' of size 'cSrcSize' using 'dt'
 450    into 'dst' which must be already allocated.
 451    return : size of regenerated data (necessarily <= maxDstSize)
 452             or an errorCode, which can be tested using FSE_isError() */
 453 static  size_t FSE_decompress_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const FSE_DTable* dt);
 454
 455 /*!
 456 Tutorial :
 457 ----------
 458 (Note : these functions only decompress FSE-compressed blocks.
 459  If block is uncompressed, use memcpy() instead
 460  If block is a single repeated byte, use memset() instead )
 461
 462 The first step is to obtain the normalized frequencies of symbols.
 463 This can be performed by FSE_readNCount() if it was saved using FSE_writeNCount().
 464 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
 465 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
 466 or size the table to handle worst case situations (typically 256).
 467 FSE_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
 468 The result of FSE_readNCount() is the number of bytes read from 'rBuffer'.
 469 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
 470 If there is an error, the function will return an error code, which can be tested using FSE_isError().
 471
 472 The next step is to build the decompression tables 'FSE_DTable' from 'normalizedCounter'.
 473 This is performed by the function FSE_buildDTable().
 474 The space required by 'FSE_DTable' must be already allocated using FSE_createDTable().
 475 If there is an error, the function will return an error code, which can be tested using FSE_isError().
 476
 477 'FSE_DTable' can then be used to decompress 'cSrc', with FSE_decompress_usingDTable().
 478 'cSrcSize' must be strictly correct, otherwise decompression will fail.
 479 FSE_decompress_usingDTable() result will tell how many bytes were regenerated (<=maxDstSize).
 480 If there is an error, the function will return an error code, which can be tested using FSE_isError(). (ex: dst buffer too small)
 481 */
 482
 483
 484 #if defined (__cplusplus)
 485 }
 486 #endif
 487
 488 #endif  /* FSE_H */
 489
 490
 491 /* ******************************************************************
 492    bitstream
 493    Part of NewGen Entropy library
 494    header file (to include)
 495    Copyright (C) 2013-2015, Yann Collet.
 496
 497    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 498
 499    Redistribution and use in source and binary forms, with or without
 500    modification, are permitted provided that the following conditions are
 501    met:
 502
 503        * Redistributions of source code must retain the above copyright
 504    notice, this list of conditions and the following disclaimer.
 505        * Redistributions in binary form must reproduce the above
 506    copyright notice, this list of conditions and the following disclaimer
 507    in the documentation and/or other materials provided with the
 508    distribution.
 509
 510    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 511    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 512    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 513    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 514    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 515    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 516    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 517    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 518    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 519    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 520    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 521
 522    You can contact the author at :
 523    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 524    - Public forum : https://groups.google.com/forum/#!forum/lz4c
 525 ****************************************************************** */
 526 #ifndef BITSTREAM_H_MODULE
 527 #define BITSTREAM_H_MODULE
 528
 529 #if defined (__cplusplus)
 530 extern "C" {
 531 #endif
 532
 533
 534 /*
 535 *  This API consists of small unitary functions, which highly benefit from being inlined.
 536 *  Since link-time-optimization is not available for all compilers,
 537 *  these functions are defined into a .h to be included.
 538 */
 539
 540 /**********************************************
 541 *  bitStream decompression API (read backward)
 542 **********************************************/
 543 typedef struct
 544 {
 545     size_t   bitContainer;
 546     unsigned bitsConsumed;
 547     const char* ptr;
 548     const char* start;
 549 } BIT_DStream_t;
 550
 551 typedef enum { BIT_DStream_unfinished = 0,
 552                BIT_DStream_endOfBuffer = 1,
 553                BIT_DStream_completed = 2,
 554                BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */
 555                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
 556
 557 MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
 558 MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
 559 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
 560 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
 561
 562
 563
 564
 565 /******************************************
 566 *  unsafe API
 567 ******************************************/
 568 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
 569 /* faster, but works only if nbBits >= 1 */
 570
 571
 572
 573 /****************************************************************
 574 *  Helper functions
 575 ****************************************************************/
 576 MEM_STATIC unsigned BIT_highbit32 (U32 val)
 577 {
 578 #   if defined(_MSC_VER)   /* Visual */
 579     unsigned long r;
 580     return _BitScanReverse(&r, val) ? (unsigned)r : 0;
 581 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */
 582     return __builtin_clz (val) ^ 31;
 583 #   else   /* Software version */
 584     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 };
 585     U32 v = val;
 586     unsigned r;
 587     v |= v >> 1;
 588     v |= v >> 2;
 589     v |= v >> 4;
 590     v |= v >> 8;
 591     v |= v >> 16;
 592     r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
 593     return r;
 594 #   endif
 595 }
 596
 597
 598 /**********************************************************
 599 * bitStream decoding
 600 **********************************************************/
 601
 602 /*!BIT_initDStream
 603 *  Initialize a BIT_DStream_t.
 604 *  @bitD : a pointer to an already allocated BIT_DStream_t structure
 605 *  @srcBuffer must point at the beginning of a bitStream
 606 *  @srcSize must be the exact size of the bitStream
 607 *  @result : size of stream (== srcSize) or an errorCode if a problem is detected
 608 */
 609 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
 610 {
 611     if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
 612
 613     if (srcSize >=  sizeof(size_t))   /* normal case */
 614     {
 615         U32 contain32;
 616         bitD->start = (const char*)srcBuffer;
 617         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(size_t);
 618         bitD->bitContainer = MEM_readLEST(bitD->ptr);
 619         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
 620         if (contain32 == 0) return ERROR(GENERIC);   /* endMark not present */
 621         bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
 622     }
 623     else
 624     {
 625         U32 contain32;
 626         bitD->start = (const char*)srcBuffer;
 627         bitD->ptr   = bitD->start;
 628         bitD->bitContainer = *(const BYTE*)(bitD->start);
 629         switch(srcSize)
 630         {
 631             case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);/* fall-through */
 632             case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);/* fall-through */
 633             case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);/* fall-through */
 634             case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24; /* fall-through */
 635             case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16; /* fall-through */
 636             case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) <<  8; /* fall-through */
 637             default: break;
 638         }
 639         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
 640         if (contain32 == 0) return ERROR(GENERIC);   /* endMark not present */
 641         bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
 642         bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
 643     }
 644
 645     return srcSize;
 646 }
 647
 648 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
 649 {
 650     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
 651     return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
 652 }
 653
 654 /*! BIT_lookBitsFast :
 655 *   unsafe version; only works if nbBits >= 1 */
 656 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
 657 {
 658     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
 659     return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
 660 }
 661
 662 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
 663 {
 664     bitD->bitsConsumed += nbBits;
 665 }
 666
 667 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
 668 {
 669     size_t value = BIT_lookBits(bitD, nbBits);
 670     BIT_skipBits(bitD, nbBits);
 671     return value;
 672 }
 673
 674 /*!BIT_readBitsFast :
 675 *  unsafe version; only works if nbBits >= 1 */
 676 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
 677 {
 678     size_t value = BIT_lookBitsFast(bitD, nbBits);
 679     BIT_skipBits(bitD, nbBits);
 680     return value;
 681 }
 682
 683 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
 684 {
 685     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should never happen */
 686         return BIT_DStream_overflow;
 687
 688     if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
 689     {
 690         bitD->ptr -= bitD->bitsConsumed >> 3;
 691         bitD->bitsConsumed &= 7;
 692         bitD->bitContainer = MEM_readLEST(bitD->ptr);
 693         return BIT_DStream_unfinished;
 694     }
 695     if (bitD->ptr == bitD->start)
 696     {
 697         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
 698         return BIT_DStream_completed;
 699     }
 700     {
 701         U32 nbBytes = bitD->bitsConsumed >> 3;
 702         BIT_DStream_status result = BIT_DStream_unfinished;
 703         if (bitD->ptr - nbBytes < bitD->start)
 704         {
 705             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
 706             result = BIT_DStream_endOfBuffer;
 707         }
 708         bitD->ptr -= nbBytes;
 709         bitD->bitsConsumed -= nbBytes*8;
 710         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
 711         return result;
 712     }
 713 }
 714
 715 /*! BIT_endOfDStream
 716 *   @return Tells if DStream has reached its exact end
 717 */
 718 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
 719 {
 720     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
 721 }
 722
 723 #if defined (__cplusplus)
 724 }
 725 #endif
 726
 727 #endif /* BITSTREAM_H_MODULE */
 728
 729
 730
 731 /* ******************************************************************
 732    FSE : Finite State Entropy coder
 733    header file for static linking (only)
 734    Copyright (C) 2013-2015, Yann Collet
 735
 736    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 737
 738    Redistribution and use in source and binary forms, with or without
 739    modification, are permitted provided that the following conditions are
 740    met:
 741
 742        * Redistributions of source code must retain the above copyright
 743    notice, this list of conditions and the following disclaimer.
 744        * Redistributions in binary form must reproduce the above
 745    copyright notice, this list of conditions and the following disclaimer
 746    in the documentation and/or other materials provided with the
 747    distribution.
 748
 749    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 750    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 751    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 752    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 753    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 754    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 755    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 756    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 757    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 758    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 759    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 760
 761    You can contact the author at :
 762    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 763    - Public forum : https://groups.google.com/forum/#!forum/lz4c
 764 ****************************************************************** */
 765 #ifndef FSE_STATIC_H
 766 #define FSE_STATIC_H
 767
 768 #if defined (__cplusplus)
 769 extern "C" {
 770 #endif
 771
 772
 773 /* *****************************************
 774 *  Static allocation
 775 *******************************************/
 776 /* FSE buffer bounds */
 777 #define FSE_NCOUNTBOUND 512
 778 #define FSE_BLOCKBOUND(size) (size + (size>>7))
 779 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
 780
 781 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
 782 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue)   (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
 783 #define FSE_DTABLE_SIZE_U32(maxTableLog)                   (1 + (1<<maxTableLog))
 784
 785
 786 /* *****************************************
 787 *  FSE advanced API
 788 *******************************************/
 789 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
 790 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
 791
 792 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
 793 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
 794
 795
 796
 797 /* *****************************************
 798 *  FSE symbol decompression API
 799 *******************************************/
 800 typedef struct
 801 {
 802     size_t      state;
 803     const void* table;   /* precise table may vary, depending on U16 */
 804 } FSE_DState_t;
 805
 806
 807 static void     FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
 808
 809 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
 810
 811 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
 812
 813
 814 /* *****************************************
 815 *  FSE unsafe API
 816 *******************************************/
 817 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
 818 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
 819
 820
 821 /* *****************************************
 822 *  Implementation of inlined functions
 823 *******************************************/
 824 /* decompression */
 825
 826 typedef struct {
 827     U16 tableLog;
 828     U16 fastMode;
 829 } FSE_DTableHeader;   /* sizeof U32 */
 830
 831 typedef struct
 832 {
 833     unsigned short newState;
 834     unsigned char  symbol;
 835     unsigned char  nbBits;
 836 } FSE_decode_t;   /* size == U32 */
 837
 838 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
 839 {
 840     FSE_DTableHeader DTableH;
 841     memcpy(&DTableH, dt, sizeof(DTableH));
 842     DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
 843     BIT_reloadDStream(bitD);
 844     DStatePtr->table = dt + 1;
 845 }
 846
 847 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
 848 {
 849     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
 850     const U32  nbBits = DInfo.nbBits;
 851     BYTE symbol = DInfo.symbol;
 852     size_t lowBits = BIT_readBits(bitD, nbBits);
 853
 854     DStatePtr->state = DInfo.newState + lowBits;
 855     return symbol;
 856 }
 857
 858 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
 859 {
 860     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
 861     const U32 nbBits = DInfo.nbBits;
 862     BYTE symbol = DInfo.symbol;
 863     size_t lowBits = BIT_readBitsFast(bitD, nbBits);
 864
 865     DStatePtr->state = DInfo.newState + lowBits;
 866     return symbol;
 867 }
 868
 869 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
 870 {
 871     return DStatePtr->state == 0;
 872 }
 873
 874
 875 #if defined (__cplusplus)
 876 }
 877 #endif
 878
 879 #endif  /* FSE_STATIC_H */
 880
 881 /* ******************************************************************
 882    FSE : Finite State Entropy coder
 883    Copyright (C) 2013-2015, Yann Collet.
 884
 885    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 886
 887    Redistribution and use in source and binary forms, with or without
 888    modification, are permitted provided that the following conditions are
 889    met:
 890
 891        * Redistributions of source code must retain the above copyright
 892    notice, this list of conditions and the following disclaimer.
 893        * Redistributions in binary form must reproduce the above
 894    copyright notice, this list of conditions and the following disclaimer
 895    in the documentation and/or other materials provided with the
 896    distribution.
 897
 898    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 899    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 900    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 901    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 902    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 903    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 904    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 905    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 906    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 907    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 908    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 909
 910     You can contact the author at :
 911     - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
 912     - Public forum : https://groups.google.com/forum/#!forum/lz4c
 913 ****************************************************************** */
 914
 915 #ifndef FSE_COMMONDEFS_ONLY
 916
 917 /* **************************************************************
 918 *  Tuning parameters
 919 ****************************************************************/
 920 /*!MEMORY_USAGE :
 921 *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
 922 *  Increasing memory usage improves compression ratio
 923 *  Reduced memory usage can improve speed, due to cache effect
 924 *  Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
 925 #define FSE_MAX_MEMORY_USAGE 14
 926 #define FSE_DEFAULT_MEMORY_USAGE 13
 927
 928 /*!FSE_MAX_SYMBOL_VALUE :
 929 *  Maximum symbol value authorized.
 930 *  Required for proper stack allocation */
 931 #define FSE_MAX_SYMBOL_VALUE 255
 932
 933
 934 /* **************************************************************
 935 *  template functions type & suffix
 936 ****************************************************************/
 937 #define FSE_FUNCTION_TYPE BYTE
 938 #define FSE_FUNCTION_EXTENSION
 939 #define FSE_DECODE_TYPE FSE_decode_t
 940
 941
 942 #endif   /* !FSE_COMMONDEFS_ONLY */
 943
 944 /* **************************************************************
 945 *  Compiler specifics
 946 ****************************************************************/
 947 #ifdef _MSC_VER    /* Visual Studio */
 948 #  define FORCE_INLINE static __forceinline
 949 #  include <intrin.h>                    /* For Visual 2005 */
 950 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
 951 #  pragma warning(disable : 4214)        /* disable: C4214: non-int bitfields */
 952 #else
 953 #  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
 954 #    ifdef __GNUC__
 955 #      define FORCE_INLINE static inline __attribute__((always_inline))
 956 #    else
 957 #      define FORCE_INLINE static inline
 958 #    endif
 959 #  else
 960 #    define FORCE_INLINE static
 961 #  endif /* __STDC_VERSION__ */
 962 #endif
 963
 964
 965 /* **************************************************************
 966 *  Dependencies
 967 ****************************************************************/
 968 #include <stdlib.h>     /* malloc, free, qsort */
 969 #include <string.h>     /* memcpy, memset */
 970 #include <stdio.h>      /* printf (debug) */
 971
 972
 973 /* ***************************************************************
 974 *  Constants
 975 *****************************************************************/
 976 #define FSE_MAX_TABLELOG  (FSE_MAX_MEMORY_USAGE-2)
 977 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
 978 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
 979 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
 980 #define FSE_MIN_TABLELOG 5
 981
 982 #define FSE_TABLELOG_ABSOLUTE_MAX 15
 983 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
 984 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
 985 #endif
 986
 987
 988 /* **************************************************************
 989 *  Error Management
 990 ****************************************************************/
 991 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
 992
 993
 994 /* **************************************************************
 995 *  Complex types
 996 ****************************************************************/
 997 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
 998
 999
1000 /*-**************************************************************
1001 *  Templates
1002 ****************************************************************/
1003 /*
1004   designed to be included
1005   for type-specific functions (template emulation in C)
1006   Objective is to write these functions only once, for improved maintenance
1007 */
1008
1009 /* safety checks */
1010 #ifndef FSE_FUNCTION_EXTENSION
1011 #  error "FSE_FUNCTION_EXTENSION must be defined"
1012 #endif
1013 #ifndef FSE_FUNCTION_TYPE
1014 #  error "FSE_FUNCTION_TYPE must be defined"
1015 #endif
1016
1017 /* Function names */
1018 #define FSE_CAT(X,Y) X##Y
1019 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
1020 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
1021
1022 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
1023
1024
1025 static size_t FSE_buildDTable(FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1026 {
1027     FSE_DTableHeader DTableH;
1028     void* const tdPtr = dt+1;   /* because dt is unsigned, 32-bits aligned on 32-bits */
1029     FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*) (tdPtr);
1030     const U32 tableSize = 1 << tableLog;
1031     const U32 tableMask = tableSize-1;
1032     const U32 step = FSE_tableStep(tableSize);
1033     U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
1034     U32 position = 0;
1035     U32 highThreshold = tableSize-1;
1036     const S16 largeLimit= (S16)(1 << (tableLog-1));
1037     U32 noLarge = 1;
1038     U32 s;
1039
1040     /* Sanity Checks */
1041     if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1042     if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1043
1044     /* Init, lay down lowprob symbols */
1045     memset(tableDecode, 0, sizeof(FSE_DECODE_TYPE) * (maxSymbolValue+1) );   /* useless init, but keep static analyzer happy, and we don't need to performance optimize legacy decoders */
1046     DTableH.tableLog = (U16)tableLog;
1047     for (s=0; s<=maxSymbolValue; s++)
1048     {
1049         if (normalizedCounter[s]==-1)
1050         {
1051             tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
1052             symbolNext[s] = 1;
1053         }
1054         else
1055         {
1056             if (normalizedCounter[s] >= largeLimit) noLarge=0;
1057             symbolNext[s] = normalizedCounter[s];
1058         }
1059     }
1060
1061     /* Spread symbols */
1062     for (s=0; s<=maxSymbolValue; s++)
1063     {
1064         int i;
1065         for (i=0; i<normalizedCounter[s]; i++)
1066         {
1067             tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
1068             position = (position + step) & tableMask;
1069             while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
1070         }
1071     }
1072
1073     if (position!=0) return ERROR(GENERIC);   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1074
1075     /* Build Decoding table */
1076     {
1077         U32 i;
1078         for (i=0; i<tableSize; i++)
1079         {
1080             FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
1081             U16 nextState = symbolNext[symbol]++;
1082             tableDecode[i].nbBits = (BYTE) (tableLog - BIT_highbit32 ((U32)nextState) );
1083             tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
1084         }
1085     }
1086
1087     DTableH.fastMode = (U16)noLarge;
1088     memcpy(dt, &DTableH, sizeof(DTableH));
1089     return 0;
1090 }
1091
1092
1093 #ifndef FSE_COMMONDEFS_ONLY
1094 /******************************************
1095 *  FSE helper functions
1096 ******************************************/
1097 static unsigned FSE_isError(size_t code) { return ERR_isError(code); }
1098
1099
1100 /****************************************************************
1101 *  FSE NCount encoding-decoding
1102 ****************************************************************/
1103 static short FSE_abs(short a)
1104 {
1105     return a<0 ? -a : a;
1106 }
1107
1108 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1109                  const void* headerBuffer, size_t hbSize)
1110 {
1111     const BYTE* const istart = (const BYTE*) headerBuffer;
1112     const BYTE* const iend = istart + hbSize;
1113     const BYTE* ip = istart;
1114     int nbBits;
1115     int remaining;
1116     int threshold;
1117     U32 bitStream;
1118     int bitCount;
1119     unsigned charnum = 0;
1120     int previous0 = 0;
1121
1122     if (hbSize < 4) return ERROR(srcSize_wrong);
1123     bitStream = MEM_readLE32(ip);
1124     nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG;   /* extract tableLog */
1125     if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1126     bitStream >>= 4;
1127     bitCount = 4;
1128     *tableLogPtr = nbBits;
1129     remaining = (1<<nbBits)+1;
1130     threshold = 1<<nbBits;
1131     nbBits++;
1132
1133     while ((remaining>1) && (charnum<=*maxSVPtr))
1134     {
1135         if (previous0)
1136         {
1137             unsigned n0 = charnum;
1138             while ((bitStream & 0xFFFF) == 0xFFFF)
1139             {
1140                 n0+=24;
1141                 if (ip < iend-5)
1142                 {
1143                     ip+=2;
1144                     bitStream = MEM_readLE32(ip) >> bitCount;
1145                 }
1146                 else
1147                 {
1148                     bitStream >>= 16;
1149                     bitCount+=16;
1150                 }
1151             }
1152             while ((bitStream & 3) == 3)
1153             {
1154                 n0+=3;
1155                 bitStream>>=2;
1156                 bitCount+=2;
1157             }
1158             n0 += bitStream & 3;
1159             bitCount += 2;
1160             if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1161             while (charnum < n0) normalizedCounter[charnum++] = 0;
1162             if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1163             {
1164                 ip += bitCount>>3;
1165                 bitCount &= 7;
1166                 bitStream = MEM_readLE32(ip) >> bitCount;
1167             }
1168             else
1169                 bitStream >>= 2;
1170         }
1171         {
1172             const short max = (short)((2*threshold-1)-remaining);
1173             short count;
1174
1175             if ((bitStream & (threshold-1)) < (U32)max)
1176             {
1177                 count = (short)(bitStream & (threshold-1));
1178                 bitCount   += nbBits-1;
1179             }
1180             else
1181             {
1182                 count = (short)(bitStream & (2*threshold-1));
1183                 if (count >= threshold) count -= max;
1184                 bitCount   += nbBits;
1185             }
1186
1187             count--;   /* extra accuracy */
1188             remaining -= FSE_abs(count);
1189             normalizedCounter[charnum++] = count;
1190             previous0 = !count;
1191             while (remaining < threshold)
1192             {
1193                 nbBits--;
1194                 threshold >>= 1;
1195             }
1196
1197             {
1198                 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
1199                 {
1200                     ip += bitCount>>3;
1201                     bitCount &= 7;
1202                 }
1203                 else
1204                 {
1205                     bitCount -= (int)(8 * (iend - 4 - ip));
1206                     ip = iend - 4;
1207                 }
1208                 bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1209             }
1210         }
1211     }
1212     if (remaining != 1) return ERROR(GENERIC);
1213     *maxSVPtr = charnum-1;
1214
1215     ip += (bitCount+7)>>3;
1216     if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1217     return ip-istart;
1218 }
1219
1220
1221 /*********************************************************
1222 *  Decompression (Byte symbols)
1223 *********************************************************/
1224 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
1225 {
1226     void* ptr = dt;
1227     FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1228     void* dPtr = dt + 1;
1229     FSE_decode_t* const cell = (FSE_decode_t*)dPtr;
1230
1231     DTableH->tableLog = 0;
1232     DTableH->fastMode = 0;
1233
1234     cell->newState = 0;
1235     cell->symbol = symbolValue;
1236     cell->nbBits = 0;
1237
1238     return 0;
1239 }
1240
1241
1242 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
1243 {
1244     void* ptr = dt;
1245     FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
1246     void* dPtr = dt + 1;
1247     FSE_decode_t* const dinfo = (FSE_decode_t*)dPtr;
1248     const unsigned tableSize = 1 << nbBits;
1249     const unsigned tableMask = tableSize - 1;
1250     const unsigned maxSymbolValue = tableMask;
1251     unsigned s;
1252
1253     /* Sanity checks */
1254     if (nbBits < 1) return ERROR(GENERIC);         /* min size */
1255
1256     /* Build Decoding Table */
1257     DTableH->tableLog = (U16)nbBits;
1258     DTableH->fastMode = 1;
1259     for (s=0; s<=maxSymbolValue; s++)
1260     {
1261         dinfo[s].newState = 0;
1262         dinfo[s].symbol = (BYTE)s;
1263         dinfo[s].nbBits = (BYTE)nbBits;
1264     }
1265
1266     return 0;
1267 }
1268
1269 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
1270           void* dst, size_t maxDstSize,
1271     const void* cSrc, size_t cSrcSize,
1272     const FSE_DTable* dt, const unsigned fast)
1273 {
1274     BYTE* const ostart = (BYTE*) dst;
1275     BYTE* op = ostart;
1276     BYTE* const omax = op + maxDstSize;
1277     BYTE* const olimit = omax-3;
1278
1279     BIT_DStream_t bitD;
1280     FSE_DState_t state1;
1281     FSE_DState_t state2;
1282     size_t errorCode;
1283
1284     /* Init */
1285     errorCode = BIT_initDStream(&bitD, cSrc, cSrcSize);   /* replaced last arg by maxCompressed Size */
1286     if (FSE_isError(errorCode)) return errorCode;
1287
1288     FSE_initDState(&state1, &bitD, dt);
1289     FSE_initDState(&state2, &bitD, dt);
1290
1291 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
1292
1293     /* 4 symbols per loop */
1294     for ( ; (BIT_reloadDStream(&bitD)==BIT_DStream_unfinished) && (op<olimit) ; op+=4)
1295     {
1296         op[0] = FSE_GETSYMBOL(&state1);
1297
1298         if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1299             BIT_reloadDStream(&bitD);
1300
1301         op[1] = FSE_GETSYMBOL(&state2);
1302
1303         if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1304             { if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) { op+=2; break; } }
1305
1306         op[2] = FSE_GETSYMBOL(&state1);
1307
1308         if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1309             BIT_reloadDStream(&bitD);
1310
1311         op[3] = FSE_GETSYMBOL(&state2);
1312     }
1313
1314     /* tail */
1315     /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
1316     while (1)
1317     {
1318         if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
1319             break;
1320
1321         *op++ = FSE_GETSYMBOL(&state1);
1322
1323         if ( (BIT_reloadDStream(&bitD)>BIT_DStream_completed) || (op==omax) || (BIT_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
1324             break;
1325
1326         *op++ = FSE_GETSYMBOL(&state2);
1327     }
1328
1329     /* end ? */
1330     if (BIT_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
1331         return op-ostart;
1332
1333     if (op==omax) return ERROR(dstSize_tooSmall);   /* dst buffer is full, but cSrc unfinished */
1334
1335     return ERROR(corruption_detected);
1336 }
1337
1338
1339 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
1340                             const void* cSrc, size_t cSrcSize,
1341                             const FSE_DTable* dt)
1342 {
1343     FSE_DTableHeader DTableH;
1344     U32 fastMode;
1345
1346     memcpy(&DTableH, dt, sizeof(DTableH));
1347     fastMode = DTableH.fastMode;
1348
1349     /* select fast mode (static) */
1350     if (fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1351     return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1352 }
1353
1354
1355 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1356 {
1357     const BYTE* const istart = (const BYTE*)cSrc;
1358     const BYTE* ip = istart;
1359     short counting[FSE_MAX_SYMBOL_VALUE+1];
1360     DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
1361     unsigned tableLog;
1362     unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
1363     size_t errorCode;
1364
1365     if (cSrcSize<2) return ERROR(srcSize_wrong);   /* too small input size */
1366
1367     /* normal FSE decoding mode */
1368     errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1369     if (FSE_isError(errorCode)) return errorCode;
1370     if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);   /* too small input size */
1371     ip += errorCode;
1372     cSrcSize -= errorCode;
1373
1374     errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
1375     if (FSE_isError(errorCode)) return errorCode;
1376
1377     /* always return, even if it is an error code */
1378     return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
1379 }
1380
1381
1382
1383 #endif   /* FSE_COMMONDEFS_ONLY */
1384
1385
1386 /* ******************************************************************
1387    Huff0 : Huffman coder, part of New Generation Entropy library
1388    header file
1389    Copyright (C) 2013-2015, Yann Collet.
1390
1391    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1392
1393    Redistribution and use in source and binary forms, with or without
1394    modification, are permitted provided that the following conditions are
1395    met:
1396
1397        * Redistributions of source code must retain the above copyright
1398    notice, this list of conditions and the following disclaimer.
1399        * Redistributions in binary form must reproduce the above
1400    copyright notice, this list of conditions and the following disclaimer
1401    in the documentation and/or other materials provided with the
1402    distribution.
1403
1404    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1405    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1406    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1407    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1408    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1409    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1410    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1411    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1412    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1413    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1414    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1415
1416    You can contact the author at :
1417    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1418    - Public forum : https://groups.google.com/forum/#!forum/lz4c
1419 ****************************************************************** */
1420 #ifndef HUFF0_H
1421 #define HUFF0_H
1422
1423 #if defined (__cplusplus)
1424 extern "C" {
1425 #endif
1426
1427
1428 /* ****************************************
1429 *  Dependency
1430 ******************************************/
1431 #include <stddef.h>    /* size_t */
1432
1433
1434 /* ****************************************
1435 *  Huff0 simple functions
1436 ******************************************/
1437 static size_t HUF_decompress(void* dst,  size_t dstSize,
1438                 const void* cSrc, size_t cSrcSize);
1439 /*!
1440 HUF_decompress():
1441     Decompress Huff0 data from buffer 'cSrc', of size 'cSrcSize',
1442     into already allocated destination buffer 'dst', of size 'dstSize'.
1443     'dstSize' must be the exact size of original (uncompressed) data.
1444     Note : in contrast with FSE, HUF_decompress can regenerate RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data, because it knows size to regenerate.
1445     @return : size of regenerated data (== dstSize)
1446               or an error code, which can be tested using HUF_isError()
1447 */
1448
1449
1450 /* ****************************************
1451 *  Tool functions
1452 ******************************************/
1453 /* Error Management */
1454 static unsigned    HUF_isError(size_t code);        /* tells if a return value is an error code */
1455
1456
1457 #if defined (__cplusplus)
1458 }
1459 #endif
1460
1461 #endif   /* HUFF0_H */
1462
1463
1464 /* ******************************************************************
1465    Huff0 : Huffman coder, part of New Generation Entropy library
1466    header file for static linking (only)
1467    Copyright (C) 2013-2015, Yann Collet
1468
1469    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1470
1471    Redistribution and use in source and binary forms, with or without
1472    modification, are permitted provided that the following conditions are
1473    met:
1474
1475        * Redistributions of source code must retain the above copyright
1476    notice, this list of conditions and the following disclaimer.
1477        * Redistributions in binary form must reproduce the above
1478    copyright notice, this list of conditions and the following disclaimer
1479    in the documentation and/or other materials provided with the
1480    distribution.
1481
1482    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1483    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1484    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1485    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1486    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1487    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1488    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1489    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1490    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1491    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1492    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1493
1494    You can contact the author at :
1495    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1496    - Public forum : https://groups.google.com/forum/#!forum/lz4c
1497 ****************************************************************** */
1498 #ifndef HUFF0_STATIC_H
1499 #define HUFF0_STATIC_H
1500
1501 #if defined (__cplusplus)
1502 extern "C" {
1503 #endif
1504
1505
1506
1507 /* ****************************************
1508 *  Static allocation macros
1509 ******************************************/
1510 /* static allocation of Huff0's DTable */
1511 #define HUF_DTABLE_SIZE(maxTableLog)   (1 + (1<<maxTableLog))  /* nb Cells; use unsigned short for X2, unsigned int for X4 */
1512 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1513         unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1514 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1515         unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1516 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1517         unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1518
1519
1520 /* ****************************************
1521 *  Advanced decompression functions
1522 ******************************************/
1523 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
1524 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-symbols decoder */
1525
1526
1527 /* ****************************************
1528 *  Huff0 detailed API
1529 ******************************************/
1530 /*!
1531 HUF_decompress() does the following:
1532 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1533 2. build Huffman table from save, using HUF_readDTableXn()
1534 3. decode 1 or 4 segments in parallel using HUF_decompressSXn_usingDTable
1535
1536 */
1537 static size_t HUF_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1538 static size_t HUF_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1539
1540 static size_t HUF_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1541 static size_t HUF_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1542
1543
1544 #if defined (__cplusplus)
1545 }
1546 #endif
1547
1548 #endif /* HUFF0_STATIC_H */
1549
1550
1551
1552 /* ******************************************************************
1553    Huff0 : Huffman coder, part of New Generation Entropy library
1554    Copyright (C) 2013-2015, Yann Collet.
1555
1556    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1557
1558    Redistribution and use in source and binary forms, with or without
1559    modification, are permitted provided that the following conditions are
1560    met:
1561
1562        * Redistributions of source code must retain the above copyright
1563    notice, this list of conditions and the following disclaimer.
1564        * Redistributions in binary form must reproduce the above
1565    copyright notice, this list of conditions and the following disclaimer
1566    in the documentation and/or other materials provided with the
1567    distribution.
1568
1569    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1570    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1571    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1572    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1573    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1574    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1575    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1576    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1577    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1578    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1579    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1580
1581     You can contact the author at :
1582     - FSE+Huff0 source repository : https://github.com/Cyan4973/FiniteStateEntropy
1583 ****************************************************************** */
1584
1585 /* **************************************************************
1586 *  Compiler specifics
1587 ****************************************************************/
1588 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1589 /* inline is defined */
1590 #elif defined(_MSC_VER)
1591 #  define inline __inline
1592 #else
1593 #  define inline /* disable inline */
1594 #endif
1595
1596
1597 #ifdef _MSC_VER    /* Visual Studio */
1598 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1599 #endif
1600
1601
1602 /* **************************************************************
1603 *  Includes
1604 ****************************************************************/
1605 #include <stdlib.h>     /* malloc, free, qsort */
1606 #include <string.h>     /* memcpy, memset */
1607 #include <stdio.h>      /* printf (debug) */
1608
1609
1610 /* **************************************************************
1611 *  Constants
1612 ****************************************************************/
1613 #define HUF_ABSOLUTEMAX_TABLELOG  16   /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1614 #define HUF_MAX_TABLELOG  12           /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1615 #define HUF_DEFAULT_TABLELOG  HUF_MAX_TABLELOG   /* tableLog by default, when not specified */
1616 #define HUF_MAX_SYMBOL_VALUE 255
1617 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1618 #  error "HUF_MAX_TABLELOG is too large !"
1619 #endif
1620
1621
1622 /* **************************************************************
1623 *  Error Management
1624 ****************************************************************/
1625 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1626 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1627
1628
1629
1630 /*-*******************************************************
1631 *  Huff0 : Huffman block decompression
1632 *********************************************************/
1633 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2;   /* single-symbol decoding */
1634
1635 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4;  /* double-symbols decoding */
1636
1637 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1638
1639 /*! HUF_readStats
1640     Read compact Huffman tree, saved by HUF_writeCTable
1641     @huffWeight : destination buffer
1642     @return : size read from `src`
1643 */
1644 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1645                             U32* nbSymbolsPtr, U32* tableLogPtr,
1646                             const void* src, size_t srcSize)
1647 {
1648     U32 weightTotal;
1649     U32 tableLog;
1650     const BYTE* ip = (const BYTE*) src;
1651     size_t iSize;
1652     size_t oSize;
1653     U32 n;
1654
1655     if (!srcSize) return ERROR(srcSize_wrong);
1656     iSize = ip[0];
1657     //memset(huffWeight, 0, hwSize);   /* is not necessary, even though some analyzer complain ... */
1658
1659     if (iSize >= 128)  /* special header */
1660     {
1661         if (iSize >= (242))   /* RLE */
1662         {
1663             static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1664             oSize = l[iSize-242];
1665             memset(huffWeight, 1, hwSize);
1666             iSize = 0;
1667         }
1668         else   /* Incompressible */
1669         {
1670             oSize = iSize - 127;
1671             iSize = ((oSize+1)/2);
1672             if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1673             if (oSize >= hwSize) return ERROR(corruption_detected);
1674             ip += 1;
1675             for (n=0; n<oSize; n+=2)
1676             {
1677                 huffWeight[n]   = ip[n/2] >> 4;
1678                 huffWeight[n+1] = ip[n/2] & 15;
1679             }
1680         }
1681     }
1682     else  /* header compressed with FSE (normal case) */
1683     {
1684         if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1685         oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize);   /* max (hwSize-1) values decoded, as last one is implied */
1686         if (FSE_isError(oSize)) return oSize;
1687     }
1688
1689     /* collect weight stats */
1690     memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1691     weightTotal = 0;
1692     for (n=0; n<oSize; n++)
1693     {
1694         if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1695         rankStats[huffWeight[n]]++;
1696         weightTotal += (1 << huffWeight[n]) >> 1;
1697     }
1698     if (weightTotal == 0) return ERROR(corruption_detected);
1699
1700     /* get last non-null symbol weight (implied, total must be 2^n) */
1701     tableLog = BIT_highbit32(weightTotal) + 1;
1702     if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1703     {
1704         U32 total = 1 << tableLog;
1705         U32 rest = total - weightTotal;
1706         U32 verif = 1 << BIT_highbit32(rest);
1707         U32 lastWeight = BIT_highbit32(rest) + 1;
1708         if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
1709         huffWeight[oSize] = (BYTE)lastWeight;
1710         rankStats[lastWeight]++;
1711     }
1712
1713     /* check tree construction validity */
1714     if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected);   /* by construction : at least 2 elts of rank 1, must be even */
1715
1716     /* results */
1717     *nbSymbolsPtr = (U32)(oSize+1);
1718     *tableLogPtr = tableLog;
1719     return iSize+1;
1720 }
1721
1722
1723 /**************************/
1724 /* single-symbol decoding */
1725 /**************************/
1726
1727 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1728 {
1729     BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1730     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];   /* large enough for values from 0 to 16 */
1731     U32 tableLog = 0;
1732     size_t iSize;
1733     U32 nbSymbols = 0;
1734     U32 n;
1735     U32 nextRankStart;
1736     void* const dtPtr = DTable + 1;
1737     HUF_DEltX2* const dt = (HUF_DEltX2*)dtPtr;
1738
1739     HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16));   /* if compilation fails here, assertion is false */
1740     //memset(huffWeight, 0, sizeof(huffWeight));   /* is not necessary, even though some analyzer complain ... */
1741
1742     iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1743     if (HUF_isError(iSize)) return iSize;
1744
1745     /* check result */
1746     if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge);   /* DTable is too small */
1747     DTable[0] = (U16)tableLog;   /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1748
1749     /* Prepare ranks */
1750     nextRankStart = 0;
1751     for (n=1; n<=tableLog; n++)
1752     {
1753         U32 current = nextRankStart;
1754         nextRankStart += (rankVal[n] << (n-1));
1755         rankVal[n] = current;
1756     }
1757
1758     /* fill DTable */
1759     for (n=0; n<nbSymbols; n++)
1760     {
1761         const U32 w = huffWeight[n];
1762         const U32 length = (1 << w) >> 1;
1763         U32 i;
1764         HUF_DEltX2 D;
1765         D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1766         for (i = rankVal[w]; i < rankVal[w] + length; i++)
1767             dt[i] = D;
1768         rankVal[w] += length;
1769     }
1770
1771     return iSize;
1772 }
1773
1774 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1775 {
1776         const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1777         const BYTE c = dt[val].byte;
1778         BIT_skipBits(Dstream, dt[val].nbBits);
1779         return c;
1780 }
1781
1782 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1783     *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1784
1785 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1786     if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1787         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1788
1789 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1790     if (MEM_64bits()) \
1791         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1792
1793 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1794 {
1795     BYTE* const pStart = p;
1796
1797     /* up to 4 symbols at a time */
1798     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1799     {
1800         HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1801         HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1802         HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1803         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1804     }
1805
1806     /* closer to the end */
1807     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1808         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1809
1810     /* no more data to retrieve from bitstream, hence no need to reload */
1811     while (p < pEnd)
1812         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1813
1814     return pEnd-pStart;
1815 }
1816
1817
1818 static size_t HUF_decompress4X2_usingDTable(
1819           void* dst,  size_t dstSize,
1820     const void* cSrc, size_t cSrcSize,
1821     const U16* DTable)
1822 {
1823     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
1824
1825     {
1826         const BYTE* const istart = (const BYTE*) cSrc;
1827         BYTE* const ostart = (BYTE*) dst;
1828         BYTE* const oend = ostart + dstSize;
1829         const void* const dtPtr = DTable;
1830         const HUF_DEltX2* const dt = ((const HUF_DEltX2*)dtPtr) +1;
1831         const U32 dtLog = DTable[0];
1832         size_t errorCode;
1833
1834         /* Init */
1835         BIT_DStream_t bitD1;
1836         BIT_DStream_t bitD2;
1837         BIT_DStream_t bitD3;
1838         BIT_DStream_t bitD4;
1839         const size_t length1 = MEM_readLE16(istart);
1840         const size_t length2 = MEM_readLE16(istart+2);
1841         const size_t length3 = MEM_readLE16(istart+4);
1842         size_t length4;
1843         const BYTE* const istart1 = istart + 6;  /* jumpTable */
1844         const BYTE* const istart2 = istart1 + length1;
1845         const BYTE* const istart3 = istart2 + length2;
1846         const BYTE* const istart4 = istart3 + length3;
1847         const size_t segmentSize = (dstSize+3) / 4;
1848         BYTE* const opStart2 = ostart + segmentSize;
1849         BYTE* const opStart3 = opStart2 + segmentSize;
1850         BYTE* const opStart4 = opStart3 + segmentSize;
1851         BYTE* op1 = ostart;
1852         BYTE* op2 = opStart2;
1853         BYTE* op3 = opStart3;
1854         BYTE* op4 = opStart4;
1855         U32 endSignal;
1856
1857         length4 = cSrcSize - (length1 + length2 + length3 + 6);
1858         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
1859         errorCode = BIT_initDStream(&bitD1, istart1, length1);
1860         if (HUF_isError(errorCode)) return errorCode;
1861         errorCode = BIT_initDStream(&bitD2, istart2, length2);
1862         if (HUF_isError(errorCode)) return errorCode;
1863         errorCode = BIT_initDStream(&bitD3, istart3, length3);
1864         if (HUF_isError(errorCode)) return errorCode;
1865         errorCode = BIT_initDStream(&bitD4, istart4, length4);
1866         if (HUF_isError(errorCode)) return errorCode;
1867
1868         /* 16-32 symbols per loop (4-8 symbols per stream) */
1869         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1870         for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1871         {
1872             HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1873             HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1874             HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1875             HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1876             HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1877             HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1878             HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1879             HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1880             HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1881             HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1882             HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1883             HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1884             HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1885             HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1886             HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1887             HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1888
1889             endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1890         }
1891
1892         /* check corruption */
1893         if (op1 > opStart2) return ERROR(corruption_detected);
1894         if (op2 > opStart3) return ERROR(corruption_detected);
1895         if (op3 > opStart4) return ERROR(corruption_detected);
1896         /* note : op4 supposed already verified within main loop */
1897
1898         /* finish bitStreams one by one */
1899         HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1900         HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1901         HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1902         HUF_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
1903
1904         /* check */
1905         endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1906         if (!endSignal) return ERROR(corruption_detected);
1907
1908         /* decoded size */
1909         return dstSize;
1910     }
1911 }
1912
1913
1914 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1915 {
1916     HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1917     const BYTE* ip = (const BYTE*) cSrc;
1918     size_t errorCode;
1919
1920     errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1921     if (HUF_isError(errorCode)) return errorCode;
1922     if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1923     ip += errorCode;
1924     cSrcSize -= errorCode;
1925
1926     return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1927 }
1928
1929
1930 /***************************/
1931 /* double-symbols decoding */
1932 /***************************/
1933
1934 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1935                            const U32* rankValOrigin, const int minWeight,
1936                            const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1937                            U32 nbBitsBaseline, U16 baseSeq)
1938 {
1939     HUF_DEltX4 DElt;
1940     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1941     U32 s;
1942
1943     /* get pre-calculated rankVal */
1944     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1945
1946     /* fill skipped values */
1947     if (minWeight>1)
1948     {
1949         U32 i, skipSize = rankVal[minWeight];
1950         MEM_writeLE16(&(DElt.sequence), baseSeq);
1951         DElt.nbBits   = (BYTE)(consumed);
1952         DElt.length   = 1;
1953         for (i = 0; i < skipSize; i++)
1954             DTable[i] = DElt;
1955     }
1956
1957     /* fill DTable */
1958     for (s=0; s<sortedListSize; s++)   /* note : sortedSymbols already skipped */
1959     {
1960         const U32 symbol = sortedSymbols[s].symbol;
1961         const U32 weight = sortedSymbols[s].weight;
1962         const U32 nbBits = nbBitsBaseline - weight;
1963         const U32 length = 1 << (sizeLog-nbBits);
1964         const U32 start = rankVal[weight];
1965         U32 i = start;
1966         const U32 end = start + length;
1967
1968         MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1969         DElt.nbBits = (BYTE)(nbBits + consumed);
1970         DElt.length = 2;
1971         do { DTable[i++] = DElt; } while (i<end);   /* since length >= 1 */
1972
1973         rankVal[weight] += length;
1974     }
1975 }
1976
1977 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1978
1979 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1980                            const sortedSymbol_t* sortedList, const U32 sortedListSize,
1981                            const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1982                            const U32 nbBitsBaseline)
1983 {
1984     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1985     const int scaleLog = nbBitsBaseline - targetLog;   /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1986     const U32 minBits  = nbBitsBaseline - maxWeight;
1987     U32 s;
1988
1989     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1990
1991     /* fill DTable */
1992     for (s=0; s<sortedListSize; s++)
1993     {
1994         const U16 symbol = sortedList[s].symbol;
1995         const U32 weight = sortedList[s].weight;
1996         const U32 nbBits = nbBitsBaseline - weight;
1997         const U32 start = rankVal[weight];
1998         const U32 length = 1 << (targetLog-nbBits);
1999
2000         if (targetLog-nbBits >= minBits)   /* enough room for a second symbol */
2001         {
2002             U32 sortedRank;
2003             int minWeight = nbBits + scaleLog;
2004             if (minWeight < 1) minWeight = 1;
2005             sortedRank = rankStart[minWeight];
2006             HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2007                            rankValOrigin[nbBits], minWeight,
2008                            sortedList+sortedRank, sortedListSize-sortedRank,
2009                            nbBitsBaseline, symbol);
2010         }
2011         else
2012         {
2013             U32 i;
2014             const U32 end = start + length;
2015             HUF_DEltX4 DElt;
2016
2017             MEM_writeLE16(&(DElt.sequence), symbol);
2018             DElt.nbBits   = (BYTE)(nbBits);
2019             DElt.length   = 1;
2020             for (i = start; i < end; i++)
2021                 DTable[i] = DElt;
2022         }
2023         rankVal[weight] += length;
2024     }
2025 }
2026
2027 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2028 {
2029     BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
2030     sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
2031     U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2032     U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2033     U32* const rankStart = rankStart0+1;
2034     rankVal_t rankVal;
2035     U32 tableLog, maxW, sizeOfSort, nbSymbols;
2036     const U32 memLog = DTable[0];
2037     size_t iSize;
2038     void* dtPtr = DTable;
2039     HUF_DEltX4* const dt = ((HUF_DEltX4*)dtPtr) + 1;
2040
2041     HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32));   /* if compilation fails here, assertion is false */
2042     if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2043     //memset(weightList, 0, sizeof(weightList));   /* is not necessary, even though some analyzer complain ... */
2044
2045     iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2046     if (HUF_isError(iSize)) return iSize;
2047
2048     /* check result */
2049     if (tableLog > memLog) return ERROR(tableLog_tooLarge);   /* DTable can't fit code depth */
2050
2051     /* find maxWeight */
2052     for (maxW = tableLog; rankStats[maxW]==0; maxW--)
2053         { if (!maxW) return ERROR(GENERIC); }  /* necessarily finds a solution before maxW==0 */
2054
2055     /* Get start index of each weight */
2056     {
2057         U32 w, nextRankStart = 0;
2058         for (w=1; w<=maxW; w++)
2059         {
2060             U32 current = nextRankStart;
2061             nextRankStart += rankStats[w];
2062             rankStart[w] = current;
2063         }
2064         rankStart[0] = nextRankStart;   /* put all 0w symbols at the end of sorted list*/
2065         sizeOfSort = nextRankStart;
2066     }
2067
2068     /* sort symbols by weight */
2069     {
2070         U32 s;
2071         for (s=0; s<nbSymbols; s++)
2072         {
2073             U32 w = weightList[s];
2074             U32 r = rankStart[w]++;
2075             sortedSymbol[r].symbol = (BYTE)s;
2076             sortedSymbol[r].weight = (BYTE)w;
2077         }
2078         rankStart[0] = 0;   /* forget 0w symbols; this is beginning of weight(1) */
2079     }
2080
2081     /* Build rankVal */
2082     {
2083         const U32 minBits = tableLog+1 - maxW;
2084         U32 nextRankVal = 0;
2085         U32 w, consumed;
2086         const int rescale = (memLog-tableLog) - 1;   /* tableLog <= memLog */
2087         U32* rankVal0 = rankVal[0];
2088         for (w=1; w<=maxW; w++)
2089         {
2090             U32 current = nextRankVal;
2091             nextRankVal += rankStats[w] << (w+rescale);
2092             rankVal0[w] = current;
2093         }
2094         for (consumed = minBits; consumed <= memLog - minBits; consumed++)
2095         {
2096             U32* rankValPtr = rankVal[consumed];
2097             for (w = 1; w <= maxW; w++)
2098             {
2099                 rankValPtr[w] = rankVal0[w] >> consumed;
2100             }
2101         }
2102     }
2103
2104     HUF_fillDTableX4(dt, memLog,
2105                    sortedSymbol, sizeOfSort,
2106                    rankStart0, rankVal, maxW,
2107                    tableLog+1);
2108
2109     return iSize;
2110 }
2111
2112
2113 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2114 {
2115     const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2116     memcpy(op, dt+val, 2);
2117     BIT_skipBits(DStream, dt[val].nbBits);
2118     return dt[val].length;
2119 }
2120
2121 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
2122 {
2123     const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2124     memcpy(op, dt+val, 1);
2125     if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
2126     else
2127     {
2128         if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
2129         {
2130             BIT_skipBits(DStream, dt[val].nbBits);
2131             if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2132                 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 */
2133         }
2134     }
2135     return 1;
2136 }
2137
2138
2139 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2140     ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2141
2142 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2143     if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
2144         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2145
2146 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2147     if (MEM_64bits()) \
2148         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2149
2150 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
2151 {
2152     BYTE* const pStart = p;
2153
2154     /* up to 8 symbols at a time */
2155     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
2156     {
2157         HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2158         HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
2159         HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
2160         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2161     }
2162
2163     /* closer to the end */
2164     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2165         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2166
2167     while (p <= pEnd-2)
2168         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);   /* no need to reload : reached the end of DStream */
2169
2170     if (p < pEnd)
2171         p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2172
2173     return p-pStart;
2174 }
2175
2176 static size_t HUF_decompress4X4_usingDTable(
2177           void* dst,  size_t dstSize,
2178     const void* cSrc, size_t cSrcSize,
2179     const U32* DTable)
2180 {
2181     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
2182
2183     {
2184         const BYTE* const istart = (const BYTE*) cSrc;
2185         BYTE* const ostart = (BYTE*) dst;
2186         BYTE* const oend = ostart + dstSize;
2187         const void* const dtPtr = DTable;
2188         const HUF_DEltX4* const dt = ((const HUF_DEltX4*)dtPtr) +1;
2189         const U32 dtLog = DTable[0];
2190         size_t errorCode;
2191
2192         /* Init */
2193         BIT_DStream_t bitD1;
2194         BIT_DStream_t bitD2;
2195         BIT_DStream_t bitD3;
2196         BIT_DStream_t bitD4;
2197         const size_t length1 = MEM_readLE16(istart);
2198         const size_t length2 = MEM_readLE16(istart+2);
2199         const size_t length3 = MEM_readLE16(istart+4);
2200         size_t length4;
2201         const BYTE* const istart1 = istart + 6;  /* jumpTable */
2202         const BYTE* const istart2 = istart1 + length1;
2203         const BYTE* const istart3 = istart2 + length2;
2204         const BYTE* const istart4 = istart3 + length3;
2205         const size_t segmentSize = (dstSize+3) / 4;
2206         BYTE* const opStart2 = ostart + segmentSize;
2207         BYTE* const opStart3 = opStart2 + segmentSize;
2208         BYTE* const opStart4 = opStart3 + segmentSize;
2209         BYTE* op1 = ostart;
2210         BYTE* op2 = opStart2;
2211         BYTE* op3 = opStart3;
2212         BYTE* op4 = opStart4;
2213         U32 endSignal;
2214
2215         length4 = cSrcSize - (length1 + length2 + length3 + 6);
2216         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
2217         errorCode = BIT_initDStream(&bitD1, istart1, length1);
2218         if (HUF_isError(errorCode)) return errorCode;
2219         errorCode = BIT_initDStream(&bitD2, istart2, length2);
2220         if (HUF_isError(errorCode)) return errorCode;
2221         errorCode = BIT_initDStream(&bitD3, istart3, length3);
2222         if (HUF_isError(errorCode)) return errorCode;
2223         errorCode = BIT_initDStream(&bitD4, istart4, length4);
2224         if (HUF_isError(errorCode)) return errorCode;
2225
2226         /* 16-32 symbols per loop (4-8 symbols per stream) */
2227         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2228         for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2229         {
2230             HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2231             HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2232             HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2233             HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2234             HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2235             HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2236             HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2237             HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2238             HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2239             HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2240             HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2241             HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2242             HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2243             HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2244             HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2245             HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2246
2247             endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2248         }
2249
2250         /* check corruption */
2251         if (op1 > opStart2) return ERROR(corruption_detected);
2252         if (op2 > opStart3) return ERROR(corruption_detected);
2253         if (op3 > opStart4) return ERROR(corruption_detected);
2254         /* note : op4 supposed already verified within main loop */
2255
2256         /* finish bitStreams one by one */
2257         HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2258         HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2259         HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2260         HUF_decodeStreamX4(op4, &bitD4, oend,     dt, dtLog);
2261
2262         /* check */
2263         endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2264         if (!endSignal) return ERROR(corruption_detected);
2265
2266         /* decoded size */
2267         return dstSize;
2268     }
2269 }
2270
2271
2272 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2273 {
2274     HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2275     const BYTE* ip = (const BYTE*) cSrc;
2276
2277     size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2278     if (HUF_isError(hSize)) return hSize;
2279     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2280     ip += hSize;
2281     cSrcSize -= hSize;
2282
2283     return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2284 }
2285
2286
2287 /**********************************/
2288 /* Generic decompression selector */
2289 /**********************************/
2290
2291 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2292 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2293 {
2294     /* single, double, quad */
2295     {{0,0}, {1,1}, {2,2}},  /* Q==0 : impossible */
2296     {{0,0}, {1,1}, {2,2}},  /* Q==1 : impossible */
2297     {{  38,130}, {1313, 74}, {2151, 38}},   /* Q == 2 : 12-18% */
2298     {{ 448,128}, {1353, 74}, {2238, 41}},   /* Q == 3 : 18-25% */
2299     {{ 556,128}, {1353, 74}, {2238, 47}},   /* Q == 4 : 25-32% */
2300     {{ 714,128}, {1418, 74}, {2436, 53}},   /* Q == 5 : 32-38% */
2301     {{ 883,128}, {1437, 74}, {2464, 61}},   /* Q == 6 : 38-44% */
2302     {{ 897,128}, {1515, 75}, {2622, 68}},   /* Q == 7 : 44-50% */
2303     {{ 926,128}, {1613, 75}, {2730, 75}},   /* Q == 8 : 50-56% */
2304     {{ 947,128}, {1729, 77}, {3359, 77}},   /* Q == 9 : 56-62% */
2305     {{1107,128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
2306     {{1177,128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
2307     {{1242,128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
2308     {{1349,128}, {2644,106}, {5260,106}},   /* Q ==13 : 81-87% */
2309     {{1455,128}, {2422,124}, {4174,124}},   /* Q ==14 : 87-93% */
2310     {{ 722,128}, {1891,145}, {1936,146}},   /* Q ==15 : 93-99% */
2311 };
2312
2313 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2314
2315 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2316 {
2317     static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2318     /* estimate decompression time */
2319     U32 Q;
2320     const U32 D256 = (U32)(dstSize >> 8);
2321     U32 Dtime[3];
2322     U32 algoNb = 0;
2323     int n;
2324
2325     /* validation checks */
2326     if (dstSize == 0) return ERROR(dstSize_tooSmall);
2327     if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
2328     if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
2329     if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
2330
2331     /* decoder timing evaluation */
2332     Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
2333     for (n=0; n<3; n++)
2334         Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2335
2336     Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2337
2338     if (Dtime[1] < Dtime[0]) algoNb = 1;
2339
2340     return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2341
2342     //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize);   /* multi-streams single-symbol decoding */
2343     //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize);   /* multi-streams double-symbols decoding */
2344     //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize);   /* multi-streams quad-symbols decoding */
2345 }
2346
2347
2348
2349 #endif   /* ZSTD_CCOMMON_H_MODULE */
2350
2351
2352 /*
2353     zstd - decompression module fo v0.4 legacy format
2354     Copyright (C) 2015-2016, Yann Collet.
2355
2356     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2357
2358     Redistribution and use in source and binary forms, with or without
2359     modification, are permitted provided that the following conditions are
2360     met:
2361     * Redistributions of source code must retain the above copyright
2362     notice, this list of conditions and the following disclaimer.
2363     * Redistributions in binary form must reproduce the above
2364     copyright notice, this list of conditions and the following disclaimer
2365     in the documentation and/or other materials provided with the
2366     distribution.
2367     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2368     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2369     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2370     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2371     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2372     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2373     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2374     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2375     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2376     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2377     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2378
2379     You can contact the author at :
2380     - zstd source repository : https://github.com/Cyan4973/zstd
2381     - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2382 */
2383
2384 /* ***************************************************************
2385 *  Tuning parameters
2386 *****************************************************************/
2387 /*!
2388  * HEAPMODE :
2389  * Select how default decompression function ZSTD_decompress() will allocate memory,
2390  * in memory stack (0), or in memory heap (1, requires malloc())
2391  */
2392 #ifndef ZSTD_HEAPMODE
2393 #  define ZSTD_HEAPMODE 1
2394 #endif
2395
2396
2397 /* *******************************************************
2398 *  Includes
2399 *********************************************************/
2400 #include <stdlib.h>      /* calloc */
2401 #include <string.h>      /* memcpy, memmove */
2402 #include <stdio.h>       /* debug : printf */
2403
2404
2405 /* *******************************************************
2406 *  Compiler specifics
2407 *********************************************************/
2408 #ifdef _MSC_VER    /* Visual Studio */
2409 #  include <intrin.h>                    /* For Visual 2005 */
2410 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
2411 #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
2412 #endif
2413
2414
2415 /* *************************************
2416 *  Local types
2417 ***************************************/
2418 typedef struct
2419 {
2420     blockType_t blockType;
2421     U32 origSize;
2422 } blockProperties_t;
2423
2424
2425 /* *******************************************************
2426 *  Memory operations
2427 **********************************************************/
2428 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2429
2430
2431 /* *************************************
2432 *  Error Management
2433 ***************************************/
2434
2435 /*! ZSTD_isError
2436 *   tells if a return value is an error code */
2437 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2438
2439
2440 /* *************************************************************
2441 *   Context management
2442 ***************************************************************/
2443 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2444                ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTD_dStage;
2445
2446 struct ZSTDv04_Dctx_s
2447 {
2448     U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2449     U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2450     U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2451     const void* previousDstEnd;
2452     const void* base;
2453     const void* vBase;
2454     const void* dictEnd;
2455     size_t expected;
2456     size_t headerSize;
2457     ZSTD_parameters params;
2458     blockType_t bType;
2459     ZSTD_dStage stage;
2460     const BYTE* litPtr;
2461     size_t litSize;
2462     BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2463     BYTE headerBuffer[ZSTD_frameHeaderSize_max];
2464 };  /* typedef'd to ZSTD_DCtx within "zstd_static.h" */
2465
2466 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2467 {
2468     dctx->expected = ZSTD_frameHeaderSize_min;
2469     dctx->stage = ZSTDds_getFrameHeaderSize;
2470     dctx->previousDstEnd = NULL;
2471     dctx->base = NULL;
2472     dctx->vBase = NULL;
2473     dctx->dictEnd = NULL;
2474     return 0;
2475 }
2476
2477 static ZSTD_DCtx* ZSTD_createDCtx(void)
2478 {
2479     ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2480     if (dctx==NULL) return NULL;
2481     ZSTD_resetDCtx(dctx);
2482     return dctx;
2483 }
2484
2485 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
2486 {
2487     free(dctx);
2488     return 0;
2489 }
2490
2491
2492 /* *************************************************************
2493 *   Decompression section
2494 ***************************************************************/
2495 /** ZSTD_decodeFrameHeader_Part1
2496 *   decode the 1st part of the Frame Header, which tells Frame Header size.
2497 *   srcSize must be == ZSTD_frameHeaderSize_min
2498 *   @return : the full size of the Frame Header */
2499 static size_t ZSTD_decodeFrameHeader_Part1(ZSTD_DCtx* zc, const void* src, size_t srcSize)
2500 {
2501     U32 magicNumber;
2502     if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);
2503     magicNumber = MEM_readLE32(src);
2504     if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
2505     zc->headerSize = ZSTD_frameHeaderSize_min;
2506     return zc->headerSize;
2507 }
2508
2509
2510 static size_t ZSTD_getFrameParams(ZSTD_parameters* params, const void* src, size_t srcSize)
2511 {
2512     U32 magicNumber;
2513     if (srcSize < ZSTD_frameHeaderSize_min) return ZSTD_frameHeaderSize_max;
2514     magicNumber = MEM_readLE32(src);
2515     if (magicNumber != ZSTD_MAGICNUMBER) return ERROR(prefix_unknown);
2516     memset(params, 0, sizeof(*params));
2517     params->windowLog = (((const BYTE*)src)[4] & 15) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
2518     if ((((const BYTE*)src)[4] >> 4) != 0) return ERROR(frameParameter_unsupported);   /* reserved bits */
2519     return 0;
2520 }
2521
2522 /** ZSTD_decodeFrameHeader_Part2
2523 *   decode the full Frame Header
2524 *   srcSize must be the size provided by ZSTD_decodeFrameHeader_Part1
2525 *   @return : 0, or an error code, which can be tested using ZSTD_isError() */
2526 static size_t ZSTD_decodeFrameHeader_Part2(ZSTD_DCtx* zc, const void* src, size_t srcSize)
2527 {
2528     size_t result;
2529     if (srcSize != zc->headerSize) return ERROR(srcSize_wrong);
2530     result = ZSTD_getFrameParams(&(zc->params), src, srcSize);
2531     if ((MEM_32bits()) && (zc->params.windowLog > 25)) return ERROR(frameParameter_unsupported);
2532     return result;
2533 }
2534
2535
2536 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2537 {
2538     const BYTE* const in = (const BYTE* const)src;
2539     BYTE headerFlags;
2540     U32 cSize;
2541
2542     if (srcSize < 3) return ERROR(srcSize_wrong);
2543
2544     headerFlags = *in;
2545     cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2546
2547     bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2548     bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2549
2550     if (bpPtr->blockType == bt_end) return 0;
2551     if (bpPtr->blockType == bt_rle) return 1;
2552     return cSize;
2553 }
2554
2555 static size_t ZSTD_copyRawBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2556 {
2557     if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2558     if (srcSize > 0) {
2559         memcpy(dst, src, srcSize);
2560     }
2561     return srcSize;
2562 }
2563
2564
2565 /** ZSTD_decompressLiterals
2566     @return : nb of bytes read from src, or an error code*/
2567 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2568                                 const void* src, size_t srcSize)
2569 {
2570     const BYTE* ip = (const BYTE*)src;
2571
2572     const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2573     const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2574
2575     if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2576     if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2577
2578     if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2579
2580     *maxDstSizePtr = litSize;
2581     return litCSize + 5;
2582 }
2583
2584
2585 /** ZSTD_decodeLiteralsBlock
2586     @return : nb of bytes read from src (< srcSize ) */
2587 static size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
2588                           const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
2589 {
2590     const BYTE* const istart = (const BYTE*) src;
2591
2592     /* any compressed block with literals segment must be at least this size */
2593     if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2594
2595     switch(*istart & 3)
2596     {
2597     /* compressed */
2598     case 0:
2599         {
2600             size_t litSize = BLOCKSIZE;
2601             const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2602             dctx->litPtr = dctx->litBuffer;
2603             dctx->litSize = litSize;
2604             memset(dctx->litBuffer + dctx->litSize, 0, 8);
2605             return readSize;   /* works if it's an error too */
2606         }
2607     case IS_RAW:
2608         {
2609             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2610             if (litSize > srcSize-11)   /* risk of reading too far with wildcopy */
2611             {
2612                 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2613                 if (litSize > srcSize-3) return ERROR(corruption_detected);
2614                 memcpy(dctx->litBuffer, istart, litSize);
2615                 dctx->litPtr = dctx->litBuffer;
2616                 dctx->litSize = litSize;
2617                 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2618                 return litSize+3;
2619             }
2620             /* direct reference into compressed stream */
2621             dctx->litPtr = istart+3;
2622             dctx->litSize = litSize;
2623             return litSize+3;        }
2624     case IS_RLE:
2625         {
2626             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2627             if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2628             memset(dctx->litBuffer, istart[3], litSize + 8);
2629             dctx->litPtr = dctx->litBuffer;
2630             dctx->litSize = litSize;
2631             return 4;
2632         }
2633     default:
2634         return ERROR(corruption_detected);   /* forbidden nominal case */
2635     }
2636 }
2637
2638
2639 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2640                          FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2641                          const void* src, size_t srcSize)
2642 {
2643     const BYTE* const istart = (const BYTE* const)src;
2644     const BYTE* ip = istart;
2645     const BYTE* const iend = istart + srcSize;
2646     U32 LLtype, Offtype, MLtype;
2647     U32 LLlog, Offlog, MLlog;
2648     size_t dumpsLength;
2649
2650     /* check */
2651     if (srcSize < 5) return ERROR(srcSize_wrong);
2652
2653     /* SeqHead */
2654     *nbSeq = MEM_readLE16(ip); ip+=2;
2655     LLtype  = *ip >> 6;
2656     Offtype = (*ip >> 4) & 3;
2657     MLtype  = (*ip >> 2) & 3;
2658     if (*ip & 2)
2659     {
2660         dumpsLength  = ip[2];
2661         dumpsLength += ip[1] << 8;
2662         ip += 3;
2663     }
2664     else
2665     {
2666         dumpsLength  = ip[1];
2667         dumpsLength += (ip[0] & 1) << 8;
2668         ip += 2;
2669     }
2670     *dumpsPtr = ip;
2671     ip += dumpsLength;
2672     *dumpsLengthPtr = dumpsLength;
2673
2674     /* check */
2675     if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2676
2677     /* sequences */
2678     {
2679         S16 norm[MaxML+1];    /* assumption : MaxML >= MaxLL >= MaxOff */
2680         size_t headerSize;
2681
2682         /* Build DTables */
2683         switch(LLtype)
2684         {
2685         case bt_rle :
2686             LLlog = 0;
2687             FSE_buildDTable_rle(DTableLL, *ip++); break;
2688         case bt_raw :
2689             LLlog = LLbits;
2690             FSE_buildDTable_raw(DTableLL, LLbits); break;
2691         default :
2692             {   U32 max = MaxLL;
2693                 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2694                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2695                 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2696                 ip += headerSize;
2697                 FSE_buildDTable(DTableLL, norm, max, LLlog);
2698         }   }
2699
2700         switch(Offtype)
2701         {
2702         case bt_rle :
2703             Offlog = 0;
2704             if (ip > iend-2) return ERROR(srcSize_wrong);   /* min : "raw", hence no header, but at least xxLog bits */
2705             FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2706             break;
2707         case bt_raw :
2708             Offlog = Offbits;
2709             FSE_buildDTable_raw(DTableOffb, Offbits); break;
2710         default :
2711             {   U32 max = MaxOff;
2712                 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2713                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2714                 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2715                 ip += headerSize;
2716                 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2717         }   }
2718
2719         switch(MLtype)
2720         {
2721         case bt_rle :
2722             MLlog = 0;
2723             if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2724             FSE_buildDTable_rle(DTableML, *ip++); break;
2725         case bt_raw :
2726             MLlog = MLbits;
2727             FSE_buildDTable_raw(DTableML, MLbits); break;
2728         default :
2729             {   U32 max = MaxML;
2730                 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2731                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2732                 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2733                 ip += headerSize;
2734                 FSE_buildDTable(DTableML, norm, max, MLlog);
2735     }   }   }
2736
2737     return ip-istart;
2738 }
2739
2740
2741 typedef struct {
2742     size_t litLength;
2743     size_t offset;
2744     size_t matchLength;
2745 } seq_t;
2746
2747 typedef struct {
2748     BIT_DStream_t DStream;
2749     FSE_DState_t stateLL;
2750     FSE_DState_t stateOffb;
2751     FSE_DState_t stateML;
2752     size_t prevOffset;
2753     const BYTE* dumps;
2754     const BYTE* dumpsEnd;
2755 } seqState_t;
2756
2757
2758 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2759 {
2760     size_t litLength;
2761     size_t prevOffset;
2762     size_t offset;
2763     size_t matchLength;
2764     const BYTE* dumps = seqState->dumps;
2765     const BYTE* const de = seqState->dumpsEnd;
2766
2767     /* Literal length */
2768     litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2769     prevOffset = litLength ? seq->offset : seqState->prevOffset;
2770     if (litLength == MaxLL) {
2771         const U32 add = dumps<de ? *dumps++ : 0;
2772         if (add < 255) litLength += add;
2773         else if (dumps + 3 <= de) {
2774             litLength = MEM_readLE24(dumps);
2775             dumps += 3;
2776         }
2777         if (dumps >= de) { dumps = de-1; }  /* late correction, to avoid read overflow (data is now corrupted anyway) */
2778     }
2779
2780     /* Offset */
2781     {   static const U32 offsetPrefix[MaxOff+1] = {
2782                 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2783                 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2784                 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2785         U32 offsetCode, nbBits;
2786         offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream));   /* <= maxOff, by table construction */
2787         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2788         nbBits = offsetCode - 1;
2789         if (offsetCode==0) nbBits = 0;   /* cmove */
2790         offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2791         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2792         if (offsetCode==0) offset = prevOffset;   /* cmove */
2793         if (offsetCode | !litLength) seqState->prevOffset = seq->offset;   /* cmove */
2794     }
2795
2796     /* MatchLength */
2797     matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2798     if (matchLength == MaxML) {
2799         const U32 add = dumps<de ? *dumps++ : 0;
2800         if (add < 255) matchLength += add;
2801         else if (dumps + 3 <= de){
2802             matchLength = MEM_readLE24(dumps);
2803             dumps += 3;
2804         }
2805         if (dumps >= de) { dumps = de-1; }  /* late correction, to avoid read overflow (data is now corrupted anyway) */
2806     }
2807     matchLength += MINMATCH;
2808
2809     /* save result */
2810     seq->litLength = litLength;
2811     seq->offset = offset;
2812     seq->matchLength = matchLength;
2813     seqState->dumps = dumps;
2814 }
2815
2816
2817 static size_t ZSTD_execSequence(BYTE* op,
2818                                 BYTE* const oend, seq_t sequence,
2819                                 const BYTE** litPtr, const BYTE* const litLimit,
2820                                 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
2821 {
2822     static const int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
2823     static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
2824     BYTE* const oLitEnd = op + sequence.litLength;
2825     const size_t sequenceLength = sequence.litLength + sequence.matchLength;
2826     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
2827     BYTE* const oend_8 = oend-8;
2828     const BYTE* const litEnd = *litPtr + sequence.litLength;
2829     const BYTE* match = oLitEnd - sequence.offset;
2830
2831     /* checks */
2832     size_t const seqLength = sequence.litLength + sequence.matchLength;
2833
2834     if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
2835     if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
2836     /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
2837     if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
2838
2839     if (oMatchEnd > oend) return ERROR(dstSize_tooSmall);   /* overwrite beyond dst buffer */
2840     if (litEnd > litLimit) return ERROR(corruption_detected);   /* overRead beyond lit buffer */
2841
2842     /* copy Literals */
2843     ZSTD_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength);   /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2844     op = oLitEnd;
2845     *litPtr = litEnd;   /* update for next sequence */
2846
2847     /* copy Match */
2848     if (sequence.offset > (size_t)(oLitEnd - base))
2849     {
2850         /* offset beyond prefix */
2851         if (sequence.offset > (size_t)(oLitEnd - vBase))
2852             return ERROR(corruption_detected);
2853         match = dictEnd - (base-match);
2854         if (match + sequence.matchLength <= dictEnd)
2855         {
2856             memmove(oLitEnd, match, sequence.matchLength);
2857             return sequenceLength;
2858         }
2859         /* span extDict & currentPrefixSegment */
2860         {
2861             size_t length1 = dictEnd - match;
2862             memmove(oLitEnd, match, length1);
2863             op = oLitEnd + length1;
2864             sequence.matchLength -= length1;
2865             match = base;
2866             if (op > oend_8 || sequence.matchLength < MINMATCH) {
2867               while (op < oMatchEnd) *op++ = *match++;
2868               return sequenceLength;
2869             }
2870         }
2871     }
2872     /* Requirement: op <= oend_8 */
2873
2874     /* match within prefix */
2875     if (sequence.offset < 8) {
2876         /* close range match, overlap */
2877         const int sub2 = dec64table[sequence.offset];
2878         op[0] = match[0];
2879         op[1] = match[1];
2880         op[2] = match[2];
2881         op[3] = match[3];
2882         match += dec32table[sequence.offset];
2883         ZSTD_copy4(op+4, match);
2884         match -= sub2;
2885     } else {
2886         ZSTD_copy8(op, match);
2887     }
2888     op += 8; match += 8;
2889
2890     if (oMatchEnd > oend-(16-MINMATCH))
2891     {
2892         if (op < oend_8)
2893         {
2894             ZSTD_wildcopy(op, match, oend_8 - op);
2895             match += oend_8 - op;
2896             op = oend_8;
2897         }
2898         while (op < oMatchEnd) *op++ = *match++;
2899     }
2900     else
2901     {
2902         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8, but must be signed */
2903     }
2904     return sequenceLength;
2905 }
2906
2907
2908 static size_t ZSTD_decompressSequences(
2909                                ZSTD_DCtx* dctx,
2910                                void* dst, size_t maxDstSize,
2911                          const void* seqStart, size_t seqSize)
2912 {
2913     const BYTE* ip = (const BYTE*)seqStart;
2914     const BYTE* const iend = ip + seqSize;
2915     BYTE* const ostart = (BYTE* const)dst;
2916     BYTE* op = ostart;
2917     BYTE* const oend = ostart + maxDstSize;
2918     size_t errorCode, dumpsLength;
2919     const BYTE* litPtr = dctx->litPtr;
2920     const BYTE* const litEnd = litPtr + dctx->litSize;
2921     int nbSeq;
2922     const BYTE* dumps;
2923     U32* DTableLL = dctx->LLTable;
2924     U32* DTableML = dctx->MLTable;
2925     U32* DTableOffb = dctx->OffTable;
2926     const BYTE* const base = (const BYTE*) (dctx->base);
2927     const BYTE* const vBase = (const BYTE*) (dctx->vBase);
2928     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
2929
2930     /* Build Decoding Tables */
2931     errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2932                                       DTableLL, DTableML, DTableOffb,
2933                                       ip, iend-ip);
2934     if (ZSTD_isError(errorCode)) return errorCode;
2935     ip += errorCode;
2936
2937     /* Regen sequences */
2938     {
2939         seq_t sequence;
2940         seqState_t seqState;
2941
2942         memset(&sequence, 0, sizeof(sequence));
2943         sequence.offset = 4;
2944         seqState.dumps = dumps;
2945         seqState.dumpsEnd = dumps + dumpsLength;
2946         seqState.prevOffset = 4;
2947         errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2948         if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2949         FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2950         FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2951         FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2952
2953         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; )
2954         {
2955             size_t oneSeqSize;
2956             nbSeq--;
2957             ZSTD_decodeSequence(&sequence, &seqState);
2958             oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
2959             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2960             op += oneSeqSize;
2961         }
2962
2963         /* check if reached exact end */
2964         if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected);   /* DStream should be entirely and exactly consumed; otherwise data is corrupted */
2965
2966         /* last literal segment */
2967         {
2968             size_t lastLLSize = litEnd - litPtr;
2969             if (litPtr > litEnd) return ERROR(corruption_detected);
2970             if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2971             if (lastLLSize > 0) {
2972                 if (op != litPtr) memcpy(op, litPtr, lastLLSize);
2973                 op += lastLLSize;
2974             }
2975         }
2976     }
2977
2978     return op-ostart;
2979 }
2980
2981
2982 static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
2983 {
2984     if (dst != dctx->previousDstEnd)   /* not contiguous */
2985     {
2986         dctx->dictEnd = dctx->previousDstEnd;
2987         dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
2988         dctx->base = dst;
2989         dctx->previousDstEnd = dst;
2990     }
2991 }
2992
2993
2994 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
2995                             void* dst, size_t maxDstSize,
2996                       const void* src, size_t srcSize)
2997 {
2998     /* blockType == blockCompressed */
2999     const BYTE* ip = (const BYTE*)src;
3000     size_t litCSize;
3001
3002     if (srcSize > BLOCKSIZE) return ERROR(corruption_detected);
3003
3004     /* Decode literals sub-block */
3005     litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
3006     if (ZSTD_isError(litCSize)) return litCSize;
3007     ip += litCSize;
3008     srcSize -= litCSize;
3009
3010     return ZSTD_decompressSequences(dctx, dst, maxDstSize, ip, srcSize);
3011 }
3012
3013
3014 static size_t ZSTD_decompress_usingDict(ZSTD_DCtx* ctx,
3015                                  void* dst, size_t maxDstSize,
3016                                  const void* src, size_t srcSize,
3017                                  const void* dict, size_t dictSize)
3018 {
3019     const BYTE* ip = (const BYTE*)src;
3020     const BYTE* iend = ip + srcSize;
3021     BYTE* const ostart = (BYTE* const)dst;
3022     BYTE* op = ostart;
3023     BYTE* const oend = ostart + maxDstSize;
3024     size_t remainingSize = srcSize;
3025     blockProperties_t blockProperties;
3026
3027     /* init */
3028     ZSTD_resetDCtx(ctx);
3029     if (dict)
3030     {
3031         ZSTD_decompress_insertDictionary(ctx, dict, dictSize);
3032         ctx->dictEnd = ctx->previousDstEnd;
3033         ctx->vBase = (const char*)dst - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
3034         ctx->base = dst;
3035     }
3036     else
3037     {
3038         ctx->vBase = ctx->base = ctx->dictEnd = dst;
3039     }
3040
3041     /* Frame Header */
3042     {
3043         size_t frameHeaderSize;
3044         if (srcSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3045         frameHeaderSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
3046         if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
3047         if (srcSize < frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
3048         ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3049         frameHeaderSize = ZSTD_decodeFrameHeader_Part2(ctx, src, frameHeaderSize);
3050         if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
3051     }
3052
3053     /* Loop on each block */
3054     while (1)
3055     {
3056         size_t decodedSize=0;
3057         size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
3058         if (ZSTD_isError(cBlockSize)) return cBlockSize;
3059
3060         ip += ZSTD_blockHeaderSize;
3061         remainingSize -= ZSTD_blockHeaderSize;
3062         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3063
3064         switch(blockProperties.blockType)
3065         {
3066         case bt_compressed:
3067             decodedSize = ZSTD_decompressBlock_internal(ctx, op, oend-op, ip, cBlockSize);
3068             break;
3069         case bt_raw :
3070             decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
3071             break;
3072         case bt_rle :
3073             return ERROR(GENERIC);   /* not yet supported */
3074             break;
3075         case bt_end :
3076             /* end of frame */
3077             if (remainingSize) return ERROR(srcSize_wrong);
3078             break;
3079         default:
3080             return ERROR(GENERIC);   /* impossible */
3081         }
3082         if (cBlockSize == 0) break;   /* bt_end */
3083
3084         if (ZSTD_isError(decodedSize)) return decodedSize;
3085         op += decodedSize;
3086         ip += cBlockSize;
3087         remainingSize -= cBlockSize;
3088     }
3089
3090     return op-ostart;
3091 }
3092
3093 /* ZSTD_errorFrameSizeInfoLegacy() :
3094    assumes `cSize` and `dBound` are _not_ NULL */
3095 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3096 {
3097     *cSize = ret;
3098     *dBound = ZSTD_CONTENTSIZE_ERROR;
3099 }
3100
3101 void ZSTDv04_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3102 {
3103     const BYTE* ip = (const BYTE*)src;
3104     size_t remainingSize = srcSize;
3105     size_t nbBlocks = 0;
3106     blockProperties_t blockProperties;
3107
3108     /* Frame Header */
3109     if (srcSize < ZSTD_frameHeaderSize_min) {
3110         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3111         return;
3112     }
3113     if (MEM_readLE32(src) != ZSTD_MAGICNUMBER) {
3114         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3115         return;
3116     }
3117     ip += ZSTD_frameHeaderSize_min; remainingSize -= ZSTD_frameHeaderSize_min;
3118
3119     /* Loop on each block */
3120     while (1)
3121     {
3122         size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
3123         if (ZSTD_isError(cBlockSize)) {
3124             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3125             return;
3126         }
3127
3128         ip += ZSTD_blockHeaderSize;
3129         remainingSize -= ZSTD_blockHeaderSize;
3130         if (cBlockSize > remainingSize) {
3131             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3132             return;
3133         }
3134
3135         if (cBlockSize == 0) break;   /* bt_end */
3136
3137         ip += cBlockSize;
3138         remainingSize -= cBlockSize;
3139         nbBlocks++;
3140     }
3141
3142     *cSize = ip - (const BYTE*)src;
3143     *dBound = nbBlocks * BLOCKSIZE;
3144 }
3145
3146 /* ******************************
3147 *  Streaming Decompression API
3148 ********************************/
3149 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3150 {
3151     return dctx->expected;
3152 }
3153
3154 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3155 {
3156     /* Sanity check */
3157     if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3158     ZSTD_checkContinuity(ctx, dst);
3159
3160     /* Decompress : frame header; part 1 */
3161     switch (ctx->stage)
3162     {
3163     case ZSTDds_getFrameHeaderSize :
3164         /* get frame header size */
3165         if (srcSize != ZSTD_frameHeaderSize_min) return ERROR(srcSize_wrong);   /* impossible */
3166         ctx->headerSize = ZSTD_decodeFrameHeader_Part1(ctx, src, ZSTD_frameHeaderSize_min);
3167         if (ZSTD_isError(ctx->headerSize)) return ctx->headerSize;
3168         memcpy(ctx->headerBuffer, src, ZSTD_frameHeaderSize_min);
3169         if (ctx->headerSize > ZSTD_frameHeaderSize_min) return ERROR(GENERIC);   /* impossible */
3170         ctx->expected = 0;   /* not necessary to copy more */
3171         /* fallthrough */
3172     case ZSTDds_decodeFrameHeader:
3173         /* get frame header */
3174         {   size_t const result = ZSTD_decodeFrameHeader_Part2(ctx, ctx->headerBuffer, ctx->headerSize);
3175             if (ZSTD_isError(result)) return result;
3176             ctx->expected = ZSTD_blockHeaderSize;
3177             ctx->stage = ZSTDds_decodeBlockHeader;
3178             return 0;
3179         }
3180     case ZSTDds_decodeBlockHeader:
3181         /* Decode block header */
3182         {   blockProperties_t bp;
3183             size_t const blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3184             if (ZSTD_isError(blockSize)) return blockSize;
3185             if (bp.blockType == bt_end)
3186             {
3187                 ctx->expected = 0;
3188                 ctx->stage = ZSTDds_getFrameHeaderSize;
3189             }
3190             else
3191             {
3192                 ctx->expected = blockSize;
3193                 ctx->bType = bp.blockType;
3194                 ctx->stage = ZSTDds_decompressBlock;
3195             }
3196             return 0;
3197         }
3198     case ZSTDds_decompressBlock:
3199         {
3200             /* Decompress : block content */
3201             size_t rSize;
3202             switch(ctx->bType)
3203             {
3204             case bt_compressed:
3205                 rSize = ZSTD_decompressBlock_internal(ctx, dst, maxDstSize, src, srcSize);
3206                 break;
3207             case bt_raw :
3208                 rSize = ZSTD_copyRawBlock(dst, maxDstSize, src, srcSize);
3209                 break;
3210             case bt_rle :
3211                 return ERROR(GENERIC);   /* not yet handled */
3212                 break;
3213             case bt_end :   /* should never happen (filtered at phase 1) */
3214                 rSize = 0;
3215                 break;
3216             default:
3217                 return ERROR(GENERIC);
3218             }
3219             ctx->stage = ZSTDds_decodeBlockHeader;
3220             ctx->expected = ZSTD_blockHeaderSize;
3221             ctx->previousDstEnd = (char*)dst + rSize;
3222             return rSize;
3223         }
3224     default:
3225         return ERROR(GENERIC);   /* impossible */
3226     }
3227 }
3228
3229
3230 static void ZSTD_decompress_insertDictionary(ZSTD_DCtx* ctx, const void* dict, size_t dictSize)
3231 {
3232     ctx->dictEnd = ctx->previousDstEnd;
3233     ctx->vBase = (const char*)dict - ((const char*)(ctx->previousDstEnd) - (const char*)(ctx->base));
3234     ctx->base = dict;
3235     ctx->previousDstEnd = (const char*)dict + dictSize;
3236 }
3237
3238
3239
3240 /*
3241     Buffered version of Zstd compression library
3242     Copyright (C) 2015, Yann Collet.
3243
3244     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
3245
3246     Redistribution and use in source and binary forms, with or without
3247     modification, are permitted provided that the following conditions are
3248     met:
3249     * Redistributions of source code must retain the above copyright
3250     notice, this list of conditions and the following disclaimer.
3251     * Redistributions in binary form must reproduce the above
3252     copyright notice, this list of conditions and the following disclaimer
3253     in the documentation and/or other materials provided with the
3254     distribution.
3255     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3256     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3257     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3258     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3259     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3260     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3261     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3262     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3263     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3264     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3265     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3266
3267     You can contact the author at :
3268     - zstd source repository : https://github.com/Cyan4973/zstd
3269     - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
3270 */
3271
3272 /* The objects defined into this file should be considered experimental.
3273  * They are not labelled stable, as their prototype may change in the future.
3274  * You can use them for tests, provide feedback, or if you can endure risk of future changes.
3275  */
3276
3277 /* *************************************
3278 *  Includes
3279 ***************************************/
3280 #include <stdlib.h>
3281
3282
3283 /** ************************************************
3284 *  Streaming decompression
3285 *
3286 *  A ZBUFF_DCtx object is required to track streaming operation.
3287 *  Use ZBUFF_createDCtx() and ZBUFF_freeDCtx() to create/release resources.
3288 *  Use ZBUFF_decompressInit() to start a new decompression operation.
3289 *  ZBUFF_DCtx objects can be reused multiple times.
3290 *
3291 *  Use ZBUFF_decompressContinue() repetitively to consume your input.
3292 *  *srcSizePtr and *maxDstSizePtr can be any size.
3293 *  The function will report how many bytes were read or written by modifying *srcSizePtr and *maxDstSizePtr.
3294 *  Note that it may not consume the entire input, in which case it's up to the caller to call again the function with remaining input.
3295 *  The content of dst will be overwritten (up to *maxDstSizePtr) at each function call, so save its content if it matters or change dst .
3296 *  return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to improve latency)
3297 *            or 0 when a frame is completely decoded
3298 *            or an error code, which can be tested using ZBUFF_isError().
3299 *
3300 *  Hint : recommended buffer sizes (not compulsory)
3301 *  output : 128 KB block size is the internal unit, it ensures it's always possible to write a full block when it's decoded.
3302 *  input : just follow indications from ZBUFF_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3303 * **************************************************/
3304
3305 typedef enum { ZBUFFds_init, ZBUFFds_readHeader, ZBUFFds_loadHeader, ZBUFFds_decodeHeader,
3306                ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFF_dStage;
3307
3308 /* *** Resource management *** */
3309
3310 #define ZSTD_frameHeaderSize_max 5   /* too magical, should come from reference */
3311 struct ZBUFFv04_DCtx_s {
3312     ZSTD_DCtx* zc;
3313     ZSTD_parameters params;
3314     char* inBuff;
3315     size_t inBuffSize;
3316     size_t inPos;
3317     char* outBuff;
3318     size_t outBuffSize;
3319     size_t outStart;
3320     size_t outEnd;
3321     size_t hPos;
3322     const char* dict;
3323     size_t dictSize;
3324     ZBUFF_dStage stage;
3325     unsigned char headerBuffer[ZSTD_frameHeaderSize_max];
3326 };   /* typedef'd to ZBUFF_DCtx within "zstd_buffered.h" */
3327
3328 typedef ZBUFFv04_DCtx ZBUFF_DCtx;
3329
3330
3331 static ZBUFF_DCtx* ZBUFF_createDCtx(void)
3332 {
3333     ZBUFF_DCtx* zbc = (ZBUFF_DCtx*)malloc(sizeof(ZBUFF_DCtx));
3334     if (zbc==NULL) return NULL;
3335     memset(zbc, 0, sizeof(*zbc));
3336     zbc->zc = ZSTD_createDCtx();
3337     zbc->stage = ZBUFFds_init;
3338     return zbc;
3339 }
3340
3341 static size_t ZBUFF_freeDCtx(ZBUFF_DCtx* zbc)
3342 {
3343     if (zbc==NULL) return 0;   /* support free on null */
3344     ZSTD_freeDCtx(zbc->zc);
3345     free(zbc->inBuff);
3346     free(zbc->outBuff);
3347     free(zbc);
3348     return 0;
3349 }
3350
3351
3352 /* *** Initialization *** */
3353
3354 static size_t ZBUFF_decompressInit(ZBUFF_DCtx* zbc)
3355 {
3356     zbc->stage = ZBUFFds_readHeader;
3357     zbc->hPos = zbc->inPos = zbc->outStart = zbc->outEnd = zbc->dictSize = 0;
3358     return ZSTD_resetDCtx(zbc->zc);
3359 }
3360
3361
3362 static size_t ZBUFF_decompressWithDictionary(ZBUFF_DCtx* zbc, const void* src, size_t srcSize)
3363 {
3364     zbc->dict = (const char*)src;
3365     zbc->dictSize = srcSize;
3366     return 0;
3367 }
3368
3369 static size_t ZBUFF_limitCopy(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3370 {
3371     size_t length = MIN(maxDstSize, srcSize);
3372     if (length > 0) {
3373         memcpy(dst, src, length);
3374     }
3375     return length;
3376 }
3377
3378 /* *** Decompression *** */
3379
3380 static size_t ZBUFF_decompressContinue(ZBUFF_DCtx* zbc, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3381 {
3382     const char* const istart = (const char*)src;
3383     const char* ip = istart;
3384     const char* const iend = istart + *srcSizePtr;
3385     char* const ostart = (char*)dst;
3386     char* op = ostart;
3387     char* const oend = ostart + *maxDstSizePtr;
3388     U32 notDone = 1;
3389
3390     DEBUGLOG(5, "ZBUFF_decompressContinue");
3391     while (notDone)
3392     {
3393         switch(zbc->stage)
3394         {
3395
3396         case ZBUFFds_init :
3397             DEBUGLOG(5, "ZBUFF_decompressContinue: stage==ZBUFFds_init => ERROR(init_missing)");
3398             return ERROR(init_missing);
3399
3400         case ZBUFFds_readHeader :
3401             /* read header from src */
3402             {   size_t const headerSize = ZSTD_getFrameParams(&(zbc->params), src, *srcSizePtr);
3403                 if (ZSTD_isError(headerSize)) return headerSize;
3404                 if (headerSize) {
3405                     /* not enough input to decode header : tell how many bytes would be necessary */
3406                     memcpy(zbc->headerBuffer+zbc->hPos, src, *srcSizePtr);
3407                     zbc->hPos += *srcSizePtr;
3408                     *maxDstSizePtr = 0;
3409                     zbc->stage = ZBUFFds_loadHeader;
3410                     return headerSize - zbc->hPos;
3411                 }
3412                 zbc->stage = ZBUFFds_decodeHeader;
3413                 break;
3414             }
3415
3416         case ZBUFFds_loadHeader:
3417             /* complete header from src */
3418             {   size_t headerSize = ZBUFF_limitCopy(
3419                     zbc->headerBuffer + zbc->hPos, ZSTD_frameHeaderSize_max - zbc->hPos,
3420                     src, *srcSizePtr);
3421                 zbc->hPos += headerSize;
3422                 ip += headerSize;
3423                 headerSize = ZSTD_getFrameParams(&(zbc->params), zbc->headerBuffer, zbc->hPos);
3424                 if (ZSTD_isError(headerSize)) return headerSize;
3425                 if (headerSize) {
3426                     /* not enough input to decode header : tell how many bytes would be necessary */
3427                     *maxDstSizePtr = 0;
3428                     return headerSize - zbc->hPos;
3429             }   }
3430             /* intentional fallthrough */
3431
3432         case ZBUFFds_decodeHeader:
3433                 /* apply header to create / resize buffers */
3434                 {   size_t const neededOutSize = (size_t)1 << zbc->params.windowLog;
3435                     size_t const neededInSize = BLOCKSIZE;   /* a block is never > BLOCKSIZE */
3436                     if (zbc->inBuffSize < neededInSize) {
3437                         free(zbc->inBuff);
3438                         zbc->inBuffSize = neededInSize;
3439                         zbc->inBuff = (char*)malloc(neededInSize);
3440                         if (zbc->inBuff == NULL) return ERROR(memory_allocation);
3441                     }
3442                     if (zbc->outBuffSize < neededOutSize) {
3443                         free(zbc->outBuff);
3444                         zbc->outBuffSize = neededOutSize;
3445                         zbc->outBuff = (char*)malloc(neededOutSize);
3446                         if (zbc->outBuff == NULL) return ERROR(memory_allocation);
3447                 }   }
3448                 if (zbc->dictSize)
3449                     ZSTD_decompress_insertDictionary(zbc->zc, zbc->dict, zbc->dictSize);
3450                 if (zbc->hPos) {
3451                     /* some data already loaded into headerBuffer : transfer into inBuff */
3452                     memcpy(zbc->inBuff, zbc->headerBuffer, zbc->hPos);
3453                     zbc->inPos = zbc->hPos;
3454                     zbc->hPos = 0;
3455                     zbc->stage = ZBUFFds_load;
3456                     break;
3457                 }
3458                 zbc->stage = ZBUFFds_read;
3459                 /* fall-through */
3460         case ZBUFFds_read:
3461             {
3462                 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3463                 if (neededInSize==0)   /* end of frame */
3464                 {
3465                     zbc->stage = ZBUFFds_init;
3466                     notDone = 0;
3467                     break;
3468                 }
3469                 if ((size_t)(iend-ip) >= neededInSize)
3470                 {
3471                     /* directly decode from src */
3472                     size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
3473                         zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3474                         ip, neededInSize);
3475                     if (ZSTD_isError(decodedSize)) return decodedSize;
3476                     ip += neededInSize;
3477                     if (!decodedSize) break;   /* this was just a header */
3478                     zbc->outEnd = zbc->outStart +  decodedSize;
3479                     zbc->stage = ZBUFFds_flush;
3480                     break;
3481                 }
3482                 if (ip==iend) { notDone = 0; break; }   /* no more input */
3483                 zbc->stage = ZBUFFds_load;
3484             }
3485             /* fall-through */
3486         case ZBUFFds_load:
3487             {
3488                 size_t neededInSize = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3489                 size_t toLoad = neededInSize - zbc->inPos;   /* should always be <= remaining space within inBuff */
3490                 size_t loadedSize;
3491                 if (toLoad > zbc->inBuffSize - zbc->inPos) return ERROR(corruption_detected);   /* should never happen */
3492                 loadedSize = ZBUFF_limitCopy(zbc->inBuff + zbc->inPos, toLoad, ip, iend-ip);
3493                 ip += loadedSize;
3494                 zbc->inPos += loadedSize;
3495                 if (loadedSize < toLoad) { notDone = 0; break; }   /* not enough input, wait for more */
3496                 {
3497                     size_t decodedSize = ZSTD_decompressContinue(zbc->zc,
3498                         zbc->outBuff + zbc->outStart, zbc->outBuffSize - zbc->outStart,
3499                         zbc->inBuff, neededInSize);
3500                     if (ZSTD_isError(decodedSize)) return decodedSize;
3501                     zbc->inPos = 0;   /* input is consumed */
3502                     if (!decodedSize) { zbc->stage = ZBUFFds_read; break; }   /* this was just a header */
3503                     zbc->outEnd = zbc->outStart +  decodedSize;
3504                     zbc->stage = ZBUFFds_flush;
3505                     /* ZBUFFds_flush follows */
3506                 }
3507             }
3508             /* fall-through */
3509         case ZBUFFds_flush:
3510             {
3511                 size_t toFlushSize = zbc->outEnd - zbc->outStart;
3512                 size_t flushedSize = ZBUFF_limitCopy(op, oend-op, zbc->outBuff + zbc->outStart, toFlushSize);
3513                 op += flushedSize;
3514                 zbc->outStart += flushedSize;
3515                 if (flushedSize == toFlushSize)
3516                 {
3517                     zbc->stage = ZBUFFds_read;
3518                     if (zbc->outStart + BLOCKSIZE > zbc->outBuffSize)
3519                         zbc->outStart = zbc->outEnd = 0;
3520                     break;
3521                 }
3522                 /* cannot flush everything */
3523                 notDone = 0;
3524                 break;
3525             }
3526         default: return ERROR(GENERIC);   /* impossible */
3527         }
3528     }
3529
3530     *srcSizePtr = ip-istart;
3531     *maxDstSizePtr = op-ostart;
3532
3533     {
3534         size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zbc->zc);
3535         if (nextSrcSizeHint > 3) nextSrcSizeHint+= 3;   /* get the next block header while at it */
3536         nextSrcSizeHint -= zbc->inPos;   /* already loaded*/
3537         return nextSrcSizeHint;
3538     }
3539 }
3540
3541
3542 /* *************************************
3543 *  Tool functions
3544 ***************************************/
3545 unsigned ZBUFFv04_isError(size_t errorCode) { return ERR_isError(errorCode); }
3546 const char* ZBUFFv04_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
3547
3548 size_t ZBUFFv04_recommendedDInSize()  { return BLOCKSIZE + 3; }
3549 size_t ZBUFFv04_recommendedDOutSize() { return BLOCKSIZE; }
3550
3551
3552
3553 /*- ========================================================================= -*/
3554
3555 /* final wrapping stage */
3556
3557 size_t ZSTDv04_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3558 {
3559     return ZSTD_decompress_usingDict(dctx, dst, maxDstSize, src, srcSize, NULL, 0);
3560 }
3561
3562 size_t ZSTDv04_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3563 {
3564 #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE==1)
3565     size_t regenSize;
3566     ZSTD_DCtx* dctx = ZSTD_createDCtx();
3567     if (dctx==NULL) return ERROR(memory_allocation);
3568     regenSize = ZSTDv04_decompressDCtx(dctx, dst, maxDstSize, src, srcSize);
3569     ZSTD_freeDCtx(dctx);
3570     return regenSize;
3571 #else
3572     ZSTD_DCtx dctx;
3573     return ZSTDv04_decompressDCtx(&dctx, dst, maxDstSize, src, srcSize);
3574 #endif
3575 }
3576
3577 size_t ZSTDv04_resetDCtx(ZSTDv04_Dctx* dctx) { return ZSTD_resetDCtx(dctx); }
3578
3579 size_t ZSTDv04_nextSrcSizeToDecompress(ZSTDv04_Dctx* dctx)
3580 {
3581     return ZSTD_nextSrcSizeToDecompress(dctx);
3582 }
3583
3584 size_t ZSTDv04_decompressContinue(ZSTDv04_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3585 {
3586     return ZSTD_decompressContinue(dctx, dst, maxDstSize, src, srcSize);
3587 }
3588
3589
3590
3591 ZBUFFv04_DCtx* ZBUFFv04_createDCtx(void) { return ZBUFF_createDCtx(); }
3592 size_t ZBUFFv04_freeDCtx(ZBUFFv04_DCtx* dctx) { return ZBUFF_freeDCtx(dctx); }
3593
3594 size_t ZBUFFv04_decompressInit(ZBUFFv04_DCtx* dctx) { return ZBUFF_decompressInit(dctx); }
3595 size_t ZBUFFv04_decompressWithDictionary(ZBUFFv04_DCtx* dctx, const void* src, size_t srcSize)
3596 { return ZBUFF_decompressWithDictionary(dctx, src, srcSize); }
3597
3598 size_t ZBUFFv04_decompressContinue(ZBUFFv04_DCtx* dctx, void* dst, size_t* maxDstSizePtr, const void* src, size_t* srcSizePtr)
3599 {
3600     DEBUGLOG(5, "ZBUFFv04_decompressContinue");
3601     return ZBUFF_decompressContinue(dctx, dst, maxDstSizePtr, src, srcSizePtr);
3602 }
3603
3604 ZSTD_DCtx* ZSTDv04_createDCtx(void) { return ZSTD_createDCtx(); }
3605 size_t ZSTDv04_freeDCtx(ZSTD_DCtx* dctx) { return ZSTD_freeDCtx(dctx); }