sys/contrib/zstd/lib/decompress/zstd_decompress.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 *  Tuning parameters
  14 *****************************************************************/
  15 /*!
  16  * HEAPMODE :
  17  * Select how default decompression function ZSTD_decompress() allocates its context,
  18  * on stack (0), or into heap (1, default; requires malloc()).
  19  * Note that functions with explicit context such as ZSTD_decompressDCtx() are unaffected.
  20  */
  21 #ifndef ZSTD_HEAPMODE
  22 #  define ZSTD_HEAPMODE 1
  23 #endif
  24
  25 /*!
  26 *  LEGACY_SUPPORT :
  27 *  if set to 1+, ZSTD_decompress() can decode older formats (v0.1+)
  28 */
  29 #ifndef ZSTD_LEGACY_SUPPORT
  30 #  define ZSTD_LEGACY_SUPPORT 0
  31 #endif
  32
  33 /*!
  34  *  MAXWINDOWSIZE_DEFAULT :
  35  *  maximum window size accepted by DStream __by default__.
  36  *  Frames requiring more memory will be rejected.
  37  *  It's possible to set a different limit using ZSTD_DCtx_setMaxWindowSize().
  38  */
  39 #ifndef ZSTD_MAXWINDOWSIZE_DEFAULT
  40 #  define ZSTD_MAXWINDOWSIZE_DEFAULT (((U32)1 << ZSTD_WINDOWLOG_DEFAULTMAX) + 1)
  41 #endif
  42
  43 /*!
  44  *  NO_FORWARD_PROGRESS_MAX :
  45  *  maximum allowed nb of calls to ZSTD_decompressStream() and ZSTD_decompress_generic()
  46  *  without any forward progress
  47  *  (defined as: no byte read from input, and no byte flushed to output)
  48  *  before triggering an error.
  49  */
  50 #ifndef ZSTD_NO_FORWARD_PROGRESS_MAX
  51 #  define ZSTD_NO_FORWARD_PROGRESS_MAX 16
  52 #endif
  53
  54
  55 /*-*******************************************************
  56 *  Dependencies
  57 *********************************************************/
  58 #include <string.h>      /* memcpy, memmove, memset */
  59 #include "compiler.h"    /* prefetch */
  60 #include "cpu.h"         /* bmi2 */
  61 #include "mem.h"         /* low level memory routines */
  62 #define FSE_STATIC_LINKING_ONLY
  63 #include "fse.h"
  64 #define HUF_STATIC_LINKING_ONLY
  65 #include "huf.h"
  66 #include "zstd_internal.h"
  67
  68 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
  69 #  include "zstd_legacy.h"
  70 #endif
  71
  72 static const void* ZSTD_DDictDictContent(const ZSTD_DDict* ddict);
  73 static size_t ZSTD_DDictDictSize(const ZSTD_DDict* ddict);
  74
  75
  76 /*-*************************************
  77 *  Errors
  78 ***************************************/
  79 #define ZSTD_isError ERR_isError   /* for inlining */
  80 #define FSE_isError  ERR_isError
  81 #define HUF_isError  ERR_isError
  82
  83
  84 /*_*******************************************************
  85 *  Memory operations
  86 **********************************************************/
  87 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
  88
  89
  90 /*-*************************************************************
  91 *   Context management
  92 ***************************************************************/
  93 typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
  94                ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
  95                ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,
  96                ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;
  97
  98 typedef enum { zdss_init=0, zdss_loadHeader,
  99                zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
 100
 101
 102 typedef struct {
 103     U32 fastMode;
 104     U32 tableLog;
 105 } ZSTD_seqSymbol_header;
 106
 107 typedef struct {
 108     U16  nextState;
 109     BYTE nbAdditionalBits;
 110     BYTE nbBits;
 111     U32  baseValue;
 112 } ZSTD_seqSymbol;
 113
 114 #define SEQSYMBOL_TABLE_SIZE(log)   (1 + (1 << (log)))
 115
 116 typedef struct {
 117     ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)];    /* Note : Space reserved for FSE Tables */
 118     ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)];   /* is also used as temporary workspace while building hufTable during DDict creation */
 119     ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)];    /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */
 120     HUF_DTable hufTable[HUF_DTABLE_SIZE(HufLog)];  /* can accommodate HUF_decompress4X */
 121     U32 rep[ZSTD_REP_NUM];
 122 } ZSTD_entropyDTables_t;
 123
 124 struct ZSTD_DCtx_s
 125 {
 126     const ZSTD_seqSymbol* LLTptr;
 127     const ZSTD_seqSymbol* MLTptr;
 128     const ZSTD_seqSymbol* OFTptr;
 129     const HUF_DTable* HUFptr;
 130     ZSTD_entropyDTables_t entropy;
 131     U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32];   /* space needed when building huffman tables */
 132     const void* previousDstEnd;   /* detect continuity */
 133     const void* prefixStart;      /* start of current segment */
 134     const void* virtualStart;     /* virtual start of previous segment if it was just before current one */
 135     const void* dictEnd;          /* end of previous segment */
 136     size_t expected;
 137     ZSTD_frameHeader fParams;
 138     U64 decodedSize;
 139     blockType_e bType;            /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */
 140     ZSTD_dStage stage;
 141     U32 litEntropy;
 142     U32 fseEntropy;
 143     XXH64_state_t xxhState;
 144     size_t headerSize;
 145     ZSTD_format_e format;
 146     const BYTE* litPtr;
 147     ZSTD_customMem customMem;
 148     size_t litSize;
 149     size_t rleSize;
 150     size_t staticSize;
 151     int bmi2;                     /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
 152
 153     /* dictionary */
 154     ZSTD_DDict* ddictLocal;
 155     const ZSTD_DDict* ddict;     /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */
 156     U32 dictID;
 157     int ddictIsCold;             /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */
 158
 159     /* streaming */
 160     ZSTD_dStreamStage streamStage;
 161     char*  inBuff;
 162     size_t inBuffSize;
 163     size_t inPos;
 164     size_t maxWindowSize;
 165     char*  outBuff;
 166     size_t outBuffSize;
 167     size_t outStart;
 168     size_t outEnd;
 169     size_t lhSize;
 170     void* legacyContext;
 171     U32 previousLegacyVersion;
 172     U32 legacyVersion;
 173     U32 hostageByte;
 174     int noForwardProgress;
 175
 176     /* workspace */
 177     BYTE litBuffer[ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH];
 178     BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
 179 };  /* typedef'd to ZSTD_DCtx within "zstd.h" */
 180
 181 size_t ZSTD_sizeof_DCtx (const ZSTD_DCtx* dctx)
 182 {
 183     if (dctx==NULL) return 0;   /* support sizeof NULL */
 184     return sizeof(*dctx)
 185            + ZSTD_sizeof_DDict(dctx->ddictLocal)
 186            + dctx->inBuffSize + dctx->outBuffSize;
 187 }
 188
 189 size_t ZSTD_estimateDCtxSize(void) { return sizeof(ZSTD_DCtx); }
 190
 191
 192 static size_t ZSTD_startingInputLength(ZSTD_format_e format)
 193 {
 194     size_t const startingInputLength = (format==ZSTD_f_zstd1_magicless) ?
 195                     ZSTD_frameHeaderSize_prefix - ZSTD_FRAMEIDSIZE :
 196                     ZSTD_frameHeaderSize_prefix;
 197     ZSTD_STATIC_ASSERT(ZSTD_FRAMEHEADERSIZE_PREFIX >= ZSTD_FRAMEIDSIZE);
 198     /* only supports formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless */
 199     assert( (format == ZSTD_f_zstd1) || (format == ZSTD_f_zstd1_magicless) );
 200     return startingInputLength;
 201 }
 202
 203 static void ZSTD_initDCtx_internal(ZSTD_DCtx* dctx)
 204 {
 205     dctx->format = ZSTD_f_zstd1;  /* ZSTD_decompressBegin() invokes ZSTD_startingInputLength() with argument dctx->format */
 206     dctx->staticSize  = 0;
 207     dctx->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
 208     dctx->ddict       = NULL;
 209     dctx->ddictLocal  = NULL;
 210     dctx->dictEnd     = NULL;
 211     dctx->ddictIsCold = 0;
 212     dctx->inBuff      = NULL;
 213     dctx->inBuffSize  = 0;
 214     dctx->outBuffSize = 0;
 215     dctx->streamStage = zdss_init;
 216     dctx->legacyContext = NULL;
 217     dctx->previousLegacyVersion = 0;
 218     dctx->noForwardProgress = 0;
 219     dctx->bmi2 = ZSTD_cpuid_bmi2(ZSTD_cpuid());
 220 }
 221
 222 ZSTD_DCtx* ZSTD_initStaticDCtx(void *workspace, size_t workspaceSize)
 223 {
 224     ZSTD_DCtx* const dctx = (ZSTD_DCtx*) workspace;
 225
 226     if ((size_t)workspace & 7) return NULL;  /* 8-aligned */
 227     if (workspaceSize < sizeof(ZSTD_DCtx)) return NULL;  /* minimum size */
 228
 229     ZSTD_initDCtx_internal(dctx);
 230     dctx->staticSize = workspaceSize;
 231     dctx->inBuff = (char*)(dctx+1);
 232     return dctx;
 233 }
 234
 235 ZSTD_DCtx* ZSTD_createDCtx_advanced(ZSTD_customMem customMem)
 236 {
 237     if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
 238
 239     {   ZSTD_DCtx* const dctx = (ZSTD_DCtx*)ZSTD_malloc(sizeof(*dctx), customMem);
 240         if (!dctx) return NULL;
 241         dctx->customMem = customMem;
 242         ZSTD_initDCtx_internal(dctx);
 243         return dctx;
 244     }
 245 }
 246
 247 ZSTD_DCtx* ZSTD_createDCtx(void)
 248 {
 249     DEBUGLOG(3, "ZSTD_createDCtx");
 250     return ZSTD_createDCtx_advanced(ZSTD_defaultCMem);
 251 }
 252
 253 size_t ZSTD_freeDCtx(ZSTD_DCtx* dctx)
 254 {
 255     if (dctx==NULL) return 0;   /* support free on NULL */
 256     if (dctx->staticSize) return ERROR(memory_allocation);   /* not compatible with static DCtx */
 257     {   ZSTD_customMem const cMem = dctx->customMem;
 258         ZSTD_freeDDict(dctx->ddictLocal);
 259         dctx->ddictLocal = NULL;
 260         ZSTD_free(dctx->inBuff, cMem);
 261         dctx->inBuff = NULL;
 262 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
 263         if (dctx->legacyContext)
 264             ZSTD_freeLegacyStreamContext(dctx->legacyContext, dctx->previousLegacyVersion);
 265 #endif
 266         ZSTD_free(dctx, cMem);
 267         return 0;
 268     }
 269 }
 270
 271 /* no longer useful */
 272 void ZSTD_copyDCtx(ZSTD_DCtx* dstDCtx, const ZSTD_DCtx* srcDCtx)
 273 {
 274     size_t const toCopy = (size_t)((char*)(&dstDCtx->inBuff) - (char*)dstDCtx);
 275     memcpy(dstDCtx, srcDCtx, toCopy);  /* no need to copy workspace */
 276 }
 277
 278
 279 /*-*************************************************************
 280  *   Frame header decoding
 281  ***************************************************************/
 282
 283 /*! ZSTD_isFrame() :
 284  *  Tells if the content of `buffer` starts with a valid Frame Identifier.
 285  *  Note : Frame Identifier is 4 bytes. If `size < 4`, @return will always be 0.
 286  *  Note 2 : Legacy Frame Identifiers are considered valid only if Legacy Support is enabled.
 287  *  Note 3 : Skippable Frame Identifiers are considered valid. */
 288 unsigned ZSTD_isFrame(const void* buffer, size_t size)
 289 {
 290     if (size < ZSTD_FRAMEIDSIZE) return 0;
 291     {   U32 const magic = MEM_readLE32(buffer);
 292         if (magic == ZSTD_MAGICNUMBER) return 1;
 293         if ((magic & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) return 1;
 294     }
 295 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
 296     if (ZSTD_isLegacy(buffer, size)) return 1;
 297 #endif
 298     return 0;
 299 }
 300
 301 /** ZSTD_frameHeaderSize_internal() :
 302  *  srcSize must be large enough to reach header size fields.
 303  *  note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless.
 304  * @return : size of the Frame Header
 305  *           or an error code, which can be tested with ZSTD_isError() */
 306 static size_t ZSTD_frameHeaderSize_internal(const void* src, size_t srcSize, ZSTD_format_e format)
 307 {
 308     size_t const minInputSize = ZSTD_startingInputLength(format);
 309     if (srcSize < minInputSize) return ERROR(srcSize_wrong);
 310
 311     {   BYTE const fhd = ((const BYTE*)src)[minInputSize-1];
 312         U32 const dictID= fhd & 3;
 313         U32 const singleSegment = (fhd >> 5) & 1;
 314         U32 const fcsId = fhd >> 6;
 315         return minInputSize + !singleSegment
 316              + ZSTD_did_fieldSize[dictID] + ZSTD_fcs_fieldSize[fcsId]
 317              + (singleSegment && !fcsId);
 318     }
 319 }
 320
 321 /** ZSTD_frameHeaderSize() :
 322  *  srcSize must be >= ZSTD_frameHeaderSize_prefix.
 323  * @return : size of the Frame Header,
 324  *           or an error code (if srcSize is too small) */
 325 size_t ZSTD_frameHeaderSize(const void* src, size_t srcSize)
 326 {
 327     return ZSTD_frameHeaderSize_internal(src, srcSize, ZSTD_f_zstd1);
 328 }
 329
 330
 331 /** ZSTD_getFrameHeader_advanced() :
 332  *  decode Frame Header, or require larger `srcSize`.
 333  *  note : only works for formats ZSTD_f_zstd1 and ZSTD_f_zstd1_magicless
 334  * @return : 0, `zfhPtr` is correctly filled,
 335  *          >0, `srcSize` is too small, value is wanted `srcSize` amount,
 336  *           or an error code, which can be tested using ZSTD_isError() */
 337 size_t ZSTD_getFrameHeader_advanced(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize, ZSTD_format_e format)
 338 {
 339     const BYTE* ip = (const BYTE*)src;
 340     size_t const minInputSize = ZSTD_startingInputLength(format);
 341
 342     memset(zfhPtr, 0, sizeof(*zfhPtr));   /* not strictly necessary, but static analyzer do not understand that zfhPtr is only going to be read only if return value is zero, since they are 2 different signals */
 343     if (srcSize < minInputSize) return minInputSize;
 344     if (src==NULL) return ERROR(GENERIC);   /* invalid parameter */
 345
 346     if ( (format != ZSTD_f_zstd1_magicless)
 347       && (MEM_readLE32(src) != ZSTD_MAGICNUMBER) ) {
 348         if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
 349             /* skippable frame */
 350             if (srcSize < ZSTD_skippableHeaderSize)
 351                 return ZSTD_skippableHeaderSize; /* magic number + frame length */
 352             memset(zfhPtr, 0, sizeof(*zfhPtr));
 353             zfhPtr->frameContentSize = MEM_readLE32((const char *)src + ZSTD_FRAMEIDSIZE);
 354             zfhPtr->frameType = ZSTD_skippableFrame;
 355             return 0;
 356         }
 357         return ERROR(prefix_unknown);
 358     }
 359
 360     /* ensure there is enough `srcSize` to fully read/decode frame header */
 361     {   size_t const fhsize = ZSTD_frameHeaderSize_internal(src, srcSize, format);
 362         if (srcSize < fhsize) return fhsize;
 363         zfhPtr->headerSize = (U32)fhsize;
 364     }
 365
 366     {   BYTE const fhdByte = ip[minInputSize-1];
 367         size_t pos = minInputSize;
 368         U32 const dictIDSizeCode = fhdByte&3;
 369         U32 const checksumFlag = (fhdByte>>2)&1;
 370         U32 const singleSegment = (fhdByte>>5)&1;
 371         U32 const fcsID = fhdByte>>6;
 372         U64 windowSize = 0;
 373         U32 dictID = 0;
 374         U64 frameContentSize = ZSTD_CONTENTSIZE_UNKNOWN;
 375         if ((fhdByte & 0x08) != 0)
 376             return ERROR(frameParameter_unsupported); /* reserved bits, must be zero */
 377
 378         if (!singleSegment) {
 379             BYTE const wlByte = ip[pos++];
 380             U32 const windowLog = (wlByte >> 3) + ZSTD_WINDOWLOG_ABSOLUTEMIN;
 381             if (windowLog > ZSTD_WINDOWLOG_MAX)
 382                 return ERROR(frameParameter_windowTooLarge);
 383             windowSize = (1ULL << windowLog);
 384             windowSize += (windowSize >> 3) * (wlByte&7);
 385         }
 386         switch(dictIDSizeCode)
 387         {
 388             default: assert(0);  /* impossible */
 389             case 0 : break;
 390             case 1 : dictID = ip[pos]; pos++; break;
 391             case 2 : dictID = MEM_readLE16(ip+pos); pos+=2; break;
 392             case 3 : dictID = MEM_readLE32(ip+pos); pos+=4; break;
 393         }
 394         switch(fcsID)
 395         {
 396             default: assert(0);  /* impossible */
 397             case 0 : if (singleSegment) frameContentSize = ip[pos]; break;
 398             case 1 : frameContentSize = MEM_readLE16(ip+pos)+256; break;
 399             case 2 : frameContentSize = MEM_readLE32(ip+pos); break;
 400             case 3 : frameContentSize = MEM_readLE64(ip+pos); break;
 401         }
 402         if (singleSegment) windowSize = frameContentSize;
 403
 404         zfhPtr->frameType = ZSTD_frame;
 405         zfhPtr->frameContentSize = frameContentSize;
 406         zfhPtr->windowSize = windowSize;
 407         zfhPtr->blockSizeMax = (unsigned) MIN(windowSize, ZSTD_BLOCKSIZE_MAX);
 408         zfhPtr->dictID = dictID;
 409         zfhPtr->checksumFlag = checksumFlag;
 410     }
 411     return 0;
 412 }
 413
 414 /** ZSTD_getFrameHeader() :
 415  *  decode Frame Header, or require larger `srcSize`.
 416  *  note : this function does not consume input, it only reads it.
 417  * @return : 0, `zfhPtr` is correctly filled,
 418  *          >0, `srcSize` is too small, value is wanted `srcSize` amount,
 419  *           or an error code, which can be tested using ZSTD_isError() */
 420 size_t ZSTD_getFrameHeader(ZSTD_frameHeader* zfhPtr, const void* src, size_t srcSize)
 421 {
 422     return ZSTD_getFrameHeader_advanced(zfhPtr, src, srcSize, ZSTD_f_zstd1);
 423 }
 424
 425
 426 /** ZSTD_getFrameContentSize() :
 427  *  compatible with legacy mode
 428  * @return : decompressed size of the single frame pointed to be `src` if known, otherwise
 429  *         - ZSTD_CONTENTSIZE_UNKNOWN if the size cannot be determined
 430  *         - ZSTD_CONTENTSIZE_ERROR if an error occurred (e.g. invalid magic number, srcSize too small) */
 431 unsigned long long ZSTD_getFrameContentSize(const void *src, size_t srcSize)
 432 {
 433 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
 434     if (ZSTD_isLegacy(src, srcSize)) {
 435         unsigned long long const ret = ZSTD_getDecompressedSize_legacy(src, srcSize);
 436         return ret == 0 ? ZSTD_CONTENTSIZE_UNKNOWN : ret;
 437     }
 438 #endif
 439     {   ZSTD_frameHeader zfh;
 440         if (ZSTD_getFrameHeader(&zfh, src, srcSize) != 0)
 441             return ZSTD_CONTENTSIZE_ERROR;
 442         if (zfh.frameType == ZSTD_skippableFrame) {
 443             return 0;
 444         } else {
 445             return zfh.frameContentSize;
 446     }   }
 447 }
 448
 449 /** ZSTD_findDecompressedSize() :
 450  *  compatible with legacy mode
 451  *  `srcSize` must be the exact length of some number of ZSTD compressed and/or
 452  *      skippable frames
 453  *  @return : decompressed size of the frames contained */
 454 unsigned long long ZSTD_findDecompressedSize(const void* src, size_t srcSize)
 455 {
 456     unsigned long long totalDstSize = 0;
 457
 458     while (srcSize >= ZSTD_frameHeaderSize_prefix) {
 459         U32 const magicNumber = MEM_readLE32(src);
 460
 461         if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
 462             size_t skippableSize;
 463             if (srcSize < ZSTD_skippableHeaderSize)
 464                 return ERROR(srcSize_wrong);
 465             skippableSize = MEM_readLE32((const BYTE *)src + ZSTD_FRAMEIDSIZE)
 466                           + ZSTD_skippableHeaderSize;
 467             if (srcSize < skippableSize) {
 468                 return ZSTD_CONTENTSIZE_ERROR;
 469             }
 470
 471             src = (const BYTE *)src + skippableSize;
 472             srcSize -= skippableSize;
 473             continue;
 474         }
 475
 476         {   unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);
 477             if (ret >= ZSTD_CONTENTSIZE_ERROR) return ret;
 478
 479             /* check for overflow */
 480             if (totalDstSize + ret < totalDstSize) return ZSTD_CONTENTSIZE_ERROR;
 481             totalDstSize += ret;
 482         }
 483         {   size_t const frameSrcSize = ZSTD_findFrameCompressedSize(src, srcSize);
 484             if (ZSTD_isError(frameSrcSize)) {
 485                 return ZSTD_CONTENTSIZE_ERROR;
 486             }
 487
 488             src = (const BYTE *)src + frameSrcSize;
 489             srcSize -= frameSrcSize;
 490         }
 491     }  /* while (srcSize >= ZSTD_frameHeaderSize_prefix) */
 492
 493     if (srcSize) return ZSTD_CONTENTSIZE_ERROR;
 494
 495     return totalDstSize;
 496 }
 497
 498 /** ZSTD_getDecompressedSize() :
 499 *   compatible with legacy mode
 500 *   @return : decompressed size if known, 0 otherwise
 501               note : 0 can mean any of the following :
 502                    - frame content is empty
 503                    - decompressed size field is not present in frame header
 504                    - frame header unknown / not supported
 505                    - frame header not complete (`srcSize` too small) */
 506 unsigned long long ZSTD_getDecompressedSize(const void* src, size_t srcSize)
 507 {
 508     unsigned long long const ret = ZSTD_getFrameContentSize(src, srcSize);
 509     ZSTD_STATIC_ASSERT(ZSTD_CONTENTSIZE_ERROR < ZSTD_CONTENTSIZE_UNKNOWN);
 510     return (ret >= ZSTD_CONTENTSIZE_ERROR) ? 0 : ret;
 511 }
 512
 513
 514 /** ZSTD_decodeFrameHeader() :
 515 *   `headerSize` must be the size provided by ZSTD_frameHeaderSize().
 516 *   @return : 0 if success, or an error code, which can be tested using ZSTD_isError() */
 517 static size_t ZSTD_decodeFrameHeader(ZSTD_DCtx* dctx, const void* src, size_t headerSize)
 518 {
 519     size_t const result = ZSTD_getFrameHeader_advanced(&(dctx->fParams), src, headerSize, dctx->format);
 520     if (ZSTD_isError(result)) return result;    /* invalid header */
 521     if (result>0) return ERROR(srcSize_wrong);  /* headerSize too small */
 522     if (dctx->fParams.dictID && (dctx->dictID != dctx->fParams.dictID))
 523         return ERROR(dictionary_wrong);
 524     if (dctx->fParams.checksumFlag) XXH64_reset(&dctx->xxhState, 0);
 525     return 0;
 526 }
 527
 528
 529 /*-*************************************************************
 530  *   Block decoding
 531  ***************************************************************/
 532
 533 /*! ZSTD_getcBlockSize() :
 534 *   Provides the size of compressed block from block header `src` */
 535 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
 536                           blockProperties_t* bpPtr)
 537 {
 538     if (srcSize < ZSTD_blockHeaderSize) return ERROR(srcSize_wrong);
 539     {   U32 const cBlockHeader = MEM_readLE24(src);
 540         U32 const cSize = cBlockHeader >> 3;
 541         bpPtr->lastBlock = cBlockHeader & 1;
 542         bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3);
 543         bpPtr->origSize = cSize;   /* only useful for RLE */
 544         if (bpPtr->blockType == bt_rle) return 1;
 545         if (bpPtr->blockType == bt_reserved) return ERROR(corruption_detected);
 546         return cSize;
 547     }
 548 }
 549
 550
 551 static size_t ZSTD_copyRawBlock(void* dst, size_t dstCapacity,
 552                           const void* src, size_t srcSize)
 553 {
 554     if (dst==NULL) return ERROR(dstSize_tooSmall);
 555     if (srcSize > dstCapacity) return ERROR(dstSize_tooSmall);
 556     memcpy(dst, src, srcSize);
 557     return srcSize;
 558 }
 559
 560
 561 static size_t ZSTD_setRleBlock(void* dst, size_t dstCapacity,
 562                          const void* src, size_t srcSize,
 563                                size_t regenSize)
 564 {
 565     if (srcSize != 1) return ERROR(srcSize_wrong);
 566     if (regenSize > dstCapacity) return ERROR(dstSize_tooSmall);
 567     memset(dst, *(const BYTE*)src, regenSize);
 568     return regenSize;
 569 }
 570
 571 /* Hidden declaration for fullbench */
 572 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
 573                           const void* src, size_t srcSize);
 574 /*! ZSTD_decodeLiteralsBlock() :
 575  * @return : nb of bytes read from src (< srcSize )
 576  *  note : symbol not declared but exposed for fullbench */
 577 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
 578                           const void* src, size_t srcSize)   /* note : srcSize < BLOCKSIZE */
 579 {
 580     if (srcSize < MIN_CBLOCK_SIZE) return ERROR(corruption_detected);
 581
 582     {   const BYTE* const istart = (const BYTE*) src;
 583         symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
 584
 585         switch(litEncType)
 586         {
 587         case set_repeat:
 588             if (dctx->litEntropy==0) return ERROR(dictionary_corrupted);
 589             /* fall-through */
 590
 591         case set_compressed:
 592             if (srcSize < 5) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3 */
 593             {   size_t lhSize, litSize, litCSize;
 594                 U32 singleStream=0;
 595                 U32 const lhlCode = (istart[0] >> 2) & 3;
 596                 U32 const lhc = MEM_readLE32(istart);
 597                 switch(lhlCode)
 598                 {
 599                 case 0: case 1: default:   /* note : default is impossible, since lhlCode into [0..3] */
 600                     /* 2 - 2 - 10 - 10 */
 601                     singleStream = !lhlCode;
 602                     lhSize = 3;
 603                     litSize  = (lhc >> 4) & 0x3FF;
 604                     litCSize = (lhc >> 14) & 0x3FF;
 605                     break;
 606                 case 2:
 607                     /* 2 - 2 - 14 - 14 */
 608                     lhSize = 4;
 609                     litSize  = (lhc >> 4) & 0x3FFF;
 610                     litCSize = lhc >> 18;
 611                     break;
 612                 case 3:
 613                     /* 2 - 2 - 18 - 18 */
 614                     lhSize = 5;
 615                     litSize  = (lhc >> 4) & 0x3FFFF;
 616                     litCSize = (lhc >> 22) + (istart[4] << 10);
 617                     break;
 618                 }
 619                 if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);
 620                 if (litCSize + lhSize > srcSize) return ERROR(corruption_detected);
 621
 622                 /* prefetch huffman table if cold */
 623                 if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {
 624                     PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));
 625                 }
 626
 627                 if (HUF_isError((litEncType==set_repeat) ?
 628                                     ( singleStream ?
 629                                         HUF_decompress1X_usingDTable_bmi2(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr, dctx->bmi2) :
 630                                         HUF_decompress4X_usingDTable_bmi2(dctx->litBuffer, litSize, istart+lhSize, litCSize, dctx->HUFptr, dctx->bmi2) ) :
 631                                     ( singleStream ?
 632                                         HUF_decompress1X1_DCtx_wksp_bmi2(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize,
 633                                                                          dctx->workspace, sizeof(dctx->workspace), dctx->bmi2) :
 634                                         HUF_decompress4X_hufOnly_wksp_bmi2(dctx->entropy.hufTable, dctx->litBuffer, litSize, istart+lhSize, litCSize,
 635                                                                            dctx->workspace, sizeof(dctx->workspace), dctx->bmi2))))
 636                     return ERROR(corruption_detected);
 637
 638                 dctx->litPtr = dctx->litBuffer;
 639                 dctx->litSize = litSize;
 640                 dctx->litEntropy = 1;
 641                 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;
 642                 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
 643                 return litCSize + lhSize;
 644             }
 645
 646         case set_basic:
 647             {   size_t litSize, lhSize;
 648                 U32 const lhlCode = ((istart[0]) >> 2) & 3;
 649                 switch(lhlCode)
 650                 {
 651                 case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */
 652                     lhSize = 1;
 653                     litSize = istart[0] >> 3;
 654                     break;
 655                 case 1:
 656                     lhSize = 2;
 657                     litSize = MEM_readLE16(istart) >> 4;
 658                     break;
 659                 case 3:
 660                     lhSize = 3;
 661                     litSize = MEM_readLE24(istart) >> 4;
 662                     break;
 663                 }
 664
 665                 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) {  /* risk reading beyond src buffer with wildcopy */
 666                     if (litSize+lhSize > srcSize) return ERROR(corruption_detected);
 667                     memcpy(dctx->litBuffer, istart+lhSize, litSize);
 668                     dctx->litPtr = dctx->litBuffer;
 669                     dctx->litSize = litSize;
 670                     memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
 671                     return lhSize+litSize;
 672                 }
 673                 /* direct reference into compressed stream */
 674                 dctx->litPtr = istart+lhSize;
 675                 dctx->litSize = litSize;
 676                 return lhSize+litSize;
 677             }
 678
 679         case set_rle:
 680             {   U32 const lhlCode = ((istart[0]) >> 2) & 3;
 681                 size_t litSize, lhSize;
 682                 switch(lhlCode)
 683                 {
 684                 case 0: case 2: default:   /* note : default is impossible, since lhlCode into [0..3] */
 685                     lhSize = 1;
 686                     litSize = istart[0] >> 3;
 687                     break;
 688                 case 1:
 689                     lhSize = 2;
 690                     litSize = MEM_readLE16(istart) >> 4;
 691                     break;
 692                 case 3:
 693                     lhSize = 3;
 694                     litSize = MEM_readLE24(istart) >> 4;
 695                     if (srcSize<4) return ERROR(corruption_detected);   /* srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4 */
 696                     break;
 697                 }
 698                 if (litSize > ZSTD_BLOCKSIZE_MAX) return ERROR(corruption_detected);
 699                 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
 700                 dctx->litPtr = dctx->litBuffer;
 701                 dctx->litSize = litSize;
 702                 return lhSize+1;
 703             }
 704         default:
 705             return ERROR(corruption_detected);   /* impossible */
 706         }
 707     }
 708 }
 709
 710 /* Default FSE distribution tables.
 711  * These are pre-calculated FSE decoding tables using default distributions as defined in specification :
 712  * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions
 713  * They were generated programmatically with following method :
 714  * - start from default distributions, present in /lib/common/zstd_internal.h
 715  * - generate tables normally, using ZSTD_buildFSETable()
 716  * - printout the content of tables
 717  * - pretify output, report below, test with fuzzer to ensure it's correct */
 718
 719 /* Default FSE distribution table for Literal Lengths */
 720 static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = {
 721      {  1,  1,  1, LL_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
 722      /* nextState, nbAddBits, nbBits, baseVal */
 723      {  0,  0,  4,    0},  { 16,  0,  4,    0},
 724      { 32,  0,  5,    1},  {  0,  0,  5,    3},
 725      {  0,  0,  5,    4},  {  0,  0,  5,    6},
 726      {  0,  0,  5,    7},  {  0,  0,  5,    9},
 727      {  0,  0,  5,   10},  {  0,  0,  5,   12},
 728      {  0,  0,  6,   14},  {  0,  1,  5,   16},
 729      {  0,  1,  5,   20},  {  0,  1,  5,   22},
 730      {  0,  2,  5,   28},  {  0,  3,  5,   32},
 731      {  0,  4,  5,   48},  { 32,  6,  5,   64},
 732      {  0,  7,  5,  128},  {  0,  8,  6,  256},
 733      {  0, 10,  6, 1024},  {  0, 12,  6, 4096},
 734      { 32,  0,  4,    0},  {  0,  0,  4,    1},
 735      {  0,  0,  5,    2},  { 32,  0,  5,    4},
 736      {  0,  0,  5,    5},  { 32,  0,  5,    7},
 737      {  0,  0,  5,    8},  { 32,  0,  5,   10},
 738      {  0,  0,  5,   11},  {  0,  0,  6,   13},
 739      { 32,  1,  5,   16},  {  0,  1,  5,   18},
 740      { 32,  1,  5,   22},  {  0,  2,  5,   24},
 741      { 32,  3,  5,   32},  {  0,  3,  5,   40},
 742      {  0,  6,  4,   64},  { 16,  6,  4,   64},
 743      { 32,  7,  5,  128},  {  0,  9,  6,  512},
 744      {  0, 11,  6, 2048},  { 48,  0,  4,    0},
 745      { 16,  0,  4,    1},  { 32,  0,  5,    2},
 746      { 32,  0,  5,    3},  { 32,  0,  5,    5},
 747      { 32,  0,  5,    6},  { 32,  0,  5,    8},
 748      { 32,  0,  5,    9},  { 32,  0,  5,   11},
 749      { 32,  0,  5,   12},  {  0,  0,  6,   15},
 750      { 32,  1,  5,   18},  { 32,  1,  5,   20},
 751      { 32,  2,  5,   24},  { 32,  2,  5,   28},
 752      { 32,  3,  5,   40},  { 32,  4,  5,   48},
 753      {  0, 16,  6,65536},  {  0, 15,  6,32768},
 754      {  0, 14,  6,16384},  {  0, 13,  6, 8192},
 755 };   /* LL_defaultDTable */
 756
 757 /* Default FSE distribution table for Offset Codes */
 758 static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = {
 759     {  1,  1,  1, OF_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
 760     /* nextState, nbAddBits, nbBits, baseVal */
 761     {  0,  0,  5,    0},     {  0,  6,  4,   61},
 762     {  0,  9,  5,  509},     {  0, 15,  5,32765},
 763     {  0, 21,  5,2097149},   {  0,  3,  5,    5},
 764     {  0,  7,  4,  125},     {  0, 12,  5, 4093},
 765     {  0, 18,  5,262141},    {  0, 23,  5,8388605},
 766     {  0,  5,  5,   29},     {  0,  8,  4,  253},
 767     {  0, 14,  5,16381},     {  0, 20,  5,1048573},
 768     {  0,  2,  5,    1},     { 16,  7,  4,  125},
 769     {  0, 11,  5, 2045},     {  0, 17,  5,131069},
 770     {  0, 22,  5,4194301},   {  0,  4,  5,   13},
 771     { 16,  8,  4,  253},     {  0, 13,  5, 8189},
 772     {  0, 19,  5,524285},    {  0,  1,  5,    1},
 773     { 16,  6,  4,   61},     {  0, 10,  5, 1021},
 774     {  0, 16,  5,65533},     {  0, 28,  5,268435453},
 775     {  0, 27,  5,134217725}, {  0, 26,  5,67108861},
 776     {  0, 25,  5,33554429},  {  0, 24,  5,16777213},
 777 };   /* OF_defaultDTable */
 778
 779
 780 /* Default FSE distribution table for Match Lengths */
 781 static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = {
 782     {  1,  1,  1, ML_DEFAULTNORMLOG},  /* header : fastMode, tableLog */
 783     /* nextState, nbAddBits, nbBits, baseVal */
 784     {  0,  0,  6,    3},  {  0,  0,  4,    4},
 785     { 32,  0,  5,    5},  {  0,  0,  5,    6},
 786     {  0,  0,  5,    8},  {  0,  0,  5,    9},
 787     {  0,  0,  5,   11},  {  0,  0,  6,   13},
 788     {  0,  0,  6,   16},  {  0,  0,  6,   19},
 789     {  0,  0,  6,   22},  {  0,  0,  6,   25},
 790     {  0,  0,  6,   28},  {  0,  0,  6,   31},
 791     {  0,  0,  6,   34},  {  0,  1,  6,   37},
 792     {  0,  1,  6,   41},  {  0,  2,  6,   47},
 793     {  0,  3,  6,   59},  {  0,  4,  6,   83},
 794     {  0,  7,  6,  131},  {  0,  9,  6,  515},
 795     { 16,  0,  4,    4},  {  0,  0,  4,    5},
 796     { 32,  0,  5,    6},  {  0,  0,  5,    7},
 797     { 32,  0,  5,    9},  {  0,  0,  5,   10},
 798     {  0,  0,  6,   12},  {  0,  0,  6,   15},
 799     {  0,  0,  6,   18},  {  0,  0,  6,   21},
 800     {  0,  0,  6,   24},  {  0,  0,  6,   27},
 801     {  0,  0,  6,   30},  {  0,  0,  6,   33},
 802     {  0,  1,  6,   35},  {  0,  1,  6,   39},
 803     {  0,  2,  6,   43},  {  0,  3,  6,   51},
 804     {  0,  4,  6,   67},  {  0,  5,  6,   99},
 805     {  0,  8,  6,  259},  { 32,  0,  4,    4},
 806     { 48,  0,  4,    4},  { 16,  0,  4,    5},
 807     { 32,  0,  5,    7},  { 32,  0,  5,    8},
 808     { 32,  0,  5,   10},  { 32,  0,  5,   11},
 809     {  0,  0,  6,   14},  {  0,  0,  6,   17},
 810     {  0,  0,  6,   20},  {  0,  0,  6,   23},
 811     {  0,  0,  6,   26},  {  0,  0,  6,   29},
 812     {  0,  0,  6,   32},  {  0, 16,  6,65539},
 813     {  0, 15,  6,32771},  {  0, 14,  6,16387},
 814     {  0, 13,  6, 8195},  {  0, 12,  6, 4099},
 815     {  0, 11,  6, 2051},  {  0, 10,  6, 1027},
 816 };   /* ML_defaultDTable */
 817
 818
 819 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)
 820 {
 821     void* ptr = dt;
 822     ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;
 823     ZSTD_seqSymbol* const cell = dt + 1;
 824
 825     DTableH->tableLog = 0;
 826     DTableH->fastMode = 0;
 827
 828     cell->nbBits = 0;
 829     cell->nextState = 0;
 830     assert(nbAddBits < 255);
 831     cell->nbAdditionalBits = (BYTE)nbAddBits;
 832     cell->baseValue = baseValue;
 833 }
 834
 835
 836 /* ZSTD_buildFSETable() :
 837  * generate FSE decoding table for one symbol (ll, ml or off) */
 838 static void
 839 ZSTD_buildFSETable(ZSTD_seqSymbol* dt,
 840     const short* normalizedCounter, unsigned maxSymbolValue,
 841     const U32* baseValue, const U32* nbAdditionalBits,
 842     unsigned tableLog)
 843 {
 844     ZSTD_seqSymbol* const tableDecode = dt+1;
 845     U16 symbolNext[MaxSeq+1];
 846
 847     U32 const maxSV1 = maxSymbolValue + 1;
 848     U32 const tableSize = 1 << tableLog;
 849     U32 highThreshold = tableSize-1;
 850
 851     /* Sanity Checks */
 852     assert(maxSymbolValue <= MaxSeq);
 853     assert(tableLog <= MaxFSELog);
 854
 855     /* Init, lay down lowprob symbols */
 856     {   ZSTD_seqSymbol_header DTableH;
 857         DTableH.tableLog = tableLog;
 858         DTableH.fastMode = 1;
 859         {   S16 const largeLimit= (S16)(1 << (tableLog-1));
 860             U32 s;
 861             for (s=0; s<maxSV1; s++) {
 862                 if (normalizedCounter[s]==-1) {
 863                     tableDecode[highThreshold--].baseValue = s;
 864                     symbolNext[s] = 1;
 865                 } else {
 866                     if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
 867                     symbolNext[s] = normalizedCounter[s];
 868         }   }   }
 869         memcpy(dt, &DTableH, sizeof(DTableH));
 870     }
 871
 872     /* Spread symbols */
 873     {   U32 const tableMask = tableSize-1;
 874         U32 const step = FSE_TABLESTEP(tableSize);
 875         U32 s, position = 0;
 876         for (s=0; s<maxSV1; s++) {
 877             int i;
 878             for (i=0; i<normalizedCounter[s]; i++) {
 879                 tableDecode[position].baseValue = s;
 880                 position = (position + step) & tableMask;
 881                 while (position > highThreshold) position = (position + step) & tableMask;   /* lowprob area */
 882         }   }
 883         assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
 884     }
 885
 886     /* Build Decoding table */
 887     {   U32 u;
 888         for (u=0; u<tableSize; u++) {
 889             U32 const symbol = tableDecode[u].baseValue;
 890             U32 const nextState = symbolNext[symbol]++;
 891             tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
 892             tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
 893             assert(nbAdditionalBits[symbol] < 255);
 894             tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
 895             tableDecode[u].baseValue = baseValue[symbol];
 896     }   }
 897 }
 898
 899
 900 /*! ZSTD_buildSeqTable() :
 901  * @return : nb bytes read from src,
 902  *           or an error code if it fails */
 903 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
 904                                  symbolEncodingType_e type, U32 max, U32 maxLog,
 905                                  const void* src, size_t srcSize,
 906                                  const U32* baseValue, const U32* nbAdditionalBits,
 907                                  const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
 908                                  int ddictIsCold, int nbSeq)
 909 {
 910     switch(type)
 911     {
 912     case set_rle :
 913         if (!srcSize) return ERROR(srcSize_wrong);
 914         if ( (*(const BYTE*)src) > max) return ERROR(corruption_detected);
 915         {   U32 const symbol = *(const BYTE*)src;
 916             U32 const baseline = baseValue[symbol];
 917             U32 const nbBits = nbAdditionalBits[symbol];
 918             ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
 919         }
 920         *DTablePtr = DTableSpace;
 921         return 1;
 922     case set_basic :
 923         *DTablePtr = defaultTable;
 924         return 0;
 925     case set_repeat:
 926         if (!flagRepeatTable) return ERROR(corruption_detected);
 927         /* prefetch FSE table if used */
 928         if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
 929             const void* const pStart = *DTablePtr;
 930             size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
 931             PREFETCH_AREA(pStart, pSize);
 932         }
 933         return 0;
 934     case set_compressed :
 935         {   U32 tableLog;
 936             S16 norm[MaxSeq+1];
 937             size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
 938             if (FSE_isError(headerSize)) return ERROR(corruption_detected);
 939             if (tableLog > maxLog) return ERROR(corruption_detected);
 940             ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);
 941             *DTablePtr = DTableSpace;
 942             return headerSize;
 943         }
 944     default :   /* impossible */
 945         assert(0);
 946         return ERROR(GENERIC);
 947     }
 948 }
 949
 950 static const U32 LL_base[MaxLL+1] = {
 951                  0,    1,    2,     3,     4,     5,     6,      7,
 952                  8,    9,   10,    11,    12,    13,    14,     15,
 953                 16,   18,   20,    22,    24,    28,    32,     40,
 954                 48,   64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
 955                 0x2000, 0x4000, 0x8000, 0x10000 };
 956
 957 static const U32 OF_base[MaxOff+1] = {
 958                  0,        1,       1,       5,     0xD,     0x1D,     0x3D,     0x7D,
 959                  0xFD,   0x1FD,   0x3FD,   0x7FD,   0xFFD,   0x1FFD,   0x3FFD,   0x7FFD,
 960                  0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
 961                  0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD, 0x1FFFFFFD, 0x3FFFFFFD, 0x7FFFFFFD };
 962
 963 static const U32 OF_bits[MaxOff+1] = {
 964                      0,  1,  2,  3,  4,  5,  6,  7,
 965                      8,  9, 10, 11, 12, 13, 14, 15,
 966                     16, 17, 18, 19, 20, 21, 22, 23,
 967                     24, 25, 26, 27, 28, 29, 30, 31 };
 968
 969 static const U32 ML_base[MaxML+1] = {
 970                      3,  4,  5,    6,     7,     8,     9,    10,
 971                     11, 12, 13,   14,    15,    16,    17,    18,
 972                     19, 20, 21,   22,    23,    24,    25,    26,
 973                     27, 28, 29,   30,    31,    32,    33,    34,
 974                     35, 37, 39,   41,    43,    47,    51,    59,
 975                     67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
 976                     0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
 977
 978 /* Hidden delcaration for fullbench */
 979 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
 980                              const void* src, size_t srcSize);
 981
 982 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
 983                              const void* src, size_t srcSize)
 984 {
 985     const BYTE* const istart = (const BYTE* const)src;
 986     const BYTE* const iend = istart + srcSize;
 987     const BYTE* ip = istart;
 988     int nbSeq;
 989     DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
 990
 991     /* check */
 992     if (srcSize < MIN_SEQUENCES_SIZE) return ERROR(srcSize_wrong);
 993
 994     /* SeqHead */
 995     nbSeq = *ip++;
 996     if (!nbSeq) { *nbSeqPtr=0; return 1; }
 997     if (nbSeq > 0x7F) {
 998         if (nbSeq == 0xFF) {
 999             if (ip+2 > iend) return ERROR(srcSize_wrong);
1000             nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
1001         } else {
1002             if (ip >= iend) return ERROR(srcSize_wrong);
1003             nbSeq = ((nbSeq-0x80)<<8) + *ip++;
1004         }
1005     }
1006     *nbSeqPtr = nbSeq;
1007
1008     /* FSE table descriptors */
1009     if (ip+4 > iend) return ERROR(srcSize_wrong); /* minimum possible size */
1010     {   symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
1011         symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
1012         symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
1013         ip++;
1014
1015         /* Build DTables */
1016         {   size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
1017                                                       LLtype, MaxLL, LLFSELog,
1018                                                       ip, iend-ip,
1019                                                       LL_base, LL_bits,
1020                                                       LL_defaultDTable, dctx->fseEntropy,
1021                                                       dctx->ddictIsCold, nbSeq);
1022             if (ZSTD_isError(llhSize)) return ERROR(corruption_detected);
1023             ip += llhSize;
1024         }
1025
1026         {   size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
1027                                                       OFtype, MaxOff, OffFSELog,
1028                                                       ip, iend-ip,
1029                                                       OF_base, OF_bits,
1030                                                       OF_defaultDTable, dctx->fseEntropy,
1031                                                       dctx->ddictIsCold, nbSeq);
1032             if (ZSTD_isError(ofhSize)) return ERROR(corruption_detected);
1033             ip += ofhSize;
1034         }
1035
1036         {   size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
1037                                                       MLtype, MaxML, MLFSELog,
1038                                                       ip, iend-ip,
1039                                                       ML_base, ML_bits,
1040                                                       ML_defaultDTable, dctx->fseEntropy,
1041                                                       dctx->ddictIsCold, nbSeq);
1042             if (ZSTD_isError(mlhSize)) return ERROR(corruption_detected);
1043             ip += mlhSize;
1044         }
1045     }
1046
1047     /* prefetch dictionary content */
1048     if (dctx->ddictIsCold) {
1049         size_t const dictSize = (const char*)dctx->prefixStart - (const char*)dctx->virtualStart;
1050         size_t const psmin = MIN(dictSize, (size_t)(64*nbSeq) /* heuristic */ );
1051         size_t const pSize = MIN(psmin, 128 KB /* protection */ );
1052         const void* const pStart = (const char*)dctx->dictEnd - pSize;
1053         PREFETCH_AREA(pStart, pSize);
1054         dctx->ddictIsCold = 0;
1055     }
1056
1057     return ip-istart;
1058 }
1059
1060
1061 typedef struct {
1062     size_t litLength;
1063     size_t matchLength;
1064     size_t offset;
1065     const BYTE* match;
1066 } seq_t;
1067
1068 typedef struct {
1069     size_t state;
1070     const ZSTD_seqSymbol* table;
1071 } ZSTD_fseState;
1072
1073 typedef struct {
1074     BIT_DStream_t DStream;
1075     ZSTD_fseState stateLL;
1076     ZSTD_fseState stateOffb;
1077     ZSTD_fseState stateML;
1078     size_t prevOffset[ZSTD_REP_NUM];
1079     const BYTE* prefixStart;
1080     const BYTE* dictEnd;
1081     size_t pos;
1082 } seqState_t;
1083
1084
1085 FORCE_NOINLINE
1086 size_t ZSTD_execSequenceLast7(BYTE* op,
1087                               BYTE* const oend, seq_t sequence,
1088                               const BYTE** litPtr, const BYTE* const litLimit,
1089                               const BYTE* const base, const BYTE* const vBase, const BYTE* const dictEnd)
1090 {
1091     BYTE* const oLitEnd = op + sequence.litLength;
1092     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1093     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
1094     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
1095     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
1096     const BYTE* match = oLitEnd - sequence.offset;
1097
1098     /* check */
1099     if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1100     if (iLitEnd > litLimit) return ERROR(corruption_detected);   /* over-read beyond lit buffer */
1101     if (oLitEnd <= oend_w) return ERROR(GENERIC);   /* Precondition */
1102
1103     /* copy literals */
1104     if (op < oend_w) {
1105         ZSTD_wildcopy(op, *litPtr, oend_w - op);
1106         *litPtr += oend_w - op;
1107         op = oend_w;
1108     }
1109     while (op < oLitEnd) *op++ = *(*litPtr)++;
1110
1111     /* copy Match */
1112     if (sequence.offset > (size_t)(oLitEnd - base)) {
1113         /* offset beyond prefix */
1114         if (sequence.offset > (size_t)(oLitEnd - vBase)) return ERROR(corruption_detected);
1115         match = dictEnd - (base-match);
1116         if (match + sequence.matchLength <= dictEnd) {
1117             memmove(oLitEnd, match, sequence.matchLength);
1118             return sequenceLength;
1119         }
1120         /* span extDict & currentPrefixSegment */
1121         {   size_t const length1 = dictEnd - match;
1122             memmove(oLitEnd, match, length1);
1123             op = oLitEnd + length1;
1124             sequence.matchLength -= length1;
1125             match = base;
1126     }   }
1127     while (op < oMatchEnd) *op++ = *match++;
1128     return sequenceLength;
1129 }
1130
1131
1132 HINT_INLINE
1133 size_t ZSTD_execSequence(BYTE* op,
1134                          BYTE* const oend, seq_t sequence,
1135                          const BYTE** litPtr, const BYTE* const litLimit,
1136                          const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
1137 {
1138     BYTE* const oLitEnd = op + sequence.litLength;
1139     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1140     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
1141     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
1142     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
1143     const BYTE* match = oLitEnd - sequence.offset;
1144
1145     /* check */
1146     if (oMatchEnd>oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1147     if (iLitEnd > litLimit) return ERROR(corruption_detected);   /* over-read beyond lit buffer */
1148     if (oLitEnd>oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
1149
1150     /* copy Literals */
1151     ZSTD_copy8(op, *litPtr);
1152     if (sequence.litLength > 8)
1153         ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1154     op = oLitEnd;
1155     *litPtr = iLitEnd;   /* update for next sequence */
1156
1157     /* copy Match */
1158     if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
1159         /* offset beyond prefix -> go into extDict */
1160         if (sequence.offset > (size_t)(oLitEnd - virtualStart))
1161             return ERROR(corruption_detected);
1162         match = dictEnd + (match - prefixStart);
1163         if (match + sequence.matchLength <= dictEnd) {
1164             memmove(oLitEnd, match, sequence.matchLength);
1165             return sequenceLength;
1166         }
1167         /* span extDict & currentPrefixSegment */
1168         {   size_t const length1 = dictEnd - match;
1169             memmove(oLitEnd, match, length1);
1170             op = oLitEnd + length1;
1171             sequence.matchLength -= length1;
1172             match = prefixStart;
1173             if (op > oend_w || sequence.matchLength < MINMATCH) {
1174               U32 i;
1175               for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
1176               return sequenceLength;
1177             }
1178     }   }
1179     /* Requirement: op <= oend_w && sequence.matchLength >= MINMATCH */
1180
1181     /* match within prefix */
1182     if (sequence.offset < 8) {
1183         /* close range match, overlap */
1184         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
1185         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
1186         int const sub2 = dec64table[sequence.offset];
1187         op[0] = match[0];
1188         op[1] = match[1];
1189         op[2] = match[2];
1190         op[3] = match[3];
1191         match += dec32table[sequence.offset];
1192         ZSTD_copy4(op+4, match);
1193         match -= sub2;
1194     } else {
1195         ZSTD_copy8(op, match);
1196     }
1197     op += 8; match += 8;
1198
1199     if (oMatchEnd > oend-(16-MINMATCH)) {
1200         if (op < oend_w) {
1201             ZSTD_wildcopy(op, match, oend_w - op);
1202             match += oend_w - op;
1203             op = oend_w;
1204         }
1205         while (op < oMatchEnd) *op++ = *match++;
1206     } else {
1207         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
1208     }
1209     return sequenceLength;
1210 }
1211
1212
1213 HINT_INLINE
1214 size_t ZSTD_execSequenceLong(BYTE* op,
1215                              BYTE* const oend, seq_t sequence,
1216                              const BYTE** litPtr, const BYTE* const litLimit,
1217                              const BYTE* const prefixStart, const BYTE* const dictStart, const BYTE* const dictEnd)
1218 {
1219     BYTE* const oLitEnd = op + sequence.litLength;
1220     size_t const sequenceLength = sequence.litLength + sequence.matchLength;
1221     BYTE* const oMatchEnd = op + sequenceLength;   /* risk : address space overflow (32-bits) */
1222     BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
1223     const BYTE* const iLitEnd = *litPtr + sequence.litLength;
1224     const BYTE* match = sequence.match;
1225
1226     /* check */
1227     if (oMatchEnd > oend) return ERROR(dstSize_tooSmall); /* last match must start at a minimum distance of WILDCOPY_OVERLENGTH from oend */
1228     if (iLitEnd > litLimit) return ERROR(corruption_detected);   /* over-read beyond lit buffer */
1229     if (oLitEnd > oend_w) return ZSTD_execSequenceLast7(op, oend, sequence, litPtr, litLimit, prefixStart, dictStart, dictEnd);
1230
1231     /* copy Literals */
1232     ZSTD_copy8(op, *litPtr);  /* note : op <= oLitEnd <= oend_w == oend - 8 */
1233     if (sequence.litLength > 8)
1234         ZSTD_wildcopy(op+8, (*litPtr)+8, sequence.litLength - 8);   /* note : since oLitEnd <= oend-WILDCOPY_OVERLENGTH, no risk of overwrite beyond oend */
1235     op = oLitEnd;
1236     *litPtr = iLitEnd;   /* update for next sequence */
1237
1238     /* copy Match */
1239     if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
1240         /* offset beyond prefix */
1241         if (sequence.offset > (size_t)(oLitEnd - dictStart)) return ERROR(corruption_detected);
1242         if (match + sequence.matchLength <= dictEnd) {
1243             memmove(oLitEnd, match, sequence.matchLength);
1244             return sequenceLength;
1245         }
1246         /* span extDict & currentPrefixSegment */
1247         {   size_t const length1 = dictEnd - match;
1248             memmove(oLitEnd, match, length1);
1249             op = oLitEnd + length1;
1250             sequence.matchLength -= length1;
1251             match = prefixStart;
1252             if (op > oend_w || sequence.matchLength < MINMATCH) {
1253               U32 i;
1254               for (i = 0; i < sequence.matchLength; ++i) op[i] = match[i];
1255               return sequenceLength;
1256             }
1257     }   }
1258     assert(op <= oend_w);
1259     assert(sequence.matchLength >= MINMATCH);
1260
1261     /* match within prefix */
1262     if (sequence.offset < 8) {
1263         /* close range match, overlap */
1264         static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 };   /* added */
1265         static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 };   /* subtracted */
1266         int const sub2 = dec64table[sequence.offset];
1267         op[0] = match[0];
1268         op[1] = match[1];
1269         op[2] = match[2];
1270         op[3] = match[3];
1271         match += dec32table[sequence.offset];
1272         ZSTD_copy4(op+4, match);
1273         match -= sub2;
1274     } else {
1275         ZSTD_copy8(op, match);
1276     }
1277     op += 8; match += 8;
1278
1279     if (oMatchEnd > oend-(16-MINMATCH)) {
1280         if (op < oend_w) {
1281             ZSTD_wildcopy(op, match, oend_w - op);
1282             match += oend_w - op;
1283             op = oend_w;
1284         }
1285         while (op < oMatchEnd) *op++ = *match++;
1286     } else {
1287         ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8);   /* works even if matchLength < 8 */
1288     }
1289     return sequenceLength;
1290 }
1291
1292 static void
1293 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt)
1294 {
1295     const void* ptr = dt;
1296     const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
1297     DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
1298     DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
1299                 (U32)DStatePtr->state, DTableH->tableLog);
1300     BIT_reloadDStream(bitD);
1301     DStatePtr->table = dt + 1;
1302 }
1303
1304 FORCE_INLINE_TEMPLATE void
1305 ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD)
1306 {
1307     ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
1308     U32 const nbBits = DInfo.nbBits;
1309     size_t const lowBits = BIT_readBits(bitD, nbBits);
1310     DStatePtr->state = DInfo.nextState + lowBits;
1311 }
1312
1313 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
1314  * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
1315  * bits before reloading. This value is the maximum number of bytes we read
1316  * after reloading when we are decoding long offets.
1317  */
1318 #define LONG_OFFSETS_MAX_EXTRA_BITS_32                       \
1319     (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32       \
1320         ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32  \
1321         : 0)
1322
1323 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e;
1324
1325 FORCE_INLINE_TEMPLATE seq_t
1326 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets)
1327 {
1328     seq_t seq;
1329     U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
1330     U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
1331     U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
1332     U32 const totalBits = llBits+mlBits+ofBits;
1333     U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
1334     U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
1335     U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
1336
1337     /* sequence */
1338     {   size_t offset;
1339         if (!ofBits)
1340             offset = 0;
1341         else {
1342             ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
1343             ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
1344             assert(ofBits <= MaxOff);
1345             if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
1346                 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
1347                 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
1348                 BIT_reloadDStream(&seqState->DStream);
1349                 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
1350                 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32);   /* to avoid another reload */
1351             } else {
1352                 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/);   /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
1353                 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
1354             }
1355         }
1356
1357         if (ofBits <= 1) {
1358             offset += (llBase==0);
1359             if (offset) {
1360                 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1361                 temp += !temp;   /* 0 is not valid; input is corrupted; force offset to 1 */
1362                 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
1363                 seqState->prevOffset[1] = seqState->prevOffset[0];
1364                 seqState->prevOffset[0] = offset = temp;
1365             } else {  /* offset == 0 */
1366                 offset = seqState->prevOffset[0];
1367             }
1368         } else {
1369             seqState->prevOffset[2] = seqState->prevOffset[1];
1370             seqState->prevOffset[1] = seqState->prevOffset[0];
1371             seqState->prevOffset[0] = offset;
1372         }
1373         seq.offset = offset;
1374     }
1375
1376     seq.matchLength = mlBase
1377                     + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/) : 0);  /* <=  16 bits */
1378     if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
1379         BIT_reloadDStream(&seqState->DStream);
1380     if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
1381         BIT_reloadDStream(&seqState->DStream);
1382     /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
1383     ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
1384
1385     seq.litLength = llBase
1386                   + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits/*>0*/) : 0);    /* <=  16 bits */
1387     if (MEM_32bits())
1388         BIT_reloadDStream(&seqState->DStream);
1389
1390     DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
1391                 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
1392
1393     /* ANS state update */
1394     ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream);    /* <=  9 bits */
1395     ZSTD_updateFseState(&seqState->stateML, &seqState->DStream);    /* <=  9 bits */
1396     if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);    /* <= 18 bits */
1397     ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream);  /* <=  8 bits */
1398
1399     return seq;
1400 }
1401
1402 FORCE_INLINE_TEMPLATE size_t
1403 ZSTD_decompressSequences_body( ZSTD_DCtx* dctx,
1404                                void* dst, size_t maxDstSize,
1405                          const void* seqStart, size_t seqSize, int nbSeq,
1406                          const ZSTD_longOffset_e isLongOffset)
1407 {
1408     const BYTE* ip = (const BYTE*)seqStart;
1409     const BYTE* const iend = ip + seqSize;
1410     BYTE* const ostart = (BYTE* const)dst;
1411     BYTE* const oend = ostart + maxDstSize;
1412     BYTE* op = ostart;
1413     const BYTE* litPtr = dctx->litPtr;
1414     const BYTE* const litEnd = litPtr + dctx->litSize;
1415     const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1416     const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
1417     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1418     DEBUGLOG(5, "ZSTD_decompressSequences_body");
1419
1420     /* Regen sequences */
1421     if (nbSeq) {
1422         seqState_t seqState;
1423         dctx->fseEntropy = 1;
1424         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1425         CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend-ip), corruption_detected);
1426         ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1427         ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1428         ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1429
1430         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) {
1431             nbSeq--;
1432             {   seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset);
1433                 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
1434                 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
1435                 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1436                 op += oneSeqSize;
1437         }   }
1438
1439         /* check if reached exact end */
1440         DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
1441         if (nbSeq) return ERROR(corruption_detected);
1442         /* save reps for next block */
1443         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1444     }
1445
1446     /* last literal segment */
1447     {   size_t const lastLLSize = litEnd - litPtr;
1448         if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
1449         memcpy(op, litPtr, lastLLSize);
1450         op += lastLLSize;
1451     }
1452
1453     return op-ostart;
1454 }
1455
1456 static size_t
1457 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx,
1458                                  void* dst, size_t maxDstSize,
1459                            const void* seqStart, size_t seqSize, int nbSeq,
1460                            const ZSTD_longOffset_e isLongOffset)
1461 {
1462     return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1463 }
1464
1465
1466
1467 FORCE_INLINE_TEMPLATE seq_t
1468 ZSTD_decodeSequenceLong(seqState_t* seqState, ZSTD_longOffset_e const longOffsets)
1469 {
1470     seq_t seq;
1471     U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
1472     U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
1473     U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
1474     U32 const totalBits = llBits+mlBits+ofBits;
1475     U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
1476     U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
1477     U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
1478
1479     /* sequence */
1480     {   size_t offset;
1481         if (!ofBits)
1482             offset = 0;
1483         else {
1484             ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
1485             ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
1486             assert(ofBits <= MaxOff);
1487             if (MEM_32bits() && longOffsets) {
1488                 U32 const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN_32-1);
1489                 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
1490                 if (MEM_32bits() || extraBits) BIT_reloadDStream(&seqState->DStream);
1491                 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
1492             } else {
1493                 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits);   /* <=  (ZSTD_WINDOWLOG_MAX-1) bits */
1494                 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
1495             }
1496         }
1497
1498         if (ofBits <= 1) {
1499             offset += (llBase==0);
1500             if (offset) {
1501                 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1502                 temp += !temp;   /* 0 is not valid; input is corrupted; force offset to 1 */
1503                 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
1504                 seqState->prevOffset[1] = seqState->prevOffset[0];
1505                 seqState->prevOffset[0] = offset = temp;
1506             } else {
1507                 offset = seqState->prevOffset[0];
1508             }
1509         } else {
1510             seqState->prevOffset[2] = seqState->prevOffset[1];
1511             seqState->prevOffset[1] = seqState->prevOffset[0];
1512             seqState->prevOffset[0] = offset;
1513         }
1514         seq.offset = offset;
1515     }
1516
1517     seq.matchLength = mlBase + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0);  /* <=  16 bits */
1518     if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
1519         BIT_reloadDStream(&seqState->DStream);
1520     if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
1521         BIT_reloadDStream(&seqState->DStream);
1522     /* Verify that there is enough bits to read the rest of the data in 64-bit mode. */
1523     ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
1524
1525     seq.litLength = llBase + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0);    /* <=  16 bits */
1526     if (MEM_32bits())
1527         BIT_reloadDStream(&seqState->DStream);
1528
1529     {   size_t const pos = seqState->pos + seq.litLength;
1530         const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
1531         seq.match = matchBase + pos - seq.offset;  /* note : this operation can overflow when seq.offset is really too large, which can only happen when input is corrupted.
1532                                                     * No consequence though : no memory access will occur, overly large offset will be detected in ZSTD_execSequenceLong() */
1533         seqState->pos = pos + seq.matchLength;
1534     }
1535
1536     /* ANS state update */
1537     ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream);    /* <=  9 bits */
1538     ZSTD_updateFseState(&seqState->stateML, &seqState->DStream);    /* <=  9 bits */
1539     if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);    /* <= 18 bits */
1540     ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream);  /* <=  8 bits */
1541
1542     return seq;
1543 }
1544
1545 FORCE_INLINE_TEMPLATE size_t
1546 ZSTD_decompressSequencesLong_body(
1547                                ZSTD_DCtx* dctx,
1548                                void* dst, size_t maxDstSize,
1549                          const void* seqStart, size_t seqSize, int nbSeq,
1550                          const ZSTD_longOffset_e isLongOffset)
1551 {
1552     const BYTE* ip = (const BYTE*)seqStart;
1553     const BYTE* const iend = ip + seqSize;
1554     BYTE* const ostart = (BYTE* const)dst;
1555     BYTE* const oend = ostart + maxDstSize;
1556     BYTE* op = ostart;
1557     const BYTE* litPtr = dctx->litPtr;
1558     const BYTE* const litEnd = litPtr + dctx->litSize;
1559     const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1560     const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1561     const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1562
1563     /* Regen sequences */
1564     if (nbSeq) {
1565 #define STORED_SEQS 4
1566 #define STOSEQ_MASK (STORED_SEQS-1)
1567 #define ADVANCED_SEQS 4
1568         seq_t sequences[STORED_SEQS];
1569         int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1570         seqState_t seqState;
1571         int seqNb;
1572         dctx->fseEntropy = 1;
1573         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1574         seqState.prefixStart = prefixStart;
1575         seqState.pos = (size_t)(op-prefixStart);
1576         seqState.dictEnd = dictEnd;
1577         CHECK_E(BIT_initDStream(&seqState.DStream, ip, iend-ip), corruption_detected);
1578         ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1579         ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1580         ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1581
1582         /* prepare in advance */
1583         for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1584             sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1585         }
1586         if (seqNb<seqAdvance) return ERROR(corruption_detected);
1587
1588         /* decode and decompress */
1589         for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1590             seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1591             size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STOSEQ_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1592             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1593             PREFETCH(sequence.match);  /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */
1594             sequences[seqNb&STOSEQ_MASK] = sequence;
1595             op += oneSeqSize;
1596         }
1597         if (seqNb<nbSeq) return ERROR(corruption_detected);
1598
1599         /* finish queue */
1600         seqNb -= seqAdvance;
1601         for ( ; seqNb<nbSeq ; seqNb++) {
1602             size_t const oneSeqSize = ZSTD_execSequenceLong(op, oend, sequences[seqNb&STOSEQ_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1603             if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1604             op += oneSeqSize;
1605         }
1606
1607         /* save reps for next block */
1608         { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1609 #undef STORED_SEQS
1610 #undef STOSEQ_MASK
1611 #undef ADVANCED_SEQS
1612     }
1613
1614     /* last literal segment */
1615     {   size_t const lastLLSize = litEnd - litPtr;
1616         if (lastLLSize > (size_t)(oend-op)) return ERROR(dstSize_tooSmall);
1617         memcpy(op, litPtr, lastLLSize);
1618         op += lastLLSize;
1619     }
1620
1621     return op-ostart;
1622 }
1623
1624 static size_t
1625 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx,
1626                                  void* dst, size_t maxDstSize,
1627                            const void* seqStart, size_t seqSize, int nbSeq,
1628                            const ZSTD_longOffset_e isLongOffset)
1629 {
1630     return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1631 }
1632
1633
1634
1635 #if DYNAMIC_BMI2
1636
1637 static TARGET_ATTRIBUTE("bmi2") size_t
1638 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1639                                  void* dst, size_t maxDstSize,
1640                            const void* seqStart, size_t seqSize, int nbSeq,
1641                            const ZSTD_longOffset_e isLongOffset)
1642 {
1643     return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1644 }
1645
1646 static TARGET_ATTRIBUTE("bmi2") size_t
1647 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1648                                  void* dst, size_t maxDstSize,
1649                            const void* seqStart, size_t seqSize, int nbSeq,
1650                            const ZSTD_longOffset_e isLongOffset)
1651 {
1652     return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1653 }
1654
1655 #endif
1656
1657 typedef size_t (*ZSTD_decompressSequences_t)(
1658     ZSTD_DCtx *dctx, void *dst, size_t maxDstSize,
1659     const void *seqStart, size_t seqSize, int nbSeq,
1660     const ZSTD_longOffset_e isLongOffset);
1661
1662 static size_t ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1663                                 const void* seqStart, size_t seqSize, int nbSeq,
1664                                 const ZSTD_longOffset_e isLongOffset)
1665 {
1666     DEBUGLOG(5, "ZSTD_decompressSequences");
1667 #if DYNAMIC_BMI2
1668     if (dctx->bmi2) {
1669         return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1670     }
1671 #endif
1672   return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1673 }
1674
1675 static size_t ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx,
1676                                 void* dst, size_t maxDstSize,
1677                                 const void* seqStart, size_t seqSize, int nbSeq,
1678                                 const ZSTD_longOffset_e isLongOffset)
1679 {
1680     DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1681 #if DYNAMIC_BMI2
1682     if (dctx->bmi2) {
1683         return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1684     }
1685 #endif
1686   return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1687 }
1688
1689 /* ZSTD_getLongOffsetsShare() :
1690  * condition : offTable must be valid
1691  * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1692  *           compared to maximum possible of (1<<OffFSELog) */
1693 static unsigned
1694 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable)
1695 {
1696     const void* ptr = offTable;
1697     U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1698     const ZSTD_seqSymbol* table = offTable + 1;
1699     U32 const max = 1 << tableLog;
1700     U32 u, total = 0;
1701     DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1702
1703     assert(max <= (1 << OffFSELog));  /* max not too large */
1704     for (u=0; u<max; u++) {
1705         if (table[u].nbAdditionalBits > 22) total += 1;
1706     }
1707
1708     assert(tableLog <= OffFSELog);
1709     total <<= (OffFSELog - tableLog);  /* scale to OffFSELog */
1710
1711     return total;
1712 }
1713
1714
1715 static size_t ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
1716                             void* dst, size_t dstCapacity,
1717                       const void* src, size_t srcSize, const int frame)
1718 {   /* blockType == blockCompressed */
1719     const BYTE* ip = (const BYTE*)src;
1720     /* isLongOffset must be true if there are long offsets.
1721      * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1722      * We don't expect that to be the case in 64-bit mode.
1723      * In block mode, window size is not known, so we have to be conservative.
1724      * (note: but it could be evaluated from current-lowLimit)
1725      */
1726     ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN)));
1727     DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1728
1729     if (srcSize >= ZSTD_BLOCKSIZE_MAX) return ERROR(srcSize_wrong);
1730
1731     /* Decode literals section */
1732     {   size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1733         DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1734         if (ZSTD_isError(litCSize)) return litCSize;
1735         ip += litCSize;
1736         srcSize -= litCSize;
1737     }
1738
1739     /* Build Decoding Tables */
1740     {   int nbSeq;
1741         size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1742         if (ZSTD_isError(seqHSize)) return seqHSize;
1743         ip += seqHSize;
1744         srcSize -= seqHSize;
1745
1746         if ( (!frame || dctx->fParams.windowSize > (1<<24))
1747           && (nbSeq>0) ) {  /* could probably use a larger nbSeq limit */
1748             U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1749             U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1750             if (shareLongOffsets >= minShare)
1751                 return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1752         }
1753
1754         return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1755     }
1756 }
1757
1758
1759 static void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst)
1760 {
1761     if (dst != dctx->previousDstEnd) {   /* not contiguous */
1762         dctx->dictEnd = dctx->previousDstEnd;
1763         dctx->virtualStart = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart));
1764         dctx->prefixStart = dst;
1765         dctx->previousDstEnd = dst;
1766     }
1767 }
1768
1769 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1770                             void* dst, size_t dstCapacity,
1771                       const void* src, size_t srcSize)
1772 {
1773     size_t dSize;
1774     ZSTD_checkContinuity(dctx, dst);
1775     dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1776     dctx->previousDstEnd = (char*)dst + dSize;
1777     return dSize;
1778 }
1779
1780
1781 /** ZSTD_insertBlock() :
1782     insert `src` block into `dctx` history. Useful to track uncompressed blocks. */
1783 ZSTDLIB_API size_t ZSTD_insertBlock(ZSTD_DCtx* dctx, const void* blockStart, size_t blockSize)
1784 {
1785     ZSTD_checkContinuity(dctx, blockStart);
1786     dctx->previousDstEnd = (const char*)blockStart + blockSize;
1787     return blockSize;
1788 }
1789
1790
1791 static size_t ZSTD_generateNxBytes(void* dst, size_t dstCapacity, BYTE value, size_t length)
1792 {
1793     if (length > dstCapacity) return ERROR(dstSize_tooSmall);
1794     memset(dst, value, length);
1795     return length;
1796 }
1797
1798 /** ZSTD_findFrameCompressedSize() :
1799  *  compatible with legacy mode
1800  *  `src` must point to the start of a ZSTD frame, ZSTD legacy frame, or skippable frame
1801  *  `srcSize` must be at least as large as the frame contained
1802  *  @return : the compressed size of the frame starting at `src` */
1803 size_t ZSTD_findFrameCompressedSize(const void *src, size_t srcSize)
1804 {
1805 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
1806     if (ZSTD_isLegacy(src, srcSize))
1807         return ZSTD_findFrameCompressedSizeLegacy(src, srcSize);
1808 #endif
1809     if ( (srcSize >= ZSTD_skippableHeaderSize)
1810       && (MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START ) {
1811         return ZSTD_skippableHeaderSize + MEM_readLE32((const BYTE*)src + ZSTD_FRAMEIDSIZE);
1812     } else {
1813         const BYTE* ip = (const BYTE*)src;
1814         const BYTE* const ipstart = ip;
1815         size_t remainingSize = srcSize;
1816         ZSTD_frameHeader zfh;
1817
1818         /* Extract Frame Header */
1819         {   size_t const ret = ZSTD_getFrameHeader(&zfh, src, srcSize);
1820             if (ZSTD_isError(ret)) return ret;
1821             if (ret > 0) return ERROR(srcSize_wrong);
1822         }
1823
1824         ip += zfh.headerSize;
1825         remainingSize -= zfh.headerSize;
1826
1827         /* Loop on each block */
1828         while (1) {
1829             blockProperties_t blockProperties;
1830             size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1831             if (ZSTD_isError(cBlockSize)) return cBlockSize;
1832
1833             if (ZSTD_blockHeaderSize + cBlockSize > remainingSize)
1834                 return ERROR(srcSize_wrong);
1835
1836             ip += ZSTD_blockHeaderSize + cBlockSize;
1837             remainingSize -= ZSTD_blockHeaderSize + cBlockSize;
1838
1839             if (blockProperties.lastBlock) break;
1840         }
1841
1842         if (zfh.checksumFlag) {   /* Final frame content checksum */
1843             if (remainingSize < 4) return ERROR(srcSize_wrong);
1844             ip += 4;
1845         }
1846
1847         return ip - ipstart;
1848     }
1849 }
1850
1851 /*! ZSTD_decompressFrame() :
1852 *   @dctx must be properly initialized */
1853 static size_t ZSTD_decompressFrame(ZSTD_DCtx* dctx,
1854                                    void* dst, size_t dstCapacity,
1855                              const void** srcPtr, size_t *srcSizePtr)
1856 {
1857     const BYTE* ip = (const BYTE*)(*srcPtr);
1858     BYTE* const ostart = (BYTE* const)dst;
1859     BYTE* const oend = ostart + dstCapacity;
1860     BYTE* op = ostart;
1861     size_t remainingSize = *srcSizePtr;
1862
1863     /* check */
1864     if (remainingSize < ZSTD_frameHeaderSize_min+ZSTD_blockHeaderSize)
1865         return ERROR(srcSize_wrong);
1866
1867     /* Frame Header */
1868     {   size_t const frameHeaderSize = ZSTD_frameHeaderSize(ip, ZSTD_frameHeaderSize_prefix);
1869         if (ZSTD_isError(frameHeaderSize)) return frameHeaderSize;
1870         if (remainingSize < frameHeaderSize+ZSTD_blockHeaderSize)
1871             return ERROR(srcSize_wrong);
1872         CHECK_F( ZSTD_decodeFrameHeader(dctx, ip, frameHeaderSize) );
1873         ip += frameHeaderSize; remainingSize -= frameHeaderSize;
1874     }
1875
1876     /* Loop on each block */
1877     while (1) {
1878         size_t decodedSize;
1879         blockProperties_t blockProperties;
1880         size_t const cBlockSize = ZSTD_getcBlockSize(ip, remainingSize, &blockProperties);
1881         if (ZSTD_isError(cBlockSize)) return cBlockSize;
1882
1883         ip += ZSTD_blockHeaderSize;
1884         remainingSize -= ZSTD_blockHeaderSize;
1885         if (cBlockSize > remainingSize) return ERROR(srcSize_wrong);
1886
1887         switch(blockProperties.blockType)
1888         {
1889         case bt_compressed:
1890             decodedSize = ZSTD_decompressBlock_internal(dctx, op, oend-op, ip, cBlockSize, /* frame */ 1);
1891             break;
1892         case bt_raw :
1893             decodedSize = ZSTD_copyRawBlock(op, oend-op, ip, cBlockSize);
1894             break;
1895         case bt_rle :
1896             decodedSize = ZSTD_generateNxBytes(op, oend-op, *ip, blockProperties.origSize);
1897             break;
1898         case bt_reserved :
1899         default:
1900             return ERROR(corruption_detected);
1901         }
1902
1903         if (ZSTD_isError(decodedSize)) return decodedSize;
1904         if (dctx->fParams.checksumFlag)
1905             XXH64_update(&dctx->xxhState, op, decodedSize);
1906         op += decodedSize;
1907         ip += cBlockSize;
1908         remainingSize -= cBlockSize;
1909         if (blockProperties.lastBlock) break;
1910     }
1911
1912     if (dctx->fParams.frameContentSize != ZSTD_CONTENTSIZE_UNKNOWN) {
1913         if ((U64)(op-ostart) != dctx->fParams.frameContentSize) {
1914             return ERROR(corruption_detected);
1915     }   }
1916     if (dctx->fParams.checksumFlag) { /* Frame content checksum verification */
1917         U32 const checkCalc = (U32)XXH64_digest(&dctx->xxhState);
1918         U32 checkRead;
1919         if (remainingSize<4) return ERROR(checksum_wrong);
1920         checkRead = MEM_readLE32(ip);
1921         if (checkRead != checkCalc) return ERROR(checksum_wrong);
1922         ip += 4;
1923         remainingSize -= 4;
1924     }
1925
1926     /* Allow caller to get size read */
1927     *srcPtr = ip;
1928     *srcSizePtr = remainingSize;
1929     return op-ostart;
1930 }
1931
1932 static size_t ZSTD_decompressMultiFrame(ZSTD_DCtx* dctx,
1933                                         void* dst, size_t dstCapacity,
1934                                   const void* src, size_t srcSize,
1935                                   const void* dict, size_t dictSize,
1936                                   const ZSTD_DDict* ddict)
1937 {
1938     void* const dststart = dst;
1939     int moreThan1Frame = 0;
1940
1941     DEBUGLOG(5, "ZSTD_decompressMultiFrame");
1942     assert(dict==NULL || ddict==NULL);  /* either dict or ddict set, not both */
1943
1944     if (ddict) {
1945         dict = ZSTD_DDictDictContent(ddict);
1946         dictSize = ZSTD_DDictDictSize(ddict);
1947     }
1948
1949     while (srcSize >= ZSTD_frameHeaderSize_prefix) {
1950
1951 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT >= 1)
1952         if (ZSTD_isLegacy(src, srcSize)) {
1953             size_t decodedSize;
1954             size_t const frameSize = ZSTD_findFrameCompressedSizeLegacy(src, srcSize);
1955             if (ZSTD_isError(frameSize)) return frameSize;
1956             /* legacy support is not compatible with static dctx */
1957             if (dctx->staticSize) return ERROR(memory_allocation);
1958
1959             decodedSize = ZSTD_decompressLegacy(dst, dstCapacity, src, frameSize, dict, dictSize);
1960
1961             dst = (BYTE*)dst + decodedSize;
1962             dstCapacity -= decodedSize;
1963
1964             src = (const BYTE*)src + frameSize;
1965             srcSize -= frameSize;
1966
1967             continue;
1968         }
1969 #endif
1970
1971         {   U32 const magicNumber = MEM_readLE32(src);
1972             DEBUGLOG(4, "reading magic number %08X (expecting %08X)",
1973                         (U32)magicNumber, (U32)ZSTD_MAGICNUMBER);
1974             if ((magicNumber & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {
1975                 size_t skippableSize;
1976                 if (srcSize < ZSTD_skippableHeaderSize)
1977                     return ERROR(srcSize_wrong);
1978                 skippableSize = MEM_readLE32((const BYTE*)src + ZSTD_FRAMEIDSIZE)
1979                               + ZSTD_skippableHeaderSize;
1980                 if (srcSize < skippableSize) return ERROR(srcSize_wrong);
1981
1982                 src = (const BYTE *)src + skippableSize;
1983                 srcSize -= skippableSize;
1984                 continue;
1985         }   }
1986
1987         if (ddict) {
1988             /* we were called from ZSTD_decompress_usingDDict */
1989             CHECK_F(ZSTD_decompressBegin_usingDDict(dctx, ddict));
1990         } else {
1991             /* this will initialize correctly with no dict if dict == NULL, so
1992              * use this in all cases but ddict */
1993             CHECK_F(ZSTD_decompressBegin_usingDict(dctx, dict, dictSize));
1994         }
1995         ZSTD_checkContinuity(dctx, dst);
1996
1997         {   const size_t res = ZSTD_decompressFrame(dctx, dst, dstCapacity,
1998                                                     &src, &srcSize);
1999             if ( (ZSTD_getErrorCode(res) == ZSTD_error_prefix_unknown)
2000               && (moreThan1Frame==1) ) {
2001                 /* at least one frame successfully completed,
2002                  * but following bytes are garbage :
2003                  * it's more likely to be a srcSize error,
2004                  * specifying more bytes than compressed size of frame(s).
2005                  * This error message replaces ERROR(prefix_unknown),
2006                  * which would be confusing, as the first header is actually correct.
2007                  * Note that one could be unlucky, it might be a corruption error instead,
2008                  * happening right at the place where we expect zstd magic bytes.
2009                  * But this is _much_ less likely than a srcSize field error. */
2010                 return ERROR(srcSize_wrong);
2011             }
2012             if (ZSTD_isError(res)) return res;
2013             /* no need to bound check, ZSTD_decompressFrame already has */
2014             dst = (BYTE*)dst + res;
2015             dstCapacity -= res;
2016         }
2017         moreThan1Frame = 1;
2018     }  /* while (srcSize >= ZSTD_frameHeaderSize_prefix) */
2019
2020     if (srcSize) return ERROR(srcSize_wrong); /* input not entirely consumed */
2021
2022     return (BYTE*)dst - (BYTE*)dststart;
2023 }
2024
2025 size_t ZSTD_decompress_usingDict(ZSTD_DCtx* dctx,
2026                                  void* dst, size_t dstCapacity,
2027                            const void* src, size_t srcSize,
2028                            const void* dict, size_t dictSize)
2029 {
2030     return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize, dict, dictSize, NULL);
2031 }
2032
2033
2034 size_t ZSTD_decompressDCtx(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2035 {
2036     return ZSTD_decompress_usingDict(dctx, dst, dstCapacity, src, srcSize, NULL, 0);
2037 }
2038
2039
2040 size_t ZSTD_decompress(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2041 {
2042 #if defined(ZSTD_HEAPMODE) && (ZSTD_HEAPMODE>=1)
2043     size_t regenSize;
2044     ZSTD_DCtx* const dctx = ZSTD_createDCtx();
2045     if (dctx==NULL) return ERROR(memory_allocation);
2046     regenSize = ZSTD_decompressDCtx(dctx, dst, dstCapacity, src, srcSize);
2047     ZSTD_freeDCtx(dctx);
2048     return regenSize;
2049 #else   /* stack mode */
2050     ZSTD_DCtx dctx;
2051     ZSTD_initDCtx_internal(&dctx);
2052     return ZSTD_decompressDCtx(&dctx, dst, dstCapacity, src, srcSize);
2053 #endif
2054 }
2055
2056
2057 /*-**************************************
2058 *   Advanced Streaming Decompression API
2059 *   Bufferless and synchronous
2060 ****************************************/
2061 size_t ZSTD_nextSrcSizeToDecompress(ZSTD_DCtx* dctx) { return dctx->expected; }
2062
2063 ZSTD_nextInputType_e ZSTD_nextInputType(ZSTD_DCtx* dctx) {
2064     switch(dctx->stage)
2065     {
2066     default:   /* should not happen */
2067         assert(0);
2068     case ZSTDds_getFrameHeaderSize:
2069     case ZSTDds_decodeFrameHeader:
2070         return ZSTDnit_frameHeader;
2071     case ZSTDds_decodeBlockHeader:
2072         return ZSTDnit_blockHeader;
2073     case ZSTDds_decompressBlock:
2074         return ZSTDnit_block;
2075     case ZSTDds_decompressLastBlock:
2076         return ZSTDnit_lastBlock;
2077     case ZSTDds_checkChecksum:
2078         return ZSTDnit_checksum;
2079     case ZSTDds_decodeSkippableHeader:
2080     case ZSTDds_skipFrame:
2081         return ZSTDnit_skippableFrame;
2082     }
2083 }
2084
2085 static int ZSTD_isSkipFrame(ZSTD_DCtx* dctx) { return dctx->stage == ZSTDds_skipFrame; }
2086
2087 /** ZSTD_decompressContinue() :
2088  *  srcSize : must be the exact nb of bytes expected (see ZSTD_nextSrcSizeToDecompress())
2089  *  @return : nb of bytes generated into `dst` (necessarily <= `dstCapacity)
2090  *            or an error code, which can be tested using ZSTD_isError() */
2091 size_t ZSTD_decompressContinue(ZSTD_DCtx* dctx, void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2092 {
2093     DEBUGLOG(5, "ZSTD_decompressContinue (srcSize:%u)", (U32)srcSize);
2094     /* Sanity check */
2095     if (srcSize != dctx->expected) return ERROR(srcSize_wrong);  /* not allowed */
2096     if (dstCapacity) ZSTD_checkContinuity(dctx, dst);
2097
2098     switch (dctx->stage)
2099     {
2100     case ZSTDds_getFrameHeaderSize :
2101         assert(src != NULL);
2102         if (dctx->format == ZSTD_f_zstd1) {  /* allows header */
2103             assert(srcSize >= ZSTD_FRAMEIDSIZE);  /* to read skippable magic number */
2104             if ((MEM_readLE32(src) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {        /* skippable frame */
2105                 memcpy(dctx->headerBuffer, src, srcSize);
2106                 dctx->expected = ZSTD_skippableHeaderSize - srcSize;  /* remaining to load to get full skippable frame header */
2107                 dctx->stage = ZSTDds_decodeSkippableHeader;
2108                 return 0;
2109         }   }
2110         dctx->headerSize = ZSTD_frameHeaderSize_internal(src, srcSize, dctx->format);
2111         if (ZSTD_isError(dctx->headerSize)) return dctx->headerSize;
2112         memcpy(dctx->headerBuffer, src, srcSize);
2113         dctx->expected = dctx->headerSize - srcSize;
2114         dctx->stage = ZSTDds_decodeFrameHeader;
2115         return 0;
2116
2117     case ZSTDds_decodeFrameHeader:
2118         assert(src != NULL);
2119         memcpy(dctx->headerBuffer + (dctx->headerSize - srcSize), src, srcSize);
2120         CHECK_F(ZSTD_decodeFrameHeader(dctx, dctx->headerBuffer, dctx->headerSize));
2121         dctx->expected = ZSTD_blockHeaderSize;
2122         dctx->stage = ZSTDds_decodeBlockHeader;
2123         return 0;
2124
2125     case ZSTDds_decodeBlockHeader:
2126         {   blockProperties_t bp;
2127             size_t const cBlockSize = ZSTD_getcBlockSize(src, ZSTD_blockHeaderSize, &bp);
2128             if (ZSTD_isError(cBlockSize)) return cBlockSize;
2129             dctx->expected = cBlockSize;
2130             dctx->bType = bp.blockType;
2131             dctx->rleSize = bp.origSize;
2132             if (cBlockSize) {
2133                 dctx->stage = bp.lastBlock ? ZSTDds_decompressLastBlock : ZSTDds_decompressBlock;
2134                 return 0;
2135             }
2136             /* empty block */
2137             if (bp.lastBlock) {
2138                 if (dctx->fParams.checksumFlag) {
2139                     dctx->expected = 4;
2140                     dctx->stage = ZSTDds_checkChecksum;
2141                 } else {
2142                     dctx->expected = 0; /* end of frame */
2143                     dctx->stage = ZSTDds_getFrameHeaderSize;
2144                 }
2145             } else {
2146                 dctx->expected = ZSTD_blockHeaderSize;  /* jump to next header */
2147                 dctx->stage = ZSTDds_decodeBlockHeader;
2148             }
2149             return 0;
2150         }
2151
2152     case ZSTDds_decompressLastBlock:
2153     case ZSTDds_decompressBlock:
2154         DEBUGLOG(5, "ZSTD_decompressContinue: case ZSTDds_decompressBlock");
2155         {   size_t rSize;
2156             switch(dctx->bType)
2157             {
2158             case bt_compressed:
2159                 DEBUGLOG(5, "ZSTD_decompressContinue: case bt_compressed");
2160                 rSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 1);
2161                 break;
2162             case bt_raw :
2163                 rSize = ZSTD_copyRawBlock(dst, dstCapacity, src, srcSize);
2164                 break;
2165             case bt_rle :
2166                 rSize = ZSTD_setRleBlock(dst, dstCapacity, src, srcSize, dctx->rleSize);
2167                 break;
2168             case bt_reserved :   /* should never happen */
2169             default:
2170                 return ERROR(corruption_detected);
2171             }
2172             if (ZSTD_isError(rSize)) return rSize;
2173             DEBUGLOG(5, "ZSTD_decompressContinue: decoded size from block : %u", (U32)rSize);
2174             dctx->decodedSize += rSize;
2175             if (dctx->fParams.checksumFlag) XXH64_update(&dctx->xxhState, dst, rSize);
2176
2177             if (dctx->stage == ZSTDds_decompressLastBlock) {   /* end of frame */
2178                 DEBUGLOG(4, "ZSTD_decompressContinue: decoded size from frame : %u", (U32)dctx->decodedSize);
2179                 if (dctx->fParams.frameContentSize != ZSTD_CONTENTSIZE_UNKNOWN) {
2180                     if (dctx->decodedSize != dctx->fParams.frameContentSize) {
2181                         return ERROR(corruption_detected);
2182                 }   }
2183                 if (dctx->fParams.checksumFlag) {  /* another round for frame checksum */
2184                     dctx->expected = 4;
2185                     dctx->stage = ZSTDds_checkChecksum;
2186                 } else {
2187                     dctx->expected = 0;   /* ends here */
2188                     dctx->stage = ZSTDds_getFrameHeaderSize;
2189                 }
2190             } else {
2191                 dctx->stage = ZSTDds_decodeBlockHeader;
2192                 dctx->expected = ZSTD_blockHeaderSize;
2193                 dctx->previousDstEnd = (char*)dst + rSize;
2194             }
2195             return rSize;
2196         }
2197
2198     case ZSTDds_checkChecksum:
2199         assert(srcSize == 4);  /* guaranteed by dctx->expected */
2200         {   U32 const h32 = (U32)XXH64_digest(&dctx->xxhState);
2201             U32 const check32 = MEM_readLE32(src);
2202             DEBUGLOG(4, "ZSTD_decompressContinue: checksum : calculated %08X :: %08X read", h32, check32);
2203             if (check32 != h32) return ERROR(checksum_wrong);
2204             dctx->expected = 0;
2205             dctx->stage = ZSTDds_getFrameHeaderSize;
2206             return 0;
2207         }
2208
2209     case ZSTDds_decodeSkippableHeader:
2210         assert(src != NULL);
2211         assert(srcSize <= ZSTD_skippableHeaderSize);
2212         memcpy(dctx->headerBuffer + (ZSTD_skippableHeaderSize - srcSize), src, srcSize);   /* complete skippable header */
2213         dctx->expected = MEM_readLE32(dctx->headerBuffer + ZSTD_FRAMEIDSIZE);   /* note : dctx->expected can grow seriously large, beyond local buffer size */
2214         dctx->stage = ZSTDds_skipFrame;
2215         return 0;
2216
2217     case ZSTDds_skipFrame:
2218         dctx->expected = 0;
2219         dctx->stage = ZSTDds_getFrameHeaderSize;
2220         return 0;
2221
2222     default:
2223         return ERROR(GENERIC);   /* impossible */
2224     }
2225 }
2226
2227
2228 static size_t ZSTD_refDictContent(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2229 {
2230     dctx->dictEnd = dctx->previousDstEnd;
2231     dctx->virtualStart = (const char*)dict - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart));
2232     dctx->prefixStart = dict;
2233     dctx->previousDstEnd = (const char*)dict + dictSize;
2234     return 0;
2235 }
2236
2237 /*! ZSTD_loadEntropy() :
2238  *  dict : must point at beginning of a valid zstd dictionary.
2239  * @return : size of entropy tables read */
2240 static size_t ZSTD_loadEntropy(ZSTD_entropyDTables_t* entropy,
2241                          const void* const dict, size_t const dictSize)
2242 {
2243     const BYTE* dictPtr = (const BYTE*)dict;
2244     const BYTE* const dictEnd = dictPtr + dictSize;
2245
2246     if (dictSize <= 8) return ERROR(dictionary_corrupted);
2247     assert(MEM_readLE32(dict) == ZSTD_MAGIC_DICTIONARY);   /* dict must be valid */
2248     dictPtr += 8;   /* skip header = magic + dictID */
2249
2250     ZSTD_STATIC_ASSERT(offsetof(ZSTD_entropyDTables_t, OFTable) == offsetof(ZSTD_entropyDTables_t, LLTable) + sizeof(entropy->LLTable));
2251     ZSTD_STATIC_ASSERT(offsetof(ZSTD_entropyDTables_t, MLTable) == offsetof(ZSTD_entropyDTables_t, OFTable) + sizeof(entropy->OFTable));
2252     ZSTD_STATIC_ASSERT(sizeof(entropy->LLTable) + sizeof(entropy->OFTable) + sizeof(entropy->MLTable) >= HUF_DECOMPRESS_WORKSPACE_SIZE);
2253     {   void* const workspace = &entropy->LLTable;   /* use fse tables as temporary workspace; implies fse tables are grouped together */
2254         size_t const workspaceSize = sizeof(entropy->LLTable) + sizeof(entropy->OFTable) + sizeof(entropy->MLTable);
2255         size_t const hSize = HUF_readDTableX2_wksp(entropy->hufTable,
2256                                                 dictPtr, dictEnd - dictPtr,
2257                                                 workspace, workspaceSize);
2258         if (HUF_isError(hSize)) return ERROR(dictionary_corrupted);
2259         dictPtr += hSize;
2260     }
2261
2262     {   short offcodeNCount[MaxOff+1];
2263         U32 offcodeMaxValue = MaxOff, offcodeLog;
2264         size_t const offcodeHeaderSize = FSE_readNCount(offcodeNCount, &offcodeMaxValue, &offcodeLog, dictPtr, dictEnd-dictPtr);
2265         if (FSE_isError(offcodeHeaderSize)) return ERROR(dictionary_corrupted);
2266         if (offcodeMaxValue > MaxOff) return ERROR(dictionary_corrupted);
2267         if (offcodeLog > OffFSELog) return ERROR(dictionary_corrupted);
2268         ZSTD_buildFSETable( entropy->OFTable,
2269                             offcodeNCount, offcodeMaxValue,
2270                             OF_base, OF_bits,
2271                             offcodeLog);
2272         dictPtr += offcodeHeaderSize;
2273     }
2274
2275     {   short matchlengthNCount[MaxML+1];
2276         unsigned matchlengthMaxValue = MaxML, matchlengthLog;
2277         size_t const matchlengthHeaderSize = FSE_readNCount(matchlengthNCount, &matchlengthMaxValue, &matchlengthLog, dictPtr, dictEnd-dictPtr);
2278         if (FSE_isError(matchlengthHeaderSize)) return ERROR(dictionary_corrupted);
2279         if (matchlengthMaxValue > MaxML) return ERROR(dictionary_corrupted);
2280         if (matchlengthLog > MLFSELog) return ERROR(dictionary_corrupted);
2281         ZSTD_buildFSETable( entropy->MLTable,
2282                             matchlengthNCount, matchlengthMaxValue,
2283                             ML_base, ML_bits,
2284                             matchlengthLog);
2285         dictPtr += matchlengthHeaderSize;
2286     }
2287
2288     {   short litlengthNCount[MaxLL+1];
2289         unsigned litlengthMaxValue = MaxLL, litlengthLog;
2290         size_t const litlengthHeaderSize = FSE_readNCount(litlengthNCount, &litlengthMaxValue, &litlengthLog, dictPtr, dictEnd-dictPtr);
2291         if (FSE_isError(litlengthHeaderSize)) return ERROR(dictionary_corrupted);
2292         if (litlengthMaxValue > MaxLL) return ERROR(dictionary_corrupted);
2293         if (litlengthLog > LLFSELog) return ERROR(dictionary_corrupted);
2294         ZSTD_buildFSETable( entropy->LLTable,
2295                             litlengthNCount, litlengthMaxValue,
2296                             LL_base, LL_bits,
2297                             litlengthLog);
2298         dictPtr += litlengthHeaderSize;
2299     }
2300
2301     if (dictPtr+12 > dictEnd) return ERROR(dictionary_corrupted);
2302     {   int i;
2303         size_t const dictContentSize = (size_t)(dictEnd - (dictPtr+12));
2304         for (i=0; i<3; i++) {
2305             U32 const rep = MEM_readLE32(dictPtr); dictPtr += 4;
2306             if (rep==0 || rep >= dictContentSize) return ERROR(dictionary_corrupted);
2307             entropy->rep[i] = rep;
2308     }   }
2309
2310     return dictPtr - (const BYTE*)dict;
2311 }
2312
2313 static size_t ZSTD_decompress_insertDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2314 {
2315     if (dictSize < 8) return ZSTD_refDictContent(dctx, dict, dictSize);
2316     {   U32 const magic = MEM_readLE32(dict);
2317         if (magic != ZSTD_MAGIC_DICTIONARY) {
2318             return ZSTD_refDictContent(dctx, dict, dictSize);   /* pure content mode */
2319     }   }
2320     dctx->dictID = MEM_readLE32((const char*)dict + ZSTD_FRAMEIDSIZE);
2321
2322     /* load entropy tables */
2323     {   size_t const eSize = ZSTD_loadEntropy(&dctx->entropy, dict, dictSize);
2324         if (ZSTD_isError(eSize)) return ERROR(dictionary_corrupted);
2325         dict = (const char*)dict + eSize;
2326         dictSize -= eSize;
2327     }
2328     dctx->litEntropy = dctx->fseEntropy = 1;
2329
2330     /* reference dictionary content */
2331     return ZSTD_refDictContent(dctx, dict, dictSize);
2332 }
2333
2334 size_t ZSTD_decompressBegin(ZSTD_DCtx* dctx)
2335 {
2336     assert(dctx != NULL);
2337     dctx->expected = ZSTD_startingInputLength(dctx->format);  /* dctx->format must be properly set */
2338     dctx->stage = ZSTDds_getFrameHeaderSize;
2339     dctx->decodedSize = 0;
2340     dctx->previousDstEnd = NULL;
2341     dctx->prefixStart = NULL;
2342     dctx->virtualStart = NULL;
2343     dctx->dictEnd = NULL;
2344     dctx->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001);  /* cover both little and big endian */
2345     dctx->litEntropy = dctx->fseEntropy = 0;
2346     dctx->dictID = 0;
2347     ZSTD_STATIC_ASSERT(sizeof(dctx->entropy.rep) == sizeof(repStartValue));
2348     memcpy(dctx->entropy.rep, repStartValue, sizeof(repStartValue));  /* initial repcodes */
2349     dctx->LLTptr = dctx->entropy.LLTable;
2350     dctx->MLTptr = dctx->entropy.MLTable;
2351     dctx->OFTptr = dctx->entropy.OFTable;
2352     dctx->HUFptr = dctx->entropy.hufTable;
2353     return 0;
2354 }
2355
2356 size_t ZSTD_decompressBegin_usingDict(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2357 {
2358     CHECK_F( ZSTD_decompressBegin(dctx) );
2359     if (dict && dictSize)
2360         CHECK_E(ZSTD_decompress_insertDictionary(dctx, dict, dictSize), dictionary_corrupted);
2361     return 0;
2362 }
2363
2364
2365 /* ======   ZSTD_DDict   ====== */
2366
2367 struct ZSTD_DDict_s {
2368     void* dictBuffer;
2369     const void* dictContent;
2370     size_t dictSize;
2371     ZSTD_entropyDTables_t entropy;
2372     U32 dictID;
2373     U32 entropyPresent;
2374     ZSTD_customMem cMem;
2375 };  /* typedef'd to ZSTD_DDict within "zstd.h" */
2376
2377 static const void* ZSTD_DDictDictContent(const ZSTD_DDict* ddict)
2378 {
2379     assert(ddict != NULL);
2380     return ddict->dictContent;
2381 }
2382
2383 static size_t ZSTD_DDictDictSize(const ZSTD_DDict* ddict)
2384 {
2385     assert(ddict != NULL);
2386     return ddict->dictSize;
2387 }
2388
2389 size_t ZSTD_decompressBegin_usingDDict(ZSTD_DCtx* dctx, const ZSTD_DDict* ddict)
2390 {
2391     DEBUGLOG(4, "ZSTD_decompressBegin_usingDDict");
2392     assert(dctx != NULL);
2393     if (ddict) {
2394         dctx->ddictIsCold = (dctx->dictEnd != (const char*)ddict->dictContent + ddict->dictSize);
2395         DEBUGLOG(4, "DDict is %s",
2396                     dctx->ddictIsCold ? "~cold~" : "hot!");
2397     }
2398     CHECK_F( ZSTD_decompressBegin(dctx) );
2399     if (ddict) {   /* NULL ddict is equivalent to no dictionary */
2400         dctx->dictID = ddict->dictID;
2401         dctx->prefixStart = ddict->dictContent;
2402         dctx->virtualStart = ddict->dictContent;
2403         dctx->dictEnd = (const BYTE*)ddict->dictContent + ddict->dictSize;
2404         dctx->previousDstEnd = dctx->dictEnd;
2405         if (ddict->entropyPresent) {
2406             dctx->litEntropy = 1;
2407             dctx->fseEntropy = 1;
2408             dctx->LLTptr = ddict->entropy.LLTable;
2409             dctx->MLTptr = ddict->entropy.MLTable;
2410             dctx->OFTptr = ddict->entropy.OFTable;
2411             dctx->HUFptr = ddict->entropy.hufTable;
2412             dctx->entropy.rep[0] = ddict->entropy.rep[0];
2413             dctx->entropy.rep[1] = ddict->entropy.rep[1];
2414             dctx->entropy.rep[2] = ddict->entropy.rep[2];
2415         } else {
2416             dctx->litEntropy = 0;
2417             dctx->fseEntropy = 0;
2418         }
2419     }
2420     return 0;
2421 }
2422
2423 static size_t
2424 ZSTD_loadEntropy_inDDict(ZSTD_DDict* ddict,
2425                          ZSTD_dictContentType_e dictContentType)
2426 {
2427     ddict->dictID = 0;
2428     ddict->entropyPresent = 0;
2429     if (dictContentType == ZSTD_dct_rawContent) return 0;
2430
2431     if (ddict->dictSize < 8) {
2432         if (dictContentType == ZSTD_dct_fullDict)
2433             return ERROR(dictionary_corrupted);   /* only accept specified dictionaries */
2434         return 0;   /* pure content mode */
2435     }
2436     {   U32 const magic = MEM_readLE32(ddict->dictContent);
2437         if (magic != ZSTD_MAGIC_DICTIONARY) {
2438             if (dictContentType == ZSTD_dct_fullDict)
2439                 return ERROR(dictionary_corrupted);   /* only accept specified dictionaries */
2440             return 0;   /* pure content mode */
2441         }
2442     }
2443     ddict->dictID = MEM_readLE32((const char*)ddict->dictContent + ZSTD_FRAMEIDSIZE);
2444
2445     /* load entropy tables */
2446     CHECK_E( ZSTD_loadEntropy(&ddict->entropy,
2447                               ddict->dictContent, ddict->dictSize),
2448              dictionary_corrupted );
2449     ddict->entropyPresent = 1;
2450     return 0;
2451 }
2452
2453
2454 static size_t ZSTD_initDDict_internal(ZSTD_DDict* ddict,
2455                                       const void* dict, size_t dictSize,
2456                                       ZSTD_dictLoadMethod_e dictLoadMethod,
2457                                       ZSTD_dictContentType_e dictContentType)
2458 {
2459     if ((dictLoadMethod == ZSTD_dlm_byRef) || (!dict) || (!dictSize)) {
2460         ddict->dictBuffer = NULL;
2461         ddict->dictContent = dict;
2462         if (!dict) dictSize = 0;
2463     } else {
2464         void* const internalBuffer = ZSTD_malloc(dictSize, ddict->cMem);
2465         ddict->dictBuffer = internalBuffer;
2466         ddict->dictContent = internalBuffer;
2467         if (!internalBuffer) return ERROR(memory_allocation);
2468         memcpy(internalBuffer, dict, dictSize);
2469     }
2470     ddict->dictSize = dictSize;
2471     ddict->entropy.hufTable[0] = (HUF_DTable)((HufLog)*0x1000001);  /* cover both little and big endian */
2472
2473     /* parse dictionary content */
2474     CHECK_F( ZSTD_loadEntropy_inDDict(ddict, dictContentType) );
2475
2476     return 0;
2477 }
2478
2479 ZSTD_DDict* ZSTD_createDDict_advanced(const void* dict, size_t dictSize,
2480                                       ZSTD_dictLoadMethod_e dictLoadMethod,
2481                                       ZSTD_dictContentType_e dictContentType,
2482                                       ZSTD_customMem customMem)
2483 {
2484     if (!customMem.customAlloc ^ !customMem.customFree) return NULL;
2485
2486     {   ZSTD_DDict* const ddict = (ZSTD_DDict*) ZSTD_malloc(sizeof(ZSTD_DDict), customMem);
2487         if (ddict == NULL) return NULL;
2488         ddict->cMem = customMem;
2489         {   size_t const initResult = ZSTD_initDDict_internal(ddict,
2490                                             dict, dictSize,
2491                                             dictLoadMethod, dictContentType);
2492             if (ZSTD_isError(initResult)) {
2493                 ZSTD_freeDDict(ddict);
2494                 return NULL;
2495         }   }
2496         return ddict;
2497     }
2498 }
2499
2500 /*! ZSTD_createDDict() :
2501 *   Create a digested dictionary, to start decompression without startup delay.
2502 *   `dict` content is copied inside DDict.
2503 *   Consequently, `dict` can be released after `ZSTD_DDict` creation */
2504 ZSTD_DDict* ZSTD_createDDict(const void* dict, size_t dictSize)
2505 {
2506     ZSTD_customMem const allocator = { NULL, NULL, NULL };
2507     return ZSTD_createDDict_advanced(dict, dictSize, ZSTD_dlm_byCopy, ZSTD_dct_auto, allocator);
2508 }
2509
2510 /*! ZSTD_createDDict_byReference() :
2511  *  Create a digested dictionary, to start decompression without startup delay.
2512  *  Dictionary content is simply referenced, it will be accessed during decompression.
2513  *  Warning : dictBuffer must outlive DDict (DDict must be freed before dictBuffer) */
2514 ZSTD_DDict* ZSTD_createDDict_byReference(const void* dictBuffer, size_t dictSize)
2515 {
2516     ZSTD_customMem const allocator = { NULL, NULL, NULL };
2517     return ZSTD_createDDict_advanced(dictBuffer, dictSize, ZSTD_dlm_byRef, ZSTD_dct_auto, allocator);
2518 }
2519
2520
2521 const ZSTD_DDict* ZSTD_initStaticDDict(
2522                                 void* sBuffer, size_t sBufferSize,
2523                                 const void* dict, size_t dictSize,
2524                                 ZSTD_dictLoadMethod_e dictLoadMethod,
2525                                 ZSTD_dictContentType_e dictContentType)
2526 {
2527     size_t const neededSpace = sizeof(ZSTD_DDict)
2528                              + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize);
2529     ZSTD_DDict* const ddict = (ZSTD_DDict*)sBuffer;
2530     assert(sBuffer != NULL);
2531     assert(dict != NULL);
2532     if ((size_t)sBuffer & 7) return NULL;   /* 8-aligned */
2533     if (sBufferSize < neededSpace) return NULL;
2534     if (dictLoadMethod == ZSTD_dlm_byCopy) {
2535         memcpy(ddict+1, dict, dictSize);  /* local copy */
2536         dict = ddict+1;
2537     }
2538     if (ZSTD_isError( ZSTD_initDDict_internal(ddict,
2539                                               dict, dictSize,
2540                                               ZSTD_dlm_byRef, dictContentType) ))
2541         return NULL;
2542     return ddict;
2543 }
2544
2545
2546 size_t ZSTD_freeDDict(ZSTD_DDict* ddict)
2547 {
2548     if (ddict==NULL) return 0;   /* support free on NULL */
2549     {   ZSTD_customMem const cMem = ddict->cMem;
2550         ZSTD_free(ddict->dictBuffer, cMem);
2551         ZSTD_free(ddict, cMem);
2552         return 0;
2553     }
2554 }
2555
2556 /*! ZSTD_estimateDDictSize() :
2557  *  Estimate amount of memory that will be needed to create a dictionary for decompression.
2558  *  Note : dictionary created by reference using ZSTD_dlm_byRef are smaller */
2559 size_t ZSTD_estimateDDictSize(size_t dictSize, ZSTD_dictLoadMethod_e dictLoadMethod)
2560 {
2561     return sizeof(ZSTD_DDict) + (dictLoadMethod == ZSTD_dlm_byRef ? 0 : dictSize);
2562 }
2563
2564 size_t ZSTD_sizeof_DDict(const ZSTD_DDict* ddict)
2565 {
2566     if (ddict==NULL) return 0;   /* support sizeof on NULL */
2567     return sizeof(*ddict) + (ddict->dictBuffer ? ddict->dictSize : 0) ;
2568 }
2569
2570 /*! ZSTD_getDictID_fromDict() :
2571  *  Provides the dictID stored within dictionary.
2572  *  if @return == 0, the dictionary is not conformant with Zstandard specification.
2573  *  It can still be loaded, but as a content-only dictionary. */
2574 unsigned ZSTD_getDictID_fromDict(const void* dict, size_t dictSize)
2575 {
2576     if (dictSize < 8) return 0;
2577     if (MEM_readLE32(dict) != ZSTD_MAGIC_DICTIONARY) return 0;
2578     return MEM_readLE32((const char*)dict + ZSTD_FRAMEIDSIZE);
2579 }
2580
2581 /*! ZSTD_getDictID_fromDDict() :
2582  *  Provides the dictID of the dictionary loaded into `ddict`.
2583  *  If @return == 0, the dictionary is not conformant to Zstandard specification, or empty.
2584  *  Non-conformant dictionaries can still be loaded, but as content-only dictionaries. */
2585 unsigned ZSTD_getDictID_fromDDict(const ZSTD_DDict* ddict)
2586 {
2587     if (ddict==NULL) return 0;
2588     return ZSTD_getDictID_fromDict(ddict->dictContent, ddict->dictSize);
2589 }
2590
2591 /*! ZSTD_getDictID_fromFrame() :
2592  *  Provides the dictID required to decompresse frame stored within `src`.
2593  *  If @return == 0, the dictID could not be decoded.
2594  *  This could for one of the following reasons :
2595  *  - The frame does not require a dictionary (most common case).
2596  *  - The frame was built with dictID intentionally removed.
2597  *    Needed dictionary is a hidden information.
2598  *    Note : this use case also happens when using a non-conformant dictionary.
2599  *  - `srcSize` is too small, and as a result, frame header could not be decoded.
2600  *    Note : possible if `srcSize < ZSTD_FRAMEHEADERSIZE_MAX`.
2601  *  - This is not a Zstandard frame.
2602  *  When identifying the exact failure cause, it's possible to use
2603  *  ZSTD_getFrameHeader(), which will provide a more precise error code. */
2604 unsigned ZSTD_getDictID_fromFrame(const void* src, size_t srcSize)
2605 {
2606     ZSTD_frameHeader zfp = { 0, 0, 0, ZSTD_frame, 0, 0, 0 };
2607     size_t const hError = ZSTD_getFrameHeader(&zfp, src, srcSize);
2608     if (ZSTD_isError(hError)) return 0;
2609     return zfp.dictID;
2610 }
2611
2612
2613 /*! ZSTD_decompress_usingDDict() :
2614 *   Decompression using a pre-digested Dictionary
2615 *   Use dictionary without significant overhead. */
2616 size_t ZSTD_decompress_usingDDict(ZSTD_DCtx* dctx,
2617                                   void* dst, size_t dstCapacity,
2618                             const void* src, size_t srcSize,
2619                             const ZSTD_DDict* ddict)
2620 {
2621     /* pass content and size in case legacy frames are encountered */
2622     return ZSTD_decompressMultiFrame(dctx, dst, dstCapacity, src, srcSize,
2623                                      NULL, 0,
2624                                      ddict);
2625 }
2626
2627
2628 /*=====================================
2629 *   Streaming decompression
2630 *====================================*/
2631
2632 ZSTD_DStream* ZSTD_createDStream(void)
2633 {
2634     DEBUGLOG(3, "ZSTD_createDStream");
2635     return ZSTD_createDStream_advanced(ZSTD_defaultCMem);
2636 }
2637
2638 ZSTD_DStream* ZSTD_initStaticDStream(void *workspace, size_t workspaceSize)
2639 {
2640     return ZSTD_initStaticDCtx(workspace, workspaceSize);
2641 }
2642
2643 ZSTD_DStream* ZSTD_createDStream_advanced(ZSTD_customMem customMem)
2644 {
2645     return ZSTD_createDCtx_advanced(customMem);
2646 }
2647
2648 size_t ZSTD_freeDStream(ZSTD_DStream* zds)
2649 {
2650     return ZSTD_freeDCtx(zds);
2651 }
2652
2653
2654 /* ***  Initialization  *** */
2655
2656 size_t ZSTD_DStreamInSize(void)  { return ZSTD_BLOCKSIZE_MAX + ZSTD_blockHeaderSize; }
2657 size_t ZSTD_DStreamOutSize(void) { return ZSTD_BLOCKSIZE_MAX; }
2658
2659 size_t ZSTD_DCtx_loadDictionary_advanced(ZSTD_DCtx* dctx,
2660                                    const void* dict, size_t dictSize,
2661                                          ZSTD_dictLoadMethod_e dictLoadMethod,
2662                                          ZSTD_dictContentType_e dictContentType)
2663 {
2664     if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2665     ZSTD_freeDDict(dctx->ddictLocal);
2666     if (dict && dictSize >= 8) {
2667         dctx->ddictLocal = ZSTD_createDDict_advanced(dict, dictSize, dictLoadMethod, dictContentType, dctx->customMem);
2668         if (dctx->ddictLocal == NULL) return ERROR(memory_allocation);
2669     } else {
2670         dctx->ddictLocal = NULL;
2671     }
2672     dctx->ddict = dctx->ddictLocal;
2673     return 0;
2674 }
2675
2676 size_t ZSTD_DCtx_loadDictionary_byReference(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2677 {
2678     return ZSTD_DCtx_loadDictionary_advanced(dctx, dict, dictSize, ZSTD_dlm_byRef, ZSTD_dct_auto);
2679 }
2680
2681 size_t ZSTD_DCtx_loadDictionary(ZSTD_DCtx* dctx, const void* dict, size_t dictSize)
2682 {
2683     return ZSTD_DCtx_loadDictionary_advanced(dctx, dict, dictSize, ZSTD_dlm_byCopy, ZSTD_dct_auto);
2684 }
2685
2686 size_t ZSTD_DCtx_refPrefix_advanced(ZSTD_DCtx* dctx, const void* prefix, size_t prefixSize, ZSTD_dictContentType_e dictContentType)
2687 {
2688     return ZSTD_DCtx_loadDictionary_advanced(dctx, prefix, prefixSize, ZSTD_dlm_byRef, dictContentType);
2689 }
2690
2691 size_t ZSTD_DCtx_refPrefix(ZSTD_DCtx* dctx, const void* prefix, size_t prefixSize)
2692 {
2693     return ZSTD_DCtx_refPrefix_advanced(dctx, prefix, prefixSize, ZSTD_dct_rawContent);
2694 }
2695
2696
2697 /* ZSTD_initDStream_usingDict() :
2698  * return : expected size, aka ZSTD_frameHeaderSize_prefix.
2699  * this function cannot fail */
2700 size_t ZSTD_initDStream_usingDict(ZSTD_DStream* zds, const void* dict, size_t dictSize)
2701 {
2702     DEBUGLOG(4, "ZSTD_initDStream_usingDict");
2703     zds->streamStage = zdss_init;
2704     zds->noForwardProgress = 0;
2705     CHECK_F( ZSTD_DCtx_loadDictionary(zds, dict, dictSize) );
2706     return ZSTD_frameHeaderSize_prefix;
2707 }
2708
2709 /* note : this variant can't fail */
2710 size_t ZSTD_initDStream(ZSTD_DStream* zds)
2711 {
2712     DEBUGLOG(4, "ZSTD_initDStream");
2713     return ZSTD_initDStream_usingDict(zds, NULL, 0);
2714 }
2715
2716 /* ZSTD_initDStream_usingDDict() :
2717  * ddict will just be referenced, and must outlive decompression session
2718  * this function cannot fail */
2719 size_t ZSTD_initDStream_usingDDict(ZSTD_DStream* dctx, const ZSTD_DDict* ddict)
2720 {
2721     size_t const initResult = ZSTD_initDStream(dctx);
2722     dctx->ddict = ddict;
2723     return initResult;
2724 }
2725
2726 /* ZSTD_resetDStream() :
2727  * return : expected size, aka ZSTD_frameHeaderSize_prefix.
2728  * this function cannot fail */
2729 size_t ZSTD_resetDStream(ZSTD_DStream* dctx)
2730 {
2731     DEBUGLOG(4, "ZSTD_resetDStream");
2732     dctx->streamStage = zdss_loadHeader;
2733     dctx->lhSize = dctx->inPos = dctx->outStart = dctx->outEnd = 0;
2734     dctx->legacyVersion = 0;
2735     dctx->hostageByte = 0;
2736     return ZSTD_frameHeaderSize_prefix;
2737 }
2738
2739 size_t ZSTD_setDStreamParameter(ZSTD_DStream* dctx,
2740                                 ZSTD_DStreamParameter_e paramType, unsigned paramValue)
2741 {
2742     if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2743     switch(paramType)
2744     {
2745         default : return ERROR(parameter_unsupported);
2746         case DStream_p_maxWindowSize :
2747             DEBUGLOG(4, "setting maxWindowSize = %u KB", paramValue >> 10);
2748             dctx->maxWindowSize = paramValue ? paramValue : (U32)(-1);
2749             break;
2750     }
2751     return 0;
2752 }
2753
2754 size_t ZSTD_DCtx_refDDict(ZSTD_DCtx* dctx, const ZSTD_DDict* ddict)
2755 {
2756     if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2757     dctx->ddict = ddict;
2758     return 0;
2759 }
2760
2761 size_t ZSTD_DCtx_setMaxWindowSize(ZSTD_DCtx* dctx, size_t maxWindowSize)
2762 {
2763     if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2764     dctx->maxWindowSize = maxWindowSize;
2765     return 0;
2766 }
2767
2768 size_t ZSTD_DCtx_setFormat(ZSTD_DCtx* dctx, ZSTD_format_e format)
2769 {
2770     DEBUGLOG(4, "ZSTD_DCtx_setFormat : %u", (unsigned)format);
2771     if (dctx->streamStage != zdss_init) return ERROR(stage_wrong);
2772     dctx->format = format;
2773     return 0;
2774 }
2775
2776
2777 size_t ZSTD_sizeof_DStream(const ZSTD_DStream* dctx)
2778 {
2779     return ZSTD_sizeof_DCtx(dctx);
2780 }
2781
2782 size_t ZSTD_decodingBufferSize_min(unsigned long long windowSize, unsigned long long frameContentSize)
2783 {
2784     size_t const blockSize = (size_t) MIN(windowSize, ZSTD_BLOCKSIZE_MAX);
2785     unsigned long long const neededRBSize = windowSize + blockSize + (WILDCOPY_OVERLENGTH * 2);
2786     unsigned long long const neededSize = MIN(frameContentSize, neededRBSize);
2787     size_t const minRBSize = (size_t) neededSize;
2788     if ((unsigned long long)minRBSize != neededSize) return ERROR(frameParameter_windowTooLarge);
2789     return minRBSize;
2790 }
2791
2792 size_t ZSTD_estimateDStreamSize(size_t windowSize)
2793 {
2794     size_t const blockSize = MIN(windowSize, ZSTD_BLOCKSIZE_MAX);
2795     size_t const inBuffSize = blockSize;  /* no block can be larger */
2796     size_t const outBuffSize = ZSTD_decodingBufferSize_min(windowSize, ZSTD_CONTENTSIZE_UNKNOWN);
2797     return ZSTD_estimateDCtxSize() + inBuffSize + outBuffSize;
2798 }
2799
2800 size_t ZSTD_estimateDStreamSize_fromFrame(const void* src, size_t srcSize)
2801 {
2802     U32 const windowSizeMax = 1U << ZSTD_WINDOWLOG_MAX;   /* note : should be user-selectable */
2803     ZSTD_frameHeader zfh;
2804     size_t const err = ZSTD_getFrameHeader(&zfh, src, srcSize);
2805     if (ZSTD_isError(err)) return err;
2806     if (err>0) return ERROR(srcSize_wrong);
2807     if (zfh.windowSize > windowSizeMax)
2808         return ERROR(frameParameter_windowTooLarge);
2809     return ZSTD_estimateDStreamSize((size_t)zfh.windowSize);
2810 }
2811
2812
2813 /* *****   Decompression   ***** */
2814
2815 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
2816 {
2817     size_t const length = MIN(dstCapacity, srcSize);
2818     memcpy(dst, src, length);
2819     return length;
2820 }
2821
2822
2823 size_t ZSTD_decompressStream(ZSTD_DStream* zds, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
2824 {
2825     const char* const istart = (const char*)(input->src) + input->pos;
2826     const char* const iend = (const char*)(input->src) + input->size;
2827     const char* ip = istart;
2828     char* const ostart = (char*)(output->dst) + output->pos;
2829     char* const oend = (char*)(output->dst) + output->size;
2830     char* op = ostart;
2831     U32 someMoreWork = 1;
2832
2833     DEBUGLOG(5, "ZSTD_decompressStream");
2834     if (input->pos > input->size) {  /* forbidden */
2835         DEBUGLOG(5, "in: pos: %u   vs size: %u",
2836                     (U32)input->pos, (U32)input->size);
2837         return ERROR(srcSize_wrong);
2838     }
2839     if (output->pos > output->size) {  /* forbidden */
2840         DEBUGLOG(5, "out: pos: %u   vs size: %u",
2841                     (U32)output->pos, (U32)output->size);
2842         return ERROR(dstSize_tooSmall);
2843     }
2844     DEBUGLOG(5, "input size : %u", (U32)(input->size - input->pos));
2845
2846     while (someMoreWork) {
2847         switch(zds->streamStage)
2848         {
2849         case zdss_init :
2850             DEBUGLOG(5, "stage zdss_init => transparent reset ");
2851             ZSTD_resetDStream(zds);   /* transparent reset on starting decoding a new frame */
2852             /* fall-through */
2853
2854         case zdss_loadHeader :
2855             DEBUGLOG(5, "stage zdss_loadHeader (srcSize : %u)", (U32)(iend - ip));
2856 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
2857             if (zds->legacyVersion) {
2858                 /* legacy support is incompatible with static dctx */
2859                 if (zds->staticSize) return ERROR(memory_allocation);
2860                 {   size_t const hint = ZSTD_decompressLegacyStream(zds->legacyContext, zds->legacyVersion, output, input);
2861                     if (hint==0) zds->streamStage = zdss_init;
2862                     return hint;
2863             }   }
2864 #endif
2865             {   size_t const hSize = ZSTD_getFrameHeader_advanced(&zds->fParams, zds->headerBuffer, zds->lhSize, zds->format);
2866                 DEBUGLOG(5, "header size : %u", (U32)hSize);
2867                 if (ZSTD_isError(hSize)) {
2868 #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
2869                     U32 const legacyVersion = ZSTD_isLegacy(istart, iend-istart);
2870                     if (legacyVersion) {
2871                         const void* const dict = zds->ddict ? zds->ddict->dictContent : NULL;
2872                         size_t const dictSize = zds->ddict ? zds->ddict->dictSize : 0;
2873                         DEBUGLOG(5, "ZSTD_decompressStream: detected legacy version v0.%u", legacyVersion);
2874                         /* legacy support is incompatible with static dctx */
2875                         if (zds->staticSize) return ERROR(memory_allocation);
2876                         CHECK_F(ZSTD_initLegacyStream(&zds->legacyContext,
2877                                     zds->previousLegacyVersion, legacyVersion,
2878                                     dict, dictSize));
2879                         zds->legacyVersion = zds->previousLegacyVersion = legacyVersion;
2880                         {   size_t const hint = ZSTD_decompressLegacyStream(zds->legacyContext, legacyVersion, output, input);
2881                             if (hint==0) zds->streamStage = zdss_init;   /* or stay in stage zdss_loadHeader */
2882                             return hint;
2883                     }   }
2884 #endif
2885                     return hSize;   /* error */
2886                 }
2887                 if (hSize != 0) {   /* need more input */
2888                     size_t const toLoad = hSize - zds->lhSize;   /* if hSize!=0, hSize > zds->lhSize */
2889                     size_t const remainingInput = (size_t)(iend-ip);
2890                     assert(iend >= ip);
2891                     if (toLoad > remainingInput) {   /* not enough input to load full header */
2892                         if (remainingInput > 0) {
2893                             memcpy(zds->headerBuffer + zds->lhSize, ip, remainingInput);
2894                             zds->lhSize += remainingInput;
2895                         }
2896                         input->pos = input->size;
2897                         return (MAX(ZSTD_frameHeaderSize_min, hSize) - zds->lhSize) + ZSTD_blockHeaderSize;   /* remaining header bytes + next block header */
2898                     }
2899                     assert(ip != NULL);
2900                     memcpy(zds->headerBuffer + zds->lhSize, ip, toLoad); zds->lhSize = hSize; ip += toLoad;
2901                     break;
2902             }   }
2903
2904             /* check for single-pass mode opportunity */
2905             if (zds->fParams.frameContentSize && zds->fParams.windowSize /* skippable frame if == 0 */
2906                 && (U64)(size_t)(oend-op) >= zds->fParams.frameContentSize) {
2907                 size_t const cSize = ZSTD_findFrameCompressedSize(istart, iend-istart);
2908                 if (cSize <= (size_t)(iend-istart)) {
2909                     /* shortcut : using single-pass mode */
2910                     size_t const decompressedSize = ZSTD_decompress_usingDDict(zds, op, oend-op, istart, cSize, zds->ddict);
2911                     if (ZSTD_isError(decompressedSize)) return decompressedSize;
2912                     DEBUGLOG(4, "shortcut to single-pass ZSTD_decompress_usingDDict()")
2913                     ip = istart + cSize;
2914                     op += decompressedSize;
2915                     zds->expected = 0;
2916                     zds->streamStage = zdss_init;
2917                     someMoreWork = 0;
2918                     break;
2919             }   }
2920
2921             /* Consume header (see ZSTDds_decodeFrameHeader) */
2922             DEBUGLOG(4, "Consume header");
2923             CHECK_F(ZSTD_decompressBegin_usingDDict(zds, zds->ddict));
2924
2925             if ((MEM_readLE32(zds->headerBuffer) & 0xFFFFFFF0U) == ZSTD_MAGIC_SKIPPABLE_START) {  /* skippable frame */
2926                 zds->expected = MEM_readLE32(zds->headerBuffer + ZSTD_FRAMEIDSIZE);
2927                 zds->stage = ZSTDds_skipFrame;
2928             } else {
2929                 CHECK_F(ZSTD_decodeFrameHeader(zds, zds->headerBuffer, zds->lhSize));
2930                 zds->expected = ZSTD_blockHeaderSize;
2931                 zds->stage = ZSTDds_decodeBlockHeader;
2932             }
2933
2934             /* control buffer memory usage */
2935             DEBUGLOG(4, "Control max memory usage (%u KB <= max %u KB)",
2936                         (U32)(zds->fParams.windowSize >>10),
2937                         (U32)(zds->maxWindowSize >> 10) );
2938             zds->fParams.windowSize = MAX(zds->fParams.windowSize, 1U << ZSTD_WINDOWLOG_ABSOLUTEMIN);
2939             if (zds->fParams.windowSize > zds->maxWindowSize) return ERROR(frameParameter_windowTooLarge);
2940
2941             /* Adapt buffer sizes to frame header instructions */
2942             {   size_t const neededInBuffSize = MAX(zds->fParams.blockSizeMax, 4 /* frame checksum */);
2943                 size_t const neededOutBuffSize = ZSTD_decodingBufferSize_min(zds->fParams.windowSize, zds->fParams.frameContentSize);
2944                 if ((zds->inBuffSize < neededInBuffSize) || (zds->outBuffSize < neededOutBuffSize)) {
2945                     size_t const bufferSize = neededInBuffSize + neededOutBuffSize;
2946                     DEBUGLOG(4, "inBuff  : from %u to %u",
2947                                 (U32)zds->inBuffSize, (U32)neededInBuffSize);
2948                     DEBUGLOG(4, "outBuff : from %u to %u",
2949                                 (U32)zds->outBuffSize, (U32)neededOutBuffSize);
2950                     if (zds->staticSize) {  /* static DCtx */
2951                         DEBUGLOG(4, "staticSize : %u", (U32)zds->staticSize);
2952                         assert(zds->staticSize >= sizeof(ZSTD_DCtx));  /* controlled at init */
2953                         if (bufferSize > zds->staticSize - sizeof(ZSTD_DCtx))
2954                             return ERROR(memory_allocation);
2955                     } else {
2956                         ZSTD_free(zds->inBuff, zds->customMem);
2957                         zds->inBuffSize = 0;
2958                         zds->outBuffSize = 0;
2959                         zds->inBuff = (char*)ZSTD_malloc(bufferSize, zds->customMem);
2960                         if (zds->inBuff == NULL) return ERROR(memory_allocation);
2961                     }
2962                     zds->inBuffSize = neededInBuffSize;
2963                     zds->outBuff = zds->inBuff + zds->inBuffSize;
2964                     zds->outBuffSize = neededOutBuffSize;
2965             }   }
2966             zds->streamStage = zdss_read;
2967             /* fall-through */
2968
2969         case zdss_read:
2970             DEBUGLOG(5, "stage zdss_read");
2971             {   size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds);
2972                 DEBUGLOG(5, "neededInSize = %u", (U32)neededInSize);
2973                 if (neededInSize==0) {  /* end of frame */
2974                     zds->streamStage = zdss_init;
2975                     someMoreWork = 0;
2976                     break;
2977                 }
2978                 if ((size_t)(iend-ip) >= neededInSize) {  /* decode directly from src */
2979                     int const isSkipFrame = ZSTD_isSkipFrame(zds);
2980                     size_t const decodedSize = ZSTD_decompressContinue(zds,
2981                         zds->outBuff + zds->outStart, (isSkipFrame ? 0 : zds->outBuffSize - zds->outStart),
2982                         ip, neededInSize);
2983                     if (ZSTD_isError(decodedSize)) return decodedSize;
2984                     ip += neededInSize;
2985                     if (!decodedSize && !isSkipFrame) break;   /* this was just a header */
2986                     zds->outEnd = zds->outStart + decodedSize;
2987                     zds->streamStage = zdss_flush;
2988                     break;
2989             }   }
2990             if (ip==iend) { someMoreWork = 0; break; }   /* no more input */
2991             zds->streamStage = zdss_load;
2992             /* fall-through */
2993
2994         case zdss_load:
2995             {   size_t const neededInSize = ZSTD_nextSrcSizeToDecompress(zds);
2996                 size_t const toLoad = neededInSize - zds->inPos;
2997                 int const isSkipFrame = ZSTD_isSkipFrame(zds);
2998                 size_t loadedSize;
2999                 if (isSkipFrame) {
3000                     loadedSize = MIN(toLoad, (size_t)(iend-ip));
3001                 } else {
3002                     if (toLoad > zds->inBuffSize - zds->inPos) return ERROR(corruption_detected);   /* should never happen */
3003                     loadedSize = ZSTD_limitCopy(zds->inBuff + zds->inPos, toLoad, ip, iend-ip);
3004                 }
3005                 ip += loadedSize;
3006                 zds->inPos += loadedSize;
3007                 if (loadedSize < toLoad) { someMoreWork = 0; break; }   /* not enough input, wait for more */
3008
3009                 /* decode loaded input */
3010                 {   size_t const decodedSize = ZSTD_decompressContinue(zds,
3011                         zds->outBuff + zds->outStart, zds->outBuffSize - zds->outStart,
3012                         zds->inBuff, neededInSize);
3013                     if (ZSTD_isError(decodedSize)) return decodedSize;
3014                     zds->inPos = 0;   /* input is consumed */
3015                     if (!decodedSize && !isSkipFrame) { zds->streamStage = zdss_read; break; }   /* this was just a header */
3016                     zds->outEnd = zds->outStart +  decodedSize;
3017             }   }
3018             zds->streamStage = zdss_flush;
3019             /* fall-through */
3020
3021         case zdss_flush:
3022             {   size_t const toFlushSize = zds->outEnd - zds->outStart;
3023                 size_t const flushedSize = ZSTD_limitCopy(op, oend-op, zds->outBuff + zds->outStart, toFlushSize);
3024                 op += flushedSize;
3025                 zds->outStart += flushedSize;
3026                 if (flushedSize == toFlushSize) {  /* flush completed */
3027                     zds->streamStage = zdss_read;
3028                     if ( (zds->outBuffSize < zds->fParams.frameContentSize)
3029                       && (zds->outStart + zds->fParams.blockSizeMax > zds->outBuffSize) ) {
3030                         DEBUGLOG(5, "restart filling outBuff from beginning (left:%i, needed:%u)",
3031                                 (int)(zds->outBuffSize - zds->outStart),
3032                                 (U32)zds->fParams.blockSizeMax);
3033                         zds->outStart = zds->outEnd = 0;
3034                     }
3035                     break;
3036             }   }
3037             /* cannot complete flush */
3038             someMoreWork = 0;
3039             break;
3040
3041         default: return ERROR(GENERIC);   /* impossible */
3042     }   }
3043
3044     /* result */
3045     input->pos = (size_t)(ip - (const char*)(input->src));
3046     output->pos = (size_t)(op - (char*)(output->dst));
3047     if ((ip==istart) && (op==ostart)) {  /* no forward progress */
3048         zds->noForwardProgress ++;
3049         if (zds->noForwardProgress >= ZSTD_NO_FORWARD_PROGRESS_MAX) {
3050             if (op==oend) return ERROR(dstSize_tooSmall);
3051             if (ip==iend) return ERROR(srcSize_wrong);
3052             assert(0);
3053         }
3054     } else {
3055         zds->noForwardProgress = 0;
3056     }
3057     {   size_t nextSrcSizeHint = ZSTD_nextSrcSizeToDecompress(zds);
3058         if (!nextSrcSizeHint) {   /* frame fully decoded */
3059             if (zds->outEnd == zds->outStart) {  /* output fully flushed */
3060                 if (zds->hostageByte) {
3061                     if (input->pos >= input->size) {
3062                         /* can't release hostage (not present) */
3063                         zds->streamStage = zdss_read;
3064                         return 1;
3065                     }
3066                     input->pos++;  /* release hostage */
3067                 }   /* zds->hostageByte */
3068                 return 0;
3069             }  /* zds->outEnd == zds->outStart */
3070             if (!zds->hostageByte) { /* output not fully flushed; keep last byte as hostage; will be released when all output is flushed */
3071                 input->pos--;   /* note : pos > 0, otherwise, impossible to finish reading last block */
3072                 zds->hostageByte=1;
3073             }
3074             return 1;
3075         }  /* nextSrcSizeHint==0 */
3076         nextSrcSizeHint += ZSTD_blockHeaderSize * (ZSTD_nextInputType(zds) == ZSTDnit_block);   /* preload header of next block */
3077         assert(zds->inPos <= nextSrcSizeHint);
3078         nextSrcSizeHint -= zds->inPos;   /* part already loaded*/
3079         return nextSrcSizeHint;
3080     }
3081 }
3082
3083
3084 size_t ZSTD_decompress_generic(ZSTD_DCtx* dctx, ZSTD_outBuffer* output, ZSTD_inBuffer* input)
3085 {
3086     return ZSTD_decompressStream(dctx, output, input);
3087 }
3088
3089 size_t ZSTD_decompress_generic_simpleArgs (
3090                             ZSTD_DCtx* dctx,
3091                             void* dst, size_t dstCapacity, size_t* dstPos,
3092                       const void* src, size_t srcSize, size_t* srcPos)
3093 {
3094     ZSTD_outBuffer output = { dst, dstCapacity, *dstPos };
3095     ZSTD_inBuffer  input  = { src, srcSize, *srcPos };
3096     /* ZSTD_compress_generic() will check validity of dstPos and srcPos */
3097     size_t const cErr = ZSTD_decompress_generic(dctx, &output, &input);
3098     *dstPos = output.pos;
3099     *srcPos = input.pos;
3100     return cErr;
3101 }
3102
3103 void ZSTD_DCtx_reset(ZSTD_DCtx* dctx)
3104 {
3105     (void)ZSTD_initDStream(dctx);
3106     dctx->format = ZSTD_f_zstd1;
3107     dctx->maxWindowSize = ZSTD_MAXWINDOWSIZE_DEFAULT;
3108 }