sys/contrib/zstd/lib/legacy/zstd_v04.c

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