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

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