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

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