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

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