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