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

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