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