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