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