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