deps/libchdr/deps/zstd-1.5.6/lib/legacy/zstd_v02.c

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