lib/zstd/decompress.c

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