deps/libchdr/deps/zstd-1.5.6/lib/legacy/zstd_v03.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_v03.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 /* ******************************************************************
  29    mem.h
  30    low-level memory access routines
  31    Copyright (C) 2013-2015, Yann Collet.
  32
  33    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
  34
  35    Redistribution and use in source and binary forms, with or without
  36    modification, are permitted provided that the following conditions are
  37    met:
  38
  39        * Redistributions of source code must retain the above copyright
  40    notice, this list of conditions and the following disclaimer.
  41        * Redistributions in binary form must reproduce the above
  42    copyright notice, this list of conditions and the following disclaimer
  43    in the documentation and/or other materials provided with the
  44    distribution.
  45
  46    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  47    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  48    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  49    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  50    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  51    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  52    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  53    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  54    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  55    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  56    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  57
  58     You can contact the author at :
  59     - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
  60     - Public forum : https://groups.google.com/forum/#!forum/lz4c
  61 ****************************************************************** */
  62 #ifndef MEM_H_MODULE
  63 #define MEM_H_MODULE
  64
  65 #if defined (__cplusplus)
  66 extern "C" {
  67 #endif
  68
  69 /******************************************
  70 *  Includes
  71 ******************************************/
  72 #include <stddef.h>    /* size_t, ptrdiff_t */
  73 #include <string.h>    /* memcpy */
  74
  75
  76 /****************************************************************
  77 *  Basic Types
  78 *****************************************************************/
  79 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
  80 # if defined(_AIX)
  81 #  include <inttypes.h>
  82 # else
  83 #  include <stdint.h> /* intptr_t */
  84 # endif
  85   typedef  uint8_t BYTE;
  86   typedef uint16_t U16;
  87   typedef  int16_t S16;
  88   typedef uint32_t U32;
  89   typedef  int32_t S32;
  90   typedef uint64_t U64;
  91   typedef  int64_t S64;
  92 #else
  93   typedef unsigned char       BYTE;
  94   typedef unsigned short      U16;
  95   typedef   signed short      S16;
  96   typedef unsigned int        U32;
  97   typedef   signed int        S32;
  98   typedef unsigned long long  U64;
  99   typedef   signed long long  S64;
 100 #endif
 101
 102
 103 /****************************************************************
 104 *  Memory I/O
 105 *****************************************************************/
 106
 107 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(void*)==4; }
 108 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(void*)==8; }
 109
 110 MEM_STATIC unsigned MEM_isLittleEndian(void)
 111 {
 112     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
 113     return one.c[0];
 114 }
 115
 116 MEM_STATIC U16 MEM_read16(const void* memPtr)
 117 {
 118     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
 119 }
 120
 121 MEM_STATIC U32 MEM_read32(const void* memPtr)
 122 {
 123     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
 124 }
 125
 126 MEM_STATIC U64 MEM_read64(const void* memPtr)
 127 {
 128     U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
 129 }
 130
 131 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
 132 {
 133     memcpy(memPtr, &value, sizeof(value));
 134 }
 135
 136 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
 137 {
 138     if (MEM_isLittleEndian())
 139         return MEM_read16(memPtr);
 140     else
 141     {
 142         const BYTE* p = (const BYTE*)memPtr;
 143         return (U16)(p[0] + (p[1]<<8));
 144     }
 145 }
 146
 147 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
 148 {
 149     if (MEM_isLittleEndian())
 150     {
 151         MEM_write16(memPtr, val);
 152     }
 153     else
 154     {
 155         BYTE* p = (BYTE*)memPtr;
 156         p[0] = (BYTE)val;
 157         p[1] = (BYTE)(val>>8);
 158     }
 159 }
 160
 161 MEM_STATIC U32 MEM_readLE24(const void* memPtr)
 162 {
 163     return MEM_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
 164 }
 165
 166 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
 167 {
 168     if (MEM_isLittleEndian())
 169         return MEM_read32(memPtr);
 170     else
 171     {
 172         const BYTE* p = (const BYTE*)memPtr;
 173         return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
 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
 199 #if defined (__cplusplus)
 200 }
 201 #endif
 202
 203 #endif /* MEM_H_MODULE */
 204
 205
 206 /* ******************************************************************
 207    bitstream
 208    Part of NewGen Entropy library
 209    header file (to include)
 210    Copyright (C) 2013-2015, Yann Collet.
 211
 212    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 213
 214    Redistribution and use in source and binary forms, with or without
 215    modification, are permitted provided that the following conditions are
 216    met:
 217
 218        * Redistributions of source code must retain the above copyright
 219    notice, this list of conditions and the following disclaimer.
 220        * Redistributions in binary form must reproduce the above
 221    copyright notice, this list of conditions and the following disclaimer
 222    in the documentation and/or other materials provided with the
 223    distribution.
 224
 225    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 226    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 227    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 228    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 229    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 230    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 231    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 232    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 233    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 234    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 235    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 236
 237    You can contact the author at :
 238    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 239    - Public forum : https://groups.google.com/forum/#!forum/lz4c
 240 ****************************************************************** */
 241 #ifndef BITSTREAM_H_MODULE
 242 #define BITSTREAM_H_MODULE
 243
 244 #if defined (__cplusplus)
 245 extern "C" {
 246 #endif
 247
 248
 249 /*
 250 *  This API consists of small unitary functions, which highly benefit from being inlined.
 251 *  Since link-time-optimization is not available for all compilers,
 252 *  these functions are defined into a .h to be included.
 253 */
 254
 255
 256 /**********************************************
 257 *  bitStream decompression API (read backward)
 258 **********************************************/
 259 typedef struct
 260 {
 261     size_t   bitContainer;
 262     unsigned bitsConsumed;
 263     const char* ptr;
 264     const char* start;
 265 } BIT_DStream_t;
 266
 267 typedef enum { BIT_DStream_unfinished = 0,
 268                BIT_DStream_endOfBuffer = 1,
 269                BIT_DStream_completed = 2,
 270                BIT_DStream_overflow = 3 } BIT_DStream_status;  /* result of BIT_reloadDStream() */
 271                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
 272
 273 MEM_STATIC size_t   BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
 274 MEM_STATIC size_t   BIT_readBits(BIT_DStream_t* bitD, unsigned nbBits);
 275 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD);
 276 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* bitD);
 277
 278
 279
 280 /******************************************
 281 *  unsafe API
 282 ******************************************/
 283 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, unsigned nbBits);
 284 /* faster, but works only if nbBits >= 1 */
 285
 286
 287
 288 /****************************************************************
 289 *  Helper functions
 290 ****************************************************************/
 291 MEM_STATIC unsigned BIT_highbit32 (U32 val)
 292 {
 293 #   if defined(_MSC_VER)   /* Visual */
 294     unsigned long r;
 295     return _BitScanReverse(&r, val) ? (unsigned)r : 0;
 296 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */
 297     return __builtin_clz (val) ^ 31;
 298 #   else   /* Software version */
 299     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 };
 300     U32 v = val;
 301     unsigned r;
 302     v |= v >> 1;
 303     v |= v >> 2;
 304     v |= v >> 4;
 305     v |= v >> 8;
 306     v |= v >> 16;
 307     r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
 308     return r;
 309 #   endif
 310 }
 311
 312
 313
 314 /**********************************************************
 315 * bitStream decoding
 316 **********************************************************/
 317
 318 /*!BIT_initDStream
 319 *  Initialize a BIT_DStream_t.
 320 *  @bitD : a pointer to an already allocated BIT_DStream_t structure
 321 *  @srcBuffer must point at the beginning of a bitStream
 322 *  @srcSize must be the exact size of the bitStream
 323 *  @result : size of stream (== srcSize) or an errorCode if a problem is detected
 324 */
 325 MEM_STATIC size_t BIT_initDStream(BIT_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
 326 {
 327     if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
 328
 329     if (srcSize >=  sizeof(size_t))   /* normal case */
 330     {
 331         U32 contain32;
 332         bitD->start = (const char*)srcBuffer;
 333         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(size_t);
 334         bitD->bitContainer = MEM_readLEST(bitD->ptr);
 335         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
 336         if (contain32 == 0) return ERROR(GENERIC);   /* endMark not present */
 337         bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
 338     }
 339     else
 340     {
 341         U32 contain32;
 342         bitD->start = (const char*)srcBuffer;
 343         bitD->ptr   = bitD->start;
 344         bitD->bitContainer = *(const BYTE*)(bitD->start);
 345         switch(srcSize)
 346         {
 347             case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
 348                     /* fallthrough */
 349             case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
 350                     /* fallthrough */
 351             case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
 352                     /* fallthrough */
 353             case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
 354                     /* fallthrough */
 355             case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
 356                     /* fallthrough */
 357             case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) <<  8;
 358                     /* fallthrough */
 359             default:;
 360         }
 361         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
 362         if (contain32 == 0) return ERROR(GENERIC);   /* endMark not present */
 363         bitD->bitsConsumed = 8 - BIT_highbit32(contain32);
 364         bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
 365     }
 366
 367     return srcSize;
 368 }
 369 MEM_STATIC size_t BIT_lookBits(BIT_DStream_t* bitD, U32 nbBits)
 370 {
 371     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
 372     return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
 373 }
 374
 375 /*! BIT_lookBitsFast :
 376 *   unsafe version; only works if nbBits >= 1 */
 377 MEM_STATIC size_t BIT_lookBitsFast(BIT_DStream_t* bitD, U32 nbBits)
 378 {
 379     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
 380     return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
 381 }
 382
 383 MEM_STATIC void BIT_skipBits(BIT_DStream_t* bitD, U32 nbBits)
 384 {
 385     bitD->bitsConsumed += nbBits;
 386 }
 387
 388 MEM_STATIC size_t BIT_readBits(BIT_DStream_t* bitD, U32 nbBits)
 389 {
 390     size_t value = BIT_lookBits(bitD, nbBits);
 391     BIT_skipBits(bitD, nbBits);
 392     return value;
 393 }
 394
 395 /*!BIT_readBitsFast :
 396 *  unsafe version; only works if nbBits >= 1 */
 397 MEM_STATIC size_t BIT_readBitsFast(BIT_DStream_t* bitD, U32 nbBits)
 398 {
 399     size_t value = BIT_lookBitsFast(bitD, nbBits);
 400     BIT_skipBits(bitD, nbBits);
 401     return value;
 402 }
 403
 404 MEM_STATIC BIT_DStream_status BIT_reloadDStream(BIT_DStream_t* bitD)
 405 {
 406     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should never happen */
 407         return BIT_DStream_overflow;
 408
 409     if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
 410     {
 411         bitD->ptr -= bitD->bitsConsumed >> 3;
 412         bitD->bitsConsumed &= 7;
 413         bitD->bitContainer = MEM_readLEST(bitD->ptr);
 414         return BIT_DStream_unfinished;
 415     }
 416     if (bitD->ptr == bitD->start)
 417     {
 418         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BIT_DStream_endOfBuffer;
 419         return BIT_DStream_completed;
 420     }
 421     {
 422         U32 nbBytes = bitD->bitsConsumed >> 3;
 423         BIT_DStream_status result = BIT_DStream_unfinished;
 424         if (bitD->ptr - nbBytes < bitD->start)
 425         {
 426             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
 427             result = BIT_DStream_endOfBuffer;
 428         }
 429         bitD->ptr -= nbBytes;
 430         bitD->bitsConsumed -= nbBytes*8;
 431         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
 432         return result;
 433     }
 434 }
 435
 436 /*! BIT_endOfDStream
 437 *   @return Tells if DStream has reached its exact end
 438 */
 439 MEM_STATIC unsigned BIT_endOfDStream(const BIT_DStream_t* DStream)
 440 {
 441     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
 442 }
 443
 444 #if defined (__cplusplus)
 445 }
 446 #endif
 447
 448 #endif /* BITSTREAM_H_MODULE */
 449 /* ******************************************************************
 450    Error codes and messages
 451    Copyright (C) 2013-2015, Yann Collet
 452
 453    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 454
 455    Redistribution and use in source and binary forms, with or without
 456    modification, are permitted provided that the following conditions are
 457    met:
 458
 459        * Redistributions of source code must retain the above copyright
 460    notice, this list of conditions and the following disclaimer.
 461        * Redistributions in binary form must reproduce the above
 462    copyright notice, this list of conditions and the following disclaimer
 463    in the documentation and/or other materials provided with the
 464    distribution.
 465
 466    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 467    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 468    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 469    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 470    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 471    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 472    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 473    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 474    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 475    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 476    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 477
 478    You can contact the author at :
 479    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 480    - Public forum : https://groups.google.com/forum/#!forum/lz4c
 481 ****************************************************************** */
 482 #ifndef ERROR_H_MODULE
 483 #define ERROR_H_MODULE
 484
 485 #if defined (__cplusplus)
 486 extern "C" {
 487 #endif
 488
 489
 490 /******************************************
 491 *  Compiler-specific
 492 ******************************************/
 493 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
 494 #  define ERR_STATIC static inline
 495 #elif defined(_MSC_VER)
 496 #  define ERR_STATIC static __inline
 497 #elif defined(__GNUC__)
 498 #  define ERR_STATIC static __attribute__((unused))
 499 #else
 500 #  define ERR_STATIC static  /* this version may generate warnings for unused static functions; disable the relevant warning */
 501 #endif
 502
 503
 504 /******************************************
 505 *  Error Management
 506 ******************************************/
 507 #define PREFIX(name) ZSTD_error_##name
 508
 509 #define ERROR(name) (size_t)-PREFIX(name)
 510
 511 #define ERROR_LIST(ITEM) \
 512         ITEM(PREFIX(No_Error)) ITEM(PREFIX(GENERIC)) \
 513         ITEM(PREFIX(dstSize_tooSmall)) ITEM(PREFIX(srcSize_wrong)) \
 514         ITEM(PREFIX(prefix_unknown)) ITEM(PREFIX(corruption_detected)) \
 515         ITEM(PREFIX(tableLog_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooLarge)) ITEM(PREFIX(maxSymbolValue_tooSmall)) \
 516         ITEM(PREFIX(maxCode))
 517
 518 #define ERROR_GENERATE_ENUM(ENUM) ENUM,
 519 typedef enum { ERROR_LIST(ERROR_GENERATE_ENUM) } ERR_codes;  /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
 520
 521 #define ERROR_CONVERTTOSTRING(STRING) #STRING,
 522 #define ERROR_GENERATE_STRING(EXPR) ERROR_CONVERTTOSTRING(EXPR)
 523 static const char* ERR_strings[] = { ERROR_LIST(ERROR_GENERATE_STRING) };
 524
 525 ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); }
 526
 527 ERR_STATIC const char* ERR_getErrorName(size_t code)
 528 {
 529     static const char* codeError = "Unspecified error code";
 530     if (ERR_isError(code)) return ERR_strings[-(int)(code)];
 531     return codeError;
 532 }
 533
 534
 535 #if defined (__cplusplus)
 536 }
 537 #endif
 538
 539 #endif /* ERROR_H_MODULE */
 540 /*
 541 Constructor and Destructor of type FSE_CTable
 542     Note that its size depends on 'tableLog' and 'maxSymbolValue' */
 543 typedef unsigned FSE_CTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
 544 typedef unsigned FSE_DTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
 545
 546
 547 /* ******************************************************************
 548    FSE : Finite State Entropy coder
 549    header file for static linking (only)
 550    Copyright (C) 2013-2015, Yann Collet
 551
 552    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 553
 554    Redistribution and use in source and binary forms, with or without
 555    modification, are permitted provided that the following conditions are
 556    met:
 557
 558        * Redistributions of source code must retain the above copyright
 559    notice, this list of conditions and the following disclaimer.
 560        * Redistributions in binary form must reproduce the above
 561    copyright notice, this list of conditions and the following disclaimer
 562    in the documentation and/or other materials provided with the
 563    distribution.
 564
 565    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 566    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 567    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 568    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 569    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 570    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 571    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 572    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 573    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 574    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 575    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 576
 577    You can contact the author at :
 578    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 579    - Public forum : https://groups.google.com/forum/#!forum/lz4c
 580 ****************************************************************** */
 581 #if defined (__cplusplus)
 582 extern "C" {
 583 #endif
 584
 585
 586 /******************************************
 587 *  Static allocation
 588 ******************************************/
 589 /* FSE buffer bounds */
 590 #define FSE_NCOUNTBOUND 512
 591 #define FSE_BLOCKBOUND(size) (size + (size>>7))
 592 #define FSE_COMPRESSBOUND(size) (FSE_NCOUNTBOUND + FSE_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
 593
 594 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
 595 #define FSE_CTABLE_SIZE_U32(maxTableLog, maxSymbolValue)   (1 + (1<<(maxTableLog-1)) + ((maxSymbolValue+1)*2))
 596 #define FSE_DTABLE_SIZE_U32(maxTableLog)                   (1 + (1<<maxTableLog))
 597
 598
 599 /******************************************
 600 *  FSE advanced API
 601 ******************************************/
 602 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits);
 603 /* build a fake FSE_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
 604
 605 static size_t FSE_buildDTable_rle (FSE_DTable* dt, unsigned char symbolValue);
 606 /* build a fake FSE_DTable, designed to always generate the same symbolValue */
 607
 608
 609 /******************************************
 610 *  FSE symbol decompression API
 611 ******************************************/
 612 typedef struct
 613 {
 614     size_t      state;
 615     const void* table;   /* precise table may vary, depending on U16 */
 616 } FSE_DState_t;
 617
 618
 619 static void     FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt);
 620
 621 static unsigned char FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
 622
 623 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr);
 624
 625
 626 /******************************************
 627 *  FSE unsafe API
 628 ******************************************/
 629 static unsigned char FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD);
 630 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
 631
 632
 633 /******************************************
 634 *  Implementation of inline functions
 635 ******************************************/
 636
 637 /* decompression */
 638
 639 typedef struct {
 640     U16 tableLog;
 641     U16 fastMode;
 642 } FSE_DTableHeader;   /* sizeof U32 */
 643
 644 typedef struct
 645 {
 646     unsigned short newState;
 647     unsigned char  symbol;
 648     unsigned char  nbBits;
 649 } FSE_decode_t;   /* size == U32 */
 650
 651 MEM_STATIC void FSE_initDState(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD, const FSE_DTable* dt)
 652 {
 653     FSE_DTableHeader DTableH;
 654     memcpy(&DTableH, dt, sizeof(DTableH));
 655     DStatePtr->state = BIT_readBits(bitD, DTableH.tableLog);
 656     BIT_reloadDStream(bitD);
 657     DStatePtr->table = dt + 1;
 658 }
 659
 660 MEM_STATIC BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
 661 {
 662     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
 663     const U32  nbBits = DInfo.nbBits;
 664     BYTE symbol = DInfo.symbol;
 665     size_t lowBits = BIT_readBits(bitD, nbBits);
 666
 667     DStatePtr->state = DInfo.newState + lowBits;
 668     return symbol;
 669 }
 670
 671 MEM_STATIC BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, BIT_DStream_t* bitD)
 672 {
 673     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
 674     const U32 nbBits = DInfo.nbBits;
 675     BYTE symbol = DInfo.symbol;
 676     size_t lowBits = BIT_readBitsFast(bitD, nbBits);
 677
 678     DStatePtr->state = DInfo.newState + lowBits;
 679     return symbol;
 680 }
 681
 682 MEM_STATIC unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
 683 {
 684     return DStatePtr->state == 0;
 685 }
 686
 687
 688 #if defined (__cplusplus)
 689 }
 690 #endif
 691 /* ******************************************************************
 692    Huff0 : Huffman coder, part of New Generation Entropy library
 693    header file for static linking (only)
 694    Copyright (C) 2013-2015, Yann Collet
 695
 696    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 697
 698    Redistribution and use in source and binary forms, with or without
 699    modification, are permitted provided that the following conditions are
 700    met:
 701
 702        * Redistributions of source code must retain the above copyright
 703    notice, this list of conditions and the following disclaimer.
 704        * Redistributions in binary form must reproduce the above
 705    copyright notice, this list of conditions and the following disclaimer
 706    in the documentation and/or other materials provided with the
 707    distribution.
 708
 709    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 710    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 711    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 712    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 713    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 714    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 715    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 716    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 717    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 718    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 719    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 720
 721    You can contact the author at :
 722    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 723    - Public forum : https://groups.google.com/forum/#!forum/lz4c
 724 ****************************************************************** */
 725
 726 #if defined (__cplusplus)
 727 extern "C" {
 728 #endif
 729
 730 /******************************************
 731 *  Static allocation macros
 732 ******************************************/
 733 /* Huff0 buffer bounds */
 734 #define HUF_CTABLEBOUND 129
 735 #define HUF_BLOCKBOUND(size) (size + (size>>8) + 8)   /* only true if incompressible pre-filtered with fast heuristic */
 736 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOUND + HUF_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
 737
 738 /* static allocation of Huff0's DTable */
 739 #define HUF_DTABLE_SIZE(maxTableLog)   (1 + (1<<maxTableLog))  /* nb Cells; use unsigned short for X2, unsigned int for X4 */
 740 #define HUF_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
 741         unsigned short DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
 742 #define HUF_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
 743         unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
 744 #define HUF_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
 745         unsigned int DTable[HUF_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
 746
 747
 748 /******************************************
 749 *  Advanced functions
 750 ******************************************/
 751 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
 752 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-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 ZSTDv03_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 0xFD2FB523   /* v0.3 */
 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_DTableHeader DTableH;
1039     FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)ptr;
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));
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 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;
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;
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 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1429 #  define inline __inline
1430 #else
1431 #  define inline /* disable inline */
1432 #endif
1433
1434
1435 /****************************************************************
1436 *  Includes
1437 ****************************************************************/
1438 #include <stdlib.h>     /* malloc, free, qsort */
1439 #include <string.h>     /* memcpy, memset */
1440 #include <stdio.h>      /* printf (debug) */
1441
1442 /****************************************************************
1443 *  Error Management
1444 ****************************************************************/
1445 #define HUF_STATIC_ASSERT(c) { enum { HUF_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1446
1447
1448 /******************************************
1449 *  Helper functions
1450 ******************************************/
1451 static unsigned HUF_isError(size_t code) { return ERR_isError(code); }
1452
1453 #define HUF_ABSOLUTEMAX_TABLELOG  16   /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
1454 #define HUF_MAX_TABLELOG  12           /* max configured tableLog (for static allocation); can be modified up to HUF_ABSOLUTEMAX_TABLELOG */
1455 #define HUF_DEFAULT_TABLELOG  HUF_MAX_TABLELOG   /* tableLog by default, when not specified */
1456 #define HUF_MAX_SYMBOL_VALUE 255
1457 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
1458 #  error "HUF_MAX_TABLELOG is too large !"
1459 #endif
1460
1461
1462
1463 /*********************************************************
1464 *  Huff0 : Huffman block decompression
1465 *********************************************************/
1466 typedef struct { BYTE byte; BYTE nbBits; } HUF_DEltX2;   /* single-symbol decoding */
1467
1468 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUF_DEltX4;  /* double-symbols decoding */
1469
1470 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1471
1472 /*! HUF_readStats
1473     Read compact Huffman tree, saved by HUF_writeCTable
1474     @huffWeight : destination buffer
1475     @return : size read from `src`
1476 */
1477 static size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1478                             U32* nbSymbolsPtr, U32* tableLogPtr,
1479                             const void* src, size_t srcSize)
1480 {
1481     U32 weightTotal;
1482     U32 tableLog;
1483     const BYTE* ip = (const BYTE*) src;
1484     size_t iSize;
1485     size_t oSize;
1486     U32 n;
1487
1488     if (!srcSize) return ERROR(srcSize_wrong);
1489     iSize = ip[0];
1490     //memset(huffWeight, 0, hwSize);   /* is not necessary, even though some analyzer complain ... */
1491
1492     if (iSize >= 128)  /* special header */
1493     {
1494         if (iSize >= (242))   /* RLE */
1495         {
1496             static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1497             oSize = l[iSize-242];
1498             memset(huffWeight, 1, hwSize);
1499             iSize = 0;
1500         }
1501         else   /* Incompressible */
1502         {
1503             oSize = iSize - 127;
1504             iSize = ((oSize+1)/2);
1505             if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1506             if (oSize >= hwSize) return ERROR(corruption_detected);
1507             ip += 1;
1508             for (n=0; n<oSize; n+=2)
1509             {
1510                 huffWeight[n]   = ip[n/2] >> 4;
1511                 huffWeight[n+1] = ip[n/2] & 15;
1512             }
1513         }
1514     }
1515     else  /* header compressed with FSE (normal case) */
1516     {
1517         if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1518         oSize = FSE_decompress(huffWeight, hwSize-1, ip+1, iSize);   /* max (hwSize-1) values decoded, as last one is implied */
1519         if (FSE_isError(oSize)) return oSize;
1520     }
1521
1522     /* collect weight stats */
1523     memset(rankStats, 0, (HUF_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1524     weightTotal = 0;
1525     for (n=0; n<oSize; n++)
1526     {
1527         if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1528         rankStats[huffWeight[n]]++;
1529         weightTotal += (1 << huffWeight[n]) >> 1;
1530     }
1531     if (weightTotal == 0) return ERROR(corruption_detected);
1532
1533     /* get last non-null symbol weight (implied, total must be 2^n) */
1534     tableLog = BIT_highbit32(weightTotal) + 1;
1535     if (tableLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1536     {
1537         U32 total = 1 << tableLog;
1538         U32 rest = total - weightTotal;
1539         U32 verif = 1 << BIT_highbit32(rest);
1540         U32 lastWeight = BIT_highbit32(rest) + 1;
1541         if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
1542         huffWeight[oSize] = (BYTE)lastWeight;
1543         rankStats[lastWeight]++;
1544     }
1545
1546     /* check tree construction validity */
1547     if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected);   /* by construction : at least 2 elts of rank 1, must be even */
1548
1549     /* results */
1550     *nbSymbolsPtr = (U32)(oSize+1);
1551     *tableLogPtr = tableLog;
1552     return iSize+1;
1553 }
1554
1555
1556 /**************************/
1557 /* single-symbol decoding */
1558 /**************************/
1559
1560 static size_t HUF_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1561 {
1562     BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
1563     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];   /* large enough for values from 0 to 16 */
1564     U32 tableLog = 0;
1565     const BYTE* ip = (const BYTE*) src;
1566     size_t iSize = ip[0];
1567     U32 nbSymbols = 0;
1568     U32 n;
1569     U32 nextRankStart;
1570     void* ptr = DTable+1;
1571     HUF_DEltX2* const dt = (HUF_DEltX2*)(ptr);
1572
1573     HUF_STATIC_ASSERT(sizeof(HUF_DEltX2) == sizeof(U16));   /* if compilation fails here, assertion is false */
1574     //memset(huffWeight, 0, sizeof(huffWeight));   /* is not necessary, even though some analyzer complain ... */
1575
1576     iSize = HUF_readStats(huffWeight, HUF_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1577     if (HUF_isError(iSize)) return iSize;
1578
1579     /* check result */
1580     if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge);   /* DTable is too small */
1581     DTable[0] = (U16)tableLog;   /* maybe should separate sizeof DTable, as allocated, from used size of DTable, in case of DTable re-use */
1582
1583     /* Prepare ranks */
1584     nextRankStart = 0;
1585     for (n=1; n<=tableLog; n++)
1586     {
1587         U32 current = nextRankStart;
1588         nextRankStart += (rankVal[n] << (n-1));
1589         rankVal[n] = current;
1590     }
1591
1592     /* fill DTable */
1593     for (n=0; n<nbSymbols; n++)
1594     {
1595         const U32 w = huffWeight[n];
1596         const U32 length = (1 << w) >> 1;
1597         U32 i;
1598         HUF_DEltX2 D;
1599         D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1600         for (i = rankVal[w]; i < rankVal[w] + length; i++)
1601             dt[i] = D;
1602         rankVal[w] += length;
1603     }
1604
1605     return iSize;
1606 }
1607
1608 static BYTE HUF_decodeSymbolX2(BIT_DStream_t* Dstream, const HUF_DEltX2* dt, const U32 dtLog)
1609 {
1610         const size_t val = BIT_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1611         const BYTE c = dt[val].byte;
1612         BIT_skipBits(Dstream, dt[val].nbBits);
1613         return c;
1614 }
1615
1616 #define HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
1617     *ptr++ = HUF_decodeSymbolX2(DStreamPtr, dt, dtLog)
1618
1619 #define HUF_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
1620     if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1621         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1622
1623 #define HUF_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
1624     if (MEM_64bits()) \
1625         HUF_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
1626
1627 static inline size_t HUF_decodeStreamX2(BYTE* p, BIT_DStream_t* const bitDPtr, BYTE* const pEnd, const HUF_DEltX2* const dt, const U32 dtLog)
1628 {
1629     BYTE* const pStart = p;
1630
1631     /* up to 4 symbols at a time */
1632     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-4))
1633     {
1634         HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1635         HUF_DECODE_SYMBOLX2_1(p, bitDPtr);
1636         HUF_DECODE_SYMBOLX2_2(p, bitDPtr);
1637         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1638     }
1639
1640     /* closer to the end */
1641     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd))
1642         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1643
1644     /* no more data to retrieve from bitstream, hence no need to reload */
1645     while (p < pEnd)
1646         HUF_DECODE_SYMBOLX2_0(p, bitDPtr);
1647
1648     return pEnd-pStart;
1649 }
1650
1651
1652 static size_t HUF_decompress4X2_usingDTable(
1653           void* dst,  size_t dstSize,
1654     const void* cSrc, size_t cSrcSize,
1655     const U16* DTable)
1656 {
1657     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
1658
1659     {
1660         const BYTE* const istart = (const BYTE*) cSrc;
1661         BYTE* const ostart = (BYTE*) dst;
1662         BYTE* const oend = ostart + dstSize;
1663
1664         const void* ptr = DTable;
1665         const HUF_DEltX2* const dt = ((const HUF_DEltX2*)ptr) +1;
1666         const U32 dtLog = DTable[0];
1667         size_t errorCode;
1668
1669         /* Init */
1670         BIT_DStream_t bitD1;
1671         BIT_DStream_t bitD2;
1672         BIT_DStream_t bitD3;
1673         BIT_DStream_t bitD4;
1674         const size_t length1 = MEM_readLE16(istart);
1675         const size_t length2 = MEM_readLE16(istart+2);
1676         const size_t length3 = MEM_readLE16(istart+4);
1677         size_t length4;
1678         const BYTE* const istart1 = istart + 6;  /* jumpTable */
1679         const BYTE* const istart2 = istart1 + length1;
1680         const BYTE* const istart3 = istart2 + length2;
1681         const BYTE* const istart4 = istart3 + length3;
1682         const size_t segmentSize = (dstSize+3) / 4;
1683         BYTE* const opStart2 = ostart + segmentSize;
1684         BYTE* const opStart3 = opStart2 + segmentSize;
1685         BYTE* const opStart4 = opStart3 + segmentSize;
1686         BYTE* op1 = ostart;
1687         BYTE* op2 = opStart2;
1688         BYTE* op3 = opStart3;
1689         BYTE* op4 = opStart4;
1690         U32 endSignal;
1691
1692         length4 = cSrcSize - (length1 + length2 + length3 + 6);
1693         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
1694         errorCode = BIT_initDStream(&bitD1, istart1, length1);
1695         if (HUF_isError(errorCode)) return errorCode;
1696         errorCode = BIT_initDStream(&bitD2, istart2, length2);
1697         if (HUF_isError(errorCode)) return errorCode;
1698         errorCode = BIT_initDStream(&bitD3, istart3, length3);
1699         if (HUF_isError(errorCode)) return errorCode;
1700         errorCode = BIT_initDStream(&bitD4, istart4, length4);
1701         if (HUF_isError(errorCode)) return errorCode;
1702
1703         /* 16-32 symbols per loop (4-8 symbols per stream) */
1704         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1705         for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
1706         {
1707             HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1708             HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1709             HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1710             HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1711             HUF_DECODE_SYMBOLX2_1(op1, &bitD1);
1712             HUF_DECODE_SYMBOLX2_1(op2, &bitD2);
1713             HUF_DECODE_SYMBOLX2_1(op3, &bitD3);
1714             HUF_DECODE_SYMBOLX2_1(op4, &bitD4);
1715             HUF_DECODE_SYMBOLX2_2(op1, &bitD1);
1716             HUF_DECODE_SYMBOLX2_2(op2, &bitD2);
1717             HUF_DECODE_SYMBOLX2_2(op3, &bitD3);
1718             HUF_DECODE_SYMBOLX2_2(op4, &bitD4);
1719             HUF_DECODE_SYMBOLX2_0(op1, &bitD1);
1720             HUF_DECODE_SYMBOLX2_0(op2, &bitD2);
1721             HUF_DECODE_SYMBOLX2_0(op3, &bitD3);
1722             HUF_DECODE_SYMBOLX2_0(op4, &bitD4);
1723
1724             endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
1725         }
1726
1727         /* check corruption */
1728         if (op1 > opStart2) return ERROR(corruption_detected);
1729         if (op2 > opStart3) return ERROR(corruption_detected);
1730         if (op3 > opStart4) return ERROR(corruption_detected);
1731         /* note : op4 supposed already verified within main loop */
1732
1733         /* finish bitStreams one by one */
1734         HUF_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
1735         HUF_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
1736         HUF_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
1737         HUF_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
1738
1739         /* check */
1740         endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
1741         if (!endSignal) return ERROR(corruption_detected);
1742
1743         /* decoded size */
1744         return dstSize;
1745     }
1746 }
1747
1748
1749 static size_t HUF_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
1750 {
1751     HUF_CREATE_STATIC_DTABLEX2(DTable, HUF_MAX_TABLELOG);
1752     const BYTE* ip = (const BYTE*) cSrc;
1753     size_t errorCode;
1754
1755     errorCode = HUF_readDTableX2 (DTable, cSrc, cSrcSize);
1756     if (HUF_isError(errorCode)) return errorCode;
1757     if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
1758     ip += errorCode;
1759     cSrcSize -= errorCode;
1760
1761     return HUF_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
1762 }
1763
1764
1765 /***************************/
1766 /* double-symbols decoding */
1767 /***************************/
1768
1769 static void HUF_fillDTableX4Level2(HUF_DEltX4* DTable, U32 sizeLog, const U32 consumed,
1770                            const U32* rankValOrigin, const int minWeight,
1771                            const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
1772                            U32 nbBitsBaseline, U16 baseSeq)
1773 {
1774     HUF_DEltX4 DElt;
1775     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1776     U32 s;
1777
1778     /* get pre-calculated rankVal */
1779     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1780
1781     /* fill skipped values */
1782     if (minWeight>1)
1783     {
1784         U32 i, skipSize = rankVal[minWeight];
1785         MEM_writeLE16(&(DElt.sequence), baseSeq);
1786         DElt.nbBits   = (BYTE)(consumed);
1787         DElt.length   = 1;
1788         for (i = 0; i < skipSize; i++)
1789             DTable[i] = DElt;
1790     }
1791
1792     /* fill DTable */
1793     for (s=0; s<sortedListSize; s++)   /* note : sortedSymbols already skipped */
1794     {
1795         const U32 symbol = sortedSymbols[s].symbol;
1796         const U32 weight = sortedSymbols[s].weight;
1797         const U32 nbBits = nbBitsBaseline - weight;
1798         const U32 length = 1 << (sizeLog-nbBits);
1799         const U32 start = rankVal[weight];
1800         U32 i = start;
1801         const U32 end = start + length;
1802
1803         MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
1804         DElt.nbBits = (BYTE)(nbBits + consumed);
1805         DElt.length = 2;
1806         do { DTable[i++] = DElt; } while (i<end);   /* since length >= 1 */
1807
1808         rankVal[weight] += length;
1809     }
1810 }
1811
1812 typedef U32 rankVal_t[HUF_ABSOLUTEMAX_TABLELOG][HUF_ABSOLUTEMAX_TABLELOG + 1];
1813
1814 static void HUF_fillDTableX4(HUF_DEltX4* DTable, const U32 targetLog,
1815                            const sortedSymbol_t* sortedList, const U32 sortedListSize,
1816                            const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
1817                            const U32 nbBitsBaseline)
1818 {
1819     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];
1820     const int scaleLog = nbBitsBaseline - targetLog;   /* note : targetLog >= srcLog, hence scaleLog <= 1 */
1821     const U32 minBits  = nbBitsBaseline - maxWeight;
1822     U32 s;
1823
1824     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
1825
1826     /* fill DTable */
1827     for (s=0; s<sortedListSize; s++)
1828     {
1829         const U16 symbol = sortedList[s].symbol;
1830         const U32 weight = sortedList[s].weight;
1831         const U32 nbBits = nbBitsBaseline - weight;
1832         const U32 start = rankVal[weight];
1833         const U32 length = 1 << (targetLog-nbBits);
1834
1835         if (targetLog-nbBits >= minBits)   /* enough room for a second symbol */
1836         {
1837             U32 sortedRank;
1838             int minWeight = nbBits + scaleLog;
1839             if (minWeight < 1) minWeight = 1;
1840             sortedRank = rankStart[minWeight];
1841             HUF_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
1842                            rankValOrigin[nbBits], minWeight,
1843                            sortedList+sortedRank, sortedListSize-sortedRank,
1844                            nbBitsBaseline, symbol);
1845         }
1846         else
1847         {
1848             U32 i;
1849             const U32 end = start + length;
1850             HUF_DEltX4 DElt;
1851
1852             MEM_writeLE16(&(DElt.sequence), symbol);
1853             DElt.nbBits   = (BYTE)(nbBits);
1854             DElt.length   = 1;
1855             for (i = start; i < end; i++)
1856                 DTable[i] = DElt;
1857         }
1858         rankVal[weight] += length;
1859     }
1860 }
1861
1862 static size_t HUF_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
1863 {
1864     BYTE weightList[HUF_MAX_SYMBOL_VALUE + 1];
1865     sortedSymbol_t sortedSymbol[HUF_MAX_SYMBOL_VALUE + 1];
1866     U32 rankStats[HUF_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
1867     U32 rankStart0[HUF_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
1868     U32* const rankStart = rankStart0+1;
1869     rankVal_t rankVal;
1870     U32 tableLog, maxW, sizeOfSort, nbSymbols;
1871     const U32 memLog = DTable[0];
1872     const BYTE* ip = (const BYTE*) src;
1873     size_t iSize = ip[0];
1874     void* ptr = DTable;
1875     HUF_DEltX4* const dt = ((HUF_DEltX4*)ptr) + 1;
1876
1877     HUF_STATIC_ASSERT(sizeof(HUF_DEltX4) == sizeof(U32));   /* if compilation fails here, assertion is false */
1878     if (memLog > HUF_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
1879     //memset(weightList, 0, sizeof(weightList));   /* is not necessary, even though some analyzer complain ... */
1880
1881     iSize = HUF_readStats(weightList, HUF_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
1882     if (HUF_isError(iSize)) return iSize;
1883
1884     /* check result */
1885     if (tableLog > memLog) return ERROR(tableLog_tooLarge);   /* DTable can't fit code depth */
1886
1887     /* find maxWeight */
1888     for (maxW = tableLog; rankStats[maxW]==0; maxW--)
1889         { if (!maxW) return ERROR(GENERIC); }  /* necessarily finds a solution before maxW==0 */
1890
1891     /* Get start index of each weight */
1892     {
1893         U32 w, nextRankStart = 0;
1894         for (w=1; w<=maxW; w++)
1895         {
1896             U32 current = nextRankStart;
1897             nextRankStart += rankStats[w];
1898             rankStart[w] = current;
1899         }
1900         rankStart[0] = nextRankStart;   /* put all 0w symbols at the end of sorted list*/
1901         sizeOfSort = nextRankStart;
1902     }
1903
1904     /* sort symbols by weight */
1905     {
1906         U32 s;
1907         for (s=0; s<nbSymbols; s++)
1908         {
1909             U32 w = weightList[s];
1910             U32 r = rankStart[w]++;
1911             sortedSymbol[r].symbol = (BYTE)s;
1912             sortedSymbol[r].weight = (BYTE)w;
1913         }
1914         rankStart[0] = 0;   /* forget 0w symbols; this is beginning of weight(1) */
1915     }
1916
1917     /* Build rankVal */
1918     {
1919         const U32 minBits = tableLog+1 - maxW;
1920         U32 nextRankVal = 0;
1921         U32 w, consumed;
1922         const int rescale = (memLog-tableLog) - 1;   /* tableLog <= memLog */
1923         U32* rankVal0 = rankVal[0];
1924         for (w=1; w<=maxW; w++)
1925         {
1926             U32 current = nextRankVal;
1927             nextRankVal += rankStats[w] << (w+rescale);
1928             rankVal0[w] = current;
1929         }
1930         for (consumed = minBits; consumed <= memLog - minBits; consumed++)
1931         {
1932             U32* rankValPtr = rankVal[consumed];
1933             for (w = 1; w <= maxW; w++)
1934             {
1935                 rankValPtr[w] = rankVal0[w] >> consumed;
1936             }
1937         }
1938     }
1939
1940     HUF_fillDTableX4(dt, memLog,
1941                    sortedSymbol, sizeOfSort,
1942                    rankStart0, rankVal, maxW,
1943                    tableLog+1);
1944
1945     return iSize;
1946 }
1947
1948
1949 static U32 HUF_decodeSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1950 {
1951     const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
1952     memcpy(op, dt+val, 2);
1953     BIT_skipBits(DStream, dt[val].nbBits);
1954     return dt[val].length;
1955 }
1956
1957 static U32 HUF_decodeLastSymbolX4(void* op, BIT_DStream_t* DStream, const HUF_DEltX4* dt, const U32 dtLog)
1958 {
1959     const size_t val = BIT_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
1960     memcpy(op, dt+val, 1);
1961     if (dt[val].length==1) BIT_skipBits(DStream, dt[val].nbBits);
1962     else
1963     {
1964         if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8))
1965         {
1966             BIT_skipBits(DStream, dt[val].nbBits);
1967             if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
1968                 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 */
1969         }
1970     }
1971     return 1;
1972 }
1973
1974
1975 #define HUF_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
1976     ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1977
1978 #define HUF_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
1979     if (MEM_64bits() || (HUF_MAX_TABLELOG<=12)) \
1980         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1981
1982 #define HUF_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
1983     if (MEM_64bits()) \
1984         ptr += HUF_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
1985
1986 static inline size_t HUF_decodeStreamX4(BYTE* p, BIT_DStream_t* bitDPtr, BYTE* const pEnd, const HUF_DEltX4* const dt, const U32 dtLog)
1987 {
1988     BYTE* const pStart = p;
1989
1990     /* up to 8 symbols at a time */
1991     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p < pEnd-7))
1992     {
1993         HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
1994         HUF_DECODE_SYMBOLX4_1(p, bitDPtr);
1995         HUF_DECODE_SYMBOLX4_2(p, bitDPtr);
1996         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
1997     }
1998
1999     /* closer to the end */
2000     while ((BIT_reloadDStream(bitDPtr) == BIT_DStream_unfinished) && (p <= pEnd-2))
2001         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);
2002
2003     while (p <= pEnd-2)
2004         HUF_DECODE_SYMBOLX4_0(p, bitDPtr);   /* no need to reload : reached the end of DStream */
2005
2006     if (p < pEnd)
2007         p += HUF_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2008
2009     return p-pStart;
2010 }
2011
2012
2013
2014 static size_t HUF_decompress4X4_usingDTable(
2015           void* dst,  size_t dstSize,
2016     const void* cSrc, size_t cSrcSize,
2017     const U32* DTable)
2018 {
2019     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
2020
2021     {
2022         const BYTE* const istart = (const BYTE*) cSrc;
2023         BYTE* const ostart = (BYTE*) dst;
2024         BYTE* const oend = ostart + dstSize;
2025
2026         const void* ptr = DTable;
2027         const HUF_DEltX4* const dt = ((const HUF_DEltX4*)ptr) +1;
2028         const U32 dtLog = DTable[0];
2029         size_t errorCode;
2030
2031         /* Init */
2032         BIT_DStream_t bitD1;
2033         BIT_DStream_t bitD2;
2034         BIT_DStream_t bitD3;
2035         BIT_DStream_t bitD4;
2036         const size_t length1 = MEM_readLE16(istart);
2037         const size_t length2 = MEM_readLE16(istart+2);
2038         const size_t length3 = MEM_readLE16(istart+4);
2039         size_t length4;
2040         const BYTE* const istart1 = istart + 6;  /* jumpTable */
2041         const BYTE* const istart2 = istart1 + length1;
2042         const BYTE* const istart3 = istart2 + length2;
2043         const BYTE* const istart4 = istart3 + length3;
2044         const size_t segmentSize = (dstSize+3) / 4;
2045         BYTE* const opStart2 = ostart + segmentSize;
2046         BYTE* const opStart3 = opStart2 + segmentSize;
2047         BYTE* const opStart4 = opStart3 + segmentSize;
2048         BYTE* op1 = ostart;
2049         BYTE* op2 = opStart2;
2050         BYTE* op3 = opStart3;
2051         BYTE* op4 = opStart4;
2052         U32 endSignal;
2053
2054         length4 = cSrcSize - (length1 + length2 + length3 + 6);
2055         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
2056         errorCode = BIT_initDStream(&bitD1, istart1, length1);
2057         if (HUF_isError(errorCode)) return errorCode;
2058         errorCode = BIT_initDStream(&bitD2, istart2, length2);
2059         if (HUF_isError(errorCode)) return errorCode;
2060         errorCode = BIT_initDStream(&bitD3, istart3, length3);
2061         if (HUF_isError(errorCode)) return errorCode;
2062         errorCode = BIT_initDStream(&bitD4, istart4, length4);
2063         if (HUF_isError(errorCode)) return errorCode;
2064
2065         /* 16-32 symbols per loop (4-8 symbols per stream) */
2066         endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2067         for ( ; (endSignal==BIT_DStream_unfinished) && (op4<(oend-7)) ; )
2068         {
2069             HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2070             HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2071             HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2072             HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2073             HUF_DECODE_SYMBOLX4_1(op1, &bitD1);
2074             HUF_DECODE_SYMBOLX4_1(op2, &bitD2);
2075             HUF_DECODE_SYMBOLX4_1(op3, &bitD3);
2076             HUF_DECODE_SYMBOLX4_1(op4, &bitD4);
2077             HUF_DECODE_SYMBOLX4_2(op1, &bitD1);
2078             HUF_DECODE_SYMBOLX4_2(op2, &bitD2);
2079             HUF_DECODE_SYMBOLX4_2(op3, &bitD3);
2080             HUF_DECODE_SYMBOLX4_2(op4, &bitD4);
2081             HUF_DECODE_SYMBOLX4_0(op1, &bitD1);
2082             HUF_DECODE_SYMBOLX4_0(op2, &bitD2);
2083             HUF_DECODE_SYMBOLX4_0(op3, &bitD3);
2084             HUF_DECODE_SYMBOLX4_0(op4, &bitD4);
2085
2086             endSignal = BIT_reloadDStream(&bitD1) | BIT_reloadDStream(&bitD2) | BIT_reloadDStream(&bitD3) | BIT_reloadDStream(&bitD4);
2087         }
2088
2089         /* check corruption */
2090         if (op1 > opStart2) return ERROR(corruption_detected);
2091         if (op2 > opStart3) return ERROR(corruption_detected);
2092         if (op3 > opStart4) return ERROR(corruption_detected);
2093         /* note : op4 supposed already verified within main loop */
2094
2095         /* finish bitStreams one by one */
2096         HUF_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2097         HUF_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2098         HUF_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2099         HUF_decodeStreamX4(op4, &bitD4, oend,     dt, dtLog);
2100
2101         /* check */
2102         endSignal = BIT_endOfDStream(&bitD1) & BIT_endOfDStream(&bitD2) & BIT_endOfDStream(&bitD3) & BIT_endOfDStream(&bitD4);
2103         if (!endSignal) return ERROR(corruption_detected);
2104
2105         /* decoded size */
2106         return dstSize;
2107     }
2108 }
2109
2110
2111 static size_t HUF_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2112 {
2113     HUF_CREATE_STATIC_DTABLEX4(DTable, HUF_MAX_TABLELOG);
2114     const BYTE* ip = (const BYTE*) cSrc;
2115
2116     size_t hSize = HUF_readDTableX4 (DTable, cSrc, cSrcSize);
2117     if (HUF_isError(hSize)) return hSize;
2118     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2119     ip += hSize;
2120     cSrcSize -= hSize;
2121
2122     return HUF_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2123 }
2124
2125
2126 /**********************************/
2127 /* Generic decompression selector */
2128 /**********************************/
2129
2130 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2131 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2132 {
2133     /* single, double, quad */
2134     {{0,0}, {1,1}, {2,2}},  /* Q==0 : impossible */
2135     {{0,0}, {1,1}, {2,2}},  /* Q==1 : impossible */
2136     {{  38,130}, {1313, 74}, {2151, 38}},   /* Q == 2 : 12-18% */
2137     {{ 448,128}, {1353, 74}, {2238, 41}},   /* Q == 3 : 18-25% */
2138     {{ 556,128}, {1353, 74}, {2238, 47}},   /* Q == 4 : 25-32% */
2139     {{ 714,128}, {1418, 74}, {2436, 53}},   /* Q == 5 : 32-38% */
2140     {{ 883,128}, {1437, 74}, {2464, 61}},   /* Q == 6 : 38-44% */
2141     {{ 897,128}, {1515, 75}, {2622, 68}},   /* Q == 7 : 44-50% */
2142     {{ 926,128}, {1613, 75}, {2730, 75}},   /* Q == 8 : 50-56% */
2143     {{ 947,128}, {1729, 77}, {3359, 77}},   /* Q == 9 : 56-62% */
2144     {{1107,128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
2145     {{1177,128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
2146     {{1242,128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
2147     {{1349,128}, {2644,106}, {5260,106}},   /* Q ==13 : 81-87% */
2148     {{1455,128}, {2422,124}, {4174,124}},   /* Q ==14 : 87-93% */
2149     {{ 722,128}, {1891,145}, {1936,146}},   /* Q ==15 : 93-99% */
2150 };
2151
2152 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2153
2154 static size_t HUF_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2155 {
2156     static const decompressionAlgo decompress[3] = { HUF_decompress4X2, HUF_decompress4X4, NULL };
2157     /* estimate decompression time */
2158     U32 Q;
2159     const U32 D256 = (U32)(dstSize >> 8);
2160     U32 Dtime[3];
2161     U32 algoNb = 0;
2162     int n;
2163
2164     /* validation checks */
2165     if (dstSize == 0) return ERROR(dstSize_tooSmall);
2166     if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
2167     if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
2168     if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
2169
2170     /* decoder timing evaluation */
2171     Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
2172     for (n=0; n<3; n++)
2173         Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2174
2175     Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2176
2177     if (Dtime[1] < Dtime[0]) algoNb = 1;
2178
2179     return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2180
2181     //return HUF_decompress4X2(dst, dstSize, cSrc, cSrcSize);   /* multi-streams single-symbol decoding */
2182     //return HUF_decompress4X4(dst, dstSize, cSrc, cSrcSize);   /* multi-streams double-symbols decoding */
2183     //return HUF_decompress4X6(dst, dstSize, cSrc, cSrcSize);   /* multi-streams quad-symbols decoding */
2184 }
2185 /*
2186     zstd - standard compression library
2187     Copyright (C) 2014-2015, Yann Collet.
2188
2189     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2190
2191     Redistribution and use in source and binary forms, with or without
2192     modification, are permitted provided that the following conditions are
2193     met:
2194     * Redistributions of source code must retain the above copyright
2195     notice, this list of conditions and the following disclaimer.
2196     * Redistributions in binary form must reproduce the above
2197     copyright notice, this list of conditions and the following disclaimer
2198     in the documentation and/or other materials provided with the
2199     distribution.
2200     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2201     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2202     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2203     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2204     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2205     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2206     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2207     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2208     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2209     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2210     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2211
2212     You can contact the author at :
2213     - zstd source repository : https://github.com/Cyan4973/zstd
2214     - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
2215 */
2216
2217 /* ***************************************************************
2218 *  Tuning parameters
2219 *****************************************************************/
2220 /*!
2221 *  MEMORY_USAGE :
2222 *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
2223 *  Increasing memory usage improves compression ratio
2224 *  Reduced memory usage can improve speed, due to cache effect
2225 */
2226 #define ZSTD_MEMORY_USAGE 17
2227
2228 /*!
2229  * HEAPMODE :
2230  * Select how default compression functions will allocate memory for their hash table,
2231  * in memory stack (0, fastest), or in memory heap (1, requires malloc())
2232  * Note that compression context is fairly large, as a consequence heap memory is recommended.
2233  */
2234 #ifndef ZSTD_HEAPMODE
2235 #  define ZSTD_HEAPMODE 1
2236 #endif /* ZSTD_HEAPMODE */
2237
2238 /*!
2239 *  LEGACY_SUPPORT :
2240 *  decompressor can decode older formats (starting from Zstd 0.1+)
2241 */
2242 #ifndef ZSTD_LEGACY_SUPPORT
2243 #  define ZSTD_LEGACY_SUPPORT 1
2244 #endif
2245
2246
2247 /* *******************************************************
2248 *  Includes
2249 *********************************************************/
2250 #include <stdlib.h>      /* calloc */
2251 #include <string.h>      /* memcpy, memmove */
2252 #include <stdio.h>       /* debug : printf */
2253
2254
2255 /* *******************************************************
2256 *  Compiler specifics
2257 *********************************************************/
2258 #ifdef __AVX2__
2259 #  include <immintrin.h>   /* AVX2 intrinsics */
2260 #endif
2261
2262 #ifdef _MSC_VER    /* Visual Studio */
2263 #  include <intrin.h>                    /* For Visual 2005 */
2264 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
2265 #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
2266 #else
2267 #  define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
2268 #endif
2269
2270
2271 /* *******************************************************
2272 *  Constants
2273 *********************************************************/
2274 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
2275 #define HASH_TABLESIZE (1 << HASH_LOG)
2276 #define HASH_MASK (HASH_TABLESIZE - 1)
2277
2278 #define KNUTH 2654435761
2279
2280 #define BIT7 128
2281 #define BIT6  64
2282 #define BIT5  32
2283 #define BIT4  16
2284 #define BIT1   2
2285 #define BIT0   1
2286
2287 #define KB *(1 <<10)
2288 #define MB *(1 <<20)
2289 #define GB *(1U<<30)
2290
2291 #define BLOCKSIZE (128 KB)                 /* define, for static allocation */
2292 #define MIN_SEQUENCES_SIZE (2 /*seqNb*/ + 2 /*dumps*/ + 3 /*seqTables*/ + 1 /*bitStream*/)
2293 #define MIN_CBLOCK_SIZE (3 /*litCSize*/ + MIN_SEQUENCES_SIZE)
2294 #define IS_RAW BIT0
2295 #define IS_RLE BIT1
2296
2297 #define WORKPLACESIZE (BLOCKSIZE*3)
2298 #define MINMATCH 4
2299 #define MLbits   7
2300 #define LLbits   6
2301 #define Offbits  5
2302 #define MaxML  ((1<<MLbits )-1)
2303 #define MaxLL  ((1<<LLbits )-1)
2304 #define MaxOff   31
2305 #define LitFSELog  11
2306 #define MLFSELog   10
2307 #define LLFSELog   10
2308 #define OffFSELog   9
2309 #define MAX(a,b) ((a)<(b)?(b):(a))
2310 #define MaxSeq MAX(MaxLL, MaxML)
2311
2312 #define LITERAL_NOENTROPY 63
2313 #define COMMAND_NOENTROPY 7   /* to remove */
2314
2315 #define ZSTD_CONTENTSIZE_ERROR   (0ULL - 2)
2316
2317 static const size_t ZSTD_blockHeaderSize = 3;
2318 static const size_t ZSTD_frameHeaderSize = 4;
2319
2320
2321 /* *******************************************************
2322 *  Memory operations
2323 **********************************************************/
2324 static void   ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2325
2326 static void   ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
2327
2328 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
2329
2330 /*! ZSTD_wildcopy : custom version of memcpy(), can copy up to 7-8 bytes too many */
2331 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
2332 {
2333     const BYTE* ip = (const BYTE*)src;
2334     BYTE* op = (BYTE*)dst;
2335     BYTE* const oend = op + length;
2336     do COPY8(op, ip) while (op < oend);
2337 }
2338
2339
2340 /* **************************************
2341 *  Local structures
2342 ****************************************/
2343 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
2344
2345 typedef struct
2346 {
2347     blockType_t blockType;
2348     U32 origSize;
2349 } blockProperties_t;
2350
2351 typedef struct {
2352     void* buffer;
2353     U32*  offsetStart;
2354     U32*  offset;
2355     BYTE* offCodeStart;
2356     BYTE* offCode;
2357     BYTE* litStart;
2358     BYTE* lit;
2359     BYTE* litLengthStart;
2360     BYTE* litLength;
2361     BYTE* matchLengthStart;
2362     BYTE* matchLength;
2363     BYTE* dumpsStart;
2364     BYTE* dumps;
2365 } seqStore_t;
2366
2367
2368 /* *************************************
2369 *  Error Management
2370 ***************************************/
2371 /*! ZSTD_isError
2372 *   tells if a return value is an error code */
2373 static unsigned ZSTD_isError(size_t code) { return ERR_isError(code); }
2374
2375
2376
2377 /* *************************************************************
2378 *   Decompression section
2379 ***************************************************************/
2380 struct ZSTDv03_Dctx_s
2381 {
2382     U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
2383     U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
2384     U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
2385     void* previousDstEnd;
2386     void* base;
2387     size_t expected;
2388     blockType_t bType;
2389     U32 phase;
2390     const BYTE* litPtr;
2391     size_t litSize;
2392     BYTE litBuffer[BLOCKSIZE + 8 /* margin for wildcopy */];
2393 };   /* typedef'd to ZSTD_Dctx within "zstd_static.h" */
2394
2395
2396 static size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2397 {
2398     const BYTE* const in = (const BYTE* const)src;
2399     BYTE headerFlags;
2400     U32 cSize;
2401
2402     if (srcSize < 3) return ERROR(srcSize_wrong);
2403
2404     headerFlags = *in;
2405     cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2406
2407     bpPtr->blockType = (blockType_t)(headerFlags >> 6);
2408     bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2409
2410     if (bpPtr->blockType == bt_end) return 0;
2411     if (bpPtr->blockType == bt_rle) return 1;
2412     return cSize;
2413 }
2414
2415 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2416 {
2417     if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
2418     if (srcSize > 0) {
2419         memcpy(dst, src, srcSize);
2420     }
2421     return srcSize;
2422 }
2423
2424
2425 /** ZSTD_decompressLiterals
2426     @return : nb of bytes read from src, or an error code*/
2427 static size_t ZSTD_decompressLiterals(void* dst, size_t* maxDstSizePtr,
2428                                 const void* src, size_t srcSize)
2429 {
2430     const BYTE* ip = (const BYTE*)src;
2431
2432     const size_t litSize = (MEM_readLE32(src) & 0x1FFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2433     const size_t litCSize = (MEM_readLE32(ip+2) & 0xFFFFFF) >> 5;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2434
2435     if (litSize > *maxDstSizePtr) return ERROR(corruption_detected);
2436     if (litCSize + 5 > srcSize) return ERROR(corruption_detected);
2437
2438     if (HUF_isError(HUF_decompress(dst, litSize, ip+5, litCSize))) return ERROR(corruption_detected);
2439
2440     *maxDstSizePtr = litSize;
2441     return litCSize + 5;
2442 }
2443
2444
2445 /** ZSTD_decodeLiteralsBlock
2446     @return : nb of bytes read from src (< srcSize )*/
2447 static size_t ZSTD_decodeLiteralsBlock(void* ctx,
2448                           const void* src, size_t srcSize)
2449 {
2450     ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2451     const BYTE* const istart = (const BYTE* const)src;
2452
2453     /* any compressed block with literals segment must be at least this size */
2454     if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
2455
2456     switch(*istart & 3)
2457     {
2458     default:
2459     case 0:
2460         {
2461             size_t litSize = BLOCKSIZE;
2462             const size_t readSize = ZSTD_decompressLiterals(dctx->litBuffer, &litSize, src, srcSize);
2463             dctx->litPtr = dctx->litBuffer;
2464             dctx->litSize = litSize;
2465             memset(dctx->litBuffer + dctx->litSize, 0, 8);
2466             return readSize;   /* works if it's an error too */
2467         }
2468     case IS_RAW:
2469         {
2470             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2471             if (litSize > srcSize-11)   /* risk of reading too far with wildcopy */
2472             {
2473                 if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2474                 if (litSize > srcSize-3) return ERROR(corruption_detected);
2475                 memcpy(dctx->litBuffer, istart, litSize);
2476                 dctx->litPtr = dctx->litBuffer;
2477                 dctx->litSize = litSize;
2478                 memset(dctx->litBuffer + dctx->litSize, 0, 8);
2479                 return litSize+3;
2480             }
2481             /* direct reference into compressed stream */
2482             dctx->litPtr = istart+3;
2483             dctx->litSize = litSize;
2484             return litSize+3;
2485         }
2486     case IS_RLE:
2487         {
2488             const size_t litSize = (MEM_readLE32(istart) & 0xFFFFFF) >> 2;   /* no buffer issue : srcSize >= MIN_CBLOCK_SIZE */
2489             if (litSize > BLOCKSIZE) return ERROR(corruption_detected);
2490             memset(dctx->litBuffer, istart[3], litSize + 8);
2491             dctx->litPtr = dctx->litBuffer;
2492             dctx->litSize = litSize;
2493             return 4;
2494         }
2495     }
2496 }
2497
2498
2499 static size_t ZSTD_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
2500                          FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
2501                          const void* src, size_t srcSize)
2502 {
2503     const BYTE* const istart = (const BYTE* const)src;
2504     const BYTE* ip = istart;
2505     const BYTE* const iend = istart + srcSize;
2506     U32 LLtype, Offtype, MLtype;
2507     U32 LLlog, Offlog, MLlog;
2508     size_t dumpsLength;
2509
2510     /* check */
2511     if (srcSize < 5) return ERROR(srcSize_wrong);
2512
2513     /* SeqHead */
2514     *nbSeq = MEM_readLE16(ip); ip+=2;
2515     LLtype  = *ip >> 6;
2516     Offtype = (*ip >> 4) & 3;
2517     MLtype  = (*ip >> 2) & 3;
2518     if (*ip & 2)
2519     {
2520         dumpsLength  = ip[2];
2521         dumpsLength += ip[1] << 8;
2522         ip += 3;
2523     }
2524     else
2525     {
2526         dumpsLength  = ip[1];
2527         dumpsLength += (ip[0] & 1) << 8;
2528         ip += 2;
2529     }
2530     *dumpsPtr = ip;
2531     ip += dumpsLength;
2532     *dumpsLengthPtr = dumpsLength;
2533
2534     /* check */
2535     if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
2536
2537     /* sequences */
2538     {
2539         S16 norm[MaxML+1];    /* assumption : MaxML >= MaxLL and MaxOff */
2540         size_t headerSize;
2541
2542         /* Build DTables */
2543         switch(LLtype)
2544         {
2545         case bt_rle :
2546             LLlog = 0;
2547             FSE_buildDTable_rle(DTableLL, *ip++); break;
2548         case bt_raw :
2549             LLlog = LLbits;
2550             FSE_buildDTable_raw(DTableLL, LLbits); break;
2551         default :
2552             {   U32 max = MaxLL;
2553                 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
2554                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2555                 if (LLlog > LLFSELog) return ERROR(corruption_detected);
2556                 ip += headerSize;
2557                 FSE_buildDTable(DTableLL, norm, max, LLlog);
2558         }   }
2559
2560         switch(Offtype)
2561         {
2562         case bt_rle :
2563             Offlog = 0;
2564             if (ip > iend-2) return ERROR(srcSize_wrong);   /* min : "raw", hence no header, but at least xxLog bits */
2565             FSE_buildDTable_rle(DTableOffb, *ip++ & MaxOff); /* if *ip > MaxOff, data is corrupted */
2566             break;
2567         case bt_raw :
2568             Offlog = Offbits;
2569             FSE_buildDTable_raw(DTableOffb, Offbits); break;
2570         default :
2571             {   U32 max = MaxOff;
2572                 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
2573                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2574                 if (Offlog > OffFSELog) return ERROR(corruption_detected);
2575                 ip += headerSize;
2576                 FSE_buildDTable(DTableOffb, norm, max, Offlog);
2577         }   }
2578
2579         switch(MLtype)
2580         {
2581         case bt_rle :
2582             MLlog = 0;
2583             if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
2584             FSE_buildDTable_rle(DTableML, *ip++); break;
2585         case bt_raw :
2586             MLlog = MLbits;
2587             FSE_buildDTable_raw(DTableML, MLbits); break;
2588         default :
2589             {   U32 max = MaxML;
2590                 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
2591                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
2592                 if (MLlog > MLFSELog) return ERROR(corruption_detected);
2593                 ip += headerSize;
2594                 FSE_buildDTable(DTableML, norm, max, MLlog);
2595     }   }   }
2596
2597     return ip-istart;
2598 }
2599
2600
2601 typedef struct {
2602     size_t litLength;
2603     size_t offset;
2604     size_t matchLength;
2605 } seq_t;
2606
2607 typedef struct {
2608     BIT_DStream_t DStream;
2609     FSE_DState_t stateLL;
2610     FSE_DState_t stateOffb;
2611     FSE_DState_t stateML;
2612     size_t prevOffset;
2613     const BYTE* dumps;
2614     const BYTE* dumpsEnd;
2615 } seqState_t;
2616
2617
2618 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
2619 {
2620     size_t litLength;
2621     size_t prevOffset;
2622     size_t offset;
2623     size_t matchLength;
2624     const BYTE* dumps = seqState->dumps;
2625     const BYTE* const de = seqState->dumpsEnd;
2626
2627     /* Literal length */
2628     litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
2629     prevOffset = litLength ? seq->offset : seqState->prevOffset;
2630     seqState->prevOffset = seq->offset;
2631     if (litLength == MaxLL)
2632     {
2633         const U32 add = dumps<de ? *dumps++ : 0;
2634         if (add < 255) litLength += add;
2635         else if (dumps + 3 <= de)
2636         {
2637             litLength = MEM_readLE24(dumps);
2638             dumps += 3;
2639         }
2640         if (dumps >= de) dumps = de-1;   /* late correction, to avoid read overflow (data is now corrupted anyway) */
2641     }
2642
2643     /* Offset */
2644     {
2645         static const size_t offsetPrefix[MaxOff+1] = {  /* note : size_t faster than U32 */
2646                 1 /*fake*/, 1, 2, 4, 8, 16, 32, 64, 128, 256,
2647                 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144,
2648                 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, /*fake*/ 1, 1, 1, 1, 1 };
2649         U32 offsetCode, nbBits;
2650         offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream));   /* <= maxOff, by table construction */
2651         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2652         nbBits = offsetCode - 1;
2653         if (offsetCode==0) nbBits = 0;   /* cmove */
2654         offset = offsetPrefix[offsetCode] + BIT_readBits(&(seqState->DStream), nbBits);
2655         if (MEM_32bits()) BIT_reloadDStream(&(seqState->DStream));
2656         if (offsetCode==0) offset = prevOffset;   /* cmove */
2657     }
2658
2659     /* MatchLength */
2660     matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
2661     if (matchLength == MaxML)
2662     {
2663         const U32 add = dumps<de ? *dumps++ : 0;
2664         if (add < 255) matchLength += add;
2665         else if (dumps + 3 <= de)
2666         {
2667             matchLength = MEM_readLE24(dumps);
2668             dumps += 3;
2669         }
2670         if (dumps >= de) dumps = de-1;   /* late correction, to avoid read overflow (data is now corrupted anyway) */
2671     }
2672     matchLength += MINMATCH;
2673
2674     /* save result */
2675     seq->litLength = litLength;
2676     seq->offset = offset;
2677     seq->matchLength = matchLength;
2678     seqState->dumps = dumps;
2679 }
2680
2681
2682 static size_t ZSTD_execSequence(BYTE* op,
2683                                 seq_t sequence,
2684                                 const BYTE** litPtr, const BYTE* const litLimit,
2685                                 BYTE* const base, BYTE* const oend)
2686 {
2687     static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* added */
2688     static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11};   /* subtracted */
2689     const BYTE* const ostart = op;
2690     BYTE* const oLitEnd = op + sequence.litLength;
2691     BYTE* const oMatchEnd = op + sequence.litLength + sequence.matchLength;   /* risk : address space overflow (32-bits) */
2692     BYTE* const oend_8 = oend-8;
2693     const BYTE* const litEnd = *litPtr + sequence.litLength;
2694
2695     /* checks */
2696     size_t const seqLength = sequence.litLength + sequence.matchLength;
2697
2698     if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
2699     if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
2700     /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
2701     if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
2702     if (sequence.offset > (U32)(oLitEnd - base)) return ERROR(corruption_detected);
2703
2704     if (oMatchEnd > oend) return ERROR(dstSize_tooSmall);   /* overwrite beyond dst buffer */
2705     if (litEnd > litLimit) return ERROR(corruption_detected);   /* overRead beyond lit buffer */
2706
2707     /* copy Literals */
2708     ZSTD_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength);   /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
2709     op = oLitEnd;
2710     *litPtr = litEnd;   /* update for next sequence */
2711
2712     /* copy Match */
2713     {   const BYTE* match = op - sequence.offset;
2714
2715         /* check */
2716         if (sequence.offset > (size_t)op) return ERROR(corruption_detected);   /* address space overflow test (this test seems kept by clang optimizer) */
2717         //if (match > op) return ERROR(corruption_detected);   /* address space overflow test (is clang optimizer removing this test ?) */
2718         if (match < base) return ERROR(corruption_detected);
2719
2720         /* close range match, overlap */
2721         if (sequence.offset < 8)
2722         {
2723             const int dec64 = dec64table[sequence.offset];
2724             op[0] = match[0];
2725             op[1] = match[1];
2726             op[2] = match[2];
2727             op[3] = match[3];
2728             match += dec32table[sequence.offset];
2729             ZSTD_copy4(op+4, match);
2730             match -= dec64;
2731         }
2732         else
2733         {
2734             ZSTD_copy8(op, match);
2735         }
2736         op += 8; match += 8;
2737
2738         if (oMatchEnd > oend-(16-MINMATCH))
2739         {
2740             if (op < oend_8)
2741             {
2742                 ZSTD_wildcopy(op, match, oend_8 - op);
2743                 match += oend_8 - op;
2744                 op = oend_8;
2745             }
2746             while (op < oMatchEnd) *op++ = *match++;
2747         }
2748         else
2749         {
2750             ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
2751         }
2752     }
2753
2754     return oMatchEnd - ostart;
2755 }
2756
2757 static size_t ZSTD_decompressSequences(
2758                                void* ctx,
2759                                void* dst, size_t maxDstSize,
2760                          const void* seqStart, size_t seqSize)
2761 {
2762     ZSTD_DCtx* dctx = (ZSTD_DCtx*)ctx;
2763     const BYTE* ip = (const BYTE*)seqStart;
2764     const BYTE* const iend = ip + seqSize;
2765     BYTE* const ostart = (BYTE* const)dst;
2766     BYTE* op = ostart;
2767     BYTE* const oend = ostart + maxDstSize;
2768     size_t errorCode, dumpsLength;
2769     const BYTE* litPtr = dctx->litPtr;
2770     const BYTE* const litEnd = litPtr + dctx->litSize;
2771     int nbSeq;
2772     const BYTE* dumps;
2773     U32* DTableLL = dctx->LLTable;
2774     U32* DTableML = dctx->MLTable;
2775     U32* DTableOffb = dctx->OffTable;
2776     BYTE* const base = (BYTE*) (dctx->base);
2777
2778     /* Build Decoding Tables */
2779     errorCode = ZSTD_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
2780                                       DTableLL, DTableML, DTableOffb,
2781                                       ip, iend-ip);
2782     if (ZSTD_isError(errorCode)) return errorCode;
2783     ip += errorCode;
2784
2785     /* Regen sequences */
2786     {
2787         seq_t sequence;
2788         seqState_t seqState;
2789
2790         memset(&sequence, 0, sizeof(sequence));
2791         seqState.dumps = dumps;
2792         seqState.dumpsEnd = dumps + dumpsLength;
2793         seqState.prevOffset = sequence.offset = 4;
2794         errorCode = BIT_initDStream(&(seqState.DStream), ip, iend-ip);
2795         if (ERR_isError(errorCode)) return ERROR(corruption_detected);
2796         FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
2797         FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
2798         FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
2799
2800         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (nbSeq>0) ; )
2801         {
2802             size_t oneSeqSize;
2803             nbSeq--;
2804             ZSTD_decodeSequence(&sequence, &seqState);
2805             oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
2806             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
2807             op += oneSeqSize;
2808         }
2809
2810         /* check if reached exact end */
2811         if ( !BIT_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected);   /* requested too much : data is corrupted */
2812         if (nbSeq<0) return ERROR(corruption_detected);   /* requested too many sequences : data is corrupted */
2813
2814         /* last literal segment */
2815         {
2816             size_t lastLLSize = litEnd - litPtr;
2817             if (litPtr > litEnd) return ERROR(corruption_detected);
2818             if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
2819             if (lastLLSize > 0) {
2820                 if (op != litPtr) memmove(op, litPtr, lastLLSize);
2821                 op += lastLLSize;
2822             }
2823         }
2824     }
2825
2826     return op-ostart;
2827 }
2828
2829
2830 static size_t ZSTD_decompressBlock(
2831                             void* ctx,
2832                             void* dst, size_t maxDstSize,
2833                       const void* src, size_t srcSize)
2834 {
2835     /* blockType == blockCompressed */
2836     const BYTE* ip = (const BYTE*)src;
2837
2838     /* Decode literals sub-block */
2839     size_t litCSize = ZSTD_decodeLiteralsBlock(ctx, src, srcSize);
2840     if (ZSTD_isError(litCSize)) return litCSize;
2841     ip += litCSize;
2842     srcSize -= litCSize;
2843
2844     return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize);
2845 }
2846
2847
2848 static size_t ZSTD_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2849 {
2850     const BYTE* ip = (const BYTE*)src;
2851     const BYTE* iend = ip + srcSize;
2852     BYTE* const ostart = (BYTE* const)dst;
2853     BYTE* op = ostart;
2854     BYTE* const oend = ostart + maxDstSize;
2855     size_t remainingSize = srcSize;
2856     U32 magicNumber;
2857     blockProperties_t blockProperties;
2858
2859     /* Frame Header */
2860     if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
2861     magicNumber = MEM_readLE32(src);
2862     if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2863     ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2864
2865     /* Loop on each block */
2866     while (1)
2867     {
2868         size_t decodedSize=0;
2869         size_t cBlockSize = ZSTD_getcBlockSize(ip, iend-ip, &blockProperties);
2870         if (ZSTD_isError(cBlockSize)) return cBlockSize;
2871
2872         ip += ZSTD_blockHeaderSize;
2873         remainingSize -= ZSTD_blockHeaderSize;
2874         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
2875
2876         switch(blockProperties.blockType)
2877         {
2878         case bt_compressed:
2879             decodedSize = ZSTD_decompressBlock(ctx, op, oend-op, ip, cBlockSize);
2880             break;
2881         case bt_raw :
2882             decodedSize = ZSTD_copyUncompressedBlock(op, oend-op, ip, cBlockSize);
2883             break;
2884         case bt_rle :
2885             return ERROR(GENERIC);   /* not yet supported */
2886             break;
2887         case bt_end :
2888             /* end of frame */
2889             if (remainingSize) return ERROR(srcSize_wrong);
2890             break;
2891         default:
2892             return ERROR(GENERIC);   /* impossible */
2893         }
2894         if (cBlockSize == 0) break;   /* bt_end */
2895
2896         if (ZSTD_isError(decodedSize)) return decodedSize;
2897         op += decodedSize;
2898         ip += cBlockSize;
2899         remainingSize -= cBlockSize;
2900     }
2901
2902     return op-ostart;
2903 }
2904
2905 static size_t ZSTD_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2906 {
2907     ZSTD_DCtx ctx;
2908     ctx.base = dst;
2909     return ZSTD_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
2910 }
2911
2912 /* ZSTD_errorFrameSizeInfoLegacy() :
2913    assumes `cSize` and `dBound` are _not_ NULL */
2914 MEM_STATIC void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
2915 {
2916     *cSize = ret;
2917     *dBound = ZSTD_CONTENTSIZE_ERROR;
2918 }
2919
2920 void ZSTDv03_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
2921 {
2922     const BYTE* ip = (const BYTE*)src;
2923     size_t remainingSize = srcSize;
2924     size_t nbBlocks = 0;
2925     U32 magicNumber;
2926     blockProperties_t blockProperties;
2927
2928     /* Frame Header */
2929     if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
2930         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2931         return;
2932     }
2933     magicNumber = MEM_readLE32(src);
2934     if (magicNumber != ZSTD_magicNumber) {
2935         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
2936         return;
2937     }
2938     ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2939
2940     /* Loop on each block */
2941     while (1)
2942     {
2943         size_t cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
2944         if (ZSTD_isError(cBlockSize)) {
2945             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
2946             return;
2947         }
2948
2949         ip += ZSTD_blockHeaderSize;
2950         remainingSize -= ZSTD_blockHeaderSize;
2951         if (cBlockSize > remainingSize) {
2952             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2953             return;
2954         }
2955
2956         if (cBlockSize == 0) break;   /* bt_end */
2957
2958         ip += cBlockSize;
2959         remainingSize -= cBlockSize;
2960         nbBlocks++;
2961     }
2962
2963     *cSize = ip - (const BYTE*)src;
2964     *dBound = nbBlocks * BLOCKSIZE;
2965 }
2966
2967
2968 /*******************************
2969 *  Streaming Decompression API
2970 *******************************/
2971
2972 static size_t ZSTD_resetDCtx(ZSTD_DCtx* dctx)
2973 {
2974     dctx->expected = ZSTD_frameHeaderSize;
2975     dctx->phase = 0;
2976     dctx->previousDstEnd = NULL;
2977     dctx->base = NULL;
2978     return 0;
2979 }
2980
2981 static ZSTD_DCtx* ZSTD_createDCtx(void)
2982 {
2983     ZSTD_DCtx* dctx = (ZSTD_DCtx*)malloc(sizeof(ZSTD_DCtx));
2984     if (dctx==NULL) return NULL;
2985     ZSTD_resetDCtx(dctx);
2986     return dctx;
2987 }
2988
2989 static size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
2990 {
2991     free(dctx);
2992     return 0;
2993 }
2994
2995 static size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx)
2996 {
2997     return dctx->expected;
2998 }
2999
3000 static size_t ZSTD_decompressContinue(ZSTD_DCtx* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3001 {
3002     /* Sanity check */
3003     if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
3004     if (dst != ctx->previousDstEnd)  /* not contiguous */
3005         ctx->base = dst;
3006
3007     /* Decompress : frame header */
3008     if (ctx->phase == 0)
3009     {
3010         /* Check frame magic header */
3011         U32 magicNumber = MEM_readLE32(src);
3012         if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
3013         ctx->phase = 1;
3014         ctx->expected = ZSTD_blockHeaderSize;
3015         return 0;
3016     }
3017
3018     /* Decompress : block header */
3019     if (ctx->phase == 1)
3020     {
3021         blockProperties_t bp;
3022         size_t blockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
3023         if (ZSTD_isError(blockSize)) return blockSize;
3024         if (bp.blockType == bt_end)
3025         {
3026             ctx->expected = 0;
3027             ctx->phase = 0;
3028         }
3029         else
3030         {
3031             ctx->expected = blockSize;
3032             ctx->bType = bp.blockType;
3033             ctx->phase = 2;
3034         }
3035
3036         return 0;
3037     }
3038
3039     /* Decompress : block content */
3040     {
3041         size_t rSize;
3042         switch(ctx->bType)
3043         {
3044         case bt_compressed:
3045             rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
3046             break;
3047         case bt_raw :
3048             rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
3049             break;
3050         case bt_rle :
3051             return ERROR(GENERIC);   /* not yet handled */
3052             break;
3053         case bt_end :   /* should never happen (filtered at phase 1) */
3054             rSize = 0;
3055             break;
3056         default:
3057             return ERROR(GENERIC);
3058         }
3059         ctx->phase = 1;
3060         ctx->expected = ZSTD_blockHeaderSize;
3061         if (ZSTD_isError(rSize)) return rSize;
3062         ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
3063         return rSize;
3064     }
3065
3066 }
3067
3068
3069 /* wrapper layer */
3070
3071 unsigned ZSTDv03_isError(size_t code)
3072 {
3073     return ZSTD_isError(code);
3074 }
3075
3076 size_t ZSTDv03_decompress( void* dst, size_t maxOriginalSize,
3077                      const void* src, size_t compressedSize)
3078 {
3079     return ZSTD_decompress(dst, maxOriginalSize, src, compressedSize);
3080 }
3081
3082 ZSTDv03_Dctx* ZSTDv03_createDCtx(void)
3083 {
3084     return (ZSTDv03_Dctx*)ZSTD_createDCtx();
3085 }
3086
3087 size_t ZSTDv03_freeDCtx(ZSTDv03_Dctx* dctx)
3088 {
3089     return ZSTD_freeDCtx((ZSTD_DCtx*)dctx);
3090 }
3091
3092 size_t ZSTDv03_resetDCtx(ZSTDv03_Dctx* dctx)
3093 {
3094     return ZSTD_resetDCtx((ZSTD_DCtx*)dctx);
3095 }
3096
3097 size_t ZSTDv03_nextSrcSizeToDecompress(ZSTDv03_Dctx* dctx)
3098 {
3099     return ZSTD_nextSrcSizeToDecompress((ZSTD_DCtx*)dctx);
3100 }
3101
3102 size_t ZSTDv03_decompressContinue(ZSTDv03_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
3103 {
3104     return ZSTD_decompressContinue((ZSTD_DCtx*)dctx, dst, maxDstSize, src, srcSize);
3105 }