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 static const size_t ZSTD_blockHeaderSize = 3;
2373 static const size_t ZSTD_frameHeaderSize = 4;
2374
2375
2376 /* *******************************************************
2377 *  Memory operations
2378 **********************************************************/
2379 static void   ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2380
2381 static void   ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2382
2383 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2384
2385 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2386 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2387 {
2388     const BYTE* ip = (const BYTE*)src;
2389     BYTE* op = (BYTE*)dst;
2390     BYTE* const oend = op + length;
2391     do COPY8(op, ip) while (op < oend);
2392 }
2393
2394
2395 /* **************************************
2396 *  Local structures
2397 ****************************************/
2398 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2399
2400 typedef struct
2401 {
2402     blockType_t blockType;
2403     U32 origSize;
2404 } blockProperties_t;
2405
2406 typedef struct {
2407     void* buffer;
2408     U32*  offsetStart;
2409     U32*  offset;
2410     BYTE* offCodeStart;
2411     BYTE* offCode;
2412     BYTE* litStart;
2413     BYTE* lit;
2414     BYTE* litLengthStart;
2415     BYTE* litLength;
2416     BYTE* matchLengthStart;
2417     BYTE* matchLength;
2418     BYTE* dumpsStart;
2419     BYTE* dumps;
2420 } seqStore_t;
2421
2422
2423 /* *************************************
2424 *  Error Management
2425 ***************************************/
2426 /*! ZSTD_isError
2427 *   tells if a return value is an error code */
2428 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2429
2430
2431
2432 /* *************************************************************
2433 *   Decompression section
2434 ***************************************************************/
2435 struct ZSTD_DCtx_s
2436 {
2437     U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2438     U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2439     U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2440     void* previousDstEnd;
2441     void* base;
2442     size_t expected;
2443     blockType_t bType;
2444     U32 phase;
2445     const BYTE* litPtr;
2446     size_t litSize;
2447     BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2448 };   /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2449
2450
2451 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2452 {
2453     const BYTE* const in = (const BYTE* const)src;
2454     BYTE headerFlags;
2455     U32 cSize;
2456
2457     if (srcSize < 3) return ERROR(srcSize_wrong);
2458
2459     headerFlags = *in;
2460     cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2461
2462     bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2463     bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2464
2465     if (bpPtr->blockType == bt_end) return 0;
2466     if (bpPtr->blockType == bt_rle) return 1;
2467     return cSize;
2468 }
2469
2470 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2471 {
2472     if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2473     memcpy(dst, src, srcSize);
2474     return srcSize;
2475 }
2476
2477
2478 /** ZSTD_decompressLiterals
2479     @return : nb of bytes read from src, or an error code*/
2480 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2481                                 const void* src, size_t srcSize)
2482 {
2483     const BYTE* ip = (const BYTE*)src;
2484
2485     const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2486     const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2487
2488     if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2489     if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2490
2491     if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2492
2493     *maxDstSizePtr = litSize;
2494     return litCSize + 5;
2495 }
2496
2497
2498 /** ZSTD_decodeLiteralsBlock
2499     @return : nb of bytes read from src (< srcSize )*/
2500 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2501                           const void* src, size_t srcSize)
2502 {
2503     ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2504     const BYTE* const istart = (const BYTE* const)src;
2505
2506     /* any compressed block with literals segment must be at least this size */
2507     if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2508
2509     switch(*istart & 3)
2510     {
2511     default:
2512     case 0:
2513         {
2514             size_t litSize = BLOCKSIZE;
2515             const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2516             dctx->litPtr = dctx->litBuffer;
2517             dctx->litSize = litSize;
2518             memset(dctx->litBuffer + dctx->litSize, 0, 8);
2519             return readSize;   /* works if it's an error too */
2520         }
2521     case IS_RAW:
2522         {
2523             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2524             if (litSize > srcSize-11)   /* risk of reading too far with wildcopy */
2525             {
2526                 if (litSize > srcSize-3) return ERROR(corruption_detected);
2527                 memcpy(dctx->litBuffer, istart, litSize);
2528                 dctx->litPtr = dctx->litBuffer;
2529                 dctx->litSize = litSize;
2530                 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2531                 return litSize+3;
2532             }
2533             /* direct reference into compressed stream */
2534             dctx->litPtr = istart+3;
2535             dctx->litSize = litSize;
2536             return litSize+3;
2537         }
2538     case IS_RLE:
2539         {
2540             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2541             if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2542             memset(dctx->litBuffer, istart[3], litSize + 8);
2543             dctx->litPtr = dctx->litBuffer;
2544             dctx->litSize = litSize;
2545             return 4;
2546         }
2547     }
2548 }
2549
2550
2551 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2552                          FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2553                          const void* src, size_t srcSize)
2554 {
2555     const BYTE* const istart = (const BYTE* const)src;
2556     const BYTE* ip = istart;
2557     const BYTE* const iend = istart + srcSize;
2558     U32 LLtype, Offtype, MLtype;
2559     U32 LLlog, Offlog, MLlog;
2560     size_t dumpsLength;
2561
2562     /* check */
2563     if (srcSize < 5) return ERROR(srcSize_wrong);
2564
2565     /* SeqHead */
2566     *nbSeq = MEM_readLE16(ip); ip+=2;
2567     LLtype  = *ip >> 6;
2568     Offtype = (*ip >> 4) & 3;
2569     MLtype  = (*ip >> 2) & 3;
2570     if (*ip & 2)
2571     {
2572         dumpsLength  = ip[2];
2573         dumpsLength += ip[1] << 8;
2574         ip += 3;
2575     }
2576     else
2577     {
2578         dumpsLength  = ip[1];
2579         dumpsLength += (ip[0] & 1) << 8;
2580         ip += 2;
2581     }
2582     *dumpsPtr = ip;
2583     ip += dumpsLength;
2584     *dumpsLengthPtr = dumpsLength;
2585
2586     /* check */
2587     if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2588
2589     /* sequences */
2590     {
2591         S16 norm[MaxML+1];    /* assumption : MaxML >= MaxLL and MaxOff */
2592         size_t headerSize;
2593
2594         /* Build DTables */
2595         switch(LLtype)
2596         {
2597         case bt_rle :
2598             LLlog = 0;
2599             FSE_buildDTable_rle(DTableLL, *ip++); break;
2600         case bt_raw :
2601             LLlog = LLbits;
2602             FSE_buildDTable_raw(DTableLL, LLbits); break;
2603         default :
2604             {   U32 max = MaxLL;
2605                 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2606                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2607                 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2608                 ip += headerSize;
2609                 FSE_buildDTable(DTableLL, norm, max, LLlog);
2610         }   }
2611
2612         switch(Offtype)
2613         {
2614         case bt_rle :
2615             Offlog = 0;
2616             if (ip > iend-2) return ERROR(srcSize_wrong);   /* min : "raw", hence no header, but at least xxLog bits */
2617             FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2618             break;
2619         case bt_raw :
2620             Offlog = Offbits;
2621             FSE_buildDTable_raw(DTableOffb, Offbits); break;
2622         default :
2623             {   U32 max = MaxOff;
2624                 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2625                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2626                 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2627                 ip += headerSize;
2628                 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2629         }   }
2630
2631         switch(MLtype)
2632         {
2633         case bt_rle :
2634             MLlog = 0;
2635             if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2636             FSE_buildDTable_rle(DTableML, *ip++); break;
2637         case bt_raw :
2638             MLlog = MLbits;
2639             FSE_buildDTable_raw(DTableML, MLbits); break;
2640         default :
2641             {   U32 max = MaxML;
2642                 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2643                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2644                 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2645                 ip += headerSize;
2646                 FSE_buildDTable(DTableML, norm, max, MLlog);
2647     }   }   }
2648
2649     return ip-istart;
2650 }
2651
2652
2653 typedef struct {
2654     size_t litLength;
2655     size_t offset;
2656     size_t matchLength;
2657 } seq_t;
2658
2659 typedef struct {
2660     BIT_DStream_t DStream;
2661     FSE_DState_t stateLL;
2662     FSE_DState_t stateOffb;
2663     FSE_DState_t stateML;
2664     size_t prevOffset;
2665     const BYTE* dumps;
2666     const BYTE* dumpsEnd;
2667 } seqState_t;
2668
2669
2670 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2671 {
2672     size_t litLength;
2673     size_t prevOffset;
2674     size_t offset;
2675     size_t matchLength;
2676     const BYTE* dumps = seqState->dumps;
2677     const BYTE* const de = seqState->dumpsEnd;
2678
2679     /* Literal length */
2680     litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2681     prevOffset = litLength ? seq->offset : seqState->prevOffset;
2682     seqState->prevOffset = seq->offset;
2683     if (litLength == MaxLL)
2684     {
2685         U32 add = *dumps++;
2686         if (add < 255) litLength += add;
2687         else
2688         {
2689             litLength = MEM_readLE32(dumps) & 0xFFFFFF;  /* no pb : dumps is always followed by seq tables > 1 byte */
2690             dumps += 3;
2691         }
2692         if (dumps >= de) dumps = de-1;   /* late correction, to avoid read overflow (data is now corrupted anyway) */
2693     }
2694
2695     /* Offset */
2696     {
2697         static const size_t offsetPrefix[MaxOff+1] = {  /* note : size_t faster than U32 */
2698                 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2699                 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2700                 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2701         U32 offsetCode, nbBits;
2702         offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream));   /* <= maxOff, by table construction */
2703         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2704         nbBits = offsetCode - 1;
2705         if (offsetCode==0) nbBits = 0;   /* cmove */
2706         offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2707         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2708         if (offsetCode==0) offset = prevOffset;   /* cmove */
2709     }
2710
2711     /* MatchLength */
2712     matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2713     if (matchLength == MaxML)
2714     {
2715         U32 add = *dumps++;
2716         if (add < 255) matchLength += add;
2717         else
2718         {
2719             matchLength = MEM_readLE32(dumps) & 0xFFFFFF;  /* no pb : dumps is always followed by seq tables > 1 byte */
2720             dumps += 3;
2721         }
2722         if (dumps >= de) dumps = de-1;   /* late correction, to avoid read overflow (data is now corrupted anyway) */
2723     }
2724     matchLength += MINMATCH;
2725
2726     /* save result */
2727     seq->litLength = litLength;
2728     seq->offset = offset;
2729     seq->matchLength = matchLength;
2730     seqState->dumps = dumps;
2731 }
2732
2733
2734 static size_t ZSTD_execSequence(BYTE* op,
2735                                 seq_t sequence,
2736                                 const BYTE** litPtr, const BYTE* const litLimit,
2737                                 BYTE* const base, BYTE* const oend)
2738 {
2739     static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* added */
2740     static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11};   /* substracted */
2741     const BYTE* const ostart = op;
2742     BYTE* const oLitEnd = op + sequence.litLength;
2743     BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength;   /* risk : address space overflow (32-bits) */
2744     BYTE* const oend_8 = oend-8;
2745     const BYTE* const litEnd = *litPtr + sequence.litLength;
2746
2747     /* checks */
2748     if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);   /* last match must start at a minimum distance of 8 from oend */
2749     if (oMatchEnd > oend) return ERROR(dstSize_tooSmall);   /* overwrite beyond dst buffer */
2750     if (litEnd > litLimit) return ERROR(corruption_detected);   /* overRead beyond lit buffer */
2751
2752     /* copy Literals */
2753     ZSTD_wildcopy(op, *litPtr, sequence.litLength);   /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2754     op = oLitEnd;
2755     *litPtr = litEnd;   /* update for next sequence */
2756
2757     /* copy Match */
2758     {
2759         const BYTE* match = op - sequence.offset;
2760
2761         /* check */
2762         if (sequence.offset > (size_t)op) return ERROR(corruption_detected);   /* address space overflow test (this test seems kept by clang optimizer) */
2763         //if (match > op) return ERROR(corruption_detected);   /* address space overflow test (is clang optimizer removing this test ?) */
2764         if (match < base) return ERROR(corruption_detected);
2765
2766         /* close range match, overlap */
2767         if (sequence.offset < 8)
2768         {
2769             const int dec64 = dec64table[sequence.offset];
2770             op[0] = match[0];
2771             op[1] = match[1];
2772             op[2] = match[2];
2773             op[3] = match[3];
2774             match += dec32table[sequence.offset];
2775             ZSTD_copy4(op+4, match);
2776             match -= dec64;
2777         }
2778         else
2779         {
2780             ZSTD_copy8(op, match);
2781         }
2782         op += 8; match += 8;
2783
2784         if (oMatchEnd > oend-(16-MINMATCH))
2785         {
2786             if (op < oend_8)
2787             {
2788                 ZSTD_wildcopy(op, match, oend_8 - op);
2789                 match += oend_8 - op;
2790                 op = oend_8;
2791             }
2792             while (op < oMatchEnd) *op++ = *match++;
2793         }
2794         else
2795         {
2796             ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
2797         }
2798     }
2799
2800     return oMatchEnd - ostart;
2801 }
2802
2803 static size_t ZSTD_decompressSequences(
2804                                void* ctx,
2805                                void* dst, size_t maxDstSize,
2806                          const void* seqStart, size_t seqSize)
2807 {
2808     ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2809     const BYTE* ip = (const BYTE*)seqStart;
2810     const BYTE* const iend = ip + seqSize;
2811     BYTE* const ostart = (BYTE* const)dst;
2812     BYTE* op = ostart;
2813     BYTE* const oend = ostart + maxDstSize;
2814     size_t errorCode, dumpsLength;
2815     const BYTE* litPtr = dctx->litPtr;
2816     const BYTE* const litEnd = litPtr + dctx->litSize;
2817     int nbSeq;
2818     const BYTE* dumps;
2819     U32* DTableLL = dctx->LLTable;
2820     U32* DTableML = dctx->MLTable;
2821     U32* DTableOffb = dctx->OffTable;
2822     BYTE* const base = (BYTE*) (dctx->base);
2823
2824     /* Build Decoding Tables */
2825     errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2826                                       DTableLL, DTableML, DTableOffb,
2827                                       ip, iend-ip);
2828     if (ZSTD_isError(errorCode)) return errorCode;
2829     ip += errorCode;
2830
2831     /* Regen sequences */
2832     {
2833         seq_t sequence;
2834         seqState_t seqState;
2835
2836         memset(&sequence, 0, sizeof(sequence));
2837         seqState.dumps = dumps;
2838         seqState.dumpsEnd = dumps + dumpsLength;
2839         seqState.prevOffset = sequence.offset = 4;
2840         errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2841         if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2842         FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2843         FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2844         FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2845
2846         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
2847         {
2848             size_t oneSeqSize;
2849             nbSeq--;
2850             ZSTD_decodeSequence(&sequence, &seqState);
2851             oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
2852             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2853             op += oneSeqSize;
2854         }
2855
2856         /* check if reached exact end */
2857         if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected);   /* requested too much : data is corrupted */
2858         if (nbSeq<0) return ERROR(corruption_detected);   /* requested too many sequences : data is corrupted */
2859
2860         /* last literal segment */
2861         {
2862             size_t lastLLSize = litEnd - litPtr;
2863             if (litPtr > litEnd) return ERROR(corruption_detected);
2864             if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2865             if (op != litPtr) memmove(op, litPtr, lastLLSize);
2866             op += lastLLSize;
2867         }
2868     }
2869
2870     return op-ostart;
2871 }
2872
2873
2874 static size_t ZSTD_decompressBlock(
2875                             void* ctx,
2876                             void* dst, size_t maxDstSize,
2877                       const void* src, size_t srcSize)
2878 {
2879     /* blockType == blockCompressed */
2880     const BYTE* ip = (const BYTE*)src;
2881
2882     /* Decode literals sub-block */
2883     size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
2884     if (ZSTD_isError(litCSize)) return litCSize;
2885     ip += litCSize;
2886     srcSize -= litCSize;
2887
2888     return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
2889 }
2890
2891
2892 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2893 {
2894     const BYTE* ip = (const BYTE*)src;
2895     const BYTE* iend = ip + srcSize;
2896     BYTE* const ostart = (BYTE* const)dst;
2897     BYTE* op = ostart;
2898     BYTE* const oend = ostart + maxDstSize;
2899     size_t remainingSize = srcSize;
2900     U32 magicNumber;
2901     blockProperties_t blockProperties;
2902
2903     /* Frame Header */
2904     if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2905     magicNumber = MEM_readLE32(src);
2906     if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2907     ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2908
2909     /* Loop on each block */
2910     while (1)
2911     {
2912         size_t decodedSize=0;
2913         size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
2914         if (ZSTD_isError(cBlockSize)) return cBlockSize;
2915
2916         ip += ZSTD_blockHeaderSize;
2917         remainingSize -= ZSTD_blockHeaderSize;
2918         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2919
2920         switch(blockProperties.blockType)
2921         {
2922         case bt_compressed:
2923             decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
2924             break;
2925         case bt_raw :
2926             decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
2927             break;
2928         case bt_rle :
2929             return ERROR(GENERIC);   /* not yet supported */
2930             break;
2931         case bt_end :
2932             /* end of frame */
2933             if (remainingSize) return ERROR(srcSize_wrong);
2934             break;
2935         default:
2936             return ERROR(GENERIC);   /* impossible */
2937         }
2938         if (cBlockSize == 0) break;   /* bt_end */
2939
2940         if (ZSTD_isError(decodedSize)) return decodedSize;
2941         op += decodedSize;
2942         ip += cBlockSize;
2943         remainingSize -= cBlockSize;
2944     }
2945
2946     return op-ostart;
2947 }
2948
2949 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2950 {
2951     ZSTD_DCtx ctx;
2952     ctx.base = dst;
2953     return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
2954 }
2955
2956 static size_t ZSTD_findFrameCompressedSize(const void* src, size_t srcSize)
2957 {
2958     const BYTE* ip = (const BYTE*)src;
2959     size_t remainingSize = srcSize;
2960     U32 magicNumber;
2961     blockProperties_t blockProperties;
2962
2963     /* Frame Header */
2964     if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2965     magicNumber = MEM_readLE32(src);
2966     if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2967     ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2968
2969     /* Loop on each block */
2970     while (1)
2971     {
2972         size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
2973         if (ZSTD_isError(cBlockSize)) return cBlockSize;
2974
2975         ip += ZSTD_blockHeaderSize;
2976         remainingSize -= ZSTD_blockHeaderSize;
2977         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2978
2979         if (cBlockSize == 0) break;   /* bt_end */
2980
2981         ip += cBlockSize;
2982         remainingSize -= cBlockSize;
2983     }
2984
2985     return ip - (const BYTE*)src;
2986 }
2987
2988
2989 /*******************************
2990 *  Streaming Decompression API
2991 *******************************/
2992
2993 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2994 {
2995     dctx->expected = ZSTD_frameHeaderSize;
2996     dctx->phase = 0;
2997     dctx->previousDstEnd = NULL;
2998     dctx->base = NULL;
2999     return 0;
3000 }
3001
3002 static ZSTD_DCtx* ZSTD_createDCtx(void)
3003 {
3004     ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
3005     if (dctx==NULL) return NULL;
3006     ZSTD_resetDCtx(dctx);
3007     return dctx;
3008 }
3009
3010 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
3011 {
3012     free(dctx);
3013     return 0;
3014 }
3015
3016 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
3017 {
3018     return dctx->expected;
3019 }
3020
3021 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3022 {
3023     /* Sanity check */
3024     if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3025     if (dst != ctx->previousDstEnd)  /* not contiguous */
3026         ctx->base = dst;
3027
3028     /* Decompress : frame header */
3029     if (ctx->phase == 0)
3030     {
3031         /* Check frame magic header */
3032         U32 magicNumber = MEM_readLE32(src);
3033         if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3034         ctx->phase = 1;
3035         ctx->expected = ZSTD_blockHeaderSize;
3036         return 0;
3037     }
3038
3039     /* Decompress : block header */
3040     if (ctx->phase == 1)
3041     {
3042         blockProperties_t bp;
3043         size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3044         if (ZSTD_isError(blockSize)) return blockSize;
3045         if (bp.blockType == bt_end)
3046         {
3047             ctx->expected = 0;
3048             ctx->phase = 0;
3049         }
3050         else
3051         {
3052             ctx->expected = blockSize;
3053             ctx->bType = bp.blockType;
3054             ctx->phase = 2;
3055         }
3056
3057         return 0;
3058     }
3059
3060     /* Decompress : block content */
3061     {
3062         size_t rSize;
3063         switch(ctx->bType)
3064         {
3065         case bt_compressed:
3066             rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3067             break;
3068         case bt_raw :
3069             rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3070             break;
3071         case bt_rle :
3072             return ERROR(GENERIC);   /* not yet handled */
3073             break;
3074         case bt_end :   /* should never happen (filtered at phase 1) */
3075             rSize = 0;
3076             break;
3077         default:
3078             return ERROR(GENERIC);
3079         }
3080         ctx->phase = 1;
3081         ctx->expected = ZSTD_blockHeaderSize;
3082         ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3083         return rSize;
3084     }
3085
3086 }
3087
3088
3089 /* wrapper layer */
3090
3091 unsigned ZSTDv03_isError(size_t code)
3092 {
3093     return ZSTD_isError(code);
3094 }
3095
3096 size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3097                      const void* src, size_t compressedSize)
3098 {
3099     return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3100 }
3101
3102 size_t ZSTDv03_findFrameCompressedSize(const void* src, size_t srcSize)
3103 {
3104     return ZSTD_findFrameCompressedSize(src, srcSize);
3105 }
3106
3107 ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3108 {
3109     return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3110 }
3111
3112 size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3113 {
3114     return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3115 }
3116
3117 size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3118 {
3119     return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3120 }
3121
3122 size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3123 {
3124     return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3125 }
3126
3127 size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3128 {
3129     return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);
3130 }