lib/legacy/zstd_v01.c

   1 /*
   2  * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
   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 /******************************************
  13 *  Includes
  14 ******************************************/
  15 #include <stddef.h>    /* size_t, ptrdiff_t */
  16 #include "zstd_v01.h"
  17 #include "error_private.h"
  18
  19
  20 /******************************************
  21 *  Static allocation
  22 ******************************************/
  23 /* You can statically allocate FSE CTable/DTable as a table of unsigned using below macro */
  24 #define FSE_DTABLE_SIZE_U32(maxTableLog)                   (1 + (1<<maxTableLog))
  25
  26 /* You can statically allocate Huff0 DTable as a table of unsigned short using below macro */
  27 #define HUF_DTABLE_SIZE_U16(maxTableLog)   (1 + (1<<maxTableLog))
  28 #define HUF_CREATE_STATIC_DTABLE(DTable, maxTableLog) \
  29         unsigned short DTable[HUF_DTABLE_SIZE_U16(maxTableLog)] = { maxTableLog }
  30
  31
  32 /******************************************
  33 *  Error Management
  34 ******************************************/
  35 #define FSE_LIST_ERRORS(ITEM) \
  36         ITEM(FSE_OK_NoError) ITEM(FSE_ERROR_GENERIC) \
  37         ITEM(FSE_ERROR_tableLog_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooLarge) ITEM(FSE_ERROR_maxSymbolValue_tooSmall) \
  38         ITEM(FSE_ERROR_dstSize_tooSmall) ITEM(FSE_ERROR_srcSize_wrong)\
  39         ITEM(FSE_ERROR_corruptionDetected) \
  40         ITEM(FSE_ERROR_maxCode)
  41
  42 #define FSE_GENERATE_ENUM(ENUM) ENUM,
  43 typedef enum { FSE_LIST_ERRORS(FSE_GENERATE_ENUM) } FSE_errorCodes;  /* enum is exposed, to detect & handle specific errors; compare function result to -enum value */
  44
  45
  46 /******************************************
  47 *  FSE symbol compression API
  48 ******************************************/
  49 /*
  50    This API consists of small unitary functions, which highly benefit from being inlined.
  51    You will want to enable link-time-optimization to ensure these functions are properly inlined in your binary.
  52    Visual seems to do it automatically.
  53    For gcc or clang, you'll need to add -flto flag at compilation and linking stages.
  54    If none of these solutions is applicable, include "fse.c" directly.
  55 */
  56
  57 typedef unsigned FSE_CTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
  58 typedef unsigned FSE_DTable;   /* don't allocate that. It's just a way to be more restrictive than void* */
  59
  60 typedef struct
  61 {
  62     size_t bitContainer;
  63     int    bitPos;
  64     char*  startPtr;
  65     char*  ptr;
  66     char*  endPtr;
  67 } FSE_CStream_t;
  68
  69 typedef struct
  70 {
  71     ptrdiff_t   value;
  72     const void* stateTable;
  73     const void* symbolTT;
  74     unsigned    stateLog;
  75 } FSE_CState_t;
  76
  77 typedef struct
  78 {
  79     size_t   bitContainer;
  80     unsigned bitsConsumed;
  81     const char* ptr;
  82     const char* start;
  83 } FSE_DStream_t;
  84
  85 typedef struct
  86 {
  87     size_t      state;
  88     const void* table;   /* precise table may vary, depending on U16 */
  89 } FSE_DState_t;
  90
  91 typedef enum { FSE_DStream_unfinished = 0,
  92                FSE_DStream_endOfBuffer = 1,
  93                FSE_DStream_completed = 2,
  94                FSE_DStream_tooFar = 3 } FSE_DStream_status;  /* result of FSE_reloadDStream() */
  95                /* 1,2,4,8 would be better for bitmap combinations, but slows down performance a bit ... ?! */
  96
  97
  98 /****************************************************************
  99 *  Tuning parameters
 100 ****************************************************************/
 101 /* MEMORY_USAGE :
 102 *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
 103 *  Increasing memory usage improves compression ratio
 104 *  Reduced memory usage can improve speed, due to cache effect
 105 *  Recommended max value is 14, for 16KB, which nicely fits into Intel x86 L1 cache */
 106 #define FSE_MAX_MEMORY_USAGE 14
 107 #define FSE_DEFAULT_MEMORY_USAGE 13
 108
 109 /* FSE_MAX_SYMBOL_VALUE :
 110 *  Maximum symbol value authorized.
 111 *  Required for proper stack allocation */
 112 #define FSE_MAX_SYMBOL_VALUE 255
 113
 114
 115 /****************************************************************
 116 *  template functions type & suffix
 117 ****************************************************************/
 118 #define FSE_FUNCTION_TYPE BYTE
 119 #define FSE_FUNCTION_EXTENSION
 120
 121
 122 /****************************************************************
 123 *  Byte symbol type
 124 ****************************************************************/
 125 typedef struct
 126 {
 127     unsigned short newState;
 128     unsigned char  symbol;
 129     unsigned char  nbBits;
 130 } FSE_decode_t;   /* size == U32 */
 131
 132
 133
 134 /****************************************************************
 135 *  Compiler specifics
 136 ****************************************************************/
 137 #ifdef _MSC_VER    /* Visual Studio */
 138 #  define FORCE_INLINE static __forceinline
 139 #  include <intrin.h>                    /* For Visual 2005 */
 140 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
 141 #  pragma warning(disable : 4214)        /* disable: C4214: non-int bitfields */
 142 #else
 143 #  define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
 144 #  if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
 145 #    ifdef __GNUC__
 146 #      define FORCE_INLINE static inline __attribute__((always_inline))
 147 #    else
 148 #      define FORCE_INLINE static inline
 149 #    endif
 150 #  else
 151 #    define FORCE_INLINE static
 152 #  endif /* __STDC_VERSION__ */
 153 #endif
 154
 155
 156 /****************************************************************
 157 *  Includes
 158 ****************************************************************/
 159 #include <stdlib.h>     /* malloc, free, qsort */
 160 #include <string.h>     /* memcpy, memset */
 161 #include <stdio.h>      /* printf (debug) */
 162
 163
 164 #ifndef MEM_ACCESS_MODULE
 165 #define MEM_ACCESS_MODULE
 166 /****************************************************************
 167 *  Basic Types
 168 *****************************************************************/
 169 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
 170 # include <stdint.h>
 171 typedef  uint8_t BYTE;
 172 typedef uint16_t U16;
 173 typedef  int16_t S16;
 174 typedef uint32_t U32;
 175 typedef  int32_t S32;
 176 typedef uint64_t U64;
 177 typedef  int64_t S64;
 178 #else
 179 typedef unsigned char       BYTE;
 180 typedef unsigned short      U16;
 181 typedef   signed short      S16;
 182 typedef unsigned int        U32;
 183 typedef   signed int        S32;
 184 typedef unsigned long long  U64;
 185 typedef   signed long long  S64;
 186 #endif
 187
 188 #endif   /* MEM_ACCESS_MODULE */
 189
 190 /****************************************************************
 191 *  Memory I/O
 192 *****************************************************************/
 193 /* FSE_FORCE_MEMORY_ACCESS
 194  * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
 195  * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
 196  * The below switch allow to select different access method for improved performance.
 197  * Method 0 (default) : use `memcpy()`. Safe and portable.
 198  * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
 199  *            This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
 200  * Method 2 : direct access. This method is portable but violate C standard.
 201  *            It can generate buggy code on targets generating assembly depending on alignment.
 202  *            But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
 203  * See http://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
 204  * Prefer these methods in priority order (0 > 1 > 2)
 205  */
 206 #ifndef FSE_FORCE_MEMORY_ACCESS   /* can be defined externally, on command line for example */
 207 #  if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
 208 #    define FSE_FORCE_MEMORY_ACCESS 2
 209 #  elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \
 210   (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
 211 #    define FSE_FORCE_MEMORY_ACCESS 1
 212 #  endif
 213 #endif
 214
 215
 216 static unsigned FSE_32bits(void)
 217 {
 218     return sizeof(void*)==4;
 219 }
 220
 221 static unsigned FSE_isLittleEndian(void)
 222 {
 223     const union { U32 i; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
 224     return one.c[0];
 225 }
 226
 227 #if defined(FSE_FORCE_MEMORY_ACCESS) && (FSE_FORCE_MEMORY_ACCESS==2)
 228
 229 static U16 FSE_read16(const void* memPtr) { return *(const U16*) memPtr; }
 230 static U32 FSE_read32(const void* memPtr) { return *(const U32*) memPtr; }
 231 static U64 FSE_read64(const void* memPtr) { return *(const U64*) memPtr; }
 232
 233 #elif defined(FSE_FORCE_MEMORY_ACCESS) && (FSE_FORCE_MEMORY_ACCESS==1)
 234
 235 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
 236 /* currently only defined for gcc and icc */
 237 typedef union { U16 u16; U32 u32; U64 u64; } __attribute__((packed)) unalign;
 238
 239 static U16 FSE_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
 240 static U32 FSE_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
 241 static U64 FSE_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
 242
 243 #else
 244
 245 static U16 FSE_read16(const void* memPtr)
 246 {
 247     U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
 248 }
 249
 250 static U32 FSE_read32(const void* memPtr)
 251 {
 252     U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
 253 }
 254
 255 static U64 FSE_read64(const void* memPtr)
 256 {
 257     U64 val; memcpy(&val, memPtr, sizeof(val)); return val;
 258 }
 259
 260 #endif // FSE_FORCE_MEMORY_ACCESS
 261
 262 static U16 FSE_readLE16(const void* memPtr)
 263 {
 264     if (FSE_isLittleEndian())
 265         return FSE_read16(memPtr);
 266     else
 267     {
 268         const BYTE* p = (const BYTE*)memPtr;
 269         return (U16)(p[0] + (p[1]<<8));
 270     }
 271 }
 272
 273 static U32 FSE_readLE32(const void* memPtr)
 274 {
 275     if (FSE_isLittleEndian())
 276         return FSE_read32(memPtr);
 277     else
 278     {
 279         const BYTE* p = (const BYTE*)memPtr;
 280         return (U32)((U32)p[0] + ((U32)p[1]<<8) + ((U32)p[2]<<16) + ((U32)p[3]<<24));
 281     }
 282 }
 283
 284
 285 static U64 FSE_readLE64(const void* memPtr)
 286 {
 287     if (FSE_isLittleEndian())
 288         return FSE_read64(memPtr);
 289     else
 290     {
 291         const BYTE* p = (const BYTE*)memPtr;
 292         return (U64)((U64)p[0] + ((U64)p[1]<<8) + ((U64)p[2]<<16) + ((U64)p[3]<<24)
 293                      + ((U64)p[4]<<32) + ((U64)p[5]<<40) + ((U64)p[6]<<48) + ((U64)p[7]<<56));
 294     }
 295 }
 296
 297 static size_t FSE_readLEST(const void* memPtr)
 298 {
 299     if (FSE_32bits())
 300         return (size_t)FSE_readLE32(memPtr);
 301     else
 302         return (size_t)FSE_readLE64(memPtr);
 303 }
 304
 305
 306
 307 /****************************************************************
 308 *  Constants
 309 *****************************************************************/
 310 #define FSE_MAX_TABLELOG  (FSE_MAX_MEMORY_USAGE-2)
 311 #define FSE_MAX_TABLESIZE (1U<<FSE_MAX_TABLELOG)
 312 #define FSE_MAXTABLESIZE_MASK (FSE_MAX_TABLESIZE-1)
 313 #define FSE_DEFAULT_TABLELOG (FSE_DEFAULT_MEMORY_USAGE-2)
 314 #define FSE_MIN_TABLELOG 5
 315
 316 #define FSE_TABLELOG_ABSOLUTE_MAX 15
 317 #if FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX
 318 #error "FSE_MAX_TABLELOG > FSE_TABLELOG_ABSOLUTE_MAX is not supported"
 319 #endif
 320
 321
 322 /****************************************************************
 323 *  Error Management
 324 ****************************************************************/
 325 #define FSE_STATIC_ASSERT(c) { enum { FSE_static_assert = 1/(int)(!!(c)) }; }   /* use only *after* variable declarations */
 326
 327
 328 /****************************************************************
 329 *  Complex types
 330 ****************************************************************/
 331 typedef struct
 332 {
 333     int deltaFindState;
 334     U32 deltaNbBits;
 335 } FSE_symbolCompressionTransform; /* total 8 bytes */
 336
 337 typedef U32 DTable_max_t[FSE_DTABLE_SIZE_U32(FSE_MAX_TABLELOG)];
 338
 339 /****************************************************************
 340 *  Internal functions
 341 ****************************************************************/
 342 FORCE_INLINE unsigned FSE_highbit32 (U32 val)
 343 {
 344 #   if defined(_MSC_VER)   /* Visual */
 345     unsigned long r;
 346     _BitScanReverse ( &r, val );
 347     return (unsigned) r;
 348 #   elif defined(__GNUC__) && (GCC_VERSION >= 304)   /* GCC Intrinsic */
 349     return 31 - __builtin_clz (val);
 350 #   else   /* Software version */
 351     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 };
 352     U32 v = val;
 353     unsigned r;
 354     v |= v >> 1;
 355     v |= v >> 2;
 356     v |= v >> 4;
 357     v |= v >> 8;
 358     v |= v >> 16;
 359     r = DeBruijnClz[ (U32) (v * 0x07C4ACDDU) >> 27];
 360     return r;
 361 #   endif
 362 }
 363
 364
 365 /****************************************************************
 366 *  Templates
 367 ****************************************************************/
 368 /*
 369   designed to be included
 370   for type-specific functions (template emulation in C)
 371   Objective is to write these functions only once, for improved maintenance
 372 */
 373
 374 /* safety checks */
 375 #ifndef FSE_FUNCTION_EXTENSION
 376 #  error "FSE_FUNCTION_EXTENSION must be defined"
 377 #endif
 378 #ifndef FSE_FUNCTION_TYPE
 379 #  error "FSE_FUNCTION_TYPE must be defined"
 380 #endif
 381
 382 /* Function names */
 383 #define FSE_CAT(X,Y) X##Y
 384 #define FSE_FUNCTION_NAME(X,Y) FSE_CAT(X,Y)
 385 #define FSE_TYPE_NAME(X,Y) FSE_CAT(X,Y)
 386
 387
 388
 389 static U32 FSE_tableStep(U32 tableSize) { return (tableSize>>1) + (tableSize>>3) + 3; }
 390
 391 #define FSE_DECODE_TYPE FSE_decode_t
 392
 393
 394 typedef struct {
 395     U16 tableLog;
 396     U16 fastMode;
 397 } FSE_DTableHeader;   /* sizeof U32 */
 398
 399 static size_t FSE_buildDTable
 400 (FSE_DTable* dt, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
 401 {
 402     void* ptr = dt;
 403     FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
 404     FSE_DECODE_TYPE* const tableDecode = (FSE_DECODE_TYPE*)(ptr) + 1;   /* because dt is unsigned, 32-bits aligned on 32-bits */
 405     const U32 tableSize = 1 << tableLog;
 406     const U32 tableMask = tableSize-1;
 407     const U32 step = FSE_tableStep(tableSize);
 408     U16 symbolNext[FSE_MAX_SYMBOL_VALUE+1];
 409     U32 position = 0;
 410     U32 highThreshold = tableSize-1;
 411     const S16 largeLimit= (S16)(1 << (tableLog-1));
 412     U32 noLarge = 1;
 413     U32 s;
 414
 415     /* Sanity Checks */
 416     if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE) return (size_t)-FSE_ERROR_maxSymbolValue_tooLarge;
 417     if (tableLog > FSE_MAX_TABLELOG) return (size_t)-FSE_ERROR_tableLog_tooLarge;
 418
 419     /* Init, lay down lowprob symbols */
 420     DTableH[0].tableLog = (U16)tableLog;
 421     for (s=0; s<=maxSymbolValue; s++)
 422     {
 423         if (normalizedCounter[s]==-1)
 424         {
 425             tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
 426             symbolNext[s] = 1;
 427         }
 428         else
 429         {
 430             if (normalizedCounter[s] >= largeLimit) noLarge=0;
 431             symbolNext[s] = normalizedCounter[s];
 432         }
 433     }
 434
 435     /* Spread symbols */
 436     for (s=0; s<=maxSymbolValue; s++)
 437     {
 438         int i;
 439         for (i=0; i<normalizedCounter[s]; i++)
 440         {
 441             tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
 442             position = (position + step) & tableMask;
 443             while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
 444         }
 445     }
 446
 447     if (position!=0) return (size_t)-FSE_ERROR_GENERIC;   /* position must reach all cells once, otherwise normalizedCounter is incorrect */
 448
 449     /* Build Decoding table */
 450     {
 451         U32 i;
 452         for (i=0; i<tableSize; i++)
 453         {
 454             FSE_FUNCTION_TYPE symbol = (FSE_FUNCTION_TYPE)(tableDecode[i].symbol);
 455             U16 nextState = symbolNext[symbol]++;
 456             tableDecode[i].nbBits = (BYTE) (tableLog - FSE_highbit32 ((U32)nextState) );
 457             tableDecode[i].newState = (U16) ( (nextState << tableDecode[i].nbBits) - tableSize);
 458         }
 459     }
 460
 461     DTableH->fastMode = (U16)noLarge;
 462     return 0;
 463 }
 464
 465
 466 /******************************************
 467 *  FSE byte symbol
 468 ******************************************/
 469 #ifndef FSE_COMMONDEFS_ONLY
 470
 471 static unsigned FSE_isError(size_t code) { return (code > (size_t)(-FSE_ERROR_maxCode)); }
 472
 473 static short FSE_abs(short a)
 474 {
 475     return a<0? -a : a;
 476 }
 477
 478
 479 /****************************************************************
 480 *  Header bitstream management
 481 ****************************************************************/
 482 static size_t FSE_readNCount (short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
 483                  const void* headerBuffer, size_t hbSize)
 484 {
 485     const BYTE* const istart = (const BYTE*) headerBuffer;
 486     const BYTE* const iend = istart + hbSize;
 487     const BYTE* ip = istart;
 488     int nbBits;
 489     int remaining;
 490     int threshold;
 491     U32 bitStream;
 492     int bitCount;
 493     unsigned charnum = 0;
 494     int previous0 = 0;
 495
 496     if (hbSize < 4) return (size_t)-FSE_ERROR_srcSize_wrong;
 497     bitStream = FSE_readLE32(ip);
 498     nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG;   /* extract tableLog */
 499     if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return (size_t)-FSE_ERROR_tableLog_tooLarge;
 500     bitStream >>= 4;
 501     bitCount = 4;
 502     *tableLogPtr = nbBits;
 503     remaining = (1<<nbBits)+1;
 504     threshold = 1<<nbBits;
 505     nbBits++;
 506
 507     while ((remaining>1) && (charnum<=*maxSVPtr))
 508     {
 509         if (previous0)
 510         {
 511             unsigned n0 = charnum;
 512             while ((bitStream & 0xFFFF) == 0xFFFF)
 513             {
 514                 n0+=24;
 515                 if (ip < iend-5)
 516                 {
 517                     ip+=2;
 518                     bitStream = FSE_readLE32(ip) >> bitCount;
 519                 }
 520                 else
 521                 {
 522                     bitStream >>= 16;
 523                     bitCount+=16;
 524                 }
 525             }
 526             while ((bitStream & 3) == 3)
 527             {
 528                 n0+=3;
 529                 bitStream>>=2;
 530                 bitCount+=2;
 531             }
 532             n0 += bitStream & 3;
 533             bitCount += 2;
 534             if (n0 > *maxSVPtr) return (size_t)-FSE_ERROR_maxSymbolValue_tooSmall;
 535             while (charnum < n0) normalizedCounter[charnum++] = 0;
 536             if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
 537             {
 538                 ip += bitCount>>3;
 539                 bitCount &= 7;
 540                 bitStream = FSE_readLE32(ip) >> bitCount;
 541             }
 542             else
 543                 bitStream >>= 2;
 544         }
 545         {
 546             const short max = (short)((2*threshold-1)-remaining);
 547             short count;
 548
 549             if ((bitStream & (threshold-1)) < (U32)max)
 550             {
 551                 count = (short)(bitStream & (threshold-1));
 552                 bitCount   += nbBits-1;
 553             }
 554             else
 555             {
 556                 count = (short)(bitStream & (2*threshold-1));
 557                 if (count >= threshold) count -= max;
 558                 bitCount   += nbBits;
 559             }
 560
 561             count--;   /* extra accuracy */
 562             remaining -= FSE_abs(count);
 563             normalizedCounter[charnum++] = count;
 564             previous0 = !count;
 565             while (remaining < threshold)
 566             {
 567                 nbBits--;
 568                 threshold >>= 1;
 569             }
 570
 571             {
 572                 if ((ip <= iend-7) || (ip + (bitCount>>3) <= iend-4))
 573                 {
 574                     ip += bitCount>>3;
 575                     bitCount &= 7;
 576                 }
 577                 else
 578                 {
 579                     bitCount -= (int)(8 * (iend - 4 - ip));
 580                     ip = iend - 4;
 581                 }
 582                 bitStream = FSE_readLE32(ip) >> (bitCount & 31);
 583             }
 584         }
 585     }
 586     if (remaining != 1) return (size_t)-FSE_ERROR_GENERIC;
 587     *maxSVPtr = charnum-1;
 588
 589     ip += (bitCount+7)>>3;
 590     if ((size_t)(ip-istart) > hbSize) return (size_t)-FSE_ERROR_srcSize_wrong;
 591     return ip-istart;
 592 }
 593
 594
 595 /*********************************************************
 596 *  Decompression (Byte symbols)
 597 *********************************************************/
 598 static size_t FSE_buildDTable_rle (FSE_DTable* dt, BYTE symbolValue)
 599 {
 600     void* ptr = dt;
 601     FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
 602     FSE_decode_t* const cell = (FSE_decode_t*)(ptr) + 1;   /* because dt is unsigned */
 603
 604     DTableH->tableLog = 0;
 605     DTableH->fastMode = 0;
 606
 607     cell->newState = 0;
 608     cell->symbol = symbolValue;
 609     cell->nbBits = 0;
 610
 611     return 0;
 612 }
 613
 614
 615 static size_t FSE_buildDTable_raw (FSE_DTable* dt, unsigned nbBits)
 616 {
 617     void* ptr = dt;
 618     FSE_DTableHeader* const DTableH = (FSE_DTableHeader*)ptr;
 619     FSE_decode_t* const dinfo = (FSE_decode_t*)(ptr) + 1;   /* because dt is unsigned */
 620     const unsigned tableSize = 1 << nbBits;
 621     const unsigned tableMask = tableSize - 1;
 622     const unsigned maxSymbolValue = tableMask;
 623     unsigned s;
 624
 625     /* Sanity checks */
 626     if (nbBits < 1) return (size_t)-FSE_ERROR_GENERIC;             /* min size */
 627
 628     /* Build Decoding Table */
 629     DTableH->tableLog = (U16)nbBits;
 630     DTableH->fastMode = 1;
 631     for (s=0; s<=maxSymbolValue; s++)
 632     {
 633         dinfo[s].newState = 0;
 634         dinfo[s].symbol = (BYTE)s;
 635         dinfo[s].nbBits = (BYTE)nbBits;
 636     }
 637
 638     return 0;
 639 }
 640
 641
 642 /* FSE_initDStream
 643  * Initialize a FSE_DStream_t.
 644  * srcBuffer must point at the beginning of an FSE block.
 645  * The function result is the size of the FSE_block (== srcSize).
 646  * If srcSize is too small, the function will return an errorCode;
 647  */
 648 static size_t FSE_initDStream(FSE_DStream_t* bitD, const void* srcBuffer, size_t srcSize)
 649 {
 650     if (srcSize < 1) return (size_t)-FSE_ERROR_srcSize_wrong;
 651
 652     if (srcSize >=  sizeof(size_t))
 653     {
 654         U32 contain32;
 655         bitD->start = (const char*)srcBuffer;
 656         bitD->ptr   = (const char*)srcBuffer + srcSize - sizeof(size_t);
 657         bitD->bitContainer = FSE_readLEST(bitD->ptr);
 658         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
 659         if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC;   /* stop bit not present */
 660         bitD->bitsConsumed = 8 - FSE_highbit32(contain32);
 661     }
 662     else
 663     {
 664         U32 contain32;
 665         bitD->start = (const char*)srcBuffer;
 666         bitD->ptr   = bitD->start;
 667         bitD->bitContainer = *(const BYTE*)(bitD->start);
 668         switch(srcSize)
 669         {
 670             case 7: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[6]) << (sizeof(size_t)*8 - 16);
 671                     /* fallthrough */
 672             case 6: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[5]) << (sizeof(size_t)*8 - 24);
 673                     /* fallthrough */
 674             case 5: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[4]) << (sizeof(size_t)*8 - 32);
 675                     /* fallthrough */
 676             case 4: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[3]) << 24;
 677                     /* fallthrough */
 678             case 3: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[2]) << 16;
 679                     /* fallthrough */
 680             case 2: bitD->bitContainer += (size_t)(((const BYTE*)(bitD->start))[1]) <<  8;
 681                     /* fallthrough */
 682             default:;
 683         }
 684         contain32 = ((const BYTE*)srcBuffer)[srcSize-1];
 685         if (contain32 == 0) return (size_t)-FSE_ERROR_GENERIC;   /* stop bit not present */
 686         bitD->bitsConsumed = 8 - FSE_highbit32(contain32);
 687         bitD->bitsConsumed += (U32)(sizeof(size_t) - srcSize)*8;
 688     }
 689
 690     return srcSize;
 691 }
 692
 693
 694 /*!FSE_lookBits
 695  * Provides next n bits from the bitContainer.
 696  * bitContainer is not modified (bits are still present for next read/look)
 697  * On 32-bits, maxNbBits==25
 698  * On 64-bits, maxNbBits==57
 699  * return : value extracted.
 700  */
 701 static size_t FSE_lookBits(FSE_DStream_t* bitD, U32 nbBits)
 702 {
 703     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
 704     return ((bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> 1) >> ((bitMask-nbBits) & bitMask);
 705 }
 706
 707 static size_t FSE_lookBitsFast(FSE_DStream_t* bitD, U32 nbBits)   /* only if nbBits >= 1 !! */
 708 {
 709     const U32 bitMask = sizeof(bitD->bitContainer)*8 - 1;
 710     return (bitD->bitContainer << (bitD->bitsConsumed & bitMask)) >> (((bitMask+1)-nbBits) & bitMask);
 711 }
 712
 713 static void FSE_skipBits(FSE_DStream_t* bitD, U32 nbBits)
 714 {
 715     bitD->bitsConsumed += nbBits;
 716 }
 717
 718
 719 /*!FSE_readBits
 720  * Read next n bits from the bitContainer.
 721  * On 32-bits, don't read more than maxNbBits==25
 722  * On 64-bits, don't read more than maxNbBits==57
 723  * Use the fast variant *only* if n >= 1.
 724  * return : value extracted.
 725  */
 726 static size_t FSE_readBits(FSE_DStream_t* bitD, U32 nbBits)
 727 {
 728     size_t value = FSE_lookBits(bitD, nbBits);
 729     FSE_skipBits(bitD, nbBits);
 730     return value;
 731 }
 732
 733 static size_t FSE_readBitsFast(FSE_DStream_t* bitD, U32 nbBits)   /* only if nbBits >= 1 !! */
 734 {
 735     size_t value = FSE_lookBitsFast(bitD, nbBits);
 736     FSE_skipBits(bitD, nbBits);
 737     return value;
 738 }
 739
 740 static unsigned FSE_reloadDStream(FSE_DStream_t* bitD)
 741 {
 742     if (bitD->bitsConsumed > (sizeof(bitD->bitContainer)*8))  /* should never happen */
 743         return FSE_DStream_tooFar;
 744
 745     if (bitD->ptr >= bitD->start + sizeof(bitD->bitContainer))
 746     {
 747         bitD->ptr -= bitD->bitsConsumed >> 3;
 748         bitD->bitsConsumed &= 7;
 749         bitD->bitContainer = FSE_readLEST(bitD->ptr);
 750         return FSE_DStream_unfinished;
 751     }
 752     if (bitD->ptr == bitD->start)
 753     {
 754         if (bitD->bitsConsumed < sizeof(bitD->bitContainer)*8) return FSE_DStream_endOfBuffer;
 755         return FSE_DStream_completed;
 756     }
 757     {
 758         U32 nbBytes = bitD->bitsConsumed >> 3;
 759         U32 result = FSE_DStream_unfinished;
 760         if (bitD->ptr - nbBytes < bitD->start)
 761         {
 762             nbBytes = (U32)(bitD->ptr - bitD->start);  /* ptr > start */
 763             result = FSE_DStream_endOfBuffer;
 764         }
 765         bitD->ptr -= nbBytes;
 766         bitD->bitsConsumed -= nbBytes*8;
 767         bitD->bitContainer = FSE_readLEST(bitD->ptr);   /* reminder : srcSize > sizeof(bitD) */
 768         return result;
 769     }
 770 }
 771
 772
 773 static void FSE_initDState(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD, const FSE_DTable* dt)
 774 {
 775     const void* ptr = dt;
 776     const FSE_DTableHeader* const DTableH = (const FSE_DTableHeader*)ptr;
 777     DStatePtr->state = FSE_readBits(bitD, DTableH->tableLog);
 778     FSE_reloadDStream(bitD);
 779     DStatePtr->table = dt + 1;
 780 }
 781
 782 static BYTE FSE_decodeSymbol(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD)
 783 {
 784     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
 785     const U32  nbBits = DInfo.nbBits;
 786     BYTE symbol = DInfo.symbol;
 787     size_t lowBits = FSE_readBits(bitD, nbBits);
 788
 789     DStatePtr->state = DInfo.newState + lowBits;
 790     return symbol;
 791 }
 792
 793 static BYTE FSE_decodeSymbolFast(FSE_DState_t* DStatePtr, FSE_DStream_t* bitD)
 794 {
 795     const FSE_decode_t DInfo = ((const FSE_decode_t*)(DStatePtr->table))[DStatePtr->state];
 796     const U32 nbBits = DInfo.nbBits;
 797     BYTE symbol = DInfo.symbol;
 798     size_t lowBits = FSE_readBitsFast(bitD, nbBits);
 799
 800     DStatePtr->state = DInfo.newState + lowBits;
 801     return symbol;
 802 }
 803
 804 /* FSE_endOfDStream
 805    Tells if bitD has reached end of bitStream or not */
 806
 807 static unsigned FSE_endOfDStream(const FSE_DStream_t* bitD)
 808 {
 809     return ((bitD->ptr == bitD->start) && (bitD->bitsConsumed == sizeof(bitD->bitContainer)*8));
 810 }
 811
 812 static unsigned FSE_endOfDState(const FSE_DState_t* DStatePtr)
 813 {
 814     return DStatePtr->state == 0;
 815 }
 816
 817
 818 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(
 819           void* dst, size_t maxDstSize,
 820     const void* cSrc, size_t cSrcSize,
 821     const FSE_DTable* dt, const unsigned fast)
 822 {
 823     BYTE* const ostart = (BYTE*) dst;
 824     BYTE* op = ostart;
 825     BYTE* const omax = op + maxDstSize;
 826     BYTE* const olimit = omax-3;
 827
 828     FSE_DStream_t bitD;
 829     FSE_DState_t state1;
 830     FSE_DState_t state2;
 831     size_t errorCode;
 832
 833     /* Init */
 834     errorCode = FSE_initDStream(&bitD, cSrc, cSrcSize);   /* replaced last arg by maxCompressed Size */
 835     if (FSE_isError(errorCode)) return errorCode;
 836
 837     FSE_initDState(&state1, &bitD, dt);
 838     FSE_initDState(&state2, &bitD, dt);
 839
 840 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
 841
 842     /* 4 symbols per loop */
 843     for ( ; (FSE_reloadDStream(&bitD)==FSE_DStream_unfinished) && (op<olimit) ; op+=4)
 844     {
 845         op[0] = FSE_GETSYMBOL(&state1);
 846
 847         if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
 848             FSE_reloadDStream(&bitD);
 849
 850         op[1] = FSE_GETSYMBOL(&state2);
 851
 852         if (FSE_MAX_TABLELOG*4+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
 853             { if (FSE_reloadDStream(&bitD) > FSE_DStream_unfinished) { op+=2; break; } }
 854
 855         op[2] = FSE_GETSYMBOL(&state1);
 856
 857         if (FSE_MAX_TABLELOG*2+7 > sizeof(bitD.bitContainer)*8)    /* This test must be static */
 858             FSE_reloadDStream(&bitD);
 859
 860         op[3] = FSE_GETSYMBOL(&state2);
 861     }
 862
 863     /* tail */
 864     /* note : FSE_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly FSE_DStream_completed */
 865     while (1)
 866     {
 867         if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state1))) )
 868             break;
 869
 870         *op++ = FSE_GETSYMBOL(&state1);
 871
 872         if ( (FSE_reloadDStream(&bitD)>FSE_DStream_completed) || (op==omax) || (FSE_endOfDStream(&bitD) && (fast || FSE_endOfDState(&state2))) )
 873             break;
 874
 875         *op++ = FSE_GETSYMBOL(&state2);
 876     }
 877
 878     /* end ? */
 879     if (FSE_endOfDStream(&bitD) && FSE_endOfDState(&state1) && FSE_endOfDState(&state2))
 880         return op-ostart;
 881
 882     if (op==omax) return (size_t)-FSE_ERROR_dstSize_tooSmall;   /* dst buffer is full, but cSrc unfinished */
 883
 884     return (size_t)-FSE_ERROR_corruptionDetected;
 885 }
 886
 887
 888 static size_t FSE_decompress_usingDTable(void* dst, size_t originalSize,
 889                             const void* cSrc, size_t cSrcSize,
 890                             const FSE_DTable* dt)
 891 {
 892     FSE_DTableHeader DTableH;
 893     memcpy(&DTableH, dt, sizeof(DTableH));   /* memcpy() into local variable, to avoid strict aliasing warning */
 894
 895     /* select fast mode (static) */
 896     if (DTableH.fastMode) return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
 897     return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
 898 }
 899
 900
 901 static size_t FSE_decompress(void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
 902 {
 903     const BYTE* const istart = (const BYTE*)cSrc;
 904     const BYTE* ip = istart;
 905     short counting[FSE_MAX_SYMBOL_VALUE+1];
 906     DTable_max_t dt;   /* Static analyzer seems unable to understand this table will be properly initialized later */
 907     unsigned tableLog;
 908     unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
 909     size_t errorCode;
 910
 911     if (cSrcSize<2) return (size_t)-FSE_ERROR_srcSize_wrong;   /* too small input size */
 912
 913     /* normal FSE decoding mode */
 914     errorCode = FSE_readNCount (counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
 915     if (FSE_isError(errorCode)) return errorCode;
 916     if (errorCode >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong;   /* too small input size */
 917     ip += errorCode;
 918     cSrcSize -= errorCode;
 919
 920     errorCode = FSE_buildDTable (dt, counting, maxSymbolValue, tableLog);
 921     if (FSE_isError(errorCode)) return errorCode;
 922
 923     /* always return, even if it is an error code */
 924     return FSE_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, dt);
 925 }
 926
 927
 928
 929 /* *******************************************************
 930 *  Huff0 : Huffman block compression
 931 *********************************************************/
 932 #define HUF_MAX_SYMBOL_VALUE 255
 933 #define HUF_DEFAULT_TABLELOG  12       /* used by default, when not specified */
 934 #define HUF_MAX_TABLELOG  12           /* max possible tableLog; for allocation purpose; can be modified */
 935 #define HUF_ABSOLUTEMAX_TABLELOG  16   /* absolute limit of HUF_MAX_TABLELOG. Beyond that value, code does not work */
 936 #if (HUF_MAX_TABLELOG > HUF_ABSOLUTEMAX_TABLELOG)
 937 #  error "HUF_MAX_TABLELOG is too large !"
 938 #endif
 939
 940 typedef struct HUF_CElt_s {
 941   U16  val;
 942   BYTE nbBits;
 943 } HUF_CElt ;
 944
 945 typedef struct nodeElt_s {
 946     U32 count;
 947     U16 parent;
 948     BYTE byte;
 949     BYTE nbBits;
 950 } nodeElt;
 951
 952
 953 /* *******************************************************
 954 *  Huff0 : Huffman block decompression
 955 *********************************************************/
 956 typedef struct {
 957     BYTE byte;
 958     BYTE nbBits;
 959 } HUF_DElt;
 960
 961 static size_t HUF_readDTable (U16* DTable, const void* src, size_t srcSize)
 962 {
 963     BYTE huffWeight[HUF_MAX_SYMBOL_VALUE + 1];
 964     U32 rankVal[HUF_ABSOLUTEMAX_TABLELOG + 1];  /* large enough for values from 0 to 16 */
 965     U32 weightTotal;
 966     U32 maxBits;
 967     const BYTE* ip = (const BYTE*) src;
 968     size_t iSize;
 969     size_t oSize;
 970     U32 n;
 971     U32 nextRankStart;
 972     void* ptr = DTable+1;
 973     HUF_DElt* const dt = (HUF_DElt*)ptr;
 974
 975     if (!srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
 976     iSize = ip[0];
 977
 978     FSE_STATIC_ASSERT(sizeof(HUF_DElt) == sizeof(U16));   /* if compilation fails here, assertion is false */
 979     //memset(huffWeight, 0, sizeof(huffWeight));   /* should not be necessary, but some analyzer complain ... */
 980     if (iSize >= 128)  /* special header */
 981     {
 982         if (iSize >= (242))   /* RLE */
 983         {
 984             static int l[14] = { 1, 2, 3, 4, 7, 8, 15, 16, 31, 32, 63, 64, 127, 128 };
 985             oSize = l[iSize-242];
 986             memset(huffWeight, 1, sizeof(huffWeight));
 987             iSize = 0;
 988         }
 989         else   /* Incompressible */
 990         {
 991             oSize = iSize - 127;
 992             iSize = ((oSize+1)/2);
 993             if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
 994             ip += 1;
 995             for (n=0; n<oSize; n+=2)
 996             {
 997                 huffWeight[n]   = ip[n/2] >> 4;
 998                 huffWeight[n+1] = ip[n/2] & 15;
 999             }
1000         }
1001     }
1002     else  /* header compressed with FSE (normal case) */
1003     {
1004         if (iSize+1 > srcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
1005         oSize = FSE_decompress(huffWeight, HUF_MAX_SYMBOL_VALUE, ip+1, iSize);   /* max 255 values decoded, last one is implied */
1006         if (FSE_isError(oSize)) return oSize;
1007     }
1008
1009     /* collect weight stats */
1010     memset(rankVal, 0, sizeof(rankVal));
1011     weightTotal = 0;
1012     for (n=0; n<oSize; n++)
1013     {
1014         if (huffWeight[n] >= HUF_ABSOLUTEMAX_TABLELOG) return (size_t)-FSE_ERROR_corruptionDetected;
1015         rankVal[huffWeight[n]]++;
1016         weightTotal += (1 << huffWeight[n]) >> 1;
1017     }
1018     if (weightTotal == 0) return (size_t)-FSE_ERROR_corruptionDetected;
1019
1020     /* get last non-null symbol weight (implied, total must be 2^n) */
1021     maxBits = FSE_highbit32(weightTotal) + 1;
1022     if (maxBits > DTable[0]) return (size_t)-FSE_ERROR_tableLog_tooLarge;   /* DTable is too small */
1023     DTable[0] = (U16)maxBits;
1024     {
1025         U32 total = 1 << maxBits;
1026         U32 rest = total - weightTotal;
1027         U32 verif = 1 << FSE_highbit32(rest);
1028         U32 lastWeight = FSE_highbit32(rest) + 1;
1029         if (verif != rest) return (size_t)-FSE_ERROR_corruptionDetected;    /* last value must be a clean power of 2 */
1030         huffWeight[oSize] = (BYTE)lastWeight;
1031         rankVal[lastWeight]++;
1032     }
1033
1034     /* check tree construction validity */
1035     if ((rankVal[1] < 2) || (rankVal[1] & 1)) return (size_t)-FSE_ERROR_corruptionDetected;   /* by construction : at least 2 elts of rank 1, must be even */
1036
1037     /* Prepare ranks */
1038     nextRankStart = 0;
1039     for (n=1; n<=maxBits; n++)
1040     {
1041         U32 current = nextRankStart;
1042         nextRankStart += (rankVal[n] << (n-1));
1043         rankVal[n] = current;
1044     }
1045
1046     /* fill DTable */
1047     for (n=0; n<=oSize; n++)
1048     {
1049         const U32 w = huffWeight[n];
1050         const U32 length = (1 << w) >> 1;
1051         U32 i;
1052         HUF_DElt D;
1053         D.byte = (BYTE)n; D.nbBits = (BYTE)(maxBits + 1 - w);
1054         for (i = rankVal[w]; i < rankVal[w] + length; i++)
1055             dt[i] = D;
1056         rankVal[w] += length;
1057     }
1058
1059     return iSize+1;
1060 }
1061
1062
1063 static BYTE HUF_decodeSymbol(FSE_DStream_t* Dstream, const HUF_DElt* dt, const U32 dtLog)
1064 {
1065         const size_t val = FSE_lookBitsFast(Dstream, dtLog); /* note : dtLog >= 1 */
1066         const BYTE c = dt[val].byte;
1067         FSE_skipBits(Dstream, dt[val].nbBits);
1068         return c;
1069 }
1070
1071 static size_t HUF_decompress_usingDTable(   /* -3% slower when non static */
1072           void* dst, size_t maxDstSize,
1073     const void* cSrc, size_t cSrcSize,
1074     const U16* DTable)
1075 {
1076     if (cSrcSize < 6) return (size_t)-FSE_ERROR_srcSize_wrong;
1077     {
1078         BYTE* const ostart = (BYTE*) dst;
1079         BYTE* op = ostart;
1080         BYTE* const omax = op + maxDstSize;
1081         BYTE* const olimit = omax-15;
1082
1083         const void* ptr = DTable;
1084         const HUF_DElt* const dt = (const HUF_DElt*)(ptr)+1;
1085         const U32 dtLog = DTable[0];
1086         size_t errorCode;
1087         U32 reloadStatus;
1088
1089         /* Init */
1090
1091         const U16* jumpTable = (const U16*)cSrc;
1092         const size_t length1 = FSE_readLE16(jumpTable);
1093         const size_t length2 = FSE_readLE16(jumpTable+1);
1094         const size_t length3 = FSE_readLE16(jumpTable+2);
1095         const size_t length4 = cSrcSize - 6 - length1 - length2 - length3;   // check coherency !!
1096         const char* const start1 = (const char*)(cSrc) + 6;
1097         const char* const start2 = start1 + length1;
1098         const char* const start3 = start2 + length2;
1099         const char* const start4 = start3 + length3;
1100         FSE_DStream_t bitD1, bitD2, bitD3, bitD4;
1101
1102         if (length1+length2+length3+6 >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
1103
1104         errorCode = FSE_initDStream(&bitD1, start1, length1);
1105         if (FSE_isError(errorCode)) return errorCode;
1106         errorCode = FSE_initDStream(&bitD2, start2, length2);
1107         if (FSE_isError(errorCode)) return errorCode;
1108         errorCode = FSE_initDStream(&bitD3, start3, length3);
1109         if (FSE_isError(errorCode)) return errorCode;
1110         errorCode = FSE_initDStream(&bitD4, start4, length4);
1111         if (FSE_isError(errorCode)) return errorCode;
1112
1113         reloadStatus=FSE_reloadDStream(&bitD2);
1114
1115         /* 16 symbols per loop */
1116         for ( ; (reloadStatus<FSE_DStream_completed) && (op<olimit);  /* D2-3-4 are supposed to be synchronized and finish together */
1117             op+=16, reloadStatus = FSE_reloadDStream(&bitD2) | FSE_reloadDStream(&bitD3) | FSE_reloadDStream(&bitD4), FSE_reloadDStream(&bitD1))
1118         {
1119     #define HUF_DECODE_SYMBOL_0(n, Dstream) \
1120             op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog);
1121
1122     #define HUF_DECODE_SYMBOL_1(n, Dstream) \
1123             op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog); \
1124             if (FSE_32bits() && (HUF_MAX_TABLELOG>12)) FSE_reloadDStream(&Dstream)
1125
1126     #define HUF_DECODE_SYMBOL_2(n, Dstream) \
1127             op[n] = HUF_decodeSymbol(&Dstream, dt, dtLog); \
1128             if (FSE_32bits()) FSE_reloadDStream(&Dstream)
1129
1130             HUF_DECODE_SYMBOL_1( 0, bitD1);
1131             HUF_DECODE_SYMBOL_1( 1, bitD2);
1132             HUF_DECODE_SYMBOL_1( 2, bitD3);
1133             HUF_DECODE_SYMBOL_1( 3, bitD4);
1134             HUF_DECODE_SYMBOL_2( 4, bitD1);
1135             HUF_DECODE_SYMBOL_2( 5, bitD2);
1136             HUF_DECODE_SYMBOL_2( 6, bitD3);
1137             HUF_DECODE_SYMBOL_2( 7, bitD4);
1138             HUF_DECODE_SYMBOL_1( 8, bitD1);
1139             HUF_DECODE_SYMBOL_1( 9, bitD2);
1140             HUF_DECODE_SYMBOL_1(10, bitD3);
1141             HUF_DECODE_SYMBOL_1(11, bitD4);
1142             HUF_DECODE_SYMBOL_0(12, bitD1);
1143             HUF_DECODE_SYMBOL_0(13, bitD2);
1144             HUF_DECODE_SYMBOL_0(14, bitD3);
1145             HUF_DECODE_SYMBOL_0(15, bitD4);
1146         }
1147
1148         if (reloadStatus!=FSE_DStream_completed)   /* not complete : some bitStream might be FSE_DStream_unfinished */
1149             return (size_t)-FSE_ERROR_corruptionDetected;
1150
1151         /* tail */
1152         {
1153             // bitTail = bitD1;   // *much* slower : -20% !??!
1154             FSE_DStream_t bitTail;
1155             bitTail.ptr = bitD1.ptr;
1156             bitTail.bitsConsumed = bitD1.bitsConsumed;
1157             bitTail.bitContainer = bitD1.bitContainer;   // required in case of FSE_DStream_endOfBuffer
1158             bitTail.start = start1;
1159             for ( ; (FSE_reloadDStream(&bitTail) < FSE_DStream_completed) && (op<omax) ; op++)
1160             {
1161                 HUF_DECODE_SYMBOL_0(0, bitTail);
1162             }
1163
1164             if (FSE_endOfDStream(&bitTail))
1165                 return op-ostart;
1166         }
1167
1168         if (op==omax) return (size_t)-FSE_ERROR_dstSize_tooSmall;   /* dst buffer is full, but cSrc unfinished */
1169
1170         return (size_t)-FSE_ERROR_corruptionDetected;
1171     }
1172 }
1173
1174
1175 static size_t HUF_decompress (void* dst, size_t maxDstSize, const void* cSrc, size_t cSrcSize)
1176 {
1177     HUF_CREATE_STATIC_DTABLE(DTable, HUF_MAX_TABLELOG);
1178     const BYTE* ip = (const BYTE*) cSrc;
1179     size_t errorCode;
1180
1181     errorCode = HUF_readDTable (DTable, cSrc, cSrcSize);
1182     if (FSE_isError(errorCode)) return errorCode;
1183     if (errorCode >= cSrcSize) return (size_t)-FSE_ERROR_srcSize_wrong;
1184     ip += errorCode;
1185     cSrcSize -= errorCode;
1186
1187     return HUF_decompress_usingDTable (dst, maxDstSize, ip, cSrcSize, DTable);
1188 }
1189
1190
1191 #endif   /* FSE_COMMONDEFS_ONLY */
1192
1193 /*
1194     zstd - standard compression library
1195     Copyright (C) 2014-2015, Yann Collet.
1196
1197     BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
1198
1199     Redistribution and use in source and binary forms, with or without
1200     modification, are permitted provided that the following conditions are
1201     met:
1202     * Redistributions of source code must retain the above copyright
1203     notice, this list of conditions and the following disclaimer.
1204     * Redistributions in binary form must reproduce the above
1205     copyright notice, this list of conditions and the following disclaimer
1206     in the documentation and/or other materials provided with the
1207     distribution.
1208     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1209     "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1210     LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1211     A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1212     OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1213     SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1214     LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1215     DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1216     THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1217     (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1218     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1219
1220     You can contact the author at :
1221     - zstd source repository : https://github.com/Cyan4973/zstd
1222     - ztsd public forum : https://groups.google.com/forum/#!forum/lz4c
1223 */
1224
1225 /****************************************************************
1226 *  Tuning parameters
1227 *****************************************************************/
1228 /* MEMORY_USAGE :
1229 *  Memory usage formula : N->2^N Bytes (examples : 10 -> 1KB; 12 -> 4KB ; 16 -> 64KB; 20 -> 1MB; etc.)
1230 *  Increasing memory usage improves compression ratio
1231 *  Reduced memory usage can improve speed, due to cache effect */
1232 #define ZSTD_MEMORY_USAGE 17
1233
1234
1235 /**************************************
1236    CPU Feature Detection
1237 **************************************/
1238 /*
1239  * Automated efficient unaligned memory access detection
1240  * Based on known hardware architectures
1241  * This list will be updated thanks to feedbacks
1242  */
1243 #if defined(CPU_HAS_EFFICIENT_UNALIGNED_MEMORY_ACCESS) \
1244     || defined(__ARM_FEATURE_UNALIGNED) \
1245     || defined(__i386__) || defined(__x86_64__) \
1246     || defined(_M_IX86) || defined(_M_X64) \
1247     || defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_8__) \
1248     || (defined(_M_ARM) && (_M_ARM >= 7))
1249 #  define ZSTD_UNALIGNED_ACCESS 1
1250 #else
1251 #  define ZSTD_UNALIGNED_ACCESS 0
1252 #endif
1253
1254
1255 /********************************************************
1256 *  Includes
1257 *********************************************************/
1258 #include <stdlib.h>      /* calloc */
1259 #include <string.h>      /* memcpy, memmove */
1260 #include <stdio.h>       /* debug : printf */
1261
1262
1263 /********************************************************
1264 *  Compiler specifics
1265 *********************************************************/
1266 #ifdef __AVX2__
1267 #  include <immintrin.h>   /* AVX2 intrinsics */
1268 #endif
1269
1270 #ifdef _MSC_VER    /* Visual Studio */
1271 #  include <intrin.h>                    /* For Visual 2005 */
1272 #  pragma warning(disable : 4127)        /* disable: C4127: conditional expression is constant */
1273 #  pragma warning(disable : 4324)        /* disable: C4324: padded structure */
1274 #endif
1275
1276
1277 #ifndef MEM_ACCESS_MODULE
1278 #define MEM_ACCESS_MODULE
1279 /********************************************************
1280 *  Basic Types
1281 *********************************************************/
1282 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   /* C99 */
1283 # include <stdint.h>
1284 typedef  uint8_t BYTE;
1285 typedef uint16_t U16;
1286 typedef  int16_t S16;
1287 typedef uint32_t U32;
1288 typedef  int32_t S32;
1289 typedef uint64_t U64;
1290 #else
1291 typedef unsigned char       BYTE;
1292 typedef unsigned short      U16;
1293 typedef   signed short      S16;
1294 typedef unsigned int        U32;
1295 typedef   signed int        S32;
1296 typedef unsigned long long  U64;
1297 #endif
1298
1299 #endif   /* MEM_ACCESS_MODULE */
1300
1301
1302 /********************************************************
1303 *  Constants
1304 *********************************************************/
1305 static const U32 ZSTD_magicNumber = 0xFD2FB51E;   /* 3rd version : seqNb header */
1306
1307 #define HASH_LOG (ZSTD_MEMORY_USAGE - 2)
1308 #define HASH_TABLESIZE (1 << HASH_LOG)
1309 #define HASH_MASK (HASH_TABLESIZE - 1)
1310
1311 #define KNUTH 2654435761
1312
1313 #define BIT7 128
1314 #define BIT6  64
1315 #define BIT5  32
1316 #define BIT4  16
1317
1318 #define KB *(1 <<10)
1319 #define MB *(1 <<20)
1320 #define GB *(1U<<30)
1321
1322 #define BLOCKSIZE (128 KB)                 /* define, for static allocation */
1323
1324 #define WORKPLACESIZE (BLOCKSIZE*3)
1325 #define MINMATCH 4
1326 #define MLbits   7
1327 #define LLbits   6
1328 #define Offbits  5
1329 #define MaxML  ((1<<MLbits )-1)
1330 #define MaxLL  ((1<<LLbits )-1)
1331 #define MaxOff ((1<<Offbits)-1)
1332 #define LitFSELog  11
1333 #define MLFSELog   10
1334 #define LLFSELog   10
1335 #define OffFSELog   9
1336 #define MAX(a,b) ((a)<(b)?(b):(a))
1337 #define MaxSeq MAX(MaxLL, MaxML)
1338
1339 #define LITERAL_NOENTROPY 63
1340 #define COMMAND_NOENTROPY 7   /* to remove */
1341
1342 #define ZSTD_CONTENTSIZE_ERROR   (0ULL - 2)
1343
1344 static const size_t ZSTD_blockHeaderSize = 3;
1345 static const size_t ZSTD_frameHeaderSize = 4;
1346
1347
1348 /********************************************************
1349 *  Memory operations
1350 *********************************************************/
1351 static unsigned ZSTD_32bits(void) { return sizeof(void*)==4; }
1352
1353 static unsigned ZSTD_isLittleEndian(void)
1354 {
1355     const union { U32 i; BYTE c[4]; } one = { 1 };   /* don't use static : performance detrimental  */
1356     return one.c[0];
1357 }
1358
1359 static U16    ZSTD_read16(const void* p) { U16 r; memcpy(&r, p, sizeof(r)); return r; }
1360
1361 static void   ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
1362
1363 static void   ZSTD_copy8(void* dst, const void* src) { memcpy(dst, src, 8); }
1364
1365 #define COPY8(d,s)    { ZSTD_copy8(d,s); d+=8; s+=8; }
1366
1367 static void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length)
1368 {
1369     const BYTE* ip = (const BYTE*)src;
1370     BYTE* op = (BYTE*)dst;
1371     BYTE* const oend = op + length;
1372     while (op < oend) COPY8(op, ip);
1373 }
1374
1375 static U16 ZSTD_readLE16(const void* memPtr)
1376 {
1377     if (ZSTD_isLittleEndian()) return ZSTD_read16(memPtr);
1378     else
1379     {
1380         const BYTE* p = (const BYTE*)memPtr;
1381         return (U16)((U16)p[0] + ((U16)p[1]<<8));
1382     }
1383 }
1384
1385 static U32 ZSTD_readLE24(const void* memPtr)
1386 {
1387     return ZSTD_readLE16(memPtr) + (((const BYTE*)memPtr)[2] << 16);
1388 }
1389
1390 static U32 ZSTD_readBE32(const void* memPtr)
1391 {
1392     const BYTE* p = (const BYTE*)memPtr;
1393     return (U32)(((U32)p[0]<<24) + ((U32)p[1]<<16) + ((U32)p[2]<<8) + ((U32)p[3]<<0));
1394 }
1395
1396
1397 /**************************************
1398 *  Local structures
1399 ***************************************/
1400 typedef struct ZSTD_Cctx_s ZSTD_Cctx;
1401
1402 typedef enum { bt_compressed, bt_raw, bt_rle, bt_end } blockType_t;
1403
1404 typedef struct
1405 {
1406     blockType_t blockType;
1407     U32 origSize;
1408 } blockProperties_t;
1409
1410 typedef struct {
1411     void* buffer;
1412     U32*  offsetStart;
1413     U32*  offset;
1414     BYTE* offCodeStart;
1415     BYTE* offCode;
1416     BYTE* litStart;
1417     BYTE* lit;
1418     BYTE* litLengthStart;
1419     BYTE* litLength;
1420     BYTE* matchLengthStart;
1421     BYTE* matchLength;
1422     BYTE* dumpsStart;
1423     BYTE* dumps;
1424 } seqStore_t;
1425
1426
1427 typedef struct ZSTD_Cctx_s
1428 {
1429     const BYTE* base;
1430     U32 current;
1431     U32 nextUpdate;
1432     seqStore_t seqStore;
1433 #ifdef __AVX2__
1434     __m256i hashTable[HASH_TABLESIZE>>3];
1435 #else
1436     U32 hashTable[HASH_TABLESIZE];
1437 #endif
1438     BYTE buffer[WORKPLACESIZE];
1439 } cctxi_t;
1440
1441
1442
1443
1444 /**************************************
1445 *  Error Management
1446 **************************************/
1447 /* published entry point */
1448 unsigned ZSTDv01_isError(size_t code) { return ERR_isError(code); }
1449
1450
1451 /**************************************
1452 *  Tool functions
1453 **************************************/
1454 #define ZSTD_VERSION_MAJOR    0    /* for breaking interface changes  */
1455 #define ZSTD_VERSION_MINOR    1    /* for new (non-breaking) interface capabilities */
1456 #define ZSTD_VERSION_RELEASE  3    /* for tweaks, bug-fixes, or development */
1457 #define ZSTD_VERSION_NUMBER  (ZSTD_VERSION_MAJOR *100*100 + ZSTD_VERSION_MINOR *100 + ZSTD_VERSION_RELEASE)
1458
1459 /**************************************************************
1460 *   Decompression code
1461 **************************************************************/
1462
1463 static size_t ZSTDv01_getcBlockSize(const void* src, size_t srcSize, blockProperties_t* bpPtr)
1464 {
1465     const BYTE* const in = (const BYTE* const)src;
1466     BYTE headerFlags;
1467     U32 cSize;
1468
1469     if (srcSize < 3) return ERROR(srcSize_wrong);
1470
1471     headerFlags = *in;
1472     cSize = in[2] + (in[1]<<8) + ((in[0] & 7)<<16);
1473
1474     bpPtr->blockType = (blockType_t)(headerFlags >> 6);
1475     bpPtr->origSize = (bpPtr->blockType == bt_rle) ? cSize : 0;
1476
1477     if (bpPtr->blockType == bt_end) return 0;
1478     if (bpPtr->blockType == bt_rle) return 1;
1479     return cSize;
1480 }
1481
1482
1483 static size_t ZSTD_copyUncompressedBlock(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
1484 {
1485     if (srcSize > maxDstSize) return ERROR(dstSize_tooSmall);
1486     memcpy(dst, src, srcSize);
1487     return srcSize;
1488 }
1489
1490
1491 static size_t ZSTD_decompressLiterals(void* ctx,
1492                                       void* dst, size_t maxDstSize,
1493                                 const void* src, size_t srcSize)
1494 {
1495     BYTE* op = (BYTE*)dst;
1496     BYTE* const oend = op + maxDstSize;
1497     const BYTE* ip = (const BYTE*)src;
1498     size_t errorCode;
1499     size_t litSize;
1500
1501     /* check : minimum 2, for litSize, +1, for content */
1502     if (srcSize <= 3) return ERROR(corruption_detected);
1503
1504     litSize = ip[1] + (ip[0]<<8);
1505     litSize += ((ip[-3] >> 3) & 7) << 16;   // mmmmh....
1506     op = oend - litSize;
1507
1508     (void)ctx;
1509     if (litSize > maxDstSize) return ERROR(dstSize_tooSmall);
1510     errorCode = HUF_decompress(op, litSize, ip+2, srcSize-2);
1511     if (FSE_isError(errorCode)) return ERROR(GENERIC);
1512     return litSize;
1513 }
1514
1515
1516 static size_t ZSTDv01_decodeLiteralsBlock(void* ctx,
1517                                 void* dst, size_t maxDstSize,
1518                           const BYTE** litStart, size_t* litSize,
1519                           const void* src, size_t srcSize)
1520 {
1521     const BYTE* const istart = (const BYTE* const)src;
1522     const BYTE* ip = istart;
1523     BYTE* const ostart = (BYTE* const)dst;
1524     BYTE* const oend = ostart + maxDstSize;
1525     blockProperties_t litbp;
1526
1527     size_t litcSize = ZSTDv01_getcBlockSize(src, srcSize, &litbp);
1528     if (ZSTDv01_isError(litcSize)) return litcSize;
1529     if (litcSize > srcSize - ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
1530     ip += ZSTD_blockHeaderSize;
1531
1532     switch(litbp.blockType)
1533     {
1534     case bt_raw:
1535         *litStart = ip;
1536         ip += litcSize;
1537         *litSize = litcSize;
1538         break;
1539     case bt_rle:
1540         {
1541             size_t rleSize = litbp.origSize;
1542             if (rleSize>maxDstSize) return ERROR(dstSize_tooSmall);
1543             if (!srcSize) return ERROR(srcSize_wrong);
1544             memset(oend - rleSize, *ip, rleSize);
1545             *litStart = oend - rleSize;
1546             *litSize = rleSize;
1547             ip++;
1548             break;
1549         }
1550     case bt_compressed:
1551         {
1552             size_t decodedLitSize = ZSTD_decompressLiterals(ctx, dst, maxDstSize, ip, litcSize);
1553             if (ZSTDv01_isError(decodedLitSize)) return decodedLitSize;
1554             *litStart = oend - decodedLitSize;
1555             *litSize = decodedLitSize;
1556             ip += litcSize;
1557             break;
1558         }
1559     case bt_end:
1560     default:
1561         return ERROR(GENERIC);
1562     }
1563
1564     return ip-istart;
1565 }
1566
1567
1568 static size_t ZSTDv01_decodeSeqHeaders(int* nbSeq, const BYTE** dumpsPtr, size_t* dumpsLengthPtr,
1569                          FSE_DTable* DTableLL, FSE_DTable* DTableML, FSE_DTable* DTableOffb,
1570                          const void* src, size_t srcSize)
1571 {
1572     const BYTE* const istart = (const BYTE* const)src;
1573     const BYTE* ip = istart;
1574     const BYTE* const iend = istart + srcSize;
1575     U32 LLtype, Offtype, MLtype;
1576     U32 LLlog, Offlog, MLlog;
1577     size_t dumpsLength;
1578
1579     /* check */
1580     if (srcSize < 5) return ERROR(srcSize_wrong);
1581
1582     /* SeqHead */
1583     *nbSeq = ZSTD_readLE16(ip); ip+=2;
1584     LLtype  = *ip >> 6;
1585     Offtype = (*ip >> 4) & 3;
1586     MLtype  = (*ip >> 2) & 3;
1587     if (*ip & 2)
1588     {
1589         dumpsLength  = ip[2];
1590         dumpsLength += ip[1] << 8;
1591         ip += 3;
1592     }
1593     else
1594     {
1595         dumpsLength  = ip[1];
1596         dumpsLength += (ip[0] & 1) << 8;
1597         ip += 2;
1598     }
1599     *dumpsPtr = ip;
1600     ip += dumpsLength;
1601     *dumpsLengthPtr = dumpsLength;
1602
1603     /* check */
1604     if (ip > iend-3) return ERROR(srcSize_wrong); /* min : all 3 are "raw", hence no header, but at least xxLog bits per type */
1605
1606     /* sequences */
1607     {
1608         S16 norm[MaxML+1];    /* assumption : MaxML >= MaxLL and MaxOff */
1609         size_t headerSize;
1610
1611         /* Build DTables */
1612         switch(LLtype)
1613         {
1614         case bt_rle :
1615             LLlog = 0;
1616             FSE_buildDTable_rle(DTableLL, *ip++); break;
1617         case bt_raw :
1618             LLlog = LLbits;
1619             FSE_buildDTable_raw(DTableLL, LLbits); break;
1620         default :
1621             {   U32 max = MaxLL;
1622                 headerSize = FSE_readNCount(norm, &max, &LLlog, ip, iend-ip);
1623                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
1624                 if (LLlog > LLFSELog) return ERROR(corruption_detected);
1625                 ip += headerSize;
1626                 FSE_buildDTable(DTableLL, norm, max, LLlog);
1627         }   }
1628
1629         switch(Offtype)
1630         {
1631         case bt_rle :
1632             Offlog = 0;
1633             if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
1634             FSE_buildDTable_rle(DTableOffb, *ip++); break;
1635         case bt_raw :
1636             Offlog = Offbits;
1637             FSE_buildDTable_raw(DTableOffb, Offbits); break;
1638         default :
1639             {   U32 max = MaxOff;
1640                 headerSize = FSE_readNCount(norm, &max, &Offlog, ip, iend-ip);
1641                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
1642                 if (Offlog > OffFSELog) return ERROR(corruption_detected);
1643                 ip += headerSize;
1644                 FSE_buildDTable(DTableOffb, norm, max, Offlog);
1645         }   }
1646
1647         switch(MLtype)
1648         {
1649         case bt_rle :
1650             MLlog = 0;
1651             if (ip > iend-2) return ERROR(srcSize_wrong); /* min : "raw", hence no header, but at least xxLog bits */
1652             FSE_buildDTable_rle(DTableML, *ip++); break;
1653         case bt_raw :
1654             MLlog = MLbits;
1655             FSE_buildDTable_raw(DTableML, MLbits); break;
1656         default :
1657             {   U32 max = MaxML;
1658                 headerSize = FSE_readNCount(norm, &max, &MLlog, ip, iend-ip);
1659                 if (FSE_isError(headerSize)) return ERROR(GENERIC);
1660                 if (MLlog > MLFSELog) return ERROR(corruption_detected);
1661                 ip += headerSize;
1662                 FSE_buildDTable(DTableML, norm, max, MLlog);
1663     }   }   }
1664
1665     return ip-istart;
1666 }
1667
1668
1669 typedef struct {
1670     size_t litLength;
1671     size_t offset;
1672     size_t matchLength;
1673 } seq_t;
1674
1675 typedef struct {
1676     FSE_DStream_t DStream;
1677     FSE_DState_t stateLL;
1678     FSE_DState_t stateOffb;
1679     FSE_DState_t stateML;
1680     size_t prevOffset;
1681     const BYTE* dumps;
1682     const BYTE* dumpsEnd;
1683 } seqState_t;
1684
1685
1686 static void ZSTD_decodeSequence(seq_t* seq, seqState_t* seqState)
1687 {
1688     size_t litLength;
1689     size_t prevOffset;
1690     size_t offset;
1691     size_t matchLength;
1692     const BYTE* dumps = seqState->dumps;
1693     const BYTE* const de = seqState->dumpsEnd;
1694
1695     /* Literal length */
1696     litLength = FSE_decodeSymbol(&(seqState->stateLL), &(seqState->DStream));
1697     prevOffset = litLength ? seq->offset : seqState->prevOffset;
1698     seqState->prevOffset = seq->offset;
1699     if (litLength == MaxLL)
1700     {
1701         const U32 add = dumps<de ? *dumps++ : 0;
1702         if (add < 255) litLength += add;
1703         else
1704         {
1705             if (dumps<=(de-3))
1706             {
1707                 litLength = ZSTD_readLE24(dumps);
1708                 dumps += 3;
1709             }
1710         }
1711     }
1712
1713     /* Offset */
1714     {
1715         U32 offsetCode, nbBits;
1716         offsetCode = FSE_decodeSymbol(&(seqState->stateOffb), &(seqState->DStream));
1717         if (ZSTD_32bits()) FSE_reloadDStream(&(seqState->DStream));
1718         nbBits = offsetCode - 1;
1719         if (offsetCode==0) nbBits = 0;   /* cmove */
1720         offset = ((size_t)1 << (nbBits & ((sizeof(offset)*8)-1))) + FSE_readBits(&(seqState->DStream), nbBits);
1721         if (ZSTD_32bits()) FSE_reloadDStream(&(seqState->DStream));
1722         if (offsetCode==0) offset = prevOffset;
1723     }
1724
1725     /* MatchLength */
1726     matchLength = FSE_decodeSymbol(&(seqState->stateML), &(seqState->DStream));
1727     if (matchLength == MaxML)
1728     {
1729         const U32 add = dumps<de ? *dumps++ : 0;
1730         if (add < 255) matchLength += add;
1731         else
1732         {
1733             if (dumps<=(de-3))
1734             {
1735                 matchLength = ZSTD_readLE24(dumps);
1736                 dumps += 3;
1737             }
1738         }
1739     }
1740     matchLength += MINMATCH;
1741
1742     /* save result */
1743     seq->litLength = litLength;
1744     seq->offset = offset;
1745     seq->matchLength = matchLength;
1746     seqState->dumps = dumps;
1747 }
1748
1749
1750 static size_t ZSTD_execSequence(BYTE* op,
1751                                 seq_t sequence,
1752                                 const BYTE** litPtr, const BYTE* const litLimit,
1753                                 BYTE* const base, BYTE* const oend)
1754 {
1755     static const int dec32table[] = {0, 1, 2, 1, 4, 4, 4, 4};   /* added */
1756     static const int dec64table[] = {8, 8, 8, 7, 8, 9,10,11};   /* subtracted */
1757     const BYTE* const ostart = op;
1758     const size_t litLength = sequence.litLength;
1759     BYTE* const endMatch = op + litLength + sequence.matchLength;    /* risk : address space overflow (32-bits) */
1760     const BYTE* const litEnd = *litPtr + litLength;
1761
1762     /* check */
1763     if (endMatch > oend) return ERROR(dstSize_tooSmall);   /* overwrite beyond dst buffer */
1764     if (litEnd > litLimit) return ERROR(corruption_detected);
1765     if (sequence.matchLength > (size_t)(*litPtr-op))  return ERROR(dstSize_tooSmall);    /* overwrite literal segment */
1766
1767     /* copy Literals */
1768     if (((size_t)(*litPtr - op) < 8) || ((size_t)(oend-litEnd) < 8) || (op+litLength > oend-8))
1769         memmove(op, *litPtr, litLength);   /* overwrite risk */
1770     else
1771         ZSTD_wildcopy(op, *litPtr, litLength);
1772     op += litLength;
1773     *litPtr = litEnd;   /* update for next sequence */
1774
1775     /* check : last match must be at a minimum distance of 8 from end of dest buffer */
1776     if (oend-op < 8) return ERROR(dstSize_tooSmall);
1777
1778     /* copy Match */
1779     {
1780         const U32 overlapRisk = (((size_t)(litEnd - endMatch)) < 12);
1781         const BYTE* match = op - sequence.offset;            /* possible underflow at op - offset ? */
1782         size_t qutt = 12;
1783         U64 saved[2];
1784
1785         /* check */
1786         if (match < base) return ERROR(corruption_detected);
1787         if (sequence.offset > (size_t)base) return ERROR(corruption_detected);
1788
1789         /* save beginning of literal sequence, in case of write overlap */
1790         if (overlapRisk)
1791         {
1792             if ((endMatch + qutt) > oend) qutt = oend-endMatch;
1793             memcpy(saved, endMatch, qutt);
1794         }
1795
1796         if (sequence.offset < 8)
1797         {
1798             const int dec64 = dec64table[sequence.offset];
1799             op[0] = match[0];
1800             op[1] = match[1];
1801             op[2] = match[2];
1802             op[3] = match[3];
1803             match += dec32table[sequence.offset];
1804             ZSTD_copy4(op+4, match);
1805             match -= dec64;
1806         } else { ZSTD_copy8(op, match); }
1807         op += 8; match += 8;
1808
1809         if (endMatch > oend-(16-MINMATCH))
1810         {
1811             if (op < oend-8)
1812             {
1813                 ZSTD_wildcopy(op, match, (oend-8) - op);
1814                 match += (oend-8) - op;
1815                 op = oend-8;
1816             }
1817             while (op<endMatch) *op++ = *match++;
1818         }
1819         else
1820             ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
1821
1822         /* restore, in case of overlap */
1823         if (overlapRisk) memcpy(endMatch, saved, qutt);
1824     }
1825
1826     return endMatch-ostart;
1827 }
1828
1829 typedef struct ZSTDv01_Dctx_s
1830 {
1831     U32 LLTable[FSE_DTABLE_SIZE_U32(LLFSELog)];
1832     U32 OffTable[FSE_DTABLE_SIZE_U32(OffFSELog)];
1833     U32 MLTable[FSE_DTABLE_SIZE_U32(MLFSELog)];
1834     void* previousDstEnd;
1835     void* base;
1836     size_t expected;
1837     blockType_t bType;
1838     U32 phase;
1839 } dctx_t;
1840
1841
1842 static size_t ZSTD_decompressSequences(
1843                                void* ctx,
1844                                void* dst, size_t maxDstSize,
1845                          const void* seqStart, size_t seqSize,
1846                          const BYTE* litStart, size_t litSize)
1847 {
1848     dctx_t* dctx = (dctx_t*)ctx;
1849     const BYTE* ip = (const BYTE*)seqStart;
1850     const BYTE* const iend = ip + seqSize;
1851     BYTE* const ostart = (BYTE* const)dst;
1852     BYTE* op = ostart;
1853     BYTE* const oend = ostart + maxDstSize;
1854     size_t errorCode, dumpsLength;
1855     const BYTE* litPtr = litStart;
1856     const BYTE* const litEnd = litStart + litSize;
1857     int nbSeq;
1858     const BYTE* dumps;
1859     U32* DTableLL = dctx->LLTable;
1860     U32* DTableML = dctx->MLTable;
1861     U32* DTableOffb = dctx->OffTable;
1862     BYTE* const base = (BYTE*) (dctx->base);
1863
1864     /* Build Decoding Tables */
1865     errorCode = ZSTDv01_decodeSeqHeaders(&nbSeq, &dumps, &dumpsLength,
1866                                       DTableLL, DTableML, DTableOffb,
1867                                       ip, iend-ip);
1868     if (ZSTDv01_isError(errorCode)) return errorCode;
1869     ip += errorCode;
1870
1871     /* Regen sequences */
1872     {
1873         seq_t sequence;
1874         seqState_t seqState;
1875
1876         memset(&sequence, 0, sizeof(sequence));
1877         seqState.dumps = dumps;
1878         seqState.dumpsEnd = dumps + dumpsLength;
1879         seqState.prevOffset = 1;
1880         errorCode = FSE_initDStream(&(seqState.DStream), ip, iend-ip);
1881         if (FSE_isError(errorCode)) return ERROR(corruption_detected);
1882         FSE_initDState(&(seqState.stateLL), &(seqState.DStream), DTableLL);
1883         FSE_initDState(&(seqState.stateOffb), &(seqState.DStream), DTableOffb);
1884         FSE_initDState(&(seqState.stateML), &(seqState.DStream), DTableML);
1885
1886         for ( ; (FSE_reloadDStream(&(seqState.DStream)) <= FSE_DStream_completed) && (nbSeq>0) ; )
1887         {
1888             size_t oneSeqSize;
1889             nbSeq--;
1890             ZSTD_decodeSequence(&sequence, &seqState);
1891             oneSeqSize = ZSTD_execSequence(op, sequence, &litPtr, litEnd, base, oend);
1892             if (ZSTDv01_isError(oneSeqSize)) return oneSeqSize;
1893             op += oneSeqSize;
1894         }
1895
1896         /* check if reached exact end */
1897         if ( !FSE_endOfDStream(&(seqState.DStream)) ) return ERROR(corruption_detected);   /* requested too much : data is corrupted */
1898         if (nbSeq<0) return ERROR(corruption_detected);   /* requested too many sequences : data is corrupted */
1899
1900         /* last literal segment */
1901         {
1902             size_t lastLLSize = litEnd - litPtr;
1903             if (op+lastLLSize > oend) return ERROR(dstSize_tooSmall);
1904             if (op != litPtr) memmove(op, litPtr, lastLLSize);
1905             op += lastLLSize;
1906         }
1907     }
1908
1909     return op-ostart;
1910 }
1911
1912
1913 static size_t ZSTD_decompressBlock(
1914                             void* ctx,
1915                             void* dst, size_t maxDstSize,
1916                       const void* src, size_t srcSize)
1917 {
1918     /* blockType == blockCompressed, srcSize is trusted */
1919     const BYTE* ip = (const BYTE*)src;
1920     const BYTE* litPtr = NULL;
1921     size_t litSize = 0;
1922     size_t errorCode;
1923
1924     /* Decode literals sub-block */
1925     errorCode = ZSTDv01_decodeLiteralsBlock(ctx, dst, maxDstSize, &litPtr, &litSize, src, srcSize);
1926     if (ZSTDv01_isError(errorCode)) return errorCode;
1927     ip += errorCode;
1928     srcSize -= errorCode;
1929
1930     return ZSTD_decompressSequences(ctx, dst, maxDstSize, ip, srcSize, litPtr, litSize);
1931 }
1932
1933
1934 size_t ZSTDv01_decompressDCtx(void* ctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
1935 {
1936     const BYTE* ip = (const BYTE*)src;
1937     const BYTE* iend = ip + srcSize;
1938     BYTE* const ostart = (BYTE* const)dst;
1939     BYTE* op = ostart;
1940     BYTE* const oend = ostart + maxDstSize;
1941     size_t remainingSize = srcSize;
1942     U32 magicNumber;
1943     size_t errorCode=0;
1944     blockProperties_t blockProperties;
1945
1946     /* Frame Header */
1947     if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
1948     magicNumber = ZSTD_readBE32(src);
1949     if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
1950     ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
1951
1952     /* Loop on each block */
1953     while (1)
1954     {
1955         size_t blockSize = ZSTDv01_getcBlockSize(ip, iend-ip, &blockProperties);
1956         if (ZSTDv01_isError(blockSize)) return blockSize;
1957
1958         ip += ZSTD_blockHeaderSize;
1959         remainingSize -= ZSTD_blockHeaderSize;
1960         if (blockSize > remainingSize) return ERROR(srcSize_wrong);
1961
1962         switch(blockProperties.blockType)
1963         {
1964         case bt_compressed:
1965             errorCode = ZSTD_decompressBlock(ctx, op, oend-op, ip, blockSize);
1966             break;
1967         case bt_raw :
1968             errorCode = ZSTD_copyUncompressedBlock(op, oend-op, ip, blockSize);
1969             break;
1970         case bt_rle :
1971             return ERROR(GENERIC);   /* not yet supported */
1972             break;
1973         case bt_end :
1974             /* end of frame */
1975             if (remainingSize) return ERROR(srcSize_wrong);
1976             break;
1977         default:
1978             return ERROR(GENERIC);
1979         }
1980         if (blockSize == 0) break;   /* bt_end */
1981
1982         if (ZSTDv01_isError(errorCode)) return errorCode;
1983         op += errorCode;
1984         ip += blockSize;
1985         remainingSize -= blockSize;
1986     }
1987
1988     return op-ostart;
1989 }
1990
1991 size_t ZSTDv01_decompress(void* dst, size_t maxDstSize, const void* src, size_t srcSize)
1992 {
1993     dctx_t ctx;
1994     ctx.base = dst;
1995     return ZSTDv01_decompressDCtx(&ctx, dst, maxDstSize, src, srcSize);
1996 }
1997
1998 /* ZSTD_errorFrameSizeInfoLegacy() :
1999    assumes `cSize` and `dBound` are _not_ NULL */
2000 static void ZSTD_errorFrameSizeInfoLegacy(size_t* cSize, unsigned long long* dBound, size_t ret)
2001 {
2002     *cSize = ret;
2003     *dBound = ZSTD_CONTENTSIZE_ERROR;
2004 }
2005
2006 void ZSTDv01_findFrameSizeInfoLegacy(const void *src, size_t srcSize, size_t* cSize, unsigned long long* dBound)
2007 {
2008     const BYTE* ip = (const BYTE*)src;
2009     size_t remainingSize = srcSize;
2010     size_t nbBlocks = 0;
2011     U32 magicNumber;
2012     blockProperties_t blockProperties;
2013
2014     /* Frame Header */
2015     if (srcSize < ZSTD_frameHeaderSize+ZSTD_blockHeaderSize) {
2016         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2017         return;
2018     }
2019     magicNumber = ZSTD_readBE32(src);
2020     if (magicNumber != ZSTD_magicNumber) {
2021         ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(prefix_unknown));
2022         return;
2023     }
2024     ip += ZSTD_frameHeaderSize; remainingSize -= ZSTD_frameHeaderSize;
2025
2026     /* Loop on each block */
2027     while (1)
2028     {
2029         size_t blockSize = ZSTDv01_getcBlockSize(ip, remainingSize, &blockProperties);
2030         if (ZSTDv01_isError(blockSize)) {
2031             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, blockSize);
2032             return;
2033         }
2034
2035         ip += ZSTD_blockHeaderSize;
2036         remainingSize -= ZSTD_blockHeaderSize;
2037         if (blockSize > remainingSize) {
2038             ZSTD_errorFrameSizeInfoLegacy(cSize, dBound, ERROR(srcSize_wrong));
2039             return;
2040         }
2041
2042         if (blockSize == 0) break;   /* bt_end */
2043
2044         ip += blockSize;
2045         remainingSize -= blockSize;
2046         nbBlocks++;
2047     }
2048
2049     *cSize = ip - (const BYTE*)src;
2050     *dBound = nbBlocks * BLOCKSIZE;
2051 }
2052
2053 /*******************************
2054 *  Streaming Decompression API
2055 *******************************/
2056
2057 size_t ZSTDv01_resetDCtx(ZSTDv01_Dctx* dctx)
2058 {
2059     dctx->expected = ZSTD_frameHeaderSize;
2060     dctx->phase = 0;
2061     dctx->previousDstEnd = NULL;
2062     dctx->base = NULL;
2063     return 0;
2064 }
2065
2066 ZSTDv01_Dctx* ZSTDv01_createDCtx(void)
2067 {
2068     ZSTDv01_Dctx* dctx = (ZSTDv01_Dctx*)malloc(sizeof(ZSTDv01_Dctx));
2069     if (dctx==NULL) return NULL;
2070     ZSTDv01_resetDCtx(dctx);
2071     return dctx;
2072 }
2073
2074 size_t ZSTDv01_freeDCtx(ZSTDv01_Dctx* dctx)
2075 {
2076     free(dctx);
2077     return 0;
2078 }
2079
2080 size_t ZSTDv01_nextSrcSizeToDecompress(ZSTDv01_Dctx* dctx)
2081 {
2082     return ((dctx_t*)dctx)->expected;
2083 }
2084
2085 size_t ZSTDv01_decompressContinue(ZSTDv01_Dctx* dctx, void* dst, size_t maxDstSize, const void* src, size_t srcSize)
2086 {
2087     dctx_t* ctx = (dctx_t*)dctx;
2088
2089     /* Sanity check */
2090     if (srcSize != ctx->expected) return ERROR(srcSize_wrong);
2091     if (dst != ctx->previousDstEnd)  /* not contiguous */
2092         ctx->base = dst;
2093
2094     /* Decompress : frame header */
2095     if (ctx->phase == 0)
2096     {
2097         /* Check frame magic header */
2098         U32 magicNumber = ZSTD_readBE32(src);
2099         if (magicNumber != ZSTD_magicNumber) return ERROR(prefix_unknown);
2100         ctx->phase = 1;
2101         ctx->expected = ZSTD_blockHeaderSize;
2102         return 0;
2103     }
2104
2105     /* Decompress : block header */
2106     if (ctx->phase == 1)
2107     {
2108         blockProperties_t bp;
2109         size_t blockSize = ZSTDv01_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
2110         if (ZSTDv01_isError(blockSize)) return blockSize;
2111         if (bp.blockType == bt_end)
2112         {
2113             ctx->expected = 0;
2114             ctx->phase = 0;
2115         }
2116         else
2117         {
2118             ctx->expected = blockSize;
2119             ctx->bType = bp.blockType;
2120             ctx->phase = 2;
2121         }
2122
2123         return 0;
2124     }
2125
2126     /* Decompress : block content */
2127     {
2128         size_t rSize;
2129         switch(ctx->bType)
2130         {
2131         case bt_compressed:
2132             rSize = ZSTD_decompressBlock(ctx, dst, maxDstSize, src, srcSize);
2133             break;
2134         case bt_raw :
2135             rSize = ZSTD_copyUncompressedBlock(dst, maxDstSize, src, srcSize);
2136             break;
2137         case bt_rle :
2138             return ERROR(GENERIC);   /* not yet handled */
2139             break;
2140         case bt_end :   /* should never happen (filtered at phase 1) */
2141             rSize = 0;
2142             break;
2143         default:
2144             return ERROR(GENERIC);
2145         }
2146         ctx->phase = 1;
2147         ctx->expected = ZSTD_blockHeaderSize;
2148         ctx->previousDstEnd = (void*)( ((char*)dst) + rSize);
2149         return rSize;
2150     }
2151
2152 }