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

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