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