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