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

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