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