deps/libchdr/deps/zstd-1.5.6/lib/legacy/zstd_v06.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 /*- Dependencies -*/
  13 #include "zstd_v06.h"
  14 #include <stddef.h>    /* size_t, ptrdiff_t */
  15 #include <string.h>    /* memcpy */
  16 #include <stdlib.h>    /* malloc, free, qsort */
  17 #include "../common/compiler.h"
  18 #include "../common/error_private.h"
  19
  20
  21
  22 /* ******************************************************************
  23    mem.h
  24    low-level memory access routines
  25    Copyright (C) 2013-2015, Yann Collet.
  26
  27    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
  28
  29    Redistribution and use in source and binary forms, with or without
  30    modification, are permitted provided that the following conditions are
  31    met:
  32
  33        * Redistributions of source code must retain the above copyright
  34    notice, this list of conditions and the following disclaimer.
  35        * Redistributions in binary form must reproduce the above
  36    copyright notice, this list of conditions and the following disclaimer
  37    in the documentation and/or other materials provided with the
  38    distribution.
  39
  40    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  41    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  42    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  43    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  44    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  45    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  46    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  47    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  48    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  49    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  50    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  51
  52     You can contact the author at :
  53     - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
  54     - Public forum : https://groups.google.com/forum/#!forum/lz4c
  55 ****************************************************************** */
  56 #ifndef MEM_H_MODULE
  57 #define MEM_H_MODULE
  58
  59 #if defined (__cplusplus)
  60 extern "C" {
  61 #endif
  62
  63
  64 /*-****************************************
  65 *  Compiler specifics
  66 ******************************************/
  67 #if defined(_MSC_VER)   /* Visual Studio */
  68 #   include <stdlib.h>  /* _byteswap_ulong */
  69 #   include <intrin.h>  /* _byteswap_* */
  70 #endif
  71
  72
  73 /*-**************************************************************
  74 *  Basic Types
  75 *****************************************************************/
  76 #if  !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
  77 # if defined(_AIX)
  78 #  include <inttypes.h>
  79 # else
  80 #  include <stdint.h> /* intptr_t */
  81 # endif
  82   typedef  uint8_t BYTE;
  83   typedef uint16_t U16;
  84   typedef  int16_t S16;
  85   typedef uint32_t U32;
  86   typedef  int32_t S32;
  87   typedef uint64_t U64;
  88   typedef  int64_t S64;
  89 #else
  90   typedef unsigned char       BYTE;
  91   typedef unsigned short      U16;
  92   typedef   signed short      S16;
  93   typedef unsigned int        U32;
  94   typedef   signed int        S32;
  95   typedef unsigned long long  U64;
  96   typedef   signed long long  S64;
  97 #endif
  98
  99
 100 /*-**************************************************************
 101 *  Memory I/O
 102 *****************************************************************/
 103
 104 MEM_STATIC unsigned MEM_32bits(void) { return sizeof(size_t)==4; }
 105 MEM_STATIC unsigned MEM_64bits(void) { return sizeof(size_t)==8; }
 106
 107 MEM_STATIC unsigned MEM_isLittleEndian(void)
 108 {
 109     const union { U32 u; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
 110     return one.c[0];
 111 }
 112
 113 MEM_STATIC U16 MEM_read16(const void* memPtr)
 114 {
 115     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
 116 }
 117
 118 MEM_STATIC U32 MEM_read32(const void* memPtr)
 119 {
 120     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
 121 }
 122
 123 MEM_STATIC U64 MEM_read64(const void* memPtr)
 124 {
 125     U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
 126 }
 127
 128 MEM_STATIC void MEM_write16(void* memPtr, U16 value)
 129 {
 130     memcpy(memPtr, &value, sizeof(value));
 131 }
 132
 133 MEM_STATIC U32 MEM_swap32(U32 in)
 134 {
 135 #if defined(_MSC_VER)     /* Visual Studio */
 136     return _byteswap_ulong(in);
 137 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
 138     return __builtin_bswap32(in);
 139 #else
 140     return  ((in << 24) & 0xff000000 ) |
 141             ((in <<  8) & 0x00ff0000 ) |
 142             ((in >>  8) & 0x0000ff00 ) |
 143             ((in >> 24) & 0x000000ff );
 144 #endif
 145 }
 146
 147 MEM_STATIC U64 MEM_swap64(U64 in)
 148 {
 149 #if defined(_MSC_VER)     /* Visual Studio */
 150     return _byteswap_uint64(in);
 151 #elif defined (__GNUC__) && (__GNUC__ * 100 + __GNUC_MINOR__ >= 403)
 152     return __builtin_bswap64(in);
 153 #else
 154     return  ((in << 56) & 0xff00000000000000ULL) |
 155             ((in << 40) & 0x00ff000000000000ULL) |
 156             ((in << 24) & 0x0000ff0000000000ULL) |
 157             ((in << 8)  & 0x000000ff00000000ULL) |
 158             ((in >> 8)  & 0x00000000ff000000ULL) |
 159             ((in >> 24) & 0x0000000000ff0000ULL) |
 160             ((in >> 40) & 0x000000000000ff00ULL) |
 161             ((in >> 56) & 0x00000000000000ffULL);
 162 #endif
 163 }
 164
 165
 166 /*=== Little endian r/w ===*/
 167
 168 MEM_STATIC U16 MEM_readLE16(const void* memPtr)
 169 {
 170     if (MEM_isLittleEndian())
 171         return MEM_read16(memPtr);
 172     else {
 173         const BYTE* p = (const BYTE*)memPtr;
 174         return (U16)(p[0] + (p[1]<<8));
 175     }
 176 }
 177
 178 MEM_STATIC void MEM_writeLE16(void* memPtr, U16 val)
 179 {
 180     if (MEM_isLittleEndian()) {
 181         MEM_write16(memPtr, val);
 182     } else {
 183         BYTE* p = (BYTE*)memPtr;
 184         p[0] = (BYTE)val;
 185         p[1] = (BYTE)(val>>8);
 186     }
 187 }
 188
 189 MEM_STATIC U32 MEM_readLE32(const void* memPtr)
 190 {
 191     if (MEM_isLittleEndian())
 192         return MEM_read32(memPtr);
 193     else
 194         return MEM_swap32(MEM_read32(memPtr));
 195 }
 196
 197
 198 MEM_STATIC U64 MEM_readLE64(const void* memPtr)
 199 {
 200     if (MEM_isLittleEndian())
 201         return MEM_read64(memPtr);
 202     else
 203         return MEM_swap64(MEM_read64(memPtr));
 204 }
 205
 206
 207 MEM_STATIC size_t MEM_readLEST(const void* memPtr)
 208 {
 209     if (MEM_32bits())
 210         return (size_t)MEM_readLE32(memPtr);
 211     else
 212         return (size_t)MEM_readLE64(memPtr);
 213 }
 214
 215
 216
 217 #if defined (__cplusplus)
 218 }
 219 #endif
 220
 221 #endif /* MEM_H_MODULE */
 222
 223 /*
 224     zstd - standard compression library
 225     Header File for static linking only
 226     Copyright (C) 2014-2016, Yann Collet.
 227
 228     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 229
 230     Redistribution and use in source and binary forms, with or without
 231     modification, are permitted provided that the following conditions are
 232     met:
 233     * Redistributions of source code must retain the above copyright
 234     notice, this list of conditions and the following disclaimer.
 235     * Redistributions in binary form must reproduce the above
 236     copyright notice, this list of conditions and the following disclaimer
 237     in the documentation and/or other materials provided with the
 238     distribution.
 239     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 240     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 241     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 242     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 243     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 244     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 245     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 246     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 247     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 248     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 249     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 250
 251     You can contact the author at :
 252     - zstd homepage : https://facebook.github.io/zstd
 253 */
 254 #ifndef ZSTDv06_STATIC_H
 255 #define ZSTDv06_STATIC_H
 256
 257 /* The prototypes defined within this file are considered experimental.
 258  * They should not be used in the context DLL as they may change in the future.
 259  * Prefer static linking if you need them, to control breaking version changes issues.
 260  */
 261
 262 #if defined (__cplusplus)
 263 extern "C" {
 264 #endif
 265
 266
 267
 268 /*- Advanced Decompression functions -*/
 269
 270 /*! ZSTDv06_decompress_usingPreparedDCtx() :
 271 *   Same as ZSTDv06_decompress_usingDict, but using a reference context `preparedDCtx`, where dictionary has been loaded.
 272 *   It avoids reloading the dictionary each time.
 273 *   `preparedDCtx` must have been properly initialized using ZSTDv06_decompressBegin_usingDict().
 274 *   Requires 2 contexts : 1 for reference (preparedDCtx), which will not be modified, and 1 to run the decompression operation (dctx) */
 275 ZSTDLIBv06_API size_t ZSTDv06_decompress_usingPreparedDCtx(
 276                                            ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* preparedDCtx,
 277                                            void* dst, size_t dstCapacity,
 278                                      const void* src, size_t srcSize);
 279
 280
 281
 282 #define ZSTDv06_FRAMEHEADERSIZE_MAX 13    /* for static allocation */
 283 static const size_t ZSTDv06_frameHeaderSize_min = 5;
 284 static const size_t ZSTDv06_frameHeaderSize_max = ZSTDv06_FRAMEHEADERSIZE_MAX;
 285
 286 ZSTDLIBv06_API size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx);
 287
 288 /*
 289   Streaming decompression, direct mode (bufferless)
 290
 291   A ZSTDv06_DCtx object is required to track streaming operations.
 292   Use ZSTDv06_createDCtx() / ZSTDv06_freeDCtx() to manage it.
 293   A ZSTDv06_DCtx object can be re-used multiple times.
 294
 295   First optional operation is to retrieve frame parameters, using ZSTDv06_getFrameParams(), which doesn't consume the input.
 296   It can provide the minimum size of rolling buffer required to properly decompress data,
 297   and optionally the final size of uncompressed content.
 298   (Note : content size is an optional info that may not be present. 0 means : content size unknown)
 299   Frame parameters are extracted from the beginning of compressed frame.
 300   The amount of data to read is variable, from ZSTDv06_frameHeaderSize_min to ZSTDv06_frameHeaderSize_max (so if `srcSize` >= ZSTDv06_frameHeaderSize_max, it will always work)
 301   If `srcSize` is too small for operation to succeed, function will return the minimum size it requires to produce a result.
 302   Result : 0 when successful, it means the ZSTDv06_frameParams structure has been filled.
 303           >0 : means there is not enough data into `src`. Provides the expected size to successfully decode header.
 304            errorCode, which can be tested using ZSTDv06_isError()
 305
 306   Start decompression, with ZSTDv06_decompressBegin() or ZSTDv06_decompressBegin_usingDict().
 307   Alternatively, you can copy a prepared context, using ZSTDv06_copyDCtx().
 308
 309   Then use ZSTDv06_nextSrcSizeToDecompress() and ZSTDv06_decompressContinue() alternatively.
 310   ZSTDv06_nextSrcSizeToDecompress() tells how much bytes to provide as 'srcSize' to ZSTDv06_decompressContinue().
 311   ZSTDv06_decompressContinue() requires this exact amount of bytes, or it will fail.
 312   ZSTDv06_decompressContinue() needs previous data blocks during decompression, up to (1 << windowlog).
 313   They should preferably be located contiguously, prior to current block. Alternatively, a round buffer is also possible.
 314
 315   @result of ZSTDv06_decompressContinue() is the number of bytes regenerated within 'dst' (necessarily <= dstCapacity)
 316   It can be zero, which is not an error; it just means ZSTDv06_decompressContinue() has decoded some header.
 317
 318   A frame is fully decoded when ZSTDv06_nextSrcSizeToDecompress() returns zero.
 319   Context can then be reset to start a new decompression.
 320 */
 321
 322
 323 /* **************************************
 324 *  Block functions
 325 ****************************************/
 326 /*! Block functions produce and decode raw zstd blocks, without frame metadata.
 327     User will have to take in charge required information to regenerate data, such as compressed and content sizes.
 328
 329     A few rules to respect :
 330     - Uncompressed block size must be <= ZSTDv06_BLOCKSIZE_MAX (128 KB)
 331     - Compressing or decompressing requires a context structure
 332       + Use ZSTDv06_createCCtx() and ZSTDv06_createDCtx()
 333     - It is necessary to init context before starting
 334       + compression : ZSTDv06_compressBegin()
 335       + decompression : ZSTDv06_decompressBegin()
 336       + variants _usingDict() are also allowed
 337       + copyCCtx() and copyDCtx() work too
 338     - When a block is considered not compressible enough, ZSTDv06_compressBlock() result will be zero.
 339       In which case, nothing is produced into `dst`.
 340       + User must test for such outcome and deal directly with uncompressed data
 341       + ZSTDv06_decompressBlock() doesn't accept uncompressed data as input !!
 342 */
 343
 344 #define ZSTDv06_BLOCKSIZE_MAX (128 * 1024)   /* define, for static allocation */
 345 ZSTDLIBv06_API size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize);
 346
 347
 348
 349 #if defined (__cplusplus)
 350 }
 351 #endif
 352
 353 #endif  /* ZSTDv06_STATIC_H */
 354 /*
 355     zstd_internal - common functions to include
 356     Header File for include
 357     Copyright (C) 2014-2016, Yann Collet.
 358
 359     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 360
 361     Redistribution and use in source and binary forms, with or without
 362     modification, are permitted provided that the following conditions are
 363     met:
 364     * Redistributions of source code must retain the above copyright
 365     notice, this list of conditions and the following disclaimer.
 366     * Redistributions in binary form must reproduce the above
 367     copyright notice, this list of conditions and the following disclaimer
 368     in the documentation and/or other materials provided with the
 369     distribution.
 370     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 371     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 372     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 373     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 374     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 375     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 376     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 377     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 378     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 379     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 380     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 381
 382     You can contact the author at :
 383     - zstd homepage : https://www.zstd.net
 384 */
 385 #ifndef ZSTDv06_CCOMMON_H_MODULE
 386 #define ZSTDv06_CCOMMON_H_MODULE
 387
 388
 389 /*-*************************************
 390 *  Common macros
 391 ***************************************/
 392 #define MIN(a,b) ((a)<(b) ? (a) : (b))
 393 #define MAX(a,b) ((a)>(b) ? (a) : (b))
 394
 395
 396 /*-*************************************
 397 *  Common constants
 398 ***************************************/
 399 #define ZSTDv06_DICT_MAGIC  0xEC30A436
 400
 401 #define ZSTDv06_REP_NUM    3
 402 #define ZSTDv06_REP_INIT   ZSTDv06_REP_NUM
 403 #define ZSTDv06_REP_MOVE   (ZSTDv06_REP_NUM-1)
 404
 405 #define KB *(1 <<10)
 406 #define MB *(1 <<20)
 407 #define GB *(1U<<30)
 408
 409 #define BIT7 128
 410 #define BIT6  64
 411 #define BIT5  32
 412 #define BIT4  16
 413 #define BIT1   2
 414 #define BIT0   1
 415
 416 #define ZSTDv06_WINDOWLOG_ABSOLUTEMIN 12
 417 static const size_t ZSTDv06_fcs_fieldSize[4] = { 0, 1, 2, 8 };
 418
 419 #define ZSTDv06_BLOCKHEADERSIZE 3   /* because C standard does not allow a static const value to be defined using another static const value .... :( */
 420 static const size_t ZSTDv06_blockHeaderSize = ZSTDv06_BLOCKHEADERSIZE;
 421 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
 422
 423 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
 424 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */)   /* for a non-null block */
 425
 426 #define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
 427
 428 #define IS_HUF 0
 429 #define IS_PCH 1
 430 #define IS_RAW 2
 431 #define IS_RLE 3
 432
 433 #define LONGNBSEQ 0x7F00
 434
 435 #define MINMATCH 3
 436 #define EQUAL_READ32 4
 437 #define REPCODE_STARTVALUE 1
 438
 439 #define Litbits  8
 440 #define MaxLit ((1<<Litbits) - 1)
 441 #define MaxML  52
 442 #define MaxLL  35
 443 #define MaxOff 28
 444 #define MaxSeq MAX(MaxLL, MaxML)   /* Assumption : MaxOff < MaxLL,MaxML */
 445 #define MLFSELog    9
 446 #define LLFSELog    9
 447 #define OffFSELog   8
 448
 449 #define FSEv06_ENCODING_RAW     0
 450 #define FSEv06_ENCODING_RLE     1
 451 #define FSEv06_ENCODING_STATIC  2
 452 #define FSEv06_ENCODING_DYNAMIC 3
 453
 454 #define ZSTD_CONTENTSIZE_ERROR   (0ULL - 2)
 455
 456 static const U32 LL_bits[MaxLL+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 457                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9,10,11,12,
 458                                      13,14,15,16 };
 459 static const S16 LL_defaultNorm[MaxLL+1] = { 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
 460                                              2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
 461                                             -1,-1,-1,-1 };
 462 static const U32 LL_defaultNormLog = 6;
 463
 464 static const U32 ML_bits[MaxML+1] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 465                                       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 466                                       1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9,10,11,
 467                                      12,13,14,15,16 };
 468 static const S16 ML_defaultNorm[MaxML+1] = { 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
 469                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 470                                              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
 471                                             -1,-1,-1,-1,-1 };
 472 static const U32 ML_defaultNormLog = 6;
 473
 474 static const S16 OF_defaultNorm[MaxOff+1] = { 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
 475                                               1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1 };
 476 static const U32 OF_defaultNormLog = 5;
 477
 478
 479 /*-*******************************************
 480 *  Shared functions to include for inlining
 481 *********************************************/
 482 static void ZSTDv06_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
 483 #define COPY8(d,s) { ZSTDv06_copy8(d,s); d+=8; s+=8; }
 484
 485 /*! ZSTDv06_wildcopy() :
 486 *   custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
 487 #define WILDCOPY_OVERLENGTH 8
 488 MEM_STATIC void ZSTDv06_wildcopy(void* dst, const void* src, ptrdiff_t length)
 489 {
 490     const BYTE* ip = (const BYTE*)src;
 491     BYTE* op = (BYTE*)dst;
 492     BYTE* const oend = op + length;
 493     do
 494         COPY8(op, ip)
 495     while (op < oend);
 496 }
 497
 498
 499
 500 /*-*******************************************
 501 *  Private interfaces
 502 *********************************************/
 503 typedef struct {
 504     U32 off;
 505     U32 len;
 506 } ZSTDv06_match_t;
 507
 508 typedef struct {
 509     U32 price;
 510     U32 off;
 511     U32 mlen;
 512     U32 litlen;
 513     U32 rep[ZSTDv06_REP_INIT];
 514 } ZSTDv06_optimal_t;
 515
 516 typedef struct { U32  unused; } ZSTDv06_stats_t;
 517
 518 typedef struct {
 519     void* buffer;
 520     U32*  offsetStart;
 521     U32*  offset;
 522     BYTE* offCodeStart;
 523     BYTE* litStart;
 524     BYTE* lit;
 525     U16*  litLengthStart;
 526     U16*  litLength;
 527     BYTE* llCodeStart;
 528     U16*  matchLengthStart;
 529     U16*  matchLength;
 530     BYTE* mlCodeStart;
 531     U32   longLengthID;   /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
 532     U32   longLengthPos;
 533     /* opt */
 534     ZSTDv06_optimal_t* priceTable;
 535     ZSTDv06_match_t* matchTable;
 536     U32* matchLengthFreq;
 537     U32* litLengthFreq;
 538     U32* litFreq;
 539     U32* offCodeFreq;
 540     U32  matchLengthSum;
 541     U32  matchSum;
 542     U32  litLengthSum;
 543     U32  litSum;
 544     U32  offCodeSum;
 545     U32  log2matchLengthSum;
 546     U32  log2matchSum;
 547     U32  log2litLengthSum;
 548     U32  log2litSum;
 549     U32  log2offCodeSum;
 550     U32  factor;
 551     U32  cachedPrice;
 552     U32  cachedLitLength;
 553     const BYTE* cachedLiterals;
 554     ZSTDv06_stats_t stats;
 555 } seqStore_t;
 556
 557 void ZSTDv06_seqToCodes(const seqStore_t* seqStorePtr, size_t const nbSeq);
 558
 559
 560 #endif   /* ZSTDv06_CCOMMON_H_MODULE */
 561 /* ******************************************************************
 562    FSE : Finite State Entropy codec
 563    Public Prototypes declaration
 564    Copyright (C) 2013-2016, Yann Collet.
 565
 566    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 567
 568    Redistribution and use in source and binary forms, with or without
 569    modification, are permitted provided that the following conditions are
 570    met:
 571
 572        * Redistributions of source code must retain the above copyright
 573    notice, this list of conditions and the following disclaimer.
 574        * Redistributions in binary form must reproduce the above
 575    copyright notice, this list of conditions and the following disclaimer
 576    in the documentation and/or other materials provided with the
 577    distribution.
 578
 579    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 580    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 581    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 582    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 583    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 584    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 585    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 586    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 587    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 588    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 589    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 590
 591    You can contact the author at :
 592    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 593 ****************************************************************** */
 594 #ifndef FSEv06_H
 595 #define FSEv06_H
 596
 597 #if defined (__cplusplus)
 598 extern "C" {
 599 #endif
 600
 601
 602
 603 /*-****************************************
 604 *  FSE simple functions
 605 ******************************************/
 606 /*! FSEv06_decompress():
 607     Decompress FSE data from buffer 'cSrc', of size 'cSrcSize',
 608     into already allocated destination buffer 'dst', of size 'dstCapacity'.
 609     @return : size of regenerated data (<= maxDstSize),
 610               or an error code, which can be tested using FSEv06_isError() .
 611
 612     ** Important ** : FSEv06_decompress() does not decompress non-compressible nor RLE data !!!
 613     Why ? : making this distinction requires a header.
 614     Header management is intentionally delegated to the user layer, which can better manage special cases.
 615 */
 616 size_t FSEv06_decompress(void* dst,  size_t dstCapacity,
 617                 const void* cSrc, size_t cSrcSize);
 618
 619
 620 /*-*****************************************
 621 *  Tool functions
 622 ******************************************/
 623 size_t FSEv06_compressBound(size_t size);       /* maximum compressed size */
 624
 625 /* Error Management */
 626 unsigned    FSEv06_isError(size_t code);        /* tells if a return value is an error code */
 627 const char* FSEv06_getErrorName(size_t code);   /* provides error code string (useful for debugging) */
 628
 629
 630
 631 /*-*****************************************
 632 *  FSE detailed API
 633 ******************************************/
 634 /*!
 635
 636 FSEv06_decompress() does the following:
 637 1. read normalized counters with readNCount()
 638 2. build decoding table 'DTable' from normalized counters
 639 3. decode the data stream using decoding table 'DTable'
 640
 641 The following API allows targeting specific sub-functions for advanced tasks.
 642 For example, it's possible to compress several blocks using the same 'CTable',
 643 or to save and provide normalized distribution using external method.
 644 */
 645
 646
 647 /* *** DECOMPRESSION *** */
 648
 649 /*! FSEv06_readNCount():
 650     Read compactly saved 'normalizedCounter' from 'rBuffer'.
 651     @return : size read from 'rBuffer',
 652               or an errorCode, which can be tested using FSEv06_isError().
 653               maxSymbolValuePtr[0] and tableLogPtr[0] will also be updated with their respective values */
 654 size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSymbolValuePtr, unsigned* tableLogPtr, const void* rBuffer, size_t rBuffSize);
 655
 656 /*! Constructor and Destructor of FSEv06_DTable.
 657     Note that its size depends on 'tableLog' */
 658 typedef unsigned FSEv06_DTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
 659 FSEv06_DTable* FSEv06_createDTable(unsigned tableLog);
 660 void        FSEv06_freeDTable(FSEv06_DTable* dt);
 661
 662 /*! FSEv06_buildDTable():
 663     Builds 'dt', which must be already allocated, using FSEv06_createDTable().
 664     return : 0, or an errorCode, which can be tested using FSEv06_isError() */
 665 size_t FSEv06_buildDTable (FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);
 666
 667 /*! FSEv06_decompress_usingDTable():
 668     Decompress compressed source `cSrc` of size `cSrcSize` using `dt`
 669     into `dst` which must be already allocated.
 670     @return : size of regenerated data (necessarily <= `dstCapacity`),
 671               or an errorCode, which can be tested using FSEv06_isError() */
 672 size_t FSEv06_decompress_usingDTable(void* dst, size_t dstCapacity, const void* cSrc, size_t cSrcSize, const FSEv06_DTable* dt);
 673
 674 /*!
 675 Tutorial :
 676 ----------
 677 (Note : these functions only decompress FSE-compressed blocks.
 678  If block is uncompressed, use memcpy() instead
 679  If block is a single repeated byte, use memset() instead )
 680
 681 The first step is to obtain the normalized frequencies of symbols.
 682 This can be performed by FSEv06_readNCount() if it was saved using FSEv06_writeNCount().
 683 'normalizedCounter' must be already allocated, and have at least 'maxSymbolValuePtr[0]+1' cells of signed short.
 684 In practice, that means it's necessary to know 'maxSymbolValue' beforehand,
 685 or size the table to handle worst case situations (typically 256).
 686 FSEv06_readNCount() will provide 'tableLog' and 'maxSymbolValue'.
 687 The result of FSEv06_readNCount() is the number of bytes read from 'rBuffer'.
 688 Note that 'rBufferSize' must be at least 4 bytes, even if useful information is less than that.
 689 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
 690
 691 The next step is to build the decompression tables 'FSEv06_DTable' from 'normalizedCounter'.
 692 This is performed by the function FSEv06_buildDTable().
 693 The space required by 'FSEv06_DTable' must be already allocated using FSEv06_createDTable().
 694 If there is an error, the function will return an error code, which can be tested using FSEv06_isError().
 695
 696 `FSEv06_DTable` can then be used to decompress `cSrc`, with FSEv06_decompress_usingDTable().
 697 `cSrcSize` must be strictly correct, otherwise decompression will fail.
 698 FSEv06_decompress_usingDTable() result will tell how many bytes were regenerated (<=`dstCapacity`).
 699 If there is an error, the function will return an error code, which can be tested using FSEv06_isError(). (ex: dst buffer too small)
 700 */
 701
 702
 703 #if defined (__cplusplus)
 704 }
 705 #endif
 706
 707 #endif  /* FSEv06_H */
 708 /* ******************************************************************
 709    bitstream
 710    Part of FSE library
 711    header file (to include)
 712    Copyright (C) 2013-2016, Yann Collet.
 713
 714    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 715
 716    Redistribution and use in source and binary forms, with or without
 717    modification, are permitted provided that the following conditions are
 718    met:
 719
 720        * Redistributions of source code must retain the above copyright
 721    notice, this list of conditions and the following disclaimer.
 722        * Redistributions in binary form must reproduce the above
 723    copyright notice, this list of conditions and the following disclaimer
 724    in the documentation and/or other materials provided with the
 725    distribution.
 726
 727    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 728    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 729    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 730    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 731    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 732    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 733    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 734    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 735    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 736    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 737    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 738
 739    You can contact the author at :
 740    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 741 ****************************************************************** */
 742 #ifndef BITSTREAM_H_MODULE
 743 #define BITSTREAM_H_MODULE
 744
 745 #if defined (__cplusplus)
 746 extern "C" {
 747 #endif
 748
 749
 750 /*
 751 *  This API consists of small unitary functions, which must be inlined for best performance.
 752 *  Since link-time-optimization is not available for all compilers,
 753 *  these functions are defined into a .h to be included.
 754 */
 755
 756
 757 /*=========================================
 758 *  Target specific
 759 =========================================*/
 760 #if defined(__BMI__) && defined(__GNUC__)
 761 #  include <immintrin.h>   /* support for bextr (experimental) */
 762 #endif
 763
 764
 765
 766 /*-********************************************
 767 *  bitStream decoding API (read backward)
 768 **********************************************/
 769 typedef struct
 770 {
 771     size_t   bitContainer;
 772     unsigned bitsConsumed;
 773     const char* ptr;
 774     const char* start;
 775 } BITv06_DStream_t;
 776
 777 typedef enum { BITv06_DStream_unfinished = 0,
 778                BITv06_DStream_endOfBuffer = 1,
 779                BITv06_DStream_completed = 2,
 780                BITv06_DStream_overflow = 3 } BITv06_DStream_status;  /* result of BITv06_reloadDStream() */
 781                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... :( */
 782
 783 MEM_STATIC size_t   BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize);
 784 MEM_STATIC size_t   BITv06_readBits(BITv06_DStream_t* bitD, unsigned nbBits);
 785 MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD);
 786 MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* bitD);
 787
 788
 789
 790 /*-****************************************
 791 *  unsafe API
 792 ******************************************/
 793 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, unsigned nbBits);
 794 /* faster, but works only if nbBits >= 1 */
 795
 796
 797
 798 /*-**************************************************************
 799 *  Internal functions
 800 ****************************************************************/
 801 MEM_STATIC unsigned BITv06_highbit32 ( U32 val)
 802 {
 803 #   if defined(_MSC_VER)   /* Visual */
 804     unsigned long r;
 805     return _BitScanReverse(&r, val) ? (unsigned)r : 0;
 806 #   elif defined(__GNUC__) && (__GNUC__ >= 3)   /* Use GCC Intrinsic */
 807     return __builtin_clz (val) ^ 31;
 808 #   else   /* Software version */
 809     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 };
 810     U32 v = val;
 811     unsigned r;
 812     v |= v >> 1;
 813     v |= v >> 2;
 814     v |= v >> 4;
 815     v |= v >> 8;
 816     v |= v >> 16;
 817     r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
 818     return r;
 819 #   endif
 820 }
 821
 822
 823
 824 /*-********************************************************
 825 * bitStream decoding
 826 **********************************************************/
 827 /*! BITv06_initDStream() :
 828 *   Initialize a BITv06_DStream_t.
 829 *   `bitD` : a pointer to an already allocated BITv06_DStream_t structure.
 830 *   `srcSize` must be the *exact* size of the bitStream, in bytes.
 831 *   @return : size of stream (== srcSize) or an errorCode if a problem is detected
 832 */
 833 MEM_STATIC size_t BITv06_initDStream(BITv06_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
 834 {
 835     if (srcSize < 1) { memset(bitD, 0, sizeof(*bitD)); return ERROR(srcSize_wrong); }
 836
 837     if (srcSize >=  sizeof(bitD->bitContainer)) {  /* normal case */
 838         bitD->start = (const char*)srcBuffer;
 839         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(bitD->bitContainer);
 840         bitD->bitContainer = MEM_readLEST(bitD->ptr);
 841         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
 842           if (lastByte == 0) return ERROR(GENERIC);   /* endMark not present */
 843           bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); }
 844     } else {
 845         bitD->start = (const char*)srcBuffer;
 846         bitD->ptr   = bitD->start;
 847         bitD->bitContainer = *(const BYTE*)(bitD->start);
 848         switch(srcSize)
 849         {
 850             case 7: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[6]) << (sizeof(bitD->bitContainer)*8 - 16);/* fall-through */
 851             case 6: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[5]) << (sizeof(bitD->bitContainer)*8 - 24);/* fall-through */
 852             case 5: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[4]) << (sizeof(bitD->bitContainer)*8 - 32);/* fall-through */
 853             case 4: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[3]) << 24; /* fall-through */
 854             case 3: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[2]) << 16; /* fall-through */
 855             case 2: bitD->bitContainer += (size_t)(((const BYTE*)(srcBuffer))[1]) <<  8; /* fall-through */
 856             default: break;
 857         }
 858         { BYTE const lastByte = ((const BYTE*)srcBuffer)[srcSize-1];
 859           if (lastByte == 0) return ERROR(GENERIC);   /* endMark not present */
 860           bitD->bitsConsumed = 8 - BITv06_highbit32(lastByte); }
 861         bitD->bitsConsumed += (U32)(sizeof(bitD->bitContainer) - srcSize)*8;
 862     }
 863
 864     return srcSize;
 865 }
 866
 867
 868  MEM_STATIC size_t BITv06_lookBits(const BITv06_DStream_t* bitD, U32 nbBits)
 869 {
 870     U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
 871     return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
 872 }
 873
 874 /*! BITv06_lookBitsFast() :
 875 *   unsafe version; only works if nbBits >= 1 */
 876 MEM_STATIC size_t BITv06_lookBitsFast(const BITv06_DStream_t* bitD, U32 nbBits)
 877 {
 878     U32 const bitMask = sizeof(bitD->bitContainer)*8 - 1;
 879     return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
 880 }
 881
 882 MEM_STATIC void BITv06_skipBits(BITv06_DStream_t* bitD, U32 nbBits)
 883 {
 884     bitD->bitsConsumed += nbBits;
 885 }
 886
 887 MEM_STATIC size_t BITv06_readBits(BITv06_DStream_t* bitD, U32 nbBits)
 888 {
 889     size_t const value = BITv06_lookBits(bitD, nbBits);
 890     BITv06_skipBits(bitD, nbBits);
 891     return value;
 892 }
 893
 894 /*! BITv06_readBitsFast() :
 895 *   unsafe version; only works if nbBits >= 1 */
 896 MEM_STATIC size_t BITv06_readBitsFast(BITv06_DStream_t* bitD, U32 nbBits)
 897 {
 898     size_t const value = BITv06_lookBitsFast(bitD, nbBits);
 899     BITv06_skipBits(bitD, nbBits);
 900     return value;
 901 }
 902
 903 MEM_STATIC BITv06_DStream_status BITv06_reloadDStream(BITv06_DStream_t* bitD)
 904 {
 905     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should never happen */
 906         return BITv06_DStream_overflow;
 907
 908     if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer)) {
 909         bitD->ptr -= bitD->bitsConsumed >> 3;
 910         bitD->bitsConsumed &= 7;
 911         bitD->bitContainer = MEM_readLEST(bitD->ptr);
 912         return BITv06_DStream_unfinished;
 913     }
 914     if (bitD->ptr == bitD->start) {
 915         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return BITv06_DStream_endOfBuffer;
 916         return BITv06_DStream_completed;
 917     }
 918     {   U32 nbBytes = bitD->bitsConsumed >> 3;
 919         BITv06_DStream_status result = BITv06_DStream_unfinished;
 920         if (bitD->ptr - nbBytes < bitD->start) {
 921             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
 922             result = BITv06_DStream_endOfBuffer;
 923         }
 924         bitD->ptr -= nbBytes;
 925         bitD->bitsConsumed -= nbBytes*8;
 926         bitD->bitContainer = MEM_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
 927         return result;
 928     }
 929 }
 930
 931 /*! BITv06_endOfDStream() :
 932 *   @return Tells if DStream has exactly reached its end (all bits consumed).
 933 */
 934 MEM_STATIC unsigned BITv06_endOfDStream(const BITv06_DStream_t* DStream)
 935 {
 936     return ((DStream->ptr == DStream->start) && (DStream->bitsConsumed == sizeof(DStream->bitContainer)*8));
 937 }
 938
 939 #if defined (__cplusplus)
 940 }
 941 #endif
 942
 943 #endif /* BITSTREAM_H_MODULE */
 944 /* ******************************************************************
 945    FSE : Finite State Entropy coder
 946    header file for static linking (only)
 947    Copyright (C) 2013-2015, Yann Collet
 948
 949    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
 950
 951    Redistribution and use in source and binary forms, with or without
 952    modification, are permitted provided that the following conditions are
 953    met:
 954
 955        * Redistributions of source code must retain the above copyright
 956    notice, this list of conditions and the following disclaimer.
 957        * Redistributions in binary form must reproduce the above
 958    copyright notice, this list of conditions and the following disclaimer
 959    in the documentation and/or other materials provided with the
 960    distribution.
 961
 962    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 963    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 964    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 965    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 966    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 967    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 968    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 969    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 970    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 971    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 972    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 973
 974    You can contact the author at :
 975    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
 976    - Public forum : https://groups.google.com/forum/#!forum/lz4c
 977 ****************************************************************** */
 978 #ifndef FSEv06_STATIC_H
 979 #define FSEv06_STATIC_H
 980
 981 #if defined (__cplusplus)
 982 extern "C" {
 983 #endif
 984
 985
 986 /* *****************************************
 987 *  Static allocation
 988 *******************************************/
 989 /* FSE buffer bounds */
 990 #define FSEv06_NCOUNTBOUND 512
 991 #define FSEv06_BLOCKBOUND(size) (size + (size>>7))
 992 #define FSEv06_COMPRESSBOUND(size) (FSEv06_NCOUNTBOUND + FSEv06_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
 993
 994 /* It is possible to statically allocate FSE CTable/DTable as a table of unsigned using below macros */
 995 #define FSEv06_DTABLE_SIZE_U32(maxTableLog)                   (1 + (1<<maxTableLog))
 996
 997
 998 /* *****************************************
 999 *  FSE advanced API
1000 *******************************************/
1001 size_t FSEv06_countFast(unsigned* count, unsigned* maxSymbolValuePtr, const void* src, size_t srcSize);
1002 /* same as FSEv06_count(), but blindly trusts that all byte values within src are <= *maxSymbolValuePtr  */
1003
1004 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits);
1005 /* build a fake FSEv06_DTable, designed to read an uncompressed bitstream where each symbol uses nbBits */
1006
1007 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, unsigned char symbolValue);
1008 /* build a fake FSEv06_DTable, designed to always generate the same symbolValue */
1009
1010
1011 /* *****************************************
1012 *  FSE symbol decompression API
1013 *******************************************/
1014 typedef struct
1015 {
1016     size_t      state;
1017     const void* table;   /* precise table may vary, depending on U16 */
1018 } FSEv06_DState_t;
1019
1020
1021 static void     FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt);
1022
1023 static unsigned char FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD);
1024
1025
1026 /* *****************************************
1027 *  FSE unsafe API
1028 *******************************************/
1029 static unsigned char FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD);
1030 /* faster, but works only if nbBits is always >= 1 (otherwise, result will be corrupted) */
1031
1032
1033 /* *****************************************
1034 *  Implementation of inlined functions
1035 *******************************************/
1036
1037
1038 /* ======    Decompression    ====== */
1039
1040 typedef struct {
1041     U16 tableLog;
1042     U16 fastMode;
1043 } FSEv06_DTableHeader;   /* sizeof U32 */
1044
1045 typedef struct
1046 {
1047     unsigned short newState;
1048     unsigned char  symbol;
1049     unsigned char  nbBits;
1050 } FSEv06_decode_t;   /* size == U32 */
1051
1052 MEM_STATIC void FSEv06_initDState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD, const FSEv06_DTable* dt)
1053 {
1054     const void* ptr = dt;
1055     const FSEv06_DTableHeader* const DTableH = (const FSEv06_DTableHeader*)ptr;
1056     DStatePtr->state = BITv06_readBits(bitD, DTableH->tableLog);
1057     BITv06_reloadDStream(bitD);
1058     DStatePtr->table = dt + 1;
1059 }
1060
1061 MEM_STATIC BYTE FSEv06_peekSymbol(const FSEv06_DState_t* DStatePtr)
1062 {
1063     FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1064     return DInfo.symbol;
1065 }
1066
1067 MEM_STATIC void FSEv06_updateState(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1068 {
1069     FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1070     U32 const nbBits = DInfo.nbBits;
1071     size_t const lowBits = BITv06_readBits(bitD, nbBits);
1072     DStatePtr->state = DInfo.newState + lowBits;
1073 }
1074
1075 MEM_STATIC BYTE FSEv06_decodeSymbol(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1076 {
1077     FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1078     U32 const nbBits = DInfo.nbBits;
1079     BYTE const symbol = DInfo.symbol;
1080     size_t const lowBits = BITv06_readBits(bitD, nbBits);
1081
1082     DStatePtr->state = DInfo.newState + lowBits;
1083     return symbol;
1084 }
1085
1086 /*! FSEv06_decodeSymbolFast() :
1087     unsafe, only works if no symbol has a probability > 50% */
1088 MEM_STATIC BYTE FSEv06_decodeSymbolFast(FSEv06_DState_t* DStatePtr, BITv06_DStream_t* bitD)
1089 {
1090     FSEv06_decode_t const DInfo = ((const FSEv06_decode_t*)(DStatePtr->table))[DStatePtr->state];
1091     U32 const nbBits = DInfo.nbBits;
1092     BYTE const symbol = DInfo.symbol;
1093     size_t const lowBits = BITv06_readBitsFast(bitD, nbBits);
1094
1095     DStatePtr->state = DInfo.newState + lowBits;
1096     return symbol;
1097 }
1098
1099
1100
1101 #ifndef FSEv06_COMMONDEFS_ONLY
1102
1103 /* **************************************************************
1104 *  Tuning parameters
1105 ****************************************************************/
1106 /*!MEMORY_USAGE :
1107 *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1108 *  Increasing memory usage improves compression ratio
1109 *  Reduced memory usage can improve speed, due to cache effect
1110 *  Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
1111 #define FSEv06_MAX_MEMORY_USAGE 14
1112 #define FSEv06_DEFAULT_MEMORY_USAGE 13
1113
1114 /*!FSEv06_MAX_SYMBOL_VALUE :
1115 *  Maximum symbol value authorized.
1116 *  Required for proper stack allocation */
1117 #define FSEv06_MAX_SYMBOL_VALUE 255
1118
1119
1120 /* **************************************************************
1121 *  template functions type & suffix
1122 ****************************************************************/
1123 #define FSEv06_FUNCTION_TYPE BYTE
1124 #define FSEv06_FUNCTION_EXTENSION
1125 #define FSEv06_DECODE_TYPE FSEv06_decode_t
1126
1127
1128 #endif   /* !FSEv06_COMMONDEFS_ONLY */
1129
1130
1131 /* ***************************************************************
1132 *  Constants
1133 *****************************************************************/
1134 #define FSEv06_MAX_TABLELOG  (FSEv06_MAX_MEMORY_USAGE-2)
1135 #define FSEv06_MAX_TABLESIZE (1U<<FSEv06_MAX_TABLELOG)
1136 #define FSEv06_MAXTABLESIZE_MASK (FSEv06_MAX_TABLESIZE-1)
1137 #define FSEv06_DEFAULT_TABLELOG (FSEv06_DEFAULT_MEMORY_USAGE-2)
1138 #define FSEv06_MIN_TABLELOG 5
1139
1140 #define FSEv06_TABLELOG_ABSOLUTE_MAX 15
1141 #if FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX
1142 #error "FSEv06_MAX_TABLELOG > FSEv06_TABLELOG_ABSOLUTE_MAX is not supported"
1143 #endif
1144
1145 #define FSEv06_TABLESTEP(tableSize) ((tableSize>>1) + (tableSize>>3) + 3)
1146
1147
1148 #if defined (__cplusplus)
1149 }
1150 #endif
1151
1152 #endif  /* FSEv06_STATIC_H */
1153 /*
1154    Common functions of New Generation Entropy library
1155    Copyright (C) 2016, Yann Collet.
1156
1157    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1158
1159    Redistribution and use in source and binary forms, with or without
1160    modification, are permitted provided that the following conditions are
1161    met:
1162
1163        * Redistributions of source code must retain the above copyright
1164    notice, this list of conditions and the following disclaimer.
1165        * Redistributions in binary form must reproduce the above
1166    copyright notice, this list of conditions and the following disclaimer
1167    in the documentation and/or other materials provided with the
1168    distribution.
1169
1170    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1171    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1172    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1173    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1174    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1175    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1176    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1177    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1178    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1179    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1180    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1181
1182     You can contact the author at :
1183     - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1184     - Public forum : https://groups.google.com/forum/#!forum/lz4c
1185 *************************************************************************** */
1186
1187
1188 /*-****************************************
1189 *  FSE Error Management
1190 ******************************************/
1191 unsigned FSEv06_isError(size_t code) { return ERR_isError(code); }
1192
1193 const char* FSEv06_getErrorName(size_t code) { return ERR_getErrorName(code); }
1194
1195
1196 /* **************************************************************
1197 *  HUF Error Management
1198 ****************************************************************/
1199 static unsigned HUFv06_isError(size_t code) { return ERR_isError(code); }
1200
1201
1202 /*-**************************************************************
1203 *  FSE NCount encoding-decoding
1204 ****************************************************************/
1205 static short FSEv06_abs(short a) { return a<0 ? -a : a; }
1206
1207 size_t FSEv06_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
1208                  const void* headerBuffer, size_t hbSize)
1209 {
1210     const BYTE* const istart = (const BYTE*) headerBuffer;
1211     const BYTE* const iend = istart + hbSize;
1212     const BYTE* ip = istart;
1213     int nbBits;
1214     int remaining;
1215     int threshold;
1216     U32 bitStream;
1217     int bitCount;
1218     unsigned charnum = 0;
1219     int previous0 = 0;
1220
1221     if (hbSize < 4) return ERROR(srcSize_wrong);
1222     bitStream = MEM_readLE32(ip);
1223     nbBits = (bitStream & 0xF) + FSEv06_MIN_TABLELOG;   /* extract tableLog */
1224     if (nbBits > FSEv06_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
1225     bitStream >>= 4;
1226     bitCount = 4;
1227     *tableLogPtr = nbBits;
1228     remaining = (1<<nbBits)+1;
1229     threshold = 1<<nbBits;
1230     nbBits++;
1231
1232     while ((remaining>1) && (charnum<=*maxSVPtr)) {
1233         if (previous0) {
1234             unsigned n0 = charnum;
1235             while ((bitStream & 0xFFFF) == 0xFFFF) {
1236                 n0+=24;
1237                 if (ip < iend-5) {
1238                     ip+=2;
1239                     bitStream = MEM_readLE32(ip) >> bitCount;
1240                 } else {
1241                     bitStream >>= 16;
1242                     bitCount+=16;
1243             }   }
1244             while ((bitStream & 3) == 3) {
1245                 n0+=3;
1246                 bitStream>>=2;
1247                 bitCount+=2;
1248             }
1249             n0 += bitStream & 3;
1250             bitCount += 2;
1251             if (n0 > *maxSVPtr) return ERROR(maxSymbolValue_tooSmall);
1252             while (charnum < n0) normalizedCounter[charnum++] = 0;
1253             if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1254                 ip += bitCount>>3;
1255                 bitCount &= 7;
1256                 bitStream = MEM_readLE32(ip) >> bitCount;
1257             }
1258             else
1259                 bitStream >>= 2;
1260         }
1261         {   short const max = (short)((2*threshold-1)-remaining);
1262             short count;
1263
1264             if ((bitStream & (threshold-1)) < (U32)max) {
1265                 count = (short)(bitStream & (threshold-1));
1266                 bitCount   += nbBits-1;
1267             } else {
1268                 count = (short)(bitStream & (2*threshold-1));
1269                 if (count >= threshold) count -= max;
1270                 bitCount   += nbBits;
1271             }
1272
1273             count--;   /* extra accuracy */
1274             remaining -= FSEv06_abs(count);
1275             normalizedCounter[charnum++] = count;
1276             previous0 = !count;
1277             while (remaining < threshold) {
1278                 nbBits--;
1279                 threshold >>= 1;
1280             }
1281
1282             if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
1283                 ip += bitCount>>3;
1284                 bitCount &= 7;
1285             } else {
1286                 bitCount -= (int)(8 * (iend - 4 - ip));
1287                 ip = iend - 4;
1288             }
1289             bitStream = MEM_readLE32(ip) >> (bitCount & 31);
1290     }   }   /* while ((remaining>1) && (charnum<=*maxSVPtr)) */
1291     if (remaining != 1) return ERROR(GENERIC);
1292     *maxSVPtr = charnum-1;
1293
1294     ip += (bitCount+7)>>3;
1295     if ((size_t)(ip-istart) > hbSize) return ERROR(srcSize_wrong);
1296     return ip-istart;
1297 }
1298 /* ******************************************************************
1299    FSE : Finite State Entropy decoder
1300    Copyright (C) 2013-2015, Yann Collet.
1301
1302    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1303
1304    Redistribution and use in source and binary forms, with or without
1305    modification, are permitted provided that the following conditions are
1306    met:
1307
1308        * Redistributions of source code must retain the above copyright
1309    notice, this list of conditions and the following disclaimer.
1310        * Redistributions in binary form must reproduce the above
1311    copyright notice, this list of conditions and the following disclaimer
1312    in the documentation and/or other materials provided with the
1313    distribution.
1314
1315    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1316    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1317    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1318    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1319    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1320    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1321    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1322    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1323    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1324    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1325    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1326
1327     You can contact the author at :
1328     - FSE source repository : https://github.com/Cyan4973/FiniteStateEntropy
1329     - Public forum : https://groups.google.com/forum/#!forum/lz4c
1330 ****************************************************************** */
1331
1332
1333 /* **************************************************************
1334 *  Compiler specifics
1335 ****************************************************************/
1336 #ifdef _MSC_VER    /* Visual Studio */
1337 #  define FORCE_INLINE static __forceinline
1338 #  include <intrin.h>                    /* For Visual 2005 */
1339 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1340 #  pragma warning(disable : 4214)        /* disable: C4214: non-int bitfields */
1341 #else
1342 #  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
1343 #    ifdef __GNUC__
1344 #      define FORCE_INLINE static inline __attribute__((always_inline))
1345 #    else
1346 #      define FORCE_INLINE static inline
1347 #    endif
1348 #  else
1349 #    define FORCE_INLINE static
1350 #  endif /* __STDC_VERSION__ */
1351 #endif
1352
1353
1354 /* **************************************************************
1355 *  Error Management
1356 ****************************************************************/
1357 #define FSEv06_isError ERR_isError
1358 #define FSEv06_STATIC_ASSERT(c) { enum { FSEv06_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1359
1360
1361 /* **************************************************************
1362 *  Complex types
1363 ****************************************************************/
1364 typedef U32 DTable_max_t[FSEv06_DTABLE_SIZE_U32(FSEv06_MAX_TABLELOG)];
1365
1366
1367 /* **************************************************************
1368 *  Templates
1369 ****************************************************************/
1370 /*
1371   designed to be included
1372   for type-specific functions (template emulation in C)
1373   Objective is to write these functions only once, for improved maintenance
1374 */
1375
1376 /* safety checks */
1377 #ifndef FSEv06_FUNCTION_EXTENSION
1378 #  error "FSEv06_FUNCTION_EXTENSION must be defined"
1379 #endif
1380 #ifndef FSEv06_FUNCTION_TYPE
1381 #  error "FSEv06_FUNCTION_TYPE must be defined"
1382 #endif
1383
1384 /* Function names */
1385 #define FSEv06_CAT(X,Y) X##Y
1386 #define FSEv06_FUNCTION_NAME(X,Y) FSEv06_CAT(X,Y)
1387 #define FSEv06_TYPE_NAME(X,Y) FSEv06_CAT(X,Y)
1388
1389
1390 /* Function templates */
1391 FSEv06_DTable* FSEv06_createDTable (unsigned tableLog)
1392 {
1393     if (tableLog > FSEv06_TABLELOG_ABSOLUTE_MAX) tableLog = FSEv06_TABLELOG_ABSOLUTE_MAX;
1394     return (FSEv06_DTable*)malloc( FSEv06_DTABLE_SIZE_U32(tableLog) * sizeof (U32) );
1395 }
1396
1397 void FSEv06_freeDTable (FSEv06_DTable* dt)
1398 {
1399     free(dt);
1400 }
1401
1402 size_t FSEv06_buildDTable(FSEv06_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
1403 {
1404     void* const tdPtr = dt+1;   /* because *dt is unsigned, 32-bits aligned on 32-bits */
1405     FSEv06_DECODE_TYPE* const tableDecode = (FSEv06_DECODE_TYPE*) (tdPtr);
1406     U16 symbolNext[FSEv06_MAX_SYMBOL_VALUE+1];
1407
1408     U32 const maxSV1 = maxSymbolValue + 1;
1409     U32 const tableSize = 1 << tableLog;
1410     U32 highThreshold = tableSize-1;
1411
1412     /* Sanity Checks */
1413     if (maxSymbolValue > FSEv06_MAX_SYMBOL_VALUE) return ERROR(maxSymbolValue_tooLarge);
1414     if (tableLog > FSEv06_MAX_TABLELOG) return ERROR(tableLog_tooLarge);
1415
1416     /* Init, lay down lowprob symbols */
1417     {   FSEv06_DTableHeader DTableH;
1418         DTableH.tableLog = (U16)tableLog;
1419         DTableH.fastMode = 1;
1420         {   S16 const largeLimit= (S16)(1 << (tableLog-1));
1421             U32 s;
1422             for (s=0; s<maxSV1; s++) {
1423                 if (normalizedCounter[s]==-1) {
1424                     tableDecode[highThreshold--].symbol = (FSEv06_FUNCTION_TYPE)s;
1425                     symbolNext[s] = 1;
1426                 } else {
1427                     if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
1428                     symbolNext[s] = normalizedCounter[s];
1429         }   }   }
1430         memcpy(dt, &DTableH, sizeof(DTableH));
1431     }
1432
1433     /* Spread symbols */
1434     {   U32 const tableMask = tableSize-1;
1435         U32 const step = FSEv06_TABLESTEP(tableSize);
1436         U32 s, position = 0;
1437         for (s=0; s<maxSV1; s++) {
1438             int i;
1439             for (i=0; i<normalizedCounter[s]; i++) {
1440                 tableDecode[position].symbol = (FSEv06_FUNCTION_TYPE)s;
1441                 position = (position + step) & tableMask;
1442                 while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
1443         }   }
1444
1445         if (position!=0) return ERROR(GENERIC);   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
1446     }
1447
1448     /* Build Decoding table */
1449     {   U32 u;
1450         for (u=0; u<tableSize; u++) {
1451             FSEv06_FUNCTION_TYPE const symbol = (FSEv06_FUNCTION_TYPE)(tableDecode[u].symbol);
1452             U16 nextState = symbolNext[symbol]++;
1453             tableDecode[u].nbBits = (BYTE) (tableLog - BITv06_highbit32 ((U32)nextState) );
1454             tableDecode[u].newState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
1455     }   }
1456
1457     return 0;
1458 }
1459
1460
1461
1462 #ifndef FSEv06_COMMONDEFS_ONLY
1463
1464 /*-*******************************************************
1465 *  Decompression (Byte symbols)
1466 *********************************************************/
1467 size_t FSEv06_buildDTable_rle (FSEv06_DTable* dt, BYTE symbolValue)
1468 {
1469     void* ptr = dt;
1470     FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr;
1471     void* dPtr = dt + 1;
1472     FSEv06_decode_t* const cell = (FSEv06_decode_t*)dPtr;
1473
1474     DTableH->tableLog = 0;
1475     DTableH->fastMode = 0;
1476
1477     cell->newState = 0;
1478     cell->symbol = symbolValue;
1479     cell->nbBits = 0;
1480
1481     return 0;
1482 }
1483
1484
1485 size_t FSEv06_buildDTable_raw (FSEv06_DTable* dt, unsigned nbBits)
1486 {
1487     void* ptr = dt;
1488     FSEv06_DTableHeader* const DTableH = (FSEv06_DTableHeader*)ptr;
1489     void* dPtr = dt + 1;
1490     FSEv06_decode_t* const dinfo = (FSEv06_decode_t*)dPtr;
1491     const unsigned tableSize = 1 << nbBits;
1492     const unsigned tableMask = tableSize - 1;
1493     const unsigned maxSV1 = tableMask+1;
1494     unsigned s;
1495
1496     /* Sanity checks */
1497     if (nbBits < 1) return ERROR(GENERIC);         /* min size */
1498
1499     /* Build Decoding Table */
1500     DTableH->tableLog = (U16)nbBits;
1501     DTableH->fastMode = 1;
1502     for (s=0; s<maxSV1; s++) {
1503         dinfo[s].newState = 0;
1504         dinfo[s].symbol = (BYTE)s;
1505         dinfo[s].nbBits = (BYTE)nbBits;
1506     }
1507
1508     return 0;
1509 }
1510
1511 FORCE_INLINE size_t FSEv06_decompress_usingDTable_generic(
1512           void* dst, size_t maxDstSize,
1513     const void* cSrc, size_t cSrcSize,
1514     const FSEv06_DTable* dt, const unsigned fast)
1515 {
1516     BYTE* const ostart = (BYTE*) dst;
1517     BYTE* op = ostart;
1518     BYTE* const omax = op + maxDstSize;
1519     BYTE* const olimit = omax-3;
1520
1521     BITv06_DStream_t bitD;
1522     FSEv06_DState_t state1;
1523     FSEv06_DState_t state2;
1524
1525     /* Init */
1526     { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize);   /* replaced last arg by maxCompressed Size */
1527       if (FSEv06_isError(errorCode)) return errorCode; }
1528
1529     FSEv06_initDState(&state1, &bitD, dt);
1530     FSEv06_initDState(&state2, &bitD, dt);
1531
1532 #define FSEv06_GETSYMBOL(statePtr) fast ? FSEv06_decodeSymbolFast(statePtr, &bitD) : FSEv06_decodeSymbol(statePtr, &bitD)
1533
1534     /* 4 symbols per loop */
1535     for ( ; (BITv06_reloadDStream(&bitD)==BITv06_DStream_unfinished) && (op<olimit) ; op+=4) {
1536         op[0] = FSEv06_GETSYMBOL(&state1);
1537
1538         if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1539             BITv06_reloadDStream(&bitD);
1540
1541         op[1] = FSEv06_GETSYMBOL(&state2);
1542
1543         if (FSEv06_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1544             { if (BITv06_reloadDStream(&bitD) > BITv06_DStream_unfinished) { op+=2; break; } }
1545
1546         op[2] = FSEv06_GETSYMBOL(&state1);
1547
1548         if (FSEv06_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
1549             BITv06_reloadDStream(&bitD);
1550
1551         op[3] = FSEv06_GETSYMBOL(&state2);
1552     }
1553
1554     /* tail */
1555     /* note : BITv06_reloadDStream(&bitD) >= FSEv06_DStream_partiallyFilled; Ends at exactly BITv06_DStream_completed */
1556     while (1) {
1557         if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1558
1559         *op++ = FSEv06_GETSYMBOL(&state1);
1560
1561         if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) {
1562             *op++ = FSEv06_GETSYMBOL(&state2);
1563             break;
1564         }
1565
1566         if (op>(omax-2)) return ERROR(dstSize_tooSmall);
1567
1568         *op++ = FSEv06_GETSYMBOL(&state2);
1569
1570         if (BITv06_reloadDStream(&bitD)==BITv06_DStream_overflow) {
1571             *op++ = FSEv06_GETSYMBOL(&state1);
1572             break;
1573     }   }
1574
1575     return op-ostart;
1576 }
1577
1578
1579 size_t FSEv06_decompress_usingDTable(void* dst, size_t originalSize,
1580                             const void* cSrc, size_t cSrcSize,
1581                             const FSEv06_DTable* dt)
1582 {
1583     const void* ptr = dt;
1584     const FSEv06_DTableHeader* DTableH = (const FSEv06_DTableHeader*)ptr;
1585     const U32 fastMode = DTableH->fastMode;
1586
1587     /* select fast mode (static) */
1588     if (fastMode) return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
1589     return FSEv06_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
1590 }
1591
1592
1593 size_t FSEv06_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1594 {
1595     const BYTE* const istart = (const BYTE*)cSrc;
1596     const BYTE* ip = istart;
1597     short counting[FSEv06_MAX_SYMBOL_VALUE+1];
1598     DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
1599     unsigned tableLog;
1600     unsigned maxSymbolValue = FSEv06_MAX_SYMBOL_VALUE;
1601
1602     if (cSrcSize<2) return ERROR(srcSize_wrong);   /* too small input size */
1603
1604     /* normal FSE decoding mode */
1605     {   size_t const NCountLength = FSEv06_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
1606         if (FSEv06_isError(NCountLength)) return NCountLength;
1607         if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong);   /* too small input size */
1608         ip += NCountLength;
1609         cSrcSize -= NCountLength;
1610     }
1611
1612     { size_t const errorCode = FSEv06_buildDTable (dt, counting, maxSymbolValue, tableLog);
1613       if (FSEv06_isError(errorCode)) return errorCode; }
1614
1615     return FSEv06_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);   /* always return, even if it is an error code */
1616 }
1617
1618
1619
1620 #endif   /* FSEv06_COMMONDEFS_ONLY */
1621 /* ******************************************************************
1622    Huffman coder, part of New Generation Entropy library
1623    header file
1624    Copyright (C) 2013-2016, Yann Collet.
1625
1626    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1627
1628    Redistribution and use in source and binary forms, with or without
1629    modification, are permitted provided that the following conditions are
1630    met:
1631
1632        * Redistributions of source code must retain the above copyright
1633    notice, this list of conditions and the following disclaimer.
1634        * Redistributions in binary form must reproduce the above
1635    copyright notice, this list of conditions and the following disclaimer
1636    in the documentation and/or other materials provided with the
1637    distribution.
1638
1639    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1640    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1641    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1642    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1643    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1644    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1645    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1646    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1647    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1648    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1649    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1650
1651    You can contact the author at :
1652    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1653 ****************************************************************** */
1654 #ifndef HUFv06_H
1655 #define HUFv06_H
1656
1657 #if defined (__cplusplus)
1658 extern "C" {
1659 #endif
1660
1661
1662 /* ****************************************
1663 *  HUF simple functions
1664 ******************************************/
1665 size_t HUFv06_decompress(void* dst,  size_t dstSize,
1666                 const void* cSrc, size_t cSrcSize);
1667 /*
1668 HUFv06_decompress() :
1669     Decompress HUF data from buffer 'cSrc', of size 'cSrcSize',
1670     into already allocated destination buffer 'dst', of size 'dstSize'.
1671     `dstSize` : must be the **exact** size of original (uncompressed) data.
1672     Note : in contrast with FSE, HUFv06_decompress can regenerate
1673            RLE (cSrcSize==1) and uncompressed (cSrcSize==dstSize) data,
1674            because it knows size to regenerate.
1675     @return : size of regenerated data (== dstSize)
1676               or an error code, which can be tested using HUFv06_isError()
1677 */
1678
1679
1680 /* ****************************************
1681 *  Tool functions
1682 ******************************************/
1683 size_t HUFv06_compressBound(size_t size);       /**< maximum compressed size */
1684
1685
1686 #if defined (__cplusplus)
1687 }
1688 #endif
1689
1690 #endif   /* HUFv06_H */
1691 /* ******************************************************************
1692    Huffman codec, part of New Generation Entropy library
1693    header file, for static linking only
1694    Copyright (C) 2013-2016, Yann Collet
1695
1696    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1697
1698    Redistribution and use in source and binary forms, with or without
1699    modification, are permitted provided that the following conditions are
1700    met:
1701
1702        * Redistributions of source code must retain the above copyright
1703    notice, this list of conditions and the following disclaimer.
1704        * Redistributions in binary form must reproduce the above
1705    copyright notice, this list of conditions and the following disclaimer
1706    in the documentation and/or other materials provided with the
1707    distribution.
1708
1709    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1710    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1711    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1712    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1713    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1714    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1715    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1716    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1717    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1718    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1719    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1720
1721    You can contact the author at :
1722    - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
1723 ****************************************************************** */
1724 #ifndef HUFv06_STATIC_H
1725 #define HUFv06_STATIC_H
1726
1727 #if defined (__cplusplus)
1728 extern "C" {
1729 #endif
1730
1731
1732 /* ****************************************
1733 *  Static allocation
1734 ******************************************/
1735 /* HUF buffer bounds */
1736 #define HUFv06_CTABLEBOUND 129
1737 #define HUFv06_BLOCKBOUND(size) (size + (size>>8) + 8)   /* only true if incompressible pre-filtered with fast heuristic */
1738 #define HUFv06_COMPRESSBOUND(size) (HUFv06_CTABLEBOUND + HUFv06_BLOCKBOUND(size))   /* Macro version, useful for static allocation */
1739
1740 /* static allocation of HUF's DTable */
1741 #define HUFv06_DTABLE_SIZE(maxTableLog)   (1 + (1<<maxTableLog))
1742 #define HUFv06_CREATE_STATIC_DTABLEX2(DTable, maxTableLog) \
1743         unsigned short DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1744 #define HUFv06_CREATE_STATIC_DTABLEX4(DTable, maxTableLog) \
1745         unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog)] = { maxTableLog }
1746 #define HUFv06_CREATE_STATIC_DTABLEX6(DTable, maxTableLog) \
1747         unsigned int DTable[HUFv06_DTABLE_SIZE(maxTableLog) * 3 / 2] = { maxTableLog }
1748
1749
1750 /* ****************************************
1751 *  Advanced decompression functions
1752 ******************************************/
1753 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
1754 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-symbols decoder */
1755
1756
1757
1758 /*!
1759 HUFv06_decompress() does the following:
1760 1. select the decompression algorithm (X2, X4, X6) based on pre-computed heuristics
1761 2. build Huffman table from save, using HUFv06_readDTableXn()
1762 3. decode 1 or 4 segments in parallel using HUFv06_decompressSXn_usingDTable
1763 */
1764 size_t HUFv06_readDTableX2 (unsigned short* DTable, const void* src, size_t srcSize);
1765 size_t HUFv06_readDTableX4 (unsigned* DTable, const void* src, size_t srcSize);
1766
1767 size_t HUFv06_decompress4X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1768 size_t HUFv06_decompress4X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1769
1770
1771 /* single stream variants */
1772 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* single-symbol decoder */
1773 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);   /* double-symbol decoder */
1774
1775 size_t HUFv06_decompress1X2_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned short* DTable);
1776 size_t HUFv06_decompress1X4_usingDTable(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize, const unsigned* DTable);
1777
1778
1779
1780 /* **************************************************************
1781 *  Constants
1782 ****************************************************************/
1783 #define HUFv06_ABSOLUTEMAX_TABLELOG  16   /* absolute limit of HUFv06_MAX_TABLELOG. Beyond that value, code does not work */
1784 #define HUFv06_MAX_TABLELOG  12           /* max configured tableLog (for static allocation); can be modified up to HUFv06_ABSOLUTEMAX_TABLELOG */
1785 #define HUFv06_DEFAULT_TABLELOG  HUFv06_MAX_TABLELOG   /* tableLog by default, when not specified */
1786 #define HUFv06_MAX_SYMBOL_VALUE 255
1787 #if (HUFv06_MAX_TABLELOG > HUFv06_ABSOLUTEMAX_TABLELOG)
1788 #  error "HUFv06_MAX_TABLELOG is too large !"
1789 #endif
1790
1791
1792
1793 /*! HUFv06_readStats() :
1794     Read compact Huffman tree, saved by HUFv06_writeCTable().
1795     `huffWeight` is destination buffer.
1796     @return : size read from `src`
1797 */
1798 MEM_STATIC size_t HUFv06_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
1799                             U32* nbSymbolsPtr, U32* tableLogPtr,
1800                             const void* src, size_t srcSize)
1801 {
1802     U32 weightTotal;
1803     const BYTE* ip = (const BYTE*) src;
1804     size_t iSize;
1805     size_t oSize;
1806
1807     if (!srcSize) return ERROR(srcSize_wrong);
1808     iSize = ip[0];
1809     /* memset(huffWeight, 0, hwSize); */   /* is not necessary, even though some analyzer complain ... */
1810
1811     if (iSize >= 128)  { /* special header */
1812         if (iSize >= (242)) {  /* RLE */
1813             static U32 l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
1814             oSize = l[iSize-242];
1815             memset(huffWeight, 1, hwSize);
1816             iSize = 0;
1817         }
1818         else {   /* Incompressible */
1819             oSize = iSize - 127;
1820             iSize = ((oSize+1)/2);
1821             if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1822             if (oSize >= hwSize) return ERROR(corruption_detected);
1823             ip += 1;
1824             {   U32 n;
1825                 for (n=0; n<oSize; n+=2) {
1826                     huffWeight[n]   = ip[n/2] >> 4;
1827                     huffWeight[n+1] = ip[n/2] & 15;
1828     }   }   }   }
1829     else  {   /* header compressed with FSE (normal case) */
1830         if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
1831         oSize = FSEv06_decompress(huffWeight, hwSize-1, ip+1, iSize);   /* max (hwSize-1) values decoded, as last one is implied */
1832         if (FSEv06_isError(oSize)) return oSize;
1833     }
1834
1835     /* collect weight stats */
1836     memset(rankStats, 0, (HUFv06_ABSOLUTEMAX_TABLELOG + 1) * sizeof(U32));
1837     weightTotal = 0;
1838     {   U32 n; for (n=0; n<oSize; n++) {
1839             if (huffWeight[n] >= HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1840             rankStats[huffWeight[n]]++;
1841             weightTotal += (1 << huffWeight[n]) >> 1;
1842     }   }
1843     if (weightTotal == 0) return ERROR(corruption_detected);
1844
1845     /* get last non-null symbol weight (implied, total must be 2^n) */
1846     {   U32 const tableLog = BITv06_highbit32(weightTotal) + 1;
1847         if (tableLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(corruption_detected);
1848         *tableLogPtr = tableLog;
1849         /* determine last weight */
1850         {   U32 const total = 1 << tableLog;
1851             U32 const rest = total - weightTotal;
1852             U32 const verif = 1 << BITv06_highbit32(rest);
1853             U32 const lastWeight = BITv06_highbit32(rest) + 1;
1854             if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
1855             huffWeight[oSize] = (BYTE)lastWeight;
1856             rankStats[lastWeight]++;
1857     }   }
1858
1859     /* check tree construction validity */
1860     if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected);   /* by construction : at least 2 elts of rank 1, must be even */
1861
1862     /* results */
1863     *nbSymbolsPtr = (U32)(oSize+1);
1864     return iSize+1;
1865 }
1866
1867
1868
1869 #if defined (__cplusplus)
1870 }
1871 #endif
1872
1873 #endif /* HUFv06_STATIC_H */
1874 /* ******************************************************************
1875    Huffman decoder, part of New Generation Entropy library
1876    Copyright (C) 2013-2016, Yann Collet.
1877
1878    BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
1879
1880    Redistribution and use in source and binary forms, with or without
1881    modification, are permitted provided that the following conditions are
1882    met:
1883
1884        * Redistributions of source code must retain the above copyright
1885    notice, this list of conditions and the following disclaimer.
1886        * Redistributions in binary form must reproduce the above
1887    copyright notice, this list of conditions and the following disclaimer
1888    in the documentation and/or other materials provided with the
1889    distribution.
1890
1891    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1892    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1893    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1894    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1895    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1896    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1897    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1898    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1899    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1900    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1901    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1902
1903     You can contact the author at :
1904     - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
1905     - Public forum : https://groups.google.com/forum/#!forum/lz4c
1906 ****************************************************************** */
1907
1908 /* **************************************************************
1909 *  Compiler specifics
1910 ****************************************************************/
1911 #if defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
1912 /* inline is defined */
1913 #elif defined(_MSC_VER)
1914 #  define inline __inline
1915 #else
1916 #  define inline /* disable inline */
1917 #endif
1918
1919
1920 #ifdef _MSC_VER    /* Visual Studio */
1921 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1922 #endif
1923
1924
1925
1926 /* **************************************************************
1927 *  Error Management
1928 ****************************************************************/
1929 #define HUFv06_STATIC_ASSERT(c) { enum { HUFv06_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
1930
1931
1932
1933 /* *******************************************************
1934 *  HUF : Huffman block decompression
1935 *********************************************************/
1936 typedef struct { BYTE byte; BYTE nbBits; } HUFv06_DEltX2;   /* single-symbol decoding */
1937
1938 typedef struct { U16 sequence; BYTE nbBits; BYTE length; } HUFv06_DEltX4;  /* double-symbols decoding */
1939
1940 typedef struct { BYTE symbol; BYTE weight; } sortedSymbol_t;
1941
1942
1943
1944 /*-***************************/
1945 /*  single-symbol decoding   */
1946 /*-***************************/
1947
1948 size_t HUFv06_readDTableX2 (U16* DTable, const void* src, size_t srcSize)
1949 {
1950     BYTE huffWeight[HUFv06_MAX_SYMBOL_VALUE + 1];
1951     U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1];   /* large enough for values from 0 to 16 */
1952     U32 tableLog = 0;
1953     size_t iSize;
1954     U32 nbSymbols = 0;
1955     U32 n;
1956     U32 nextRankStart;
1957     void* const dtPtr = DTable + 1;
1958     HUFv06_DEltX2* const dt = (HUFv06_DEltX2*)dtPtr;
1959
1960     HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX2) == sizeof(U16));   /* if compilation fails here, assertion is false */
1961     /* memset(huffWeight, 0, sizeof(huffWeight)); */   /* is not necessary, even though some analyzer complain ... */
1962
1963     iSize = HUFv06_readStats(huffWeight, HUFv06_MAX_SYMBOL_VALUE + 1, rankVal, &nbSymbols, &tableLog, src, srcSize);
1964     if (HUFv06_isError(iSize)) return iSize;
1965
1966     /* check result */
1967     if (tableLog > DTable[0]) return ERROR(tableLog_tooLarge);   /* DTable is too small */
1968     DTable[0] = (U16)tableLog;   /* maybe should separate sizeof allocated DTable, from used size of DTable, in case of re-use */
1969
1970     /* Prepare ranks */
1971     nextRankStart = 0;
1972     for (n=1; n<tableLog+1; n++) {
1973         U32 current = nextRankStart;
1974         nextRankStart += (rankVal[n] << (n-1));
1975         rankVal[n] = current;
1976     }
1977
1978     /* fill DTable */
1979     for (n=0; n<nbSymbols; n++) {
1980         const U32 w = huffWeight[n];
1981         const U32 length = (1 << w) >> 1;
1982         U32 i;
1983         HUFv06_DEltX2 D;
1984         D.byte = (BYTE)n; D.nbBits = (BYTE)(tableLog + 1 - w);
1985         for (i = rankVal[w]; i < rankVal[w] + length; i++)
1986             dt[i] = D;
1987         rankVal[w] += length;
1988     }
1989
1990     return iSize;
1991 }
1992
1993
1994 static BYTE HUFv06_decodeSymbolX2(BITv06_DStream_t* Dstream, const HUFv06_DEltX2* dt, const U32 dtLog)
1995 {
1996     const size_t val = BITv06_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1997     const BYTE c = dt[val].byte;
1998     BITv06_skipBits(Dstream, dt[val].nbBits);
1999     return c;
2000 }
2001
2002 #define HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr) \
2003     *ptr++ = HUFv06_decodeSymbolX2(DStreamPtr, dt, dtLog)
2004
2005 #define HUFv06_DECODE_SYMBOLX2_1(ptr, DStreamPtr) \
2006     if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2007         HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2008
2009 #define HUFv06_DECODE_SYMBOLX2_2(ptr, DStreamPtr) \
2010     if (MEM_64bits()) \
2011         HUFv06_DECODE_SYMBOLX2_0(ptr, DStreamPtr)
2012
2013 static inline size_t HUFv06_decodeStreamX2(BYTE* p, BITv06_DStream_t* const bitDPtr, BYTE* const pEnd, const HUFv06_DEltX2* const dt, const U32 dtLog)
2014 {
2015     BYTE* const pStart = p;
2016
2017     /* up to 4 symbols at a time */
2018     while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-4)) {
2019         HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr);
2020         HUFv06_DECODE_SYMBOLX2_1(p, bitDPtr);
2021         HUFv06_DECODE_SYMBOLX2_2(p, bitDPtr);
2022         HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2023     }
2024
2025     /* closer to the end */
2026     while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd))
2027         HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2028
2029     /* no more data to retrieve from bitstream, hence no need to reload */
2030     while (p < pEnd)
2031         HUFv06_DECODE_SYMBOLX2_0(p, bitDPtr);
2032
2033     return pEnd-pStart;
2034 }
2035
2036 size_t HUFv06_decompress1X2_usingDTable(
2037           void* dst,  size_t dstSize,
2038     const void* cSrc, size_t cSrcSize,
2039     const U16* DTable)
2040 {
2041     BYTE* op = (BYTE*)dst;
2042     BYTE* const oend = op + dstSize;
2043     const U32 dtLog = DTable[0];
2044     const void* dtPtr = DTable;
2045     const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr)+1;
2046     BITv06_DStream_t bitD;
2047
2048     { size_t const errorCode = BITv06_initDStream(&bitD, cSrc, cSrcSize);
2049       if (HUFv06_isError(errorCode)) return errorCode; }
2050
2051     HUFv06_decodeStreamX2(op, &bitD, oend, dt, dtLog);
2052
2053     /* check */
2054     if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected);
2055
2056     return dstSize;
2057 }
2058
2059 size_t HUFv06_decompress1X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2060 {
2061     HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG);
2062     const BYTE* ip = (const BYTE*) cSrc;
2063
2064     size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize);
2065     if (HUFv06_isError(errorCode)) return errorCode;
2066     if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2067     ip += errorCode;
2068     cSrcSize -= errorCode;
2069
2070     return HUFv06_decompress1X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2071 }
2072
2073
2074 size_t HUFv06_decompress4X2_usingDTable(
2075           void* dst,  size_t dstSize,
2076     const void* cSrc, size_t cSrcSize,
2077     const U16* DTable)
2078 {
2079     /* Check */
2080     if (cSrcSize < 10) return ERROR(corruption_detected);  /* strict minimum : jump table + 1 byte per stream */
2081
2082     {   const BYTE* const istart = (const BYTE*) cSrc;
2083         BYTE* const ostart = (BYTE*) dst;
2084         BYTE* const oend = ostart + dstSize;
2085         const void* const dtPtr = DTable;
2086         const HUFv06_DEltX2* const dt = ((const HUFv06_DEltX2*)dtPtr) +1;
2087         const U32 dtLog = DTable[0];
2088         size_t errorCode;
2089
2090         /* Init */
2091         BITv06_DStream_t bitD1;
2092         BITv06_DStream_t bitD2;
2093         BITv06_DStream_t bitD3;
2094         BITv06_DStream_t bitD4;
2095         const size_t length1 = MEM_readLE16(istart);
2096         const size_t length2 = MEM_readLE16(istart+2);
2097         const size_t length3 = MEM_readLE16(istart+4);
2098         size_t length4;
2099         const BYTE* const istart1 = istart + 6;  /* jumpTable */
2100         const BYTE* const istart2 = istart1 + length1;
2101         const BYTE* const istart3 = istart2 + length2;
2102         const BYTE* const istart4 = istart3 + length3;
2103         const size_t segmentSize = (dstSize+3) / 4;
2104         BYTE* const opStart2 = ostart + segmentSize;
2105         BYTE* const opStart3 = opStart2 + segmentSize;
2106         BYTE* const opStart4 = opStart3 + segmentSize;
2107         BYTE* op1 = ostart;
2108         BYTE* op2 = opStart2;
2109         BYTE* op3 = opStart3;
2110         BYTE* op4 = opStart4;
2111         U32 endSignal;
2112
2113         length4 = cSrcSize - (length1 + length2 + length3 + 6);
2114         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
2115         errorCode = BITv06_initDStream(&bitD1, istart1, length1);
2116         if (HUFv06_isError(errorCode)) return errorCode;
2117         errorCode = BITv06_initDStream(&bitD2, istart2, length2);
2118         if (HUFv06_isError(errorCode)) return errorCode;
2119         errorCode = BITv06_initDStream(&bitD3, istart3, length3);
2120         if (HUFv06_isError(errorCode)) return errorCode;
2121         errorCode = BITv06_initDStream(&bitD4, istart4, length4);
2122         if (HUFv06_isError(errorCode)) return errorCode;
2123
2124         /* 16-32 symbols per loop (4-8 symbols per stream) */
2125         endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2126         for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) {
2127             HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1);
2128             HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2);
2129             HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3);
2130             HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4);
2131             HUFv06_DECODE_SYMBOLX2_1(op1, &bitD1);
2132             HUFv06_DECODE_SYMBOLX2_1(op2, &bitD2);
2133             HUFv06_DECODE_SYMBOLX2_1(op3, &bitD3);
2134             HUFv06_DECODE_SYMBOLX2_1(op4, &bitD4);
2135             HUFv06_DECODE_SYMBOLX2_2(op1, &bitD1);
2136             HUFv06_DECODE_SYMBOLX2_2(op2, &bitD2);
2137             HUFv06_DECODE_SYMBOLX2_2(op3, &bitD3);
2138             HUFv06_DECODE_SYMBOLX2_2(op4, &bitD4);
2139             HUFv06_DECODE_SYMBOLX2_0(op1, &bitD1);
2140             HUFv06_DECODE_SYMBOLX2_0(op2, &bitD2);
2141             HUFv06_DECODE_SYMBOLX2_0(op3, &bitD3);
2142             HUFv06_DECODE_SYMBOLX2_0(op4, &bitD4);
2143             endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2144         }
2145
2146         /* check corruption */
2147         if (op1 > opStart2) return ERROR(corruption_detected);
2148         if (op2 > opStart3) return ERROR(corruption_detected);
2149         if (op3 > opStart4) return ERROR(corruption_detected);
2150         /* note : op4 supposed already verified within main loop */
2151
2152         /* finish bitStreams one by one */
2153         HUFv06_decodeStreamX2(op1, &bitD1, opStart2, dt, dtLog);
2154         HUFv06_decodeStreamX2(op2, &bitD2, opStart3, dt, dtLog);
2155         HUFv06_decodeStreamX2(op3, &bitD3, opStart4, dt, dtLog);
2156         HUFv06_decodeStreamX2(op4, &bitD4, oend,     dt, dtLog);
2157
2158         /* check */
2159         endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4);
2160         if (!endSignal) return ERROR(corruption_detected);
2161
2162         /* decoded size */
2163         return dstSize;
2164     }
2165 }
2166
2167
2168 size_t HUFv06_decompress4X2 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2169 {
2170     HUFv06_CREATE_STATIC_DTABLEX2(DTable, HUFv06_MAX_TABLELOG);
2171     const BYTE* ip = (const BYTE*) cSrc;
2172
2173     size_t const errorCode = HUFv06_readDTableX2 (DTable, cSrc, cSrcSize);
2174     if (HUFv06_isError(errorCode)) return errorCode;
2175     if (errorCode >= cSrcSize) return ERROR(srcSize_wrong);
2176     ip += errorCode;
2177     cSrcSize -= errorCode;
2178
2179     return HUFv06_decompress4X2_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2180 }
2181
2182
2183 /* *************************/
2184 /* double-symbols decoding */
2185 /* *************************/
2186
2187 static void HUFv06_fillDTableX4Level2(HUFv06_DEltX4* DTable, U32 sizeLog, const U32 consumed,
2188                            const U32* rankValOrigin, const int minWeight,
2189                            const sortedSymbol_t* sortedSymbols, const U32 sortedListSize,
2190                            U32 nbBitsBaseline, U16 baseSeq)
2191 {
2192     HUFv06_DEltX4 DElt;
2193     U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2194
2195     /* get pre-calculated rankVal */
2196     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2197
2198     /* fill skipped values */
2199     if (minWeight>1) {
2200         U32 i, skipSize = rankVal[minWeight];
2201         MEM_writeLE16(&(DElt.sequence), baseSeq);
2202         DElt.nbBits   = (BYTE)(consumed);
2203         DElt.length   = 1;
2204         for (i = 0; i < skipSize; i++)
2205             DTable[i] = DElt;
2206     }
2207
2208     /* fill DTable */
2209     { U32 s; for (s=0; s<sortedListSize; s++) {   /* note : sortedSymbols already skipped */
2210         const U32 symbol = sortedSymbols[s].symbol;
2211         const U32 weight = sortedSymbols[s].weight;
2212         const U32 nbBits = nbBitsBaseline - weight;
2213         const U32 length = 1 << (sizeLog-nbBits);
2214         const U32 start = rankVal[weight];
2215         U32 i = start;
2216         const U32 end = start + length;
2217
2218         MEM_writeLE16(&(DElt.sequence), (U16)(baseSeq + (symbol << 8)));
2219         DElt.nbBits = (BYTE)(nbBits + consumed);
2220         DElt.length = 2;
2221         do { DTable[i++] = DElt; } while (i<end);   /* since length >= 1 */
2222
2223         rankVal[weight] += length;
2224     }}
2225 }
2226
2227 typedef U32 rankVal_t[HUFv06_ABSOLUTEMAX_TABLELOG][HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2228
2229 static void HUFv06_fillDTableX4(HUFv06_DEltX4* DTable, const U32 targetLog,
2230                            const sortedSymbol_t* sortedList, const U32 sortedListSize,
2231                            const U32* rankStart, rankVal_t rankValOrigin, const U32 maxWeight,
2232                            const U32 nbBitsBaseline)
2233 {
2234     U32 rankVal[HUFv06_ABSOLUTEMAX_TABLELOG + 1];
2235     const int scaleLog = nbBitsBaseline - targetLog;   /* note : targetLog >= srcLog, hence scaleLog <= 1 */
2236     const U32 minBits  = nbBitsBaseline - maxWeight;
2237     U32 s;
2238
2239     memcpy(rankVal, rankValOrigin, sizeof(rankVal));
2240
2241     /* fill DTable */
2242     for (s=0; s<sortedListSize; s++) {
2243         const U16 symbol = sortedList[s].symbol;
2244         const U32 weight = sortedList[s].weight;
2245         const U32 nbBits = nbBitsBaseline - weight;
2246         const U32 start = rankVal[weight];
2247         const U32 length = 1 << (targetLog-nbBits);
2248
2249         if (targetLog-nbBits >= minBits) {   /* enough room for a second symbol */
2250             U32 sortedRank;
2251             int minWeight = nbBits + scaleLog;
2252             if (minWeight < 1) minWeight = 1;
2253             sortedRank = rankStart[minWeight];
2254             HUFv06_fillDTableX4Level2(DTable+start, targetLog-nbBits, nbBits,
2255                            rankValOrigin[nbBits], minWeight,
2256                            sortedList+sortedRank, sortedListSize-sortedRank,
2257                            nbBitsBaseline, symbol);
2258         } else {
2259             HUFv06_DEltX4 DElt;
2260             MEM_writeLE16(&(DElt.sequence), symbol);
2261             DElt.nbBits = (BYTE)(nbBits);
2262             DElt.length = 1;
2263             {   U32 u;
2264                 const U32 end = start + length;
2265                 for (u = start; u < end; u++) DTable[u] = DElt;
2266         }   }
2267         rankVal[weight] += length;
2268     }
2269 }
2270
2271 size_t HUFv06_readDTableX4 (U32* DTable, const void* src, size_t srcSize)
2272 {
2273     BYTE weightList[HUFv06_MAX_SYMBOL_VALUE + 1];
2274     sortedSymbol_t sortedSymbol[HUFv06_MAX_SYMBOL_VALUE + 1];
2275     U32 rankStats[HUFv06_ABSOLUTEMAX_TABLELOG + 1] = { 0 };
2276     U32 rankStart0[HUFv06_ABSOLUTEMAX_TABLELOG + 2] = { 0 };
2277     U32* const rankStart = rankStart0+1;
2278     rankVal_t rankVal;
2279     U32 tableLog, maxW, sizeOfSort, nbSymbols;
2280     const U32 memLog = DTable[0];
2281     size_t iSize;
2282     void* dtPtr = DTable;
2283     HUFv06_DEltX4* const dt = ((HUFv06_DEltX4*)dtPtr) + 1;
2284
2285     HUFv06_STATIC_ASSERT(sizeof(HUFv06_DEltX4) == sizeof(U32));   /* if compilation fails here, assertion is false */
2286     if (memLog > HUFv06_ABSOLUTEMAX_TABLELOG) return ERROR(tableLog_tooLarge);
2287     /* memset(weightList, 0, sizeof(weightList)); */   /* is not necessary, even though some analyzer complain ... */
2288
2289     iSize = HUFv06_readStats(weightList, HUFv06_MAX_SYMBOL_VALUE + 1, rankStats, &nbSymbols, &tableLog, src, srcSize);
2290     if (HUFv06_isError(iSize)) return iSize;
2291
2292     /* check result */
2293     if (tableLog > memLog) return ERROR(tableLog_tooLarge);   /* DTable can't fit code depth */
2294
2295     /* find maxWeight */
2296     for (maxW = tableLog; rankStats[maxW]==0; maxW--) {}  /* necessarily finds a solution before 0 */
2297
2298     /* Get start index of each weight */
2299     {   U32 w, nextRankStart = 0;
2300         for (w=1; w<maxW+1; w++) {
2301             U32 current = nextRankStart;
2302             nextRankStart += rankStats[w];
2303             rankStart[w] = current;
2304         }
2305         rankStart[0] = nextRankStart;   /* put all 0w symbols at the end of sorted list*/
2306         sizeOfSort = nextRankStart;
2307     }
2308
2309     /* sort symbols by weight */
2310     {   U32 s;
2311         for (s=0; s<nbSymbols; s++) {
2312             U32 const w = weightList[s];
2313             U32 const r = rankStart[w]++;
2314             sortedSymbol[r].symbol = (BYTE)s;
2315             sortedSymbol[r].weight = (BYTE)w;
2316         }
2317         rankStart[0] = 0;   /* forget 0w symbols; this is beginning of weight(1) */
2318     }
2319
2320     /* Build rankVal */
2321     {   U32* const rankVal0 = rankVal[0];
2322         {   int const rescale = (memLog-tableLog) - 1;   /* tableLog <= memLog */
2323             U32 nextRankVal = 0;
2324             U32 w;
2325             for (w=1; w<maxW+1; w++) {
2326                 U32 current = nextRankVal;
2327                 nextRankVal += rankStats[w] << (w+rescale);
2328                 rankVal0[w] = current;
2329         }   }
2330         {   U32 const minBits = tableLog+1 - maxW;
2331             U32 consumed;
2332             for (consumed = minBits; consumed < memLog - minBits + 1; consumed++) {
2333                 U32* const rankValPtr = rankVal[consumed];
2334                 U32 w;
2335                 for (w = 1; w < maxW+1; w++) {
2336                     rankValPtr[w] = rankVal0[w] >> consumed;
2337     }   }   }   }
2338
2339     HUFv06_fillDTableX4(dt, memLog,
2340                    sortedSymbol, sizeOfSort,
2341                    rankStart0, rankVal, maxW,
2342                    tableLog+1);
2343
2344     return iSize;
2345 }
2346
2347
2348 static U32 HUFv06_decodeSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog)
2349 {
2350     const size_t val = BITv06_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2351     memcpy(op, dt+val, 2);
2352     BITv06_skipBits(DStream, dt[val].nbBits);
2353     return dt[val].length;
2354 }
2355
2356 static U32 HUFv06_decodeLastSymbolX4(void* op, BITv06_DStream_t* DStream, const HUFv06_DEltX4* dt, const U32 dtLog)
2357 {
2358     const size_t val = BITv06_lookBitsFast(DStream, dtLog);   /* note : dtLog >= 1 */
2359     memcpy(op, dt+val, 1);
2360     if (dt[val].length==1) BITv06_skipBits(DStream, dt[val].nbBits);
2361     else {
2362         if (DStream->bitsConsumed < (sizeof(DStream->bitContainer)*8)) {
2363             BITv06_skipBits(DStream, dt[val].nbBits);
2364             if (DStream->bitsConsumed > (sizeof(DStream->bitContainer)*8))
2365                 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 */
2366     }   }
2367     return 1;
2368 }
2369
2370
2371 #define HUFv06_DECODE_SYMBOLX4_0(ptr, DStreamPtr) \
2372     ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2373
2374 #define HUFv06_DECODE_SYMBOLX4_1(ptr, DStreamPtr) \
2375     if (MEM_64bits() || (HUFv06_MAX_TABLELOG<=12)) \
2376         ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2377
2378 #define HUFv06_DECODE_SYMBOLX4_2(ptr, DStreamPtr) \
2379     if (MEM_64bits()) \
2380         ptr += HUFv06_decodeSymbolX4(ptr, DStreamPtr, dt, dtLog)
2381
2382 static inline size_t HUFv06_decodeStreamX4(BYTE* p, BITv06_DStream_t* bitDPtr, BYTE* const pEnd, const HUFv06_DEltX4* const dt, const U32 dtLog)
2383 {
2384     BYTE* const pStart = p;
2385
2386     /* up to 8 symbols at a time */
2387     while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p < pEnd-7)) {
2388         HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr);
2389         HUFv06_DECODE_SYMBOLX4_1(p, bitDPtr);
2390         HUFv06_DECODE_SYMBOLX4_2(p, bitDPtr);
2391         HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr);
2392     }
2393
2394     /* closer to the end */
2395     while ((BITv06_reloadDStream(bitDPtr) == BITv06_DStream_unfinished) && (p <= pEnd-2))
2396         HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr);
2397
2398     while (p <= pEnd-2)
2399         HUFv06_DECODE_SYMBOLX4_0(p, bitDPtr);   /* no need to reload : reached the end of DStream */
2400
2401     if (p < pEnd)
2402         p += HUFv06_decodeLastSymbolX4(p, bitDPtr, dt, dtLog);
2403
2404     return p-pStart;
2405 }
2406
2407
2408 size_t HUFv06_decompress1X4_usingDTable(
2409           void* dst,  size_t dstSize,
2410     const void* cSrc, size_t cSrcSize,
2411     const U32* DTable)
2412 {
2413     const BYTE* const istart = (const BYTE*) cSrc;
2414     BYTE* const ostart = (BYTE*) dst;
2415     BYTE* const oend = ostart + dstSize;
2416
2417     const U32 dtLog = DTable[0];
2418     const void* const dtPtr = DTable;
2419     const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1;
2420
2421     /* Init */
2422     BITv06_DStream_t bitD;
2423     { size_t const errorCode = BITv06_initDStream(&bitD, istart, cSrcSize);
2424       if (HUFv06_isError(errorCode)) return errorCode; }
2425
2426     /* decode */
2427     HUFv06_decodeStreamX4(ostart, &bitD, oend, dt, dtLog);
2428
2429     /* check */
2430     if (!BITv06_endOfDStream(&bitD)) return ERROR(corruption_detected);
2431
2432     /* decoded size */
2433     return dstSize;
2434 }
2435
2436 size_t HUFv06_decompress1X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2437 {
2438     HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG);
2439     const BYTE* ip = (const BYTE*) cSrc;
2440
2441     size_t const hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize);
2442     if (HUFv06_isError(hSize)) return hSize;
2443     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2444     ip += hSize;
2445     cSrcSize -= hSize;
2446
2447     return HUFv06_decompress1X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2448 }
2449
2450 size_t HUFv06_decompress4X4_usingDTable(
2451           void* dst,  size_t dstSize,
2452     const void* cSrc, size_t cSrcSize,
2453     const U32* DTable)
2454 {
2455     if (cSrcSize < 10) return ERROR(corruption_detected);   /* strict minimum : jump table + 1 byte per stream */
2456
2457     {   const BYTE* const istart = (const BYTE*) cSrc;
2458         BYTE* const ostart = (BYTE*) dst;
2459         BYTE* const oend = ostart + dstSize;
2460         const void* const dtPtr = DTable;
2461         const HUFv06_DEltX4* const dt = ((const HUFv06_DEltX4*)dtPtr) +1;
2462         const U32 dtLog = DTable[0];
2463         size_t errorCode;
2464
2465         /* Init */
2466         BITv06_DStream_t bitD1;
2467         BITv06_DStream_t bitD2;
2468         BITv06_DStream_t bitD3;
2469         BITv06_DStream_t bitD4;
2470         const size_t length1 = MEM_readLE16(istart);
2471         const size_t length2 = MEM_readLE16(istart+2);
2472         const size_t length3 = MEM_readLE16(istart+4);
2473         size_t length4;
2474         const BYTE* const istart1 = istart + 6;  /* jumpTable */
2475         const BYTE* const istart2 = istart1 + length1;
2476         const BYTE* const istart3 = istart2 + length2;
2477         const BYTE* const istart4 = istart3 + length3;
2478         const size_t segmentSize = (dstSize+3) / 4;
2479         BYTE* const opStart2 = ostart + segmentSize;
2480         BYTE* const opStart3 = opStart2 + segmentSize;
2481         BYTE* const opStart4 = opStart3 + segmentSize;
2482         BYTE* op1 = ostart;
2483         BYTE* op2 = opStart2;
2484         BYTE* op3 = opStart3;
2485         BYTE* op4 = opStart4;
2486         U32 endSignal;
2487
2488         length4 = cSrcSize - (length1 + length2 + length3 + 6);
2489         if (length4 > cSrcSize) return ERROR(corruption_detected);   /* overflow */
2490         errorCode = BITv06_initDStream(&bitD1, istart1, length1);
2491         if (HUFv06_isError(errorCode)) return errorCode;
2492         errorCode = BITv06_initDStream(&bitD2, istart2, length2);
2493         if (HUFv06_isError(errorCode)) return errorCode;
2494         errorCode = BITv06_initDStream(&bitD3, istart3, length3);
2495         if (HUFv06_isError(errorCode)) return errorCode;
2496         errorCode = BITv06_initDStream(&bitD4, istart4, length4);
2497         if (HUFv06_isError(errorCode)) return errorCode;
2498
2499         /* 16-32 symbols per loop (4-8 symbols per stream) */
2500         endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2501         for ( ; (endSignal==BITv06_DStream_unfinished) && (op4<(oend-7)) ; ) {
2502             HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1);
2503             HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2);
2504             HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3);
2505             HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4);
2506             HUFv06_DECODE_SYMBOLX4_1(op1, &bitD1);
2507             HUFv06_DECODE_SYMBOLX4_1(op2, &bitD2);
2508             HUFv06_DECODE_SYMBOLX4_1(op3, &bitD3);
2509             HUFv06_DECODE_SYMBOLX4_1(op4, &bitD4);
2510             HUFv06_DECODE_SYMBOLX4_2(op1, &bitD1);
2511             HUFv06_DECODE_SYMBOLX4_2(op2, &bitD2);
2512             HUFv06_DECODE_SYMBOLX4_2(op3, &bitD3);
2513             HUFv06_DECODE_SYMBOLX4_2(op4, &bitD4);
2514             HUFv06_DECODE_SYMBOLX4_0(op1, &bitD1);
2515             HUFv06_DECODE_SYMBOLX4_0(op2, &bitD2);
2516             HUFv06_DECODE_SYMBOLX4_0(op3, &bitD3);
2517             HUFv06_DECODE_SYMBOLX4_0(op4, &bitD4);
2518
2519             endSignal = BITv06_reloadDStream(&bitD1) | BITv06_reloadDStream(&bitD2) | BITv06_reloadDStream(&bitD3) | BITv06_reloadDStream(&bitD4);
2520         }
2521
2522         /* check corruption */
2523         if (op1 > opStart2) return ERROR(corruption_detected);
2524         if (op2 > opStart3) return ERROR(corruption_detected);
2525         if (op3 > opStart4) return ERROR(corruption_detected);
2526         /* note : op4 supposed already verified within main loop */
2527
2528         /* finish bitStreams one by one */
2529         HUFv06_decodeStreamX4(op1, &bitD1, opStart2, dt, dtLog);
2530         HUFv06_decodeStreamX4(op2, &bitD2, opStart3, dt, dtLog);
2531         HUFv06_decodeStreamX4(op3, &bitD3, opStart4, dt, dtLog);
2532         HUFv06_decodeStreamX4(op4, &bitD4, oend,     dt, dtLog);
2533
2534         /* check */
2535         endSignal = BITv06_endOfDStream(&bitD1) & BITv06_endOfDStream(&bitD2) & BITv06_endOfDStream(&bitD3) & BITv06_endOfDStream(&bitD4);
2536         if (!endSignal) return ERROR(corruption_detected);
2537
2538         /* decoded size */
2539         return dstSize;
2540     }
2541 }
2542
2543
2544 size_t HUFv06_decompress4X4 (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2545 {
2546     HUFv06_CREATE_STATIC_DTABLEX4(DTable, HUFv06_MAX_TABLELOG);
2547     const BYTE* ip = (const BYTE*) cSrc;
2548
2549     size_t hSize = HUFv06_readDTableX4 (DTable, cSrc, cSrcSize);
2550     if (HUFv06_isError(hSize)) return hSize;
2551     if (hSize >= cSrcSize) return ERROR(srcSize_wrong);
2552     ip += hSize;
2553     cSrcSize -= hSize;
2554
2555     return HUFv06_decompress4X4_usingDTable (dst, dstSize, ip, cSrcSize, DTable);
2556 }
2557
2558
2559
2560
2561 /* ********************************/
2562 /* Generic decompression selector */
2563 /* ********************************/
2564
2565 typedef struct { U32 tableTime; U32 decode256Time; } algo_time_t;
2566 static const algo_time_t algoTime[16 /* Quantization */][3 /* single, double, quad */] =
2567 {
2568     /* single, double, quad */
2569     {{0,0}, {1,1}, {2,2}},  /* Q==0 : impossible */
2570     {{0,0}, {1,1}, {2,2}},  /* Q==1 : impossible */
2571     {{  38,130}, {1313, 74}, {2151, 38}},   /* Q == 2 : 12-18% */
2572     {{ 448,128}, {1353, 74}, {2238, 41}},   /* Q == 3 : 18-25% */
2573     {{ 556,128}, {1353, 74}, {2238, 47}},   /* Q == 4 : 25-32% */
2574     {{ 714,128}, {1418, 74}, {2436, 53}},   /* Q == 5 : 32-38% */
2575     {{ 883,128}, {1437, 74}, {2464, 61}},   /* Q == 6 : 38-44% */
2576     {{ 897,128}, {1515, 75}, {2622, 68}},   /* Q == 7 : 44-50% */
2577     {{ 926,128}, {1613, 75}, {2730, 75}},   /* Q == 8 : 50-56% */
2578     {{ 947,128}, {1729, 77}, {3359, 77}},   /* Q == 9 : 56-62% */
2579     {{1107,128}, {2083, 81}, {4006, 84}},   /* Q ==10 : 62-69% */
2580     {{1177,128}, {2379, 87}, {4785, 88}},   /* Q ==11 : 69-75% */
2581     {{1242,128}, {2415, 93}, {5155, 84}},   /* Q ==12 : 75-81% */
2582     {{1349,128}, {2644,106}, {5260,106}},   /* Q ==13 : 81-87% */
2583     {{1455,128}, {2422,124}, {4174,124}},   /* Q ==14 : 87-93% */
2584     {{ 722,128}, {1891,145}, {1936,146}},   /* Q ==15 : 93-99% */
2585 };
2586
2587 typedef size_t (*decompressionAlgo)(void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize);
2588
2589 size_t HUFv06_decompress (void* dst, size_t dstSize, const void* cSrc, size_t cSrcSize)
2590 {
2591     static const decompressionAlgo decompress[3] = { HUFv06_decompress4X2, HUFv06_decompress4X4, NULL };
2592     U32 Dtime[3];   /* decompression time estimation */
2593
2594     /* validation checks */
2595     if (dstSize == 0) return ERROR(dstSize_tooSmall);
2596     if (cSrcSize > dstSize) return ERROR(corruption_detected);   /* invalid */
2597     if (cSrcSize == dstSize) { memcpy(dst, cSrc, dstSize); return dstSize; }   /* not compressed */
2598     if (cSrcSize == 1) { memset(dst, *(const BYTE*)cSrc, dstSize); return dstSize; }   /* RLE */
2599
2600     /* decoder timing evaluation */
2601     {   U32 const Q = (U32)(cSrcSize * 16 / dstSize);   /* Q < 16 since dstSize > cSrcSize */
2602         U32 const D256 = (U32)(dstSize >> 8);
2603         U32 n; for (n=0; n<3; n++)
2604             Dtime[n] = algoTime[Q][n].tableTime + (algoTime[Q][n].decode256Time * D256);
2605     }
2606
2607     Dtime[1] += Dtime[1] >> 4; Dtime[2] += Dtime[2] >> 3; /* advantage to algorithms using less memory, for cache eviction */
2608
2609     {   U32 algoNb = 0;
2610         if (Dtime[1] < Dtime[0]) algoNb = 1;
2611         /* if (Dtime[2] < Dtime[algoNb]) algoNb = 2; */   /* current speed of HUFv06_decompress4X6 is not good */
2612         return decompress[algoNb](dst, dstSize, cSrc, cSrcSize);
2613     }
2614
2615     /* return HUFv06_decompress4X2(dst, dstSize, cSrc, cSrcSize); */   /* multi-streams single-symbol decoding */
2616     /* return HUFv06_decompress4X4(dst, dstSize, cSrc, cSrcSize); */   /* multi-streams double-symbols decoding */
2617     /* return HUFv06_decompress4X6(dst, dstSize, cSrc, cSrcSize); */   /* multi-streams quad-symbols decoding */
2618 }
2619 /*
2620     Common functions of Zstd compression library
2621     Copyright (C) 2015-2016, Yann Collet.
2622
2623     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2624
2625     Redistribution and use in source and binary forms, with or without
2626     modification, are permitted provided that the following conditions are
2627     met:
2628     * Redistributions of source code must retain the above copyright
2629     notice, this list of conditions and the following disclaimer.
2630     * Redistributions in binary form must reproduce the above
2631     copyright notice, this list of conditions and the following disclaimer
2632     in the documentation and/or other materials provided with the
2633     distribution.
2634     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2635     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2636     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2637     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2638     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2639     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2640     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2641     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2642     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2643     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2644     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2645
2646     You can contact the author at :
2647     - zstd homepage : https://facebook.github.io/zstd/
2648 */
2649
2650
2651 /*-****************************************
2652 *  Version
2653 ******************************************/
2654
2655 /*-****************************************
2656 *  ZSTD Error Management
2657 ******************************************/
2658 /*! ZSTDv06_isError() :
2659 *   tells if a return value is an error code */
2660 unsigned ZSTDv06_isError(size_t code) { return ERR_isError(code); }
2661
2662 /*! ZSTDv06_getErrorName() :
2663 *   provides error code string from function result (useful for debugging) */
2664 const char* ZSTDv06_getErrorName(size_t code) { return ERR_getErrorName(code); }
2665
2666
2667 /* **************************************************************
2668 *  ZBUFF Error Management
2669 ****************************************************************/
2670 unsigned ZBUFFv06_isError(size_t errorCode) { return ERR_isError(errorCode); }
2671
2672 const char* ZBUFFv06_getErrorName(size_t errorCode) { return ERR_getErrorName(errorCode); }
2673 /*
2674     zstd - standard compression library
2675     Copyright (C) 2014-2016, Yann Collet.
2676
2677     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
2678
2679     Redistribution and use in source and binary forms, with or without
2680     modification, are permitted provided that the following conditions are
2681     met:
2682     * Redistributions of source code must retain the above copyright
2683     notice, this list of conditions and the following disclaimer.
2684     * Redistributions in binary form must reproduce the above
2685     copyright notice, this list of conditions and the following disclaimer
2686     in the documentation and/or other materials provided with the
2687     distribution.
2688     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
2689     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
2690     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
2691     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
2692     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
2693     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
2694     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
2695     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
2696     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
2697     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
2698     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
2699
2700     You can contact the author at :
2701     - zstd homepage : https://facebook.github.io/zstd
2702 */
2703
2704 /* ***************************************************************
2705 *  Tuning parameters
2706 *****************************************************************/
2707 /*!
2708  * HEAPMODE :
2709  * Select how default decompression function ZSTDv06_decompress() will allocate memory,
2710  * in memory stack (0), or in memory heap (1, requires malloc())
2711  */
2712 #ifndef ZSTDv06_HEAPMODE
2713 #  define ZSTDv06_HEAPMODE 1
2714 #endif
2715
2716
2717
2718 /*-*******************************************************
2719 *  Compiler specifics
2720 *********************************************************/
2721 #ifdef _MSC_VER    /* Visual Studio */
2722 #  include <intrin.h>                    /* For Visual 2005 */
2723 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
2724 #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
2725 #endif
2726
2727
2728 /*-*************************************
2729 *  Macros
2730 ***************************************/
2731 #define ZSTDv06_isError ERR_isError   /* for inlining */
2732 #define FSEv06_isError  ERR_isError
2733 #define HUFv06_isError  ERR_isError
2734
2735
2736 /*_*******************************************************
2737 *  Memory operations
2738 **********************************************************/
2739 static void ZSTDv06_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
2740
2741
2742 /*-*************************************************************
2743 *   Context management
2744 ***************************************************************/
2745 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
2746                ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock } ZSTDv06_dStage;
2747
2748 struct ZSTDv06_DCtx_s
2749 {
2750     FSEv06_DTable LLTable[FSEv06_DTABLE_SIZE_U32(LLFSELog)];
2751     FSEv06_DTable OffTable[FSEv06_DTABLE_SIZE_U32(OffFSELog)];
2752     FSEv06_DTable MLTable[FSEv06_DTABLE_SIZE_U32(MLFSELog)];
2753     unsigned   hufTableX4[HUFv06_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)];
2754     const void* previousDstEnd;
2755     const void* base;
2756     const void* vBase;
2757     const void* dictEnd;
2758     size_t expected;
2759     size_t headerSize;
2760     ZSTDv06_frameParams fParams;
2761     blockType_t bType;   /* used in ZSTDv06_decompressContinue(), to transfer blockType between header decoding and block decoding stages */
2762     ZSTDv06_dStage stage;
2763     U32 flagRepeatTable;
2764     const BYTE* litPtr;
2765     size_t litSize;
2766     BYTE litBuffer[ZSTDv06_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];
2767     BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX];
2768 };  /* typedef'd to ZSTDv06_DCtx within "zstd_static.h" */
2769
2770 size_t ZSTDv06_sizeofDCtx (void); /* Hidden declaration */
2771 size_t ZSTDv06_sizeofDCtx (void) { return sizeof(ZSTDv06_DCtx); }
2772
2773 size_t ZSTDv06_decompressBegin(ZSTDv06_DCtx* dctx)
2774 {
2775     dctx->expected = ZSTDv06_frameHeaderSize_min;
2776     dctx->stage = ZSTDds_getFrameHeaderSize;
2777     dctx->previousDstEnd = NULL;
2778     dctx->base = NULL;
2779     dctx->vBase = NULL;
2780     dctx->dictEnd = NULL;
2781     dctx->hufTableX4[0] = ZSTD_HUFFDTABLE_CAPACITY_LOG;
2782     dctx->flagRepeatTable = 0;
2783     return 0;
2784 }
2785
2786 ZSTDv06_DCtx* ZSTDv06_createDCtx(void)
2787 {
2788     ZSTDv06_DCtx* dctx = (ZSTDv06_DCtx*)malloc(sizeof(ZSTDv06_DCtx));
2789     if (dctx==NULL) return NULL;
2790     ZSTDv06_decompressBegin(dctx);
2791     return dctx;
2792 }
2793
2794 size_t ZSTDv06_freeDCtx(ZSTDv06_DCtx* dctx)
2795 {
2796     free(dctx);
2797     return 0;   /* reserved as a potential error code in the future */
2798 }
2799
2800 void ZSTDv06_copyDCtx(ZSTDv06_DCtx* dstDCtx, const ZSTDv06_DCtx* srcDCtx)
2801 {
2802     memcpy(dstDCtx, srcDCtx,
2803            sizeof(ZSTDv06_DCtx) - (ZSTDv06_BLOCKSIZE_MAX+WILDCOPY_OVERLENGTH + ZSTDv06_frameHeaderSize_max));  /* no need to copy workspace */
2804 }
2805
2806
2807 /*-*************************************************************
2808 *   Decompression section
2809 ***************************************************************/
2810
2811 /* Frame format description
2812    Frame Header -  [ Block Header - Block ] - Frame End
2813    1) Frame Header
2814       - 4 bytes - Magic Number : ZSTDv06_MAGICNUMBER (defined within zstd_static.h)
2815       - 1 byte  - Frame Descriptor
2816    2) Block Header
2817       - 3 bytes, starting with a 2-bits descriptor
2818                  Uncompressed, Compressed, Frame End, unused
2819    3) Block
2820       See Block Format Description
2821    4) Frame End
2822       - 3 bytes, compatible with Block Header
2823 */
2824
2825
2826 /* Frame descriptor
2827
2828    1 byte, using :
2829    bit 0-3 : windowLog - ZSTDv06_WINDOWLOG_ABSOLUTEMIN   (see zstd_internal.h)
2830    bit 4   : minmatch 4(0) or 3(1)
2831    bit 5   : reserved (must be zero)
2832    bit 6-7 : Frame content size : unknown, 1 byte, 2 bytes, 8 bytes
2833
2834    Optional : content size (0, 1, 2 or 8 bytes)
2835    0 : unknown
2836    1 : 0-255 bytes
2837    2 : 256 - 65535+256
2838    8 : up to 16 exa
2839 */
2840
2841
2842 /* Compressed Block, format description
2843
2844    Block = Literal Section - Sequences Section
2845    Prerequisite : size of (compressed) block, maximum size of regenerated data
2846
2847    1) Literal Section
2848
2849    1.1) Header : 1-5 bytes
2850         flags: 2 bits
2851             00 compressed by Huff0
2852             01 unused
2853             10 is Raw (uncompressed)
2854             11 is Rle
2855             Note : using 01 => Huff0 with precomputed table ?
2856             Note : delta map ? => compressed ?
2857
2858    1.1.1) Huff0-compressed literal block : 3-5 bytes
2859             srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2860             srcSize < 1 KB => 3 bytes (2-2-10-10)
2861             srcSize < 16KB => 4 bytes (2-2-14-14)
2862             else           => 5 bytes (2-2-18-18)
2863             big endian convention
2864
2865    1.1.2) Raw (uncompressed) literal block header : 1-3 bytes
2866         size :  5 bits: (IS_RAW<<6) + (0<<4) + size
2867                12 bits: (IS_RAW<<6) + (2<<4) + (size>>8)
2868                         size&255
2869                20 bits: (IS_RAW<<6) + (3<<4) + (size>>16)
2870                         size>>8&255
2871                         size&255
2872
2873    1.1.3) Rle (repeated single byte) literal block header : 1-3 bytes
2874         size :  5 bits: (IS_RLE<<6) + (0<<4) + size
2875                12 bits: (IS_RLE<<6) + (2<<4) + (size>>8)
2876                         size&255
2877                20 bits: (IS_RLE<<6) + (3<<4) + (size>>16)
2878                         size>>8&255
2879                         size&255
2880
2881    1.1.4) Huff0-compressed literal block, using precomputed CTables : 3-5 bytes
2882             srcSize < 1 KB => 3 bytes (2-2-10-10) => single stream
2883             srcSize < 1 KB => 3 bytes (2-2-10-10)
2884             srcSize < 16KB => 4 bytes (2-2-14-14)
2885             else           => 5 bytes (2-2-18-18)
2886             big endian convention
2887
2888         1- CTable available (stored into workspace ?)
2889         2- Small input (fast heuristic ? Full comparison ? depend on clevel ?)
2890
2891
2892    1.2) Literal block content
2893
2894    1.2.1) Huff0 block, using sizes from header
2895         See Huff0 format
2896
2897    1.2.2) Huff0 block, using prepared table
2898
2899    1.2.3) Raw content
2900
2901    1.2.4) single byte
2902
2903
2904    2) Sequences section
2905       TO DO
2906 */
2907
2908 /** ZSTDv06_frameHeaderSize() :
2909 *   srcSize must be >= ZSTDv06_frameHeaderSize_min.
2910 *   @return : size of the Frame Header */
2911 static size_t ZSTDv06_frameHeaderSize(const void* src, size_t srcSize)
2912 {
2913     if (srcSize < ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong);
2914     { U32 const fcsId = (((const BYTE*)src)[4]) >> 6;
2915       return ZSTDv06_frameHeaderSize_min + ZSTDv06_fcs_fieldSize[fcsId]; }
2916 }
2917
2918
2919 /** ZSTDv06_getFrameParams() :
2920 *   decode Frame Header, or provide expected `srcSize`.
2921 *   @return : 0, `fparamsPtr` is correctly filled,
2922 *            >0, `srcSize` is too small, result is expected `srcSize`,
2923 *             or an error code, which can be tested using ZSTDv06_isError() */
2924 size_t ZSTDv06_getFrameParams(ZSTDv06_frameParams* fparamsPtr, const void* src, size_t srcSize)
2925 {
2926     const BYTE* ip = (const BYTE*)src;
2927
2928     if (srcSize < ZSTDv06_frameHeaderSize_min) return ZSTDv06_frameHeaderSize_min;
2929     if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) return ERROR(prefix_unknown);
2930
2931     /* ensure there is enough `srcSize` to fully read/decode frame header */
2932     { size_t const fhsize = ZSTDv06_frameHeaderSize(src, srcSize);
2933       if (srcSize < fhsize) return fhsize; }
2934
2935     memset(fparamsPtr, 0, sizeof(*fparamsPtr));
2936     {   BYTE const frameDesc = ip[4];
2937         fparamsPtr->windowLog = (frameDesc & 0xF) + ZSTDv06_WINDOWLOG_ABSOLUTEMIN;
2938         if ((frameDesc & 0x20) != 0) return ERROR(frameParameter_unsupported);   /* reserved 1 bit */
2939         switch(frameDesc >> 6)  /* fcsId */
2940         {
2941             default:   /* impossible */
2942             case 0 : fparamsPtr->frameContentSize = 0; break;
2943             case 1 : fparamsPtr->frameContentSize = ip[5]; break;
2944             case 2 : fparamsPtr->frameContentSize = MEM_readLE16(ip+5)+256; break;
2945             case 3 : fparamsPtr->frameContentSize = MEM_readLE64(ip+5); break;
2946     }   }
2947     return 0;
2948 }
2949
2950
2951 /** ZSTDv06_decodeFrameHeader() :
2952 *   `srcSize` must be the size provided by ZSTDv06_frameHeaderSize().
2953 *   @return : 0 if success, or an error code, which can be tested using ZSTDv06_isError() */
2954 static size_t ZSTDv06_decodeFrameHeader(ZSTDv06_DCtx* zc, const void* src, size_t srcSize)
2955 {
2956     size_t const result = ZSTDv06_getFrameParams(&(zc->fParams), src, srcSize);
2957     if ((MEM_32bits()) && (zc->fParams.windowLog > 25)) return ERROR(frameParameter_unsupported);
2958     return result;
2959 }
2960
2961
2962 typedef struct
2963 {
2964     blockType_t blockType;
2965     U32 origSize;
2966 } blockProperties_t;
2967
2968 /*! ZSTDv06_getcBlockSize() :
2969 *   Provides the size of compressed block from block header `src` */
2970 static size_t ZSTDv06_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
2971 {
2972     const BYTE* const in = (const BYTE*)src;
2973     U32 cSize;
2974
2975     if (srcSize < ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
2976
2977     bpPtr->blockType = (blockType_t)((*in) >> 6);
2978     cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
2979     bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
2980
2981     if (bpPtr->blockType == bt_end) return 0;
2982     if (bpPtr->blockType == bt_rle) return 1;
2983     return cSize;
2984 }
2985
2986
2987 static size_t ZSTDv06_copyRawBlock(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2988 {
2989     if (dst==NULL) return ERROR(dstSize_tooSmall);
2990     if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
2991     memcpy(dst, src, srcSize);
2992     return srcSize;
2993 }
2994
2995
2996 /*! ZSTDv06_decodeLiteralsBlock() :
2997     @return : nb of bytes read from src (< srcSize ) */
2998 static size_t ZSTDv06_decodeLiteralsBlock(ZSTDv06_DCtx* dctx,
2999                           const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
3000 {
3001     const BYTE* const istart = (const BYTE*) src;
3002
3003     /* any compressed block with literals segment must be at least this size */
3004     if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
3005
3006     switch(istart[0]>> 6)
3007     {
3008     case IS_HUF:
3009         {   size_t litSize, litCSize, singleStream=0;
3010             U32 lhSize = ((istart[0]) >> 4) & 3;
3011             if (srcSize < 5) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for lhSize, + cSize (+nbSeq) */
3012             switch(lhSize)
3013             {
3014             case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3015                 /* 2 - 2 - 10 - 10 */
3016                 lhSize=3;
3017                 singleStream = istart[0] & 16;
3018                 litSize  = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3019                 litCSize = ((istart[1] &  3) << 8) + istart[2];
3020                 break;
3021             case 2:
3022                 /* 2 - 2 - 14 - 14 */
3023                 lhSize=4;
3024                 litSize  = ((istart[0] & 15) << 10) + (istart[1] << 2) + (istart[2] >> 6);
3025                 litCSize = ((istart[2] & 63) <<  8) + istart[3];
3026                 break;
3027             case 3:
3028                 /* 2 - 2 - 18 - 18 */
3029                 lhSize=5;
3030                 litSize  = ((istart[0] & 15) << 14) + (istart[1] << 6) + (istart[2] >> 2);
3031                 litCSize = ((istart[2] &  3) << 16) + (istart[3] << 8) + istart[4];
3032                 break;
3033             }
3034             if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected);
3035             if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3036
3037             if (HUFv06_isError(singleStream ?
3038                             HUFv06_decompress1X2(dctx->litBuffer, litSize, istart+lhSize, litCSize) :
3039                             HUFv06_decompress   (dctx->litBuffer, litSize, istart+lhSize, litCSize) ))
3040                 return ERROR(corruption_detected);
3041
3042             dctx->litPtr = dctx->litBuffer;
3043             dctx->litSize = litSize;
3044             memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3045             return litCSize + lhSize;
3046         }
3047     case IS_PCH:
3048         {   size_t litSize, litCSize;
3049             U32 lhSize = ((istart[0]) >> 4) & 3;
3050             if (lhSize != 1)  /* only case supported for now : small litSize, single stream */
3051                 return ERROR(corruption_detected);
3052             if (!dctx->flagRepeatTable)
3053                 return ERROR(dictionary_corrupted);
3054
3055             /* 2 - 2 - 10 - 10 */
3056             lhSize=3;
3057             litSize  = ((istart[0] & 15) << 6) + (istart[1] >> 2);
3058             litCSize = ((istart[1] &  3) << 8) + istart[2];
3059             if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
3060
3061             {   size_t const errorCode = HUFv06_decompress1X4_usingDTable(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->hufTableX4);
3062                 if (HUFv06_isError(errorCode)) return ERROR(corruption_detected);
3063             }
3064             dctx->litPtr = dctx->litBuffer;
3065             dctx->litSize = litSize;
3066             memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3067             return litCSize + lhSize;
3068         }
3069     case IS_RAW:
3070         {   size_t litSize;
3071             U32 lhSize = ((istart[0]) >> 4) & 3;
3072             switch(lhSize)
3073             {
3074             case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3075                 lhSize=1;
3076                 litSize = istart[0] & 31;
3077                 break;
3078             case 2:
3079                 litSize = ((istart[0] & 15) << 8) + istart[1];
3080                 break;
3081             case 3:
3082                 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3083                 break;
3084             }
3085
3086             if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */
3087                 if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
3088                 memcpy(dctx->litBuffer, istart+lhSize, litSize);
3089                 dctx->litPtr = dctx->litBuffer;
3090                 dctx->litSize = litSize;
3091                 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
3092                 return lhSize+litSize;
3093             }
3094             /* direct reference into compressed stream */
3095             dctx->litPtr = istart+lhSize;
3096             dctx->litSize = litSize;
3097             return lhSize+litSize;
3098         }
3099     case IS_RLE:
3100         {   size_t litSize;
3101             U32 lhSize = ((istart[0]) >> 4) & 3;
3102             switch(lhSize)
3103             {
3104             case 0: case 1: default:   /* note : default is impossible, since lhSize into [0..3] */
3105                 lhSize = 1;
3106                 litSize = istart[0] & 31;
3107                 break;
3108             case 2:
3109                 litSize = ((istart[0] & 15) << 8) + istart[1];
3110                 break;
3111             case 3:
3112                 litSize = ((istart[0] & 15) << 16) + (istart[1] << 8) + istart[2];
3113                 if (srcSize<4) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
3114                 break;
3115             }
3116             if (litSize > ZSTDv06_BLOCKSIZE_MAX) return ERROR(corruption_detected);
3117             memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
3118             dctx->litPtr = dctx->litBuffer;
3119             dctx->litSize = litSize;
3120             return lhSize+1;
3121         }
3122     default:
3123         return ERROR(corruption_detected);   /* impossible */
3124     }
3125 }
3126
3127
3128 /*! ZSTDv06_buildSeqTable() :
3129     @return : nb bytes read from src,
3130               or an error code if it fails, testable with ZSTDv06_isError()
3131 */
3132 static size_t ZSTDv06_buildSeqTable(FSEv06_DTable* DTable, U32 type, U32 max, U32 maxLog,
3133                                  const void* src, size_t srcSize,
3134                                  const S16* defaultNorm, U32 defaultLog, U32 flagRepeatTable)
3135 {
3136     switch(type)
3137     {
3138     case FSEv06_ENCODING_RLE :
3139         if (!srcSize) return ERROR(srcSize_wrong);
3140         if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
3141         FSEv06_buildDTable_rle(DTable, *(const BYTE*)src);   /* if *src > max, data is corrupted */
3142         return 1;
3143     case FSEv06_ENCODING_RAW :
3144         FSEv06_buildDTable(DTable, defaultNorm, max, defaultLog);
3145         return 0;
3146     case FSEv06_ENCODING_STATIC:
3147         if (!flagRepeatTable) return ERROR(corruption_detected);
3148         return 0;
3149     default :   /* impossible */
3150     case FSEv06_ENCODING_DYNAMIC :
3151         {   U32 tableLog;
3152             S16 norm[MaxSeq+1];
3153             size_t const headerSize = FSEv06_readNCount(norm, &max, &tableLog, src, srcSize);
3154             if (FSEv06_isError(headerSize)) return ERROR(corruption_detected);
3155             if (tableLog > maxLog) return ERROR(corruption_detected);
3156             FSEv06_buildDTable(DTable, norm, max, tableLog);
3157             return headerSize;
3158     }   }
3159 }
3160
3161
3162 static size_t ZSTDv06_decodeSeqHeaders(int* nbSeqPtr,
3163                              FSEv06_DTable* DTableLL, FSEv06_DTable* DTableML, FSEv06_DTable* DTableOffb, U32 flagRepeatTable,
3164                              const void* src, size_t srcSize)
3165 {
3166     const BYTE* const istart = (const BYTE*)src;
3167     const BYTE* const iend = istart + srcSize;
3168     const BYTE* ip = istart;
3169
3170     /* check */
3171     if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
3172
3173     /* SeqHead */
3174     {   int nbSeq = *ip++;
3175         if (!nbSeq) { *nbSeqPtr=0; return 1; }
3176         if (nbSeq > 0x7F) {
3177             if (nbSeq == 0xFF) {
3178                 if (ip+2 > iend) return ERROR(srcSize_wrong);
3179                 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
3180             } else {
3181                 if (ip >= iend) return ERROR(srcSize_wrong);
3182                 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
3183             }
3184         }
3185         *nbSeqPtr = nbSeq;
3186     }
3187
3188     /* FSE table descriptors */
3189     if (ip + 4 > iend) return ERROR(srcSize_wrong); /* min : header byte + all 3 are "raw", hence no header, but at least xxLog bits per type */
3190     {   U32 const LLtype  = *ip >> 6;
3191         U32 const Offtype = (*ip >> 4) & 3;
3192         U32 const MLtype  = (*ip >> 2) & 3;
3193         ip++;
3194
3195         /* Build DTables */
3196         {   size_t const bhSize = ZSTDv06_buildSeqTable(DTableLL, LLtype, MaxLL, LLFSELog, ip, iend-ip, LL_defaultNorm, LL_defaultNormLog, flagRepeatTable);
3197             if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3198             ip += bhSize;
3199         }
3200         {   size_t const bhSize = ZSTDv06_buildSeqTable(DTableOffb, Offtype, MaxOff, OffFSELog, ip, iend-ip, OF_defaultNorm, OF_defaultNormLog, flagRepeatTable);
3201             if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3202             ip += bhSize;
3203         }
3204         {   size_t const bhSize = ZSTDv06_buildSeqTable(DTableML, MLtype, MaxML, MLFSELog, ip, iend-ip, ML_defaultNorm, ML_defaultNormLog, flagRepeatTable);
3205             if (ZSTDv06_isError(bhSize)) return ERROR(corruption_detected);
3206             ip += bhSize;
3207     }   }
3208
3209     return ip-istart;
3210 }
3211
3212
3213 typedef struct {
3214     size_t litLength;
3215     size_t matchLength;
3216     size_t offset;
3217 } seq_t;
3218
3219 typedef struct {
3220     BITv06_DStream_t DStream;
3221     FSEv06_DState_t stateLL;
3222     FSEv06_DState_t stateOffb;
3223     FSEv06_DState_t stateML;
3224     size_t prevOffset[ZSTDv06_REP_INIT];
3225 } seqState_t;
3226
3227
3228
3229 static void ZSTDv06_decodeSequence(seq_t* seq, seqState_t* seqState)
3230 {
3231     /* Literal length */
3232     U32 const llCode = FSEv06_peekSymbol(&(seqState->stateLL));
3233     U32 const mlCode = FSEv06_peekSymbol(&(seqState->stateML));
3234     U32 const ofCode = FSEv06_peekSymbol(&(seqState->stateOffb));   /* <= maxOff, by table construction */
3235
3236     U32 const llBits = LL_bits[llCode];
3237     U32 const mlBits = ML_bits[mlCode];
3238     U32 const ofBits = ofCode;
3239     U32 const totalBits = llBits+mlBits+ofBits;
3240
3241     static const U32 LL_base[MaxLL+1] = {
3242                              0,  1,  2,  3,  4,  5,  6,  7,  8,  9,   10,    11,    12,    13,    14,     15,
3243                             16, 18, 20, 22, 24, 28, 32, 40, 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
3244                             0x2000, 0x4000, 0x8000, 0x10000 };
3245
3246     static const U32 ML_base[MaxML+1] = {
3247                              0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,   11,    12,    13,    14,    15,
3248                             16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,   27,    28,    29,    30,    31,
3249                             32, 34, 36, 38, 40, 44, 48, 56, 64, 80, 96, 0x80, 0x100, 0x200, 0x400, 0x800,
3250                             0x1000, 0x2000, 0x4000, 0x8000, 0x10000 };
3251
3252     static const U32 OF_base[MaxOff+1] = {
3253                  0,        1,       3,       7,     0xF,     0x1F,     0x3F,     0x7F,
3254                  0xFF,   0x1FF,   0x3FF,   0x7FF,   0xFFF,   0x1FFF,   0x3FFF,   0x7FFF,
3255                  0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF,
3256                  0xFFFFFF, 0x1FFFFFF, 0x3FFFFFF, /*fake*/ 1, 1 };
3257
3258     /* sequence */
3259     {   size_t offset;
3260         if (!ofCode)
3261             offset = 0;
3262         else {
3263             offset = OF_base[ofCode] + BITv06_readBits(&(seqState->DStream), ofBits);   /* <=  26 bits */
3264             if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream));
3265         }
3266
3267         if (offset < ZSTDv06_REP_NUM) {
3268             if (llCode == 0 && offset <= 1) offset = 1-offset;
3269
3270             if (offset != 0) {
3271                 size_t temp = seqState->prevOffset[offset];
3272                 if (offset != 1) {
3273                     seqState->prevOffset[2] = seqState->prevOffset[1];
3274                 }
3275                 seqState->prevOffset[1] = seqState->prevOffset[0];
3276                 seqState->prevOffset[0] = offset = temp;
3277
3278             } else {
3279                 offset = seqState->prevOffset[0];
3280             }
3281         } else {
3282             offset -= ZSTDv06_REP_MOVE;
3283             seqState->prevOffset[2] = seqState->prevOffset[1];
3284             seqState->prevOffset[1] = seqState->prevOffset[0];
3285             seqState->prevOffset[0] = offset;
3286         }
3287         seq->offset = offset;
3288     }
3289
3290     seq->matchLength = ML_base[mlCode] + MINMATCH + ((mlCode>31) ? BITv06_readBits(&(seqState->DStream), mlBits) : 0);   /* <=  16 bits */
3291     if (MEM_32bits() && (mlBits+llBits>24)) BITv06_reloadDStream(&(seqState->DStream));
3292
3293     seq->litLength = LL_base[llCode] + ((llCode>15) ? BITv06_readBits(&(seqState->DStream), llBits) : 0);   /* <=  16 bits */
3294     if (MEM_32bits() ||
3295        (totalBits > 64 - 7 - (LLFSELog+MLFSELog+OffFSELog)) ) BITv06_reloadDStream(&(seqState->DStream));
3296
3297     /* ANS state update */
3298     FSEv06_updateState(&(seqState->stateLL), &(seqState->DStream));   /* <=  9 bits */
3299     FSEv06_updateState(&(seqState->stateML), &(seqState->DStream));   /* <=  9 bits */
3300     if (MEM_32bits()) BITv06_reloadDStream(&(seqState->DStream));     /* <= 18 bits */
3301     FSEv06_updateState(&(seqState->stateOffb), &(seqState->DStream)); /* <=  8 bits */
3302 }
3303
3304
3305 static size_t ZSTDv06_execSequence(BYTE* op,
3306                                 BYTE* const oend, seq_t sequence,
3307                                 const BYTE** litPtr, const BYTE* const litLimit,
3308                                 const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
3309 {
3310     BYTE* const oLitEnd = op + sequence.litLength;
3311     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
3312     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
3313     BYTE* const oend_8 = oend-8;
3314     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
3315     const BYTE* match = oLitEnd - sequence.offset;
3316
3317     /* checks */
3318     size_t const seqLength = sequence.litLength + sequence.matchLength;
3319
3320     if (seqLength > (size_t)(oend - op)) return ERROR(dstSize_tooSmall);
3321     if (sequence.litLength > (size_t)(litLimit - *litPtr)) return ERROR(corruption_detected);
3322     /* Now we know there are no overflow in literal nor match lengths, can use pointer checks */
3323     if (oLitEnd > oend_8) return ERROR(dstSize_tooSmall);
3324
3325     if (oMatchEnd > oend) return ERROR(dstSize_tooSmall);   /* overwrite beyond dst buffer */
3326     if (iLitEnd > litLimit) return ERROR(corruption_detected);   /* overRead beyond lit buffer */
3327
3328     /* copy Literals */
3329     ZSTDv06_wildcopy(op, *litPtr, (ptrdiff_t)sequence.litLength);   /* note : oLitEnd <= oend-8 : no risk of overwrite beyond oend */
3330     op = oLitEnd;
3331     *litPtr = iLitEnd;   /* update for next sequence */
3332
3333     /* copy Match */
3334     if (sequence.offset > (size_t)(oLitEnd - base)) {
3335         /* offset beyond prefix */
3336         if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
3337         match = dictEnd - (base-match);
3338         if (match + sequence.matchLength <= dictEnd) {
3339             memmove(oLitEnd, match, sequence.matchLength);
3340             return sequenceLength;
3341         }
3342         /* span extDict & currentPrefixSegment */
3343         {   size_t const length1 = dictEnd - match;
3344             memmove(oLitEnd, match, length1);
3345             op = oLitEnd + length1;
3346             sequence.matchLength -= length1;
3347             match = base;
3348             if (op > oend_8 || sequence.matchLength < MINMATCH) {
3349               while (op < oMatchEnd) *op++ = *match++;
3350               return sequenceLength;
3351             }
3352     }   }
3353     /* Requirement: op <= oend_8 */
3354
3355     /* match within prefix */
3356     if (sequence.offset < 8) {
3357         /* close range match, overlap */
3358         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
3359         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
3360         int const sub2 = dec64table[sequence.offset];
3361         op[0] = match[0];
3362         op[1] = match[1];
3363         op[2] = match[2];
3364         op[3] = match[3];
3365         match += dec32table[sequence.offset];
3366         ZSTDv06_copy4(op+4, match);
3367         match -= sub2;
3368     } else {
3369         ZSTDv06_copy8(op, match);
3370     }
3371     op += 8; match += 8;
3372
3373     if (oMatchEnd > oend-(16-MINMATCH)) {
3374         if (op < oend_8) {
3375             ZSTDv06_wildcopy(op, match, oend_8 - op);
3376             match += oend_8 - op;
3377             op = oend_8;
3378         }
3379         while (op < oMatchEnd) *op++ = *match++;
3380     } else {
3381         ZSTDv06_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
3382     }
3383     return sequenceLength;
3384 }
3385
3386
3387 static size_t ZSTDv06_decompressSequences(
3388                                ZSTDv06_DCtx* dctx,
3389                                void* dst, size_t maxDstSize,
3390                          const void* seqStart, size_t seqSize)
3391 {
3392     const BYTE* ip = (const BYTE*)seqStart;
3393     const BYTE* const iend = ip + seqSize;
3394     BYTE* const ostart = (BYTE*)dst;
3395     BYTE* const oend = ostart + maxDstSize;
3396     BYTE* op = ostart;
3397     const BYTE* litPtr = dctx->litPtr;
3398     const BYTE* const litEnd = litPtr + dctx->litSize;
3399     FSEv06_DTable* DTableLL = dctx->LLTable;
3400     FSEv06_DTable* DTableML = dctx->MLTable;
3401     FSEv06_DTable* DTableOffb = dctx->OffTable;
3402     const BYTE* const base = (const BYTE*) (dctx->base);
3403     const BYTE* const vBase = (const BYTE*) (dctx->vBase);
3404     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
3405     int nbSeq;
3406
3407     /* Build Decoding Tables */
3408     {   size_t const seqHSize = ZSTDv06_decodeSeqHeaders(&nbSeq, DTableLL, DTableML, DTableOffb, dctx->flagRepeatTable, ip, seqSize);
3409         if (ZSTDv06_isError(seqHSize)) return seqHSize;
3410         ip += seqHSize;
3411         dctx->flagRepeatTable = 0;
3412     }
3413
3414     /* Regen sequences */
3415     if (nbSeq) {
3416         seq_t sequence;
3417         seqState_t seqState;
3418
3419         memset(&sequence, 0, sizeof(sequence));
3420         sequence.offset = REPCODE_STARTVALUE;
3421         { U32 i; for (i=0; i<ZSTDv06_REP_INIT; i++) seqState.prevOffset[i] = REPCODE_STARTVALUE; }
3422         { size_t const errorCode = BITv06_initDStream(&(seqState.DStream), ip, iend-ip);
3423           if (ERR_isError(errorCode)) return ERROR(corruption_detected); }
3424         FSEv06_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
3425         FSEv06_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
3426         FSEv06_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
3427
3428         for ( ; (BITv06_reloadDStream(&(seqState.DStream)) <= BITv06_DStream_completed) && nbSeq ; ) {
3429             nbSeq--;
3430             ZSTDv06_decodeSequence(&sequence, &seqState);
3431
3432 #if 0  /* debug */
3433             static BYTE* start = NULL;
3434             if (start==NULL) start = op;
3435             size_t pos = (size_t)(op-start);
3436             if ((pos >= 5810037) && (pos < 5810400))
3437                 printf("Dpos %6u :%5u literals & match %3u bytes at distance %6u \n",
3438                        pos, (U32)sequence.litLength, (U32)sequence.matchLength, (U32)sequence.offset);
3439 #endif
3440
3441             {   size_t const oneSeqSize = ZSTDv06_execSequence(op, oend, sequence, &litPtr, litEnd, base, vBase, dictEnd);
3442                 if (ZSTDv06_isError(oneSeqSize)) return oneSeqSize;
3443                 op += oneSeqSize;
3444         }   }
3445
3446         /* check if reached exact end */
3447         if (nbSeq) return ERROR(corruption_detected);
3448     }
3449
3450     /* last literal segment */
3451     {   size_t const lastLLSize = litEnd - litPtr;
3452         if (litPtr > litEnd) return ERROR(corruption_detected);   /* too many literals already used */
3453         if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
3454         if (lastLLSize > 0) {
3455             memcpy(op, litPtr, lastLLSize);
3456             op += lastLLSize;
3457         }
3458     }
3459
3460     return op-ostart;
3461 }
3462
3463
3464 static void ZSTDv06_checkContinuity(ZSTDv06_DCtx* dctx, const void* dst)
3465 {
3466     if (dst != dctx->previousDstEnd) {   /* not contiguous */
3467         dctx->dictEnd = dctx->previousDstEnd;
3468         dctx->vBase = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3469         dctx->base = dst;
3470         dctx->previousDstEnd = dst;
3471     }
3472 }
3473
3474
3475 static size_t ZSTDv06_decompressBlock_internal(ZSTDv06_DCtx* dctx,
3476                             void* dst, size_t dstCapacity,
3477                       const void* src, size_t srcSize)
3478 {   /* blockType == blockCompressed */
3479     const BYTE* ip = (const BYTE*)src;
3480
3481     if (srcSize >= ZSTDv06_BLOCKSIZE_MAX) return ERROR(srcSize_wrong);
3482
3483     /* Decode literals sub-block */
3484     {   size_t const litCSize = ZSTDv06_decodeLiteralsBlock(dctx, src, srcSize);
3485         if (ZSTDv06_isError(litCSize)) return litCSize;
3486         ip += litCSize;
3487         srcSize -= litCSize;
3488     }
3489     return ZSTDv06_decompressSequences(dctx, dst, dstCapacity, ip, srcSize);
3490 }
3491
3492
3493 size_t ZSTDv06_decompressBlock(ZSTDv06_DCtx* dctx,
3494                             void* dst, size_t dstCapacity,
3495                       const void* src, size_t srcSize)
3496 {
3497     ZSTDv06_checkContinuity(dctx, dst);
3498     return ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3499 }
3500
3501
3502 /*! ZSTDv06_decompressFrame() :
3503 *   `dctx` must be properly initialized */
3504 static size_t ZSTDv06_decompressFrame(ZSTDv06_DCtx* dctx,
3505                                  void* dst, size_t dstCapacity,
3506                                  const void* src, size_t srcSize)
3507 {
3508     const BYTE* ip = (const BYTE*)src;
3509     const BYTE* const iend = ip + srcSize;
3510     BYTE* const ostart = (BYTE*)dst;
3511     BYTE* op = ostart;
3512     BYTE* const oend = ostart + dstCapacity;
3513     size_t remainingSize = srcSize;
3514     blockProperties_t blockProperties = { bt_compressed, 0 };
3515
3516     /* check */
3517     if (srcSize < ZSTDv06_frameHeaderSize_min+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
3518
3519     /* Frame Header */
3520     {   size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min);
3521         if (ZSTDv06_isError(frameHeaderSize)) return frameHeaderSize;
3522         if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) return ERROR(srcSize_wrong);
3523         if (ZSTDv06_decodeFrameHeader(dctx, src, frameHeaderSize)) return ERROR(corruption_detected);
3524         ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3525     }
3526
3527     /* Loop on each block */
3528     while (1) {
3529         size_t decodedSize=0;
3530         size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, iend-ip, &blockProperties);
3531         if (ZSTDv06_isError(cBlockSize)) return cBlockSize;
3532
3533         ip += ZSTDv06_blockHeaderSize;
3534         remainingSize -= ZSTDv06_blockHeaderSize;
3535         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
3536
3537         switch(blockProperties.blockType)
3538         {
3539         case bt_compressed:
3540             decodedSize = ZSTDv06_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize);
3541             break;
3542         case bt_raw :
3543             decodedSize = ZSTDv06_copyRawBlock(op, oend-op, ip, cBlockSize);
3544             break;
3545         case bt_rle :
3546             return ERROR(GENERIC);   /* not yet supported */
3547             break;
3548         case bt_end :
3549             /* end of frame */
3550             if (remainingSize) return ERROR(srcSize_wrong);
3551             break;
3552         default:
3553             return ERROR(GENERIC);   /* impossible */
3554         }
3555         if (cBlockSize == 0) break;   /* bt_end */
3556
3557         if (ZSTDv06_isError(decodedSize)) return decodedSize;
3558         op += decodedSize;
3559         ip += cBlockSize;
3560         remainingSize -= cBlockSize;
3561     }
3562
3563     return op-ostart;
3564 }
3565
3566
3567 size_t ZSTDv06_decompress_usingPreparedDCtx(ZSTDv06_DCtx* dctx, const ZSTDv06_DCtx* refDCtx,
3568                                          void* dst, size_t dstCapacity,
3569                                    const void* src, size_t srcSize)
3570 {
3571     ZSTDv06_copyDCtx(dctx, refDCtx);
3572     ZSTDv06_checkContinuity(dctx, dst);
3573     return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3574 }
3575
3576
3577 size_t ZSTDv06_decompress_usingDict(ZSTDv06_DCtx* dctx,
3578                                  void* dst, size_t dstCapacity,
3579                                  const void* src, size_t srcSize,
3580                                  const void* dict, size_t dictSize)
3581 {
3582     ZSTDv06_decompressBegin_usingDict(dctx, dict, dictSize);
3583     ZSTDv06_checkContinuity(dctx, dst);
3584     return ZSTDv06_decompressFrame(dctx, dst, dstCapacity, src, srcSize);
3585 }
3586
3587
3588 size_t ZSTDv06_decompressDCtx(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3589 {
3590     return ZSTDv06_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
3591 }
3592
3593
3594 size_t ZSTDv06_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3595 {
3596 #if defined(ZSTDv06_HEAPMODE) && (ZSTDv06_HEAPMODE==1)
3597     size_t regenSize;
3598     ZSTDv06_DCtx* dctx = ZSTDv06_createDCtx();
3599     if (dctx==NULL) return ERROR(memory_allocation);
3600     regenSize = ZSTDv06_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
3601     ZSTDv06_freeDCtx(dctx);
3602     return regenSize;
3603 #else   /* stack mode */
3604     ZSTDv06_DCtx dctx;
3605     return ZSTDv06_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
3606 #endif
3607 }
3608
3609 /* ZSTD_errorFrameSizeInfoLegacy() :
3610    assumes `cSize` and `dBound` are _not_ NULL */
3611 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
3612 {
3613     *cSize = ret;
3614     *dBound = ZSTD_CONTENTSIZE_ERROR;
3615 }
3616
3617 void ZSTDv06_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
3618 {
3619     const BYTE* ip = (const BYTE*)src;
3620     size_t remainingSize = srcSize;
3621     size_t nbBlocks = 0;
3622     blockProperties_t blockProperties = { bt_compressed, 0 };
3623
3624     /* Frame Header */
3625     {   size_t const frameHeaderSize = ZSTDv06_frameHeaderSize(src, srcSize);
3626         if (ZSTDv06_isError(frameHeaderSize)) {
3627             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, frameHeaderSize);
3628             return;
3629         }
3630         if (MEM_readLE32(src) != ZSTDv06_MAGICNUMBER) {
3631             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
3632             return;
3633         }
3634         if (srcSize < frameHeaderSize+ZSTDv06_blockHeaderSize) {
3635             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3636             return;
3637         }
3638         ip += frameHeaderSize; remainingSize -= frameHeaderSize;
3639     }
3640
3641     /* Loop on each block */
3642     while (1) {
3643         size_t const cBlockSize = ZSTDv06_getcBlockSize(ip, remainingSize, &blockProperties);
3644         if (ZSTDv06_isError(cBlockSize)) {
3645             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, cBlockSize);
3646             return;
3647         }
3648
3649         ip += ZSTDv06_blockHeaderSize;
3650         remainingSize -= ZSTDv06_blockHeaderSize;
3651         if (cBlockSize > remainingSize) {
3652             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
3653             return;
3654         }
3655
3656         if (cBlockSize == 0) break;   /* bt_end */
3657
3658         ip += cBlockSize;
3659         remainingSize -= cBlockSize;
3660         nbBlocks++;
3661     }
3662
3663     *cSize = ip - (const BYTE*)src;
3664     *dBound = nbBlocks * ZSTDv06_BLOCKSIZE_MAX;
3665 }
3666
3667 /*_******************************
3668 *  Streaming Decompression API
3669 ********************************/
3670 size_t ZSTDv06_nextSrcSizeToDecompress(ZSTDv06_DCtx* dctx)
3671 {
3672     return dctx->expected;
3673 }
3674
3675 size_t ZSTDv06_decompressContinue(ZSTDv06_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3676 {
3677     /* Sanity check */
3678     if (srcSize != dctx->expected) return ERROR(srcSize_wrong);
3679     if (dstCapacity) ZSTDv06_checkContinuity(dctx, dst);
3680
3681     /* Decompress : frame header; part 1 */
3682     switch (dctx->stage)
3683     {
3684     case ZSTDds_getFrameHeaderSize :
3685         if (srcSize != ZSTDv06_frameHeaderSize_min) return ERROR(srcSize_wrong);   /* impossible */
3686         dctx->headerSize = ZSTDv06_frameHeaderSize(src, ZSTDv06_frameHeaderSize_min);
3687         if (ZSTDv06_isError(dctx->headerSize)) return dctx->headerSize;
3688         memcpy(dctx->headerBuffer, src, ZSTDv06_frameHeaderSize_min);
3689         if (dctx->headerSize > ZSTDv06_frameHeaderSize_min) {
3690             dctx->expected = dctx->headerSize - ZSTDv06_frameHeaderSize_min;
3691             dctx->stage = ZSTDds_decodeFrameHeader;
3692             return 0;
3693         }
3694         dctx->expected = 0;   /* not necessary to copy more */
3695         /* fall-through */
3696     case ZSTDds_decodeFrameHeader:
3697         {   size_t result;
3698             memcpy(dctx->headerBuffer + ZSTDv06_frameHeaderSize_min, src, dctx->expected);
3699             result = ZSTDv06_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize);
3700             if (ZSTDv06_isError(result)) return result;
3701             dctx->expected = ZSTDv06_blockHeaderSize;
3702             dctx->stage = ZSTDds_decodeBlockHeader;
3703             return 0;
3704         }
3705     case ZSTDds_decodeBlockHeader:
3706         {   blockProperties_t bp;
3707             size_t const cBlockSize = ZSTDv06_getcBlockSize(src, ZSTDv06_blockHeaderSize, &bp);
3708             if (ZSTDv06_isError(cBlockSize)) return cBlockSize;
3709             if (bp.blockType == bt_end) {
3710                 dctx->expected = 0;
3711                 dctx->stage = ZSTDds_getFrameHeaderSize;
3712             } else {
3713                 dctx->expected = cBlockSize;
3714                 dctx->bType = bp.blockType;
3715                 dctx->stage = ZSTDds_decompressBlock;
3716             }
3717             return 0;
3718         }
3719     case ZSTDds_decompressBlock:
3720         {   size_t rSize;
3721             switch(dctx->bType)
3722             {
3723             case bt_compressed:
3724                 rSize = ZSTDv06_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize);
3725                 break;
3726             case bt_raw :
3727                 rSize = ZSTDv06_copyRawBlock(dst, dstCapacity, src, srcSize);
3728                 break;
3729             case bt_rle :
3730                 return ERROR(GENERIC);   /* not yet handled */
3731                 break;
3732             case bt_end :   /* should never happen (filtered at phase 1) */
3733                 rSize = 0;
3734                 break;
3735             default:
3736                 return ERROR(GENERIC);   /* impossible */
3737             }
3738             dctx->stage = ZSTDds_decodeBlockHeader;
3739             dctx->expected = ZSTDv06_blockHeaderSize;
3740             if (ZSTDv06_isError(rSize)) return rSize;
3741             dctx->previousDstEnd = (char*)dst + rSize;
3742             return rSize;
3743         }
3744     default:
3745         return ERROR(GENERIC);   /* impossible */
3746     }
3747 }
3748
3749
3750 static void ZSTDv06_refDictContent(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3751 {
3752     dctx->dictEnd = dctx->previousDstEnd;
3753     dctx->vBase = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->base));
3754     dctx->base = dict;
3755     dctx->previousDstEnd = (const char*)dict + dictSize;
3756 }
3757
3758 static size_t ZSTDv06_loadEntropy(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3759 {
3760     size_t hSize, offcodeHeaderSize, matchlengthHeaderSize, litlengthHeaderSize;
3761
3762     hSize = HUFv06_readDTableX4(dctx->hufTableX4, dict, dictSize);
3763     if (HUFv06_isError(hSize)) return ERROR(dictionary_corrupted);
3764     dict = (const char*)dict + hSize;
3765     dictSize -= hSize;
3766
3767     {   short offcodeNCount[MaxOff+1];
3768         U32 offcodeMaxValue=MaxOff, offcodeLog;
3769         offcodeHeaderSize = FSEv06_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dict, dictSize);
3770         if (FSEv06_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
3771         if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
3772         { size_t const errorCode = FSEv06_buildDTable(dctx->OffTable, offcodeNCount, offcodeMaxValue, offcodeLog);
3773           if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3774         dict = (const char*)dict + offcodeHeaderSize;
3775         dictSize -= offcodeHeaderSize;
3776     }
3777
3778     {   short matchlengthNCount[MaxML+1];
3779         unsigned matchlengthMaxValue = MaxML, matchlengthLog;
3780         matchlengthHeaderSize = FSEv06_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dict, dictSize);
3781         if (FSEv06_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
3782         if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
3783         { size_t const errorCode = FSEv06_buildDTable(dctx->MLTable, matchlengthNCount, matchlengthMaxValue, matchlengthLog);
3784           if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3785         dict = (const char*)dict + matchlengthHeaderSize;
3786         dictSize -= matchlengthHeaderSize;
3787     }
3788
3789     {   short litlengthNCount[MaxLL+1];
3790         unsigned litlengthMaxValue = MaxLL, litlengthLog;
3791         litlengthHeaderSize = FSEv06_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dict, dictSize);
3792         if (FSEv06_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
3793         if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
3794         { size_t const errorCode = FSEv06_buildDTable(dctx->LLTable, litlengthNCount, litlengthMaxValue, litlengthLog);
3795           if (FSEv06_isError(errorCode)) return ERROR(dictionary_corrupted); }
3796     }
3797
3798     dctx->flagRepeatTable = 1;
3799     return hSize + offcodeHeaderSize + matchlengthHeaderSize + litlengthHeaderSize;
3800 }
3801
3802 static size_t ZSTDv06_decompress_insertDictionary(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3803 {
3804     size_t eSize;
3805     U32 const magic = MEM_readLE32(dict);
3806     if (magic != ZSTDv06_DICT_MAGIC) {
3807         /* pure content mode */
3808         ZSTDv06_refDictContent(dctx, dict, dictSize);
3809         return 0;
3810     }
3811     /* load entropy tables */
3812     dict = (const char*)dict + 4;
3813     dictSize -= 4;
3814     eSize = ZSTDv06_loadEntropy(dctx, dict, dictSize);
3815     if (ZSTDv06_isError(eSize)) return ERROR(dictionary_corrupted);
3816
3817     /* reference dictionary content */
3818     dict = (const char*)dict + eSize;
3819     dictSize -= eSize;
3820     ZSTDv06_refDictContent(dctx, dict, dictSize);
3821
3822     return 0;
3823 }
3824
3825
3826 size_t ZSTDv06_decompressBegin_usingDict(ZSTDv06_DCtx* dctx, const void* dict, size_t dictSize)
3827 {
3828     { size_t const errorCode = ZSTDv06_decompressBegin(dctx);
3829       if (ZSTDv06_isError(errorCode)) return errorCode; }
3830
3831     if (dict && dictSize) {
3832         size_t const errorCode = ZSTDv06_decompress_insertDictionary(dctx, dict, dictSize);
3833         if (ZSTDv06_isError(errorCode)) return ERROR(dictionary_corrupted);
3834     }
3835
3836     return 0;
3837 }
3838
3839 /*
3840     Buffered version of Zstd compression library
3841     Copyright (C) 2015-2016, Yann Collet.
3842
3843     BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php)
3844
3845     Redistribution and use in source and binary forms, with or without
3846     modification, are permitted provided that the following conditions are
3847     met:
3848     * Redistributions of source code must retain the above copyright
3849     notice, this list of conditions and the following disclaimer.
3850     * Redistributions in binary form must reproduce the above
3851     copyright notice, this list of conditions and the following disclaimer
3852     in the documentation and/or other materials provided with the
3853     distribution.
3854     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
3855     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
3856     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
3857     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
3858     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
3859     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
3860     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
3861     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
3862     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
3863     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
3864     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
3865
3866     You can contact the author at :
3867     - zstd homepage : https://facebook.github.io/zstd/
3868 */
3869
3870
3871 /*-***************************************************************************
3872 *  Streaming decompression howto
3873 *
3874 *  A ZBUFFv06_DCtx object is required to track streaming operations.
3875 *  Use ZBUFFv06_createDCtx() and ZBUFFv06_freeDCtx() to create/release resources.
3876 *  Use ZBUFFv06_decompressInit() to start a new decompression operation,
3877 *   or ZBUFFv06_decompressInitDictionary() if decompression requires a dictionary.
3878 *  Note that ZBUFFv06_DCtx objects can be re-init multiple times.
3879 *
3880 *  Use ZBUFFv06_decompressContinue() repetitively to consume your input.
3881 *  *srcSizePtr and *dstCapacityPtr can be any size.
3882 *  The function will report how many bytes were read or written by modifying *srcSizePtr and *dstCapacityPtr.
3883 *  Note that it may not consume the entire input, in which case it's up to the caller to present remaining input again.
3884 *  The content of @dst will be overwritten (up to *dstCapacityPtr) at each function call, so save its content if it matters, or change @dst.
3885 *  @return : a hint to preferred nb of bytes to use as input for next function call (it's only a hint, to help latency),
3886 *            or 0 when a frame is completely decoded,
3887 *            or an error code, which can be tested using ZBUFFv06_isError().
3888 *
3889 *  Hint : recommended buffer sizes (not compulsory) : ZBUFFv06_recommendedDInSize() and ZBUFFv06_recommendedDOutSize()
3890 *  output : ZBUFFv06_recommendedDOutSize==128 KB block size is the internal unit, it ensures it's always possible to write a full block when decoded.
3891 *  input  : ZBUFFv06_recommendedDInSize == 128KB + 3;
3892 *           just follow indications from ZBUFFv06_decompressContinue() to minimize latency. It should always be <= 128 KB + 3 .
3893 * *******************************************************************************/
3894
3895 typedef enum { ZBUFFds_init, ZBUFFds_loadHeader,
3896                ZBUFFds_read, ZBUFFds_load, ZBUFFds_flush } ZBUFFv06_dStage;
3897
3898 /* *** Resource management *** */
3899 struct ZBUFFv06_DCtx_s {
3900     ZSTDv06_DCtx* zd;
3901     ZSTDv06_frameParams fParams;
3902     ZBUFFv06_dStage stage;
3903     char*  inBuff;
3904     size_t inBuffSize;
3905     size_t inPos;
3906     char*  outBuff;
3907     size_t outBuffSize;
3908     size_t outStart;
3909     size_t outEnd;
3910     size_t blockSize;
3911     BYTE headerBuffer[ZSTDv06_FRAMEHEADERSIZE_MAX];
3912     size_t lhSize;
3913 };   /* typedef'd to ZBUFFv06_DCtx within "zstd_buffered.h" */
3914
3915
3916 ZBUFFv06_DCtx* ZBUFFv06_createDCtx(void)
3917 {
3918     ZBUFFv06_DCtx* zbd = (ZBUFFv06_DCtx*)malloc(sizeof(ZBUFFv06_DCtx));
3919     if (zbd==NULL) return NULL;
3920     memset(zbd, 0, sizeof(*zbd));
3921     zbd->zd = ZSTDv06_createDCtx();
3922     zbd->stage = ZBUFFds_init;
3923     return zbd;
3924 }
3925
3926 size_t ZBUFFv06_freeDCtx(ZBUFFv06_DCtx* zbd)
3927 {
3928     if (zbd==NULL) return 0;   /* support free on null */
3929     ZSTDv06_freeDCtx(zbd->zd);
3930     free(zbd->inBuff);
3931     free(zbd->outBuff);
3932     free(zbd);
3933     return 0;
3934 }
3935
3936
3937 /* *** Initialization *** */
3938
3939 size_t ZBUFFv06_decompressInitDictionary(ZBUFFv06_DCtx* zbd, const void* dict, size_t dictSize)
3940 {
3941     zbd->stage = ZBUFFds_loadHeader;
3942     zbd->lhSize = zbd->inPos = zbd->outStart = zbd->outEnd = 0;
3943     return ZSTDv06_decompressBegin_usingDict(zbd->zd, dict, dictSize);
3944 }
3945
3946 size_t ZBUFFv06_decompressInit(ZBUFFv06_DCtx* zbd)
3947 {
3948     return ZBUFFv06_decompressInitDictionary(zbd, NULL, 0);
3949 }
3950
3951
3952
3953 MEM_STATIC size_t ZBUFFv06_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
3954 {
3955     size_t length = MIN(dstCapacity, srcSize);
3956     if (length > 0) {
3957         memcpy(dst, src, length);
3958     }
3959     return length;
3960 }
3961
3962
3963 /* *** Decompression *** */
3964
3965 size_t ZBUFFv06_decompressContinue(ZBUFFv06_DCtx* zbd,
3966                                 void* dst, size_t* dstCapacityPtr,
3967                           const void* src, size_t* srcSizePtr)
3968 {
3969     const char* const istart = (const char*)src;
3970     const char* const iend = istart + *srcSizePtr;
3971     const char* ip = istart;
3972     char* const ostart = (char*)dst;
3973     char* const oend = ostart + *dstCapacityPtr;
3974     char* op = ostart;
3975     U32 notDone = 1;
3976
3977     while (notDone) {
3978         switch(zbd->stage)
3979         {
3980         case ZBUFFds_init :
3981             return ERROR(init_missing);
3982
3983         case ZBUFFds_loadHeader :
3984             {   size_t const hSize = ZSTDv06_getFrameParams(&(zbd->fParams), zbd->headerBuffer, zbd->lhSize);
3985                 if (hSize != 0) {
3986                     size_t const toLoad = hSize - zbd->lhSize;   /* if hSize!=0, hSize > zbd->lhSize */
3987                     if (ZSTDv06_isError(hSize)) return hSize;
3988                     if (toLoad > (size_t)(iend-ip)) {   /* not enough input to load full header */
3989                         if (ip != NULL)
3990                             memcpy(zbd->headerBuffer + zbd->lhSize, ip, iend-ip);
3991                         zbd->lhSize += iend-ip;
3992                         *dstCapacityPtr = 0;
3993                         return (hSize - zbd->lhSize) + ZSTDv06_blockHeaderSize;   /* remaining header bytes + next block header */
3994                     }
3995                     memcpy(zbd->headerBuffer + zbd->lhSize, ip, toLoad); zbd->lhSize = hSize; ip += toLoad;
3996                     break;
3997             }   }
3998
3999             /* Consume header */
4000             {   size_t const h1Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);  /* == ZSTDv06_frameHeaderSize_min */
4001                 size_t const h1Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer, h1Size);
4002                 if (ZSTDv06_isError(h1Result)) return h1Result;
4003                 if (h1Size < zbd->lhSize) {   /* long header */
4004                     size_t const h2Size = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4005                     size_t const h2Result = ZSTDv06_decompressContinue(zbd->zd, NULL, 0, zbd->headerBuffer+h1Size, h2Size);
4006                     if (ZSTDv06_isError(h2Result)) return h2Result;
4007             }   }
4008
4009             /* Frame header instruct buffer sizes */
4010             {   size_t const blockSize = MIN(1 << zbd->fParams.windowLog, ZSTDv06_BLOCKSIZE_MAX);
4011                 zbd->blockSize = blockSize;
4012                 if (zbd->inBuffSize < blockSize) {
4013                     free(zbd->inBuff);
4014                     zbd->inBuffSize = blockSize;
4015                     zbd->inBuff = (char*)malloc(blockSize);
4016                     if (zbd->inBuff == NULL) return ERROR(memory_allocation);
4017                 }
4018                 {   size_t const neededOutSize = ((size_t)1 << zbd->fParams.windowLog) + blockSize + WILDCOPY_OVERLENGTH * 2;
4019                     if (zbd->outBuffSize < neededOutSize) {
4020                         free(zbd->outBuff);
4021                         zbd->outBuffSize = neededOutSize;
4022                         zbd->outBuff = (char*)malloc(neededOutSize);
4023                         if (zbd->outBuff == NULL) return ERROR(memory_allocation);
4024             }   }   }
4025             zbd->stage = ZBUFFds_read;
4026             /* fall-through */
4027         case ZBUFFds_read:
4028             {   size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4029                 if (neededInSize==0) {  /* end of frame */
4030                     zbd->stage = ZBUFFds_init;
4031                     notDone = 0;
4032                     break;
4033                 }
4034                 if ((size_t)(iend-ip) >= neededInSize) {  /* decode directly from src */
4035                     size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd,
4036                         zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4037                         ip, neededInSize);
4038                     if (ZSTDv06_isError(decodedSize)) return decodedSize;
4039                     ip += neededInSize;
4040                     if (!decodedSize) break;   /* this was just a header */
4041                     zbd->outEnd = zbd->outStart +  decodedSize;
4042                     zbd->stage = ZBUFFds_flush;
4043                     break;
4044                 }
4045                 if (ip==iend) { notDone = 0; break; }   /* no more input */
4046                 zbd->stage = ZBUFFds_load;
4047             }
4048             /* fall-through */
4049         case ZBUFFds_load:
4050             {   size_t const neededInSize = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4051                 size_t const toLoad = neededInSize - zbd->inPos;   /* should always be <= remaining space within inBuff */
4052                 size_t loadedSize;
4053                 if (toLoad > zbd->inBuffSize - zbd->inPos) return ERROR(corruption_detected);   /* should never happen */
4054                 loadedSize = ZBUFFv06_limitCopy(zbd->inBuff + zbd->inPos, toLoad, ip, iend-ip);
4055                 ip += loadedSize;
4056                 zbd->inPos += loadedSize;
4057                 if (loadedSize < toLoad) { notDone = 0; break; }   /* not enough input, wait for more */
4058
4059                 /* decode loaded input */
4060                 {   size_t const decodedSize = ZSTDv06_decompressContinue(zbd->zd,
4061                         zbd->outBuff + zbd->outStart, zbd->outBuffSize - zbd->outStart,
4062                         zbd->inBuff, neededInSize);
4063                     if (ZSTDv06_isError(decodedSize)) return decodedSize;
4064                     zbd->inPos = 0;   /* input is consumed */
4065                     if (!decodedSize) { zbd->stage = ZBUFFds_read; break; }   /* this was just a header */
4066                     zbd->outEnd = zbd->outStart +  decodedSize;
4067                     zbd->stage = ZBUFFds_flush;
4068                     /* break; */ /* ZBUFFds_flush follows */
4069                 }
4070             }
4071             /* fall-through */
4072         case ZBUFFds_flush:
4073             {   size_t const toFlushSize = zbd->outEnd - zbd->outStart;
4074                 size_t const flushedSize = ZBUFFv06_limitCopy(op, oend-op, zbd->outBuff + zbd->outStart, toFlushSize);
4075                 op += flushedSize;
4076                 zbd->outStart += flushedSize;
4077                 if (flushedSize == toFlushSize) {
4078                     zbd->stage = ZBUFFds_read;
4079                     if (zbd->outStart + zbd->blockSize > zbd->outBuffSize)
4080                         zbd->outStart = zbd->outEnd = 0;
4081                     break;
4082                 }
4083                 /* cannot flush everything */
4084                 notDone = 0;
4085                 break;
4086             }
4087         default: return ERROR(GENERIC);   /* impossible */
4088     }   }
4089
4090     /* result */
4091     *srcSizePtr = ip-istart;
4092     *dstCapacityPtr = op-ostart;
4093     {   size_t nextSrcSizeHint = ZSTDv06_nextSrcSizeToDecompress(zbd->zd);
4094         if (nextSrcSizeHint > ZSTDv06_blockHeaderSize) nextSrcSizeHint+= ZSTDv06_blockHeaderSize;   /* get following block header too */
4095         nextSrcSizeHint -= zbd->inPos;   /* already loaded*/
4096         return nextSrcSizeHint;
4097     }
4098 }
4099
4100
4101
4102 /* *************************************
4103 *  Tool functions
4104 ***************************************/
4105 size_t ZBUFFv06_recommendedDInSize(void)  { return ZSTDv06_BLOCKSIZE_MAX + ZSTDv06_blockHeaderSize /* block header size*/ ; }
4106 size_t ZBUFFv06_recommendedDOutSize(void) { return ZSTDv06_BLOCKSIZE_MAX; }