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

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