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 /* zstd_decompress_block : 12 * this module takes care of decompressing _compressed_ block */ 13 14 /*-******************************************************* 15 * Dependencies 16 *********************************************************/ 17 #include <string.h> /* memcpy, memmove, memset */ 18 #include "compiler.h" /* prefetch */ 19 #include "cpu.h" /* bmi2 */ 20 #include "mem.h" /* low level memory routines */ 21 #define FSE_STATIC_LINKING_ONLY 22 #include "fse.h" 23 #define HUF_STATIC_LINKING_ONLY 24 #include "huf.h" 25 #include "zstd_internal.h" 26 #include "zstd_decompress_internal.h" /* ZSTD_DCtx */ 27 #include "zstd_ddict.h" /* ZSTD_DDictDictContent */ 28 #include "zstd_decompress_block.h" 29 30 /*_******************************************************* 31 * Macros 32 **********************************************************/ 33 34 /* These two optional macros force the use one way or another of the two 35 * ZSTD_decompressSequences implementations. You can't force in both directions 36 * at the same time. 37 */ 38 #if defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 39 defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 40 #error "Cannot force the use of the short and the long ZSTD_decompressSequences variants!" 41 #endif 42 43 44 /*_******************************************************* 45 * Memory operations 46 **********************************************************/ 47 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); } 48 49 50 /*-************************************************************* 51 * Block decoding 52 ***************************************************************/ 53 54 /*! ZSTD_getcBlockSize() : 55 * Provides the size of compressed block from block header `src` */ 56 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, 57 blockProperties_t* bpPtr) 58 { 59 RETURN_ERROR_IF(srcSize < ZSTD_blockHeaderSize, srcSize_wrong); 60 61 { U32 const cBlockHeader = MEM_readLE24(src); 62 U32 const cSize = cBlockHeader >> 3; 63 bpPtr->lastBlock = cBlockHeader & 1; 64 bpPtr->blockType = (blockType_e)((cBlockHeader >> 1) & 3); 65 bpPtr->origSize = cSize; /* only useful for RLE */ 66 if (bpPtr->blockType == bt_rle) return 1; 67 RETURN_ERROR_IF(bpPtr->blockType == bt_reserved, corruption_detected); 68 return cSize; 69 } 70 } 71 72 73 /* Hidden declaration for fullbench */ 74 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, 75 const void* src, size_t srcSize); 76 /*! ZSTD_decodeLiteralsBlock() : 77 * @return : nb of bytes read from src (< srcSize ) 78 * note : symbol not declared but exposed for fullbench */ 79 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, 80 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */ 81 { 82 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock"); 83 RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected); 84 85 { const BYTE* const istart = (const BYTE*) src; 86 symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3); 87 88 switch(litEncType) 89 { 90 case set_repeat: 91 DEBUGLOG(5, "set_repeat flag : re-using stats from previous compressed literals block"); 92 RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted); 93 /* fall-through */ 94 95 case set_compressed: 96 RETURN_ERROR_IF(srcSize < 5, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3"); 97 { size_t lhSize, litSize, litCSize; 98 U32 singleStream=0; 99 U32 const lhlCode = (istart[0] >> 2) & 3; 100 U32 const lhc = MEM_readLE32(istart); 101 size_t hufSuccess; 102 switch(lhlCode) 103 { 104 case 0: case 1: default: /* note : default is impossible, since lhlCode into [0..3] */ 105 /* 2 - 2 - 10 - 10 */ 106 singleStream = !lhlCode; 107 lhSize = 3; 108 litSize = (lhc >> 4) & 0x3FF; 109 litCSize = (lhc >> 14) & 0x3FF; 110 break; 111 case 2: 112 /* 2 - 2 - 14 - 14 */ 113 lhSize = 4; 114 litSize = (lhc >> 4) & 0x3FFF; 115 litCSize = lhc >> 18; 116 break; 117 case 3: 118 /* 2 - 2 - 18 - 18 */ 119 lhSize = 5; 120 litSize = (lhc >> 4) & 0x3FFFF; 121 litCSize = (lhc >> 22) + ((size_t)istart[4] << 10); 122 break; 123 } 124 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected); 125 RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected); 126 127 /* prefetch huffman table if cold */ 128 if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) { 129 PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable)); 130 } 131 132 if (litEncType==set_repeat) { 133 if (singleStream) { 134 hufSuccess = HUF_decompress1X_usingDTable_bmi2( 135 dctx->litBuffer, litSize, istart+lhSize, litCSize, 136 dctx->HUFptr, dctx->bmi2); 137 } else { 138 hufSuccess = HUF_decompress4X_usingDTable_bmi2( 139 dctx->litBuffer, litSize, istart+lhSize, litCSize, 140 dctx->HUFptr, dctx->bmi2); 141 } 142 } else { 143 if (singleStream) { 144 #if defined(HUF_FORCE_DECOMPRESS_X2) 145 hufSuccess = HUF_decompress1X_DCtx_wksp( 146 dctx->entropy.hufTable, dctx->litBuffer, litSize, 147 istart+lhSize, litCSize, dctx->workspace, 148 sizeof(dctx->workspace)); 149 #else 150 hufSuccess = HUF_decompress1X1_DCtx_wksp_bmi2( 151 dctx->entropy.hufTable, dctx->litBuffer, litSize, 152 istart+lhSize, litCSize, dctx->workspace, 153 sizeof(dctx->workspace), dctx->bmi2); 154 #endif 155 } else { 156 hufSuccess = HUF_decompress4X_hufOnly_wksp_bmi2( 157 dctx->entropy.hufTable, dctx->litBuffer, litSize, 158 istart+lhSize, litCSize, dctx->workspace, 159 sizeof(dctx->workspace), dctx->bmi2); 160 } 161 } 162 163 RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected); 164 165 dctx->litPtr = dctx->litBuffer; 166 dctx->litSize = litSize; 167 dctx->litEntropy = 1; 168 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable; 169 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 170 return litCSize + lhSize; 171 } 172 173 case set_basic: 174 { size_t litSize, lhSize; 175 U32 const lhlCode = ((istart[0]) >> 2) & 3; 176 switch(lhlCode) 177 { 178 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */ 179 lhSize = 1; 180 litSize = istart[0] >> 3; 181 break; 182 case 1: 183 lhSize = 2; 184 litSize = MEM_readLE16(istart) >> 4; 185 break; 186 case 3: 187 lhSize = 3; 188 litSize = MEM_readLE24(istart) >> 4; 189 break; 190 } 191 192 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */ 193 RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected); 194 memcpy(dctx->litBuffer, istart+lhSize, litSize); 195 dctx->litPtr = dctx->litBuffer; 196 dctx->litSize = litSize; 197 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH); 198 return lhSize+litSize; 199 } 200 /* direct reference into compressed stream */ 201 dctx->litPtr = istart+lhSize; 202 dctx->litSize = litSize; 203 return lhSize+litSize; 204 } 205 206 case set_rle: 207 { U32 const lhlCode = ((istart[0]) >> 2) & 3; 208 size_t litSize, lhSize; 209 switch(lhlCode) 210 { 211 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */ 212 lhSize = 1; 213 litSize = istart[0] >> 3; 214 break; 215 case 1: 216 lhSize = 2; 217 litSize = MEM_readLE16(istart) >> 4; 218 break; 219 case 3: 220 lhSize = 3; 221 litSize = MEM_readLE24(istart) >> 4; 222 RETURN_ERROR_IF(srcSize<4, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4"); 223 break; 224 } 225 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected); 226 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH); 227 dctx->litPtr = dctx->litBuffer; 228 dctx->litSize = litSize; 229 return lhSize+1; 230 } 231 default: 232 RETURN_ERROR(corruption_detected, "impossible"); 233 } 234 } 235 } 236 237 /* Default FSE distribution tables. 238 * These are pre-calculated FSE decoding tables using default distributions as defined in specification : 239 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions 240 * They were generated programmatically with following method : 241 * - start from default distributions, present in /lib/common/zstd_internal.h 242 * - generate tables normally, using ZSTD_buildFSETable() 243 * - printout the content of tables 244 * - pretify output, report below, test with fuzzer to ensure it's correct */ 245 246 /* Default FSE distribution table for Literal Lengths */ 247 static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = { 248 { 1, 1, 1, LL_DEFAULTNORMLOG}, /* header : fastMode, tableLog */ 249 /* nextState, nbAddBits, nbBits, baseVal */ 250 { 0, 0, 4, 0}, { 16, 0, 4, 0}, 251 { 32, 0, 5, 1}, { 0, 0, 5, 3}, 252 { 0, 0, 5, 4}, { 0, 0, 5, 6}, 253 { 0, 0, 5, 7}, { 0, 0, 5, 9}, 254 { 0, 0, 5, 10}, { 0, 0, 5, 12}, 255 { 0, 0, 6, 14}, { 0, 1, 5, 16}, 256 { 0, 1, 5, 20}, { 0, 1, 5, 22}, 257 { 0, 2, 5, 28}, { 0, 3, 5, 32}, 258 { 0, 4, 5, 48}, { 32, 6, 5, 64}, 259 { 0, 7, 5, 128}, { 0, 8, 6, 256}, 260 { 0, 10, 6, 1024}, { 0, 12, 6, 4096}, 261 { 32, 0, 4, 0}, { 0, 0, 4, 1}, 262 { 0, 0, 5, 2}, { 32, 0, 5, 4}, 263 { 0, 0, 5, 5}, { 32, 0, 5, 7}, 264 { 0, 0, 5, 8}, { 32, 0, 5, 10}, 265 { 0, 0, 5, 11}, { 0, 0, 6, 13}, 266 { 32, 1, 5, 16}, { 0, 1, 5, 18}, 267 { 32, 1, 5, 22}, { 0, 2, 5, 24}, 268 { 32, 3, 5, 32}, { 0, 3, 5, 40}, 269 { 0, 6, 4, 64}, { 16, 6, 4, 64}, 270 { 32, 7, 5, 128}, { 0, 9, 6, 512}, 271 { 0, 11, 6, 2048}, { 48, 0, 4, 0}, 272 { 16, 0, 4, 1}, { 32, 0, 5, 2}, 273 { 32, 0, 5, 3}, { 32, 0, 5, 5}, 274 { 32, 0, 5, 6}, { 32, 0, 5, 8}, 275 { 32, 0, 5, 9}, { 32, 0, 5, 11}, 276 { 32, 0, 5, 12}, { 0, 0, 6, 15}, 277 { 32, 1, 5, 18}, { 32, 1, 5, 20}, 278 { 32, 2, 5, 24}, { 32, 2, 5, 28}, 279 { 32, 3, 5, 40}, { 32, 4, 5, 48}, 280 { 0, 16, 6,65536}, { 0, 15, 6,32768}, 281 { 0, 14, 6,16384}, { 0, 13, 6, 8192}, 282 }; /* LL_defaultDTable */ 283 284 /* Default FSE distribution table for Offset Codes */ 285 static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = { 286 { 1, 1, 1, OF_DEFAULTNORMLOG}, /* header : fastMode, tableLog */ 287 /* nextState, nbAddBits, nbBits, baseVal */ 288 { 0, 0, 5, 0}, { 0, 6, 4, 61}, 289 { 0, 9, 5, 509}, { 0, 15, 5,32765}, 290 { 0, 21, 5,2097149}, { 0, 3, 5, 5}, 291 { 0, 7, 4, 125}, { 0, 12, 5, 4093}, 292 { 0, 18, 5,262141}, { 0, 23, 5,8388605}, 293 { 0, 5, 5, 29}, { 0, 8, 4, 253}, 294 { 0, 14, 5,16381}, { 0, 20, 5,1048573}, 295 { 0, 2, 5, 1}, { 16, 7, 4, 125}, 296 { 0, 11, 5, 2045}, { 0, 17, 5,131069}, 297 { 0, 22, 5,4194301}, { 0, 4, 5, 13}, 298 { 16, 8, 4, 253}, { 0, 13, 5, 8189}, 299 { 0, 19, 5,524285}, { 0, 1, 5, 1}, 300 { 16, 6, 4, 61}, { 0, 10, 5, 1021}, 301 { 0, 16, 5,65533}, { 0, 28, 5,268435453}, 302 { 0, 27, 5,134217725}, { 0, 26, 5,67108861}, 303 { 0, 25, 5,33554429}, { 0, 24, 5,16777213}, 304 }; /* OF_defaultDTable */ 305 306 307 /* Default FSE distribution table for Match Lengths */ 308 static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = { 309 { 1, 1, 1, ML_DEFAULTNORMLOG}, /* header : fastMode, tableLog */ 310 /* nextState, nbAddBits, nbBits, baseVal */ 311 { 0, 0, 6, 3}, { 0, 0, 4, 4}, 312 { 32, 0, 5, 5}, { 0, 0, 5, 6}, 313 { 0, 0, 5, 8}, { 0, 0, 5, 9}, 314 { 0, 0, 5, 11}, { 0, 0, 6, 13}, 315 { 0, 0, 6, 16}, { 0, 0, 6, 19}, 316 { 0, 0, 6, 22}, { 0, 0, 6, 25}, 317 { 0, 0, 6, 28}, { 0, 0, 6, 31}, 318 { 0, 0, 6, 34}, { 0, 1, 6, 37}, 319 { 0, 1, 6, 41}, { 0, 2, 6, 47}, 320 { 0, 3, 6, 59}, { 0, 4, 6, 83}, 321 { 0, 7, 6, 131}, { 0, 9, 6, 515}, 322 { 16, 0, 4, 4}, { 0, 0, 4, 5}, 323 { 32, 0, 5, 6}, { 0, 0, 5, 7}, 324 { 32, 0, 5, 9}, { 0, 0, 5, 10}, 325 { 0, 0, 6, 12}, { 0, 0, 6, 15}, 326 { 0, 0, 6, 18}, { 0, 0, 6, 21}, 327 { 0, 0, 6, 24}, { 0, 0, 6, 27}, 328 { 0, 0, 6, 30}, { 0, 0, 6, 33}, 329 { 0, 1, 6, 35}, { 0, 1, 6, 39}, 330 { 0, 2, 6, 43}, { 0, 3, 6, 51}, 331 { 0, 4, 6, 67}, { 0, 5, 6, 99}, 332 { 0, 8, 6, 259}, { 32, 0, 4, 4}, 333 { 48, 0, 4, 4}, { 16, 0, 4, 5}, 334 { 32, 0, 5, 7}, { 32, 0, 5, 8}, 335 { 32, 0, 5, 10}, { 32, 0, 5, 11}, 336 { 0, 0, 6, 14}, { 0, 0, 6, 17}, 337 { 0, 0, 6, 20}, { 0, 0, 6, 23}, 338 { 0, 0, 6, 26}, { 0, 0, 6, 29}, 339 { 0, 0, 6, 32}, { 0, 16, 6,65539}, 340 { 0, 15, 6,32771}, { 0, 14, 6,16387}, 341 { 0, 13, 6, 8195}, { 0, 12, 6, 4099}, 342 { 0, 11, 6, 2051}, { 0, 10, 6, 1027}, 343 }; /* ML_defaultDTable */ 344 345 346 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits) 347 { 348 void* ptr = dt; 349 ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr; 350 ZSTD_seqSymbol* const cell = dt + 1; 351 352 DTableH->tableLog = 0; 353 DTableH->fastMode = 0; 354 355 cell->nbBits = 0; 356 cell->nextState = 0; 357 assert(nbAddBits < 255); 358 cell->nbAdditionalBits = (BYTE)nbAddBits; 359 cell->baseValue = baseValue; 360 } 361 362 363 /* ZSTD_buildFSETable() : 364 * generate FSE decoding table for one symbol (ll, ml or off) 365 * cannot fail if input is valid => 366 * all inputs are presumed validated at this stage */ 367 void 368 ZSTD_buildFSETable(ZSTD_seqSymbol* dt, 369 const short* normalizedCounter, unsigned maxSymbolValue, 370 const U32* baseValue, const U32* nbAdditionalBits, 371 unsigned tableLog) 372 { 373 ZSTD_seqSymbol* const tableDecode = dt+1; 374 U16 symbolNext[MaxSeq+1]; 375 376 U32 const maxSV1 = maxSymbolValue + 1; 377 U32 const tableSize = 1 << tableLog; 378 U32 highThreshold = tableSize-1; 379 380 /* Sanity Checks */ 381 assert(maxSymbolValue <= MaxSeq); 382 assert(tableLog <= MaxFSELog); 383 384 /* Init, lay down lowprob symbols */ 385 { ZSTD_seqSymbol_header DTableH; 386 DTableH.tableLog = tableLog; 387 DTableH.fastMode = 1; 388 { S16 const largeLimit= (S16)(1 << (tableLog-1)); 389 U32 s; 390 for (s=0; s<maxSV1; s++) { 391 if (normalizedCounter[s]==-1) { 392 tableDecode[highThreshold--].baseValue = s; 393 symbolNext[s] = 1; 394 } else { 395 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; 396 assert(normalizedCounter[s]>=0); 397 symbolNext[s] = (U16)normalizedCounter[s]; 398 } } } 399 memcpy(dt, &DTableH, sizeof(DTableH)); 400 } 401 402 /* Spread symbols */ 403 { U32 const tableMask = tableSize-1; 404 U32 const step = FSE_TABLESTEP(tableSize); 405 U32 s, position = 0; 406 for (s=0; s<maxSV1; s++) { 407 int i; 408 for (i=0; i<normalizedCounter[s]; i++) { 409 tableDecode[position].baseValue = s; 410 position = (position + step) & tableMask; 411 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 412 } } 413 assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 414 } 415 416 /* Build Decoding table */ 417 { U32 u; 418 for (u=0; u<tableSize; u++) { 419 U32 const symbol = tableDecode[u].baseValue; 420 U32 const nextState = symbolNext[symbol]++; 421 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) ); 422 tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize); 423 assert(nbAdditionalBits[symbol] < 255); 424 tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol]; 425 tableDecode[u].baseValue = baseValue[symbol]; 426 } } 427 } 428 429 430 /*! ZSTD_buildSeqTable() : 431 * @return : nb bytes read from src, 432 * or an error code if it fails */ 433 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr, 434 symbolEncodingType_e type, unsigned max, U32 maxLog, 435 const void* src, size_t srcSize, 436 const U32* baseValue, const U32* nbAdditionalBits, 437 const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable, 438 int ddictIsCold, int nbSeq) 439 { 440 switch(type) 441 { 442 case set_rle : 443 RETURN_ERROR_IF(!srcSize, srcSize_wrong); 444 RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected); 445 { U32 const symbol = *(const BYTE*)src; 446 U32 const baseline = baseValue[symbol]; 447 U32 const nbBits = nbAdditionalBits[symbol]; 448 ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits); 449 } 450 *DTablePtr = DTableSpace; 451 return 1; 452 case set_basic : 453 *DTablePtr = defaultTable; 454 return 0; 455 case set_repeat: 456 RETURN_ERROR_IF(!flagRepeatTable, corruption_detected); 457 /* prefetch FSE table if used */ 458 if (ddictIsCold && (nbSeq > 24 /* heuristic */)) { 459 const void* const pStart = *DTablePtr; 460 size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog)); 461 PREFETCH_AREA(pStart, pSize); 462 } 463 return 0; 464 case set_compressed : 465 { unsigned tableLog; 466 S16 norm[MaxSeq+1]; 467 size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize); 468 RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected); 469 RETURN_ERROR_IF(tableLog > maxLog, corruption_detected); 470 ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog); 471 *DTablePtr = DTableSpace; 472 return headerSize; 473 } 474 default : 475 assert(0); 476 RETURN_ERROR(GENERIC, "impossible"); 477 } 478 } 479 480 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr, 481 const void* src, size_t srcSize) 482 { 483 const BYTE* const istart = (const BYTE* const)src; 484 const BYTE* const iend = istart + srcSize; 485 const BYTE* ip = istart; 486 int nbSeq; 487 DEBUGLOG(5, "ZSTD_decodeSeqHeaders"); 488 489 /* check */ 490 RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong); 491 492 /* SeqHead */ 493 nbSeq = *ip++; 494 if (!nbSeq) { 495 *nbSeqPtr=0; 496 RETURN_ERROR_IF(srcSize != 1, srcSize_wrong); 497 return 1; 498 } 499 if (nbSeq > 0x7F) { 500 if (nbSeq == 0xFF) { 501 RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong); 502 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2; 503 } else { 504 RETURN_ERROR_IF(ip >= iend, srcSize_wrong); 505 nbSeq = ((nbSeq-0x80)<<8) + *ip++; 506 } 507 } 508 *nbSeqPtr = nbSeq; 509 510 /* FSE table descriptors */ 511 RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong); /* minimum possible size: 1 byte for symbol encoding types */ 512 { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6); 513 symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3); 514 symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3); 515 ip++; 516 517 /* Build DTables */ 518 { size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr, 519 LLtype, MaxLL, LLFSELog, 520 ip, iend-ip, 521 LL_base, LL_bits, 522 LL_defaultDTable, dctx->fseEntropy, 523 dctx->ddictIsCold, nbSeq); 524 RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected); 525 ip += llhSize; 526 } 527 528 { size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr, 529 OFtype, MaxOff, OffFSELog, 530 ip, iend-ip, 531 OF_base, OF_bits, 532 OF_defaultDTable, dctx->fseEntropy, 533 dctx->ddictIsCold, nbSeq); 534 RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected); 535 ip += ofhSize; 536 } 537 538 { size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr, 539 MLtype, MaxML, MLFSELog, 540 ip, iend-ip, 541 ML_base, ML_bits, 542 ML_defaultDTable, dctx->fseEntropy, 543 dctx->ddictIsCold, nbSeq); 544 RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected); 545 ip += mlhSize; 546 } 547 } 548 549 return ip-istart; 550 } 551 552 553 typedef struct { 554 size_t litLength; 555 size_t matchLength; 556 size_t offset; 557 const BYTE* match; 558 } seq_t; 559 560 typedef struct { 561 size_t state; 562 const ZSTD_seqSymbol* table; 563 } ZSTD_fseState; 564 565 typedef struct { 566 BIT_DStream_t DStream; 567 ZSTD_fseState stateLL; 568 ZSTD_fseState stateOffb; 569 ZSTD_fseState stateML; 570 size_t prevOffset[ZSTD_REP_NUM]; 571 const BYTE* prefixStart; 572 const BYTE* dictEnd; 573 size_t pos; 574 } seqState_t; 575 576 /*! ZSTD_overlapCopy8() : 577 * Copies 8 bytes from ip to op and updates op and ip where ip <= op. 578 * If the offset is < 8 then the offset is spread to at least 8 bytes. 579 * 580 * Precondition: *ip <= *op 581 * Postcondition: *op - *op >= 8 582 */ 583 static void ZSTD_overlapCopy8(BYTE** op, BYTE const** ip, size_t offset) { 584 assert(*ip <= *op); 585 if (offset < 8) { 586 /* close range match, overlap */ 587 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 588 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */ 589 int const sub2 = dec64table[offset]; 590 (*op)[0] = (*ip)[0]; 591 (*op)[1] = (*ip)[1]; 592 (*op)[2] = (*ip)[2]; 593 (*op)[3] = (*ip)[3]; 594 *ip += dec32table[offset]; 595 ZSTD_copy4(*op+4, *ip); 596 *ip -= sub2; 597 } else { 598 ZSTD_copy8(*op, *ip); 599 } 600 *ip += 8; 601 *op += 8; 602 assert(*op - *ip >= 8); 603 } 604 605 /*! ZSTD_safecopy() : 606 * Specialized version of memcpy() that is allowed to READ up to WILDCOPY_OVERLENGTH past the input buffer 607 * and write up to 16 bytes past oend_w (op >= oend_w is allowed). 608 * This function is only called in the uncommon case where the sequence is near the end of the block. It 609 * should be fast for a single long sequence, but can be slow for several short sequences. 610 * 611 * @param ovtype controls the overlap detection 612 * - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart. 613 * - ZSTD_overlap_src_before_dst: The src and dst may overlap and may be any distance apart. 614 * The src buffer must be before the dst buffer. 615 */ 616 static void ZSTD_safecopy(BYTE* op, BYTE* const oend_w, BYTE const* ip, ptrdiff_t length, ZSTD_overlap_e ovtype) { 617 ptrdiff_t const diff = op - ip; 618 BYTE* const oend = op + length; 619 620 assert((ovtype == ZSTD_no_overlap && (diff <= -8 || diff >= 8 || op >= oend_w)) || 621 (ovtype == ZSTD_overlap_src_before_dst && diff >= 0)); 622 623 if (length < 8) { 624 /* Handle short lengths. */ 625 while (op < oend) *op++ = *ip++; 626 return; 627 } 628 if (ovtype == ZSTD_overlap_src_before_dst) { 629 /* Copy 8 bytes and ensure the offset >= 8 when there can be overlap. */ 630 assert(length >= 8); 631 ZSTD_overlapCopy8(&op, &ip, diff); 632 assert(op - ip >= 8); 633 assert(op <= oend); 634 } 635 636 if (oend <= oend_w) { 637 /* No risk of overwrite. */ 638 ZSTD_wildcopy(op, ip, length, ovtype); 639 return; 640 } 641 if (op <= oend_w) { 642 /* Wildcopy until we get close to the end. */ 643 assert(oend > oend_w); 644 ZSTD_wildcopy(op, ip, oend_w - op, ovtype); 645 ip += oend_w - op; 646 op = oend_w; 647 } 648 /* Handle the leftovers. */ 649 while (op < oend) *op++ = *ip++; 650 } 651 652 /* ZSTD_execSequenceEnd(): 653 * This version handles cases that are near the end of the output buffer. It requires 654 * more careful checks to make sure there is no overflow. By separating out these hard 655 * and unlikely cases, we can speed up the common cases. 656 * 657 * NOTE: This function needs to be fast for a single long sequence, but doesn't need 658 * to be optimized for many small sequences, since those fall into ZSTD_execSequence(). 659 */ 660 FORCE_NOINLINE 661 size_t ZSTD_execSequenceEnd(BYTE* op, 662 BYTE* const oend, seq_t sequence, 663 const BYTE** litPtr, const BYTE* const litLimit, 664 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd) 665 { 666 BYTE* const oLitEnd = op + sequence.litLength; 667 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 668 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 669 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 670 const BYTE* match = oLitEnd - sequence.offset; 671 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH; 672 673 /* bounds checks */ 674 assert(oLitEnd < oMatchEnd); 675 RETURN_ERROR_IF(oMatchEnd > oend, dstSize_tooSmall, "last match must fit within dstBuffer"); 676 RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "try to read beyond literal buffer"); 677 678 /* copy literals */ 679 ZSTD_safecopy(op, oend_w, *litPtr, sequence.litLength, ZSTD_no_overlap); 680 op = oLitEnd; 681 *litPtr = iLitEnd; 682 683 /* copy Match */ 684 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) { 685 /* offset beyond prefix */ 686 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected); 687 match = dictEnd - (prefixStart-match); 688 if (match + sequence.matchLength <= dictEnd) { 689 memmove(oLitEnd, match, sequence.matchLength); 690 return sequenceLength; 691 } 692 /* span extDict & currentPrefixSegment */ 693 { size_t const length1 = dictEnd - match; 694 memmove(oLitEnd, match, length1); 695 op = oLitEnd + length1; 696 sequence.matchLength -= length1; 697 match = prefixStart; 698 } } 699 ZSTD_safecopy(op, oend_w, match, sequence.matchLength, ZSTD_overlap_src_before_dst); 700 return sequenceLength; 701 } 702 703 HINT_INLINE 704 size_t ZSTD_execSequence(BYTE* op, 705 BYTE* const oend, seq_t sequence, 706 const BYTE** litPtr, const BYTE* const litLimit, 707 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd) 708 { 709 BYTE* const oLitEnd = op + sequence.litLength; 710 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 711 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 712 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH; 713 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 714 const BYTE* match = oLitEnd - sequence.offset; 715 716 /* Errors and uncommon cases handled here. */ 717 assert(oLitEnd < oMatchEnd); 718 if (iLitEnd > litLimit || oMatchEnd > oend_w) 719 return ZSTD_execSequenceEnd(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd); 720 721 /* Assumptions (everything else goes into ZSTD_execSequenceEnd()) */ 722 assert(iLitEnd <= litLimit /* Literal length is in bounds */); 723 assert(oLitEnd <= oend_w /* Can wildcopy literals */); 724 assert(oMatchEnd <= oend_w /* Can wildcopy matches */); 725 726 /* Copy Literals: 727 * Split out litLength <= 16 since it is nearly always true. +1.6% on gcc-9. 728 * We likely don't need the full 32-byte wildcopy. 729 */ 730 assert(WILDCOPY_OVERLENGTH >= 16); 731 ZSTD_copy16(op, (*litPtr)); 732 if (sequence.litLength > 16) { 733 ZSTD_wildcopy(op+16, (*litPtr)+16, sequence.litLength-16, ZSTD_no_overlap); 734 } 735 op = oLitEnd; 736 *litPtr = iLitEnd; /* update for next sequence */ 737 738 /* Copy Match */ 739 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) { 740 /* offset beyond prefix -> go into extDict */ 741 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected); 742 match = dictEnd + (match - prefixStart); 743 if (match + sequence.matchLength <= dictEnd) { 744 memmove(oLitEnd, match, sequence.matchLength); 745 return sequenceLength; 746 } 747 /* span extDict & currentPrefixSegment */ 748 { size_t const length1 = dictEnd - match; 749 memmove(oLitEnd, match, length1); 750 op = oLitEnd + length1; 751 sequence.matchLength -= length1; 752 match = prefixStart; 753 } } 754 /* Match within prefix of 1 or more bytes */ 755 assert(op <= oMatchEnd); 756 assert(oMatchEnd <= oend_w); 757 assert(match >= prefixStart); 758 assert(sequence.matchLength >= 1); 759 760 /* Nearly all offsets are >= WILDCOPY_VECLEN bytes, which means we can use wildcopy 761 * without overlap checking. 762 */ 763 if (sequence.offset >= WILDCOPY_VECLEN) { 764 /* We bet on a full wildcopy for matches, since we expect matches to be 765 * longer than literals (in general). In silesia, ~10% of matches are longer 766 * than 16 bytes. 767 */ 768 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength, ZSTD_no_overlap); 769 return sequenceLength; 770 } 771 assert(sequence.offset < WILDCOPY_VECLEN); 772 773 /* Copy 8 bytes and spread the offset to be >= 8. */ 774 ZSTD_overlapCopy8(&op, &match, sequence.offset); 775 776 /* If the match length is > 8 bytes, then continue with the wildcopy. */ 777 if (sequence.matchLength > 8) { 778 assert(op < oMatchEnd); 779 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst); 780 } 781 return sequenceLength; 782 } 783 784 static void 785 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt) 786 { 787 const void* ptr = dt; 788 const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr; 789 DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog); 790 DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits", 791 (U32)DStatePtr->state, DTableH->tableLog); 792 BIT_reloadDStream(bitD); 793 DStatePtr->table = dt + 1; 794 } 795 796 FORCE_INLINE_TEMPLATE void 797 ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD) 798 { 799 ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state]; 800 U32 const nbBits = DInfo.nbBits; 801 size_t const lowBits = BIT_readBits(bitD, nbBits); 802 DStatePtr->state = DInfo.nextState + lowBits; 803 } 804 805 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum 806 * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1) 807 * bits before reloading. This value is the maximum number of bytes we read 808 * after reloading when we are decoding long offsets. 809 */ 810 #define LONG_OFFSETS_MAX_EXTRA_BITS_32 \ 811 (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32 \ 812 ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32 \ 813 : 0) 814 815 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e; 816 817 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 818 FORCE_INLINE_TEMPLATE seq_t 819 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets) 820 { 821 seq_t seq; 822 U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits; 823 U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits; 824 U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits; 825 U32 const totalBits = llBits+mlBits+ofBits; 826 U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue; 827 U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue; 828 U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue; 829 830 /* sequence */ 831 { size_t offset; 832 if (!ofBits) 833 offset = 0; 834 else { 835 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1); 836 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5); 837 assert(ofBits <= MaxOff); 838 if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) { 839 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed); 840 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits); 841 BIT_reloadDStream(&seqState->DStream); 842 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits); 843 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32); /* to avoid another reload */ 844 } else { 845 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */ 846 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); 847 } 848 } 849 850 if (ofBits <= 1) { 851 offset += (llBase==0); 852 if (offset) { 853 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset]; 854 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */ 855 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1]; 856 seqState->prevOffset[1] = seqState->prevOffset[0]; 857 seqState->prevOffset[0] = offset = temp; 858 } else { /* offset == 0 */ 859 offset = seqState->prevOffset[0]; 860 } 861 } else { 862 seqState->prevOffset[2] = seqState->prevOffset[1]; 863 seqState->prevOffset[1] = seqState->prevOffset[0]; 864 seqState->prevOffset[0] = offset; 865 } 866 seq.offset = offset; 867 } 868 869 seq.matchLength = mlBase 870 + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/) : 0); /* <= 16 bits */ 871 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32)) 872 BIT_reloadDStream(&seqState->DStream); 873 if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog))) 874 BIT_reloadDStream(&seqState->DStream); 875 /* Ensure there are enough bits to read the rest of data in 64-bit mode. */ 876 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64); 877 878 seq.litLength = llBase 879 + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits/*>0*/) : 0); /* <= 16 bits */ 880 if (MEM_32bits()) 881 BIT_reloadDStream(&seqState->DStream); 882 883 DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u", 884 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset); 885 886 /* ANS state update */ 887 ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */ 888 ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */ 889 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */ 890 ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */ 891 892 return seq; 893 } 894 895 FORCE_INLINE_TEMPLATE size_t 896 DONT_VECTORIZE 897 ZSTD_decompressSequences_body( ZSTD_DCtx* dctx, 898 void* dst, size_t maxDstSize, 899 const void* seqStart, size_t seqSize, int nbSeq, 900 const ZSTD_longOffset_e isLongOffset) 901 { 902 const BYTE* ip = (const BYTE*)seqStart; 903 const BYTE* const iend = ip + seqSize; 904 BYTE* const ostart = (BYTE* const)dst; 905 BYTE* const oend = ostart + maxDstSize; 906 BYTE* op = ostart; 907 const BYTE* litPtr = dctx->litPtr; 908 const BYTE* const litEnd = litPtr + dctx->litSize; 909 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart); 910 const BYTE* const vBase = (const BYTE*) (dctx->virtualStart); 911 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 912 DEBUGLOG(5, "ZSTD_decompressSequences_body"); 913 914 /* Regen sequences */ 915 if (nbSeq) { 916 seqState_t seqState; 917 dctx->fseEntropy = 1; 918 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; } 919 RETURN_ERROR_IF( 920 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)), 921 corruption_detected); 922 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr); 923 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr); 924 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr); 925 926 ZSTD_STATIC_ASSERT( 927 BIT_DStream_unfinished < BIT_DStream_completed && 928 BIT_DStream_endOfBuffer < BIT_DStream_completed && 929 BIT_DStream_completed < BIT_DStream_overflow); 930 931 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) { 932 nbSeq--; 933 { seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset); 934 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd); 935 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize); 936 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 937 op += oneSeqSize; 938 } } 939 940 /* check if reached exact end */ 941 DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq); 942 RETURN_ERROR_IF(nbSeq, corruption_detected); 943 RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected); 944 /* save reps for next block */ 945 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); } 946 } 947 948 /* last literal segment */ 949 { size_t const lastLLSize = litEnd - litPtr; 950 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall); 951 memcpy(op, litPtr, lastLLSize); 952 op += lastLLSize; 953 } 954 955 return op-ostart; 956 } 957 958 static size_t 959 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx, 960 void* dst, size_t maxDstSize, 961 const void* seqStart, size_t seqSize, int nbSeq, 962 const ZSTD_longOffset_e isLongOffset) 963 { 964 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 965 } 966 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */ 967 968 969 970 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 971 FORCE_INLINE_TEMPLATE seq_t 972 ZSTD_decodeSequenceLong(seqState_t* seqState, ZSTD_longOffset_e const longOffsets) 973 { 974 seq_t seq; 975 U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits; 976 U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits; 977 U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits; 978 U32 const totalBits = llBits+mlBits+ofBits; 979 U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue; 980 U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue; 981 U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue; 982 983 /* sequence */ 984 { size_t offset; 985 if (!ofBits) 986 offset = 0; 987 else { 988 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1); 989 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5); 990 assert(ofBits <= MaxOff); 991 if (MEM_32bits() && longOffsets) { 992 U32 const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN_32-1); 993 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits); 994 if (MEM_32bits() || extraBits) BIT_reloadDStream(&seqState->DStream); 995 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits); 996 } else { 997 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */ 998 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); 999 } 1000 } 1001 1002 if (ofBits <= 1) { 1003 offset += (llBase==0); 1004 if (offset) { 1005 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset]; 1006 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */ 1007 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1]; 1008 seqState->prevOffset[1] = seqState->prevOffset[0]; 1009 seqState->prevOffset[0] = offset = temp; 1010 } else { 1011 offset = seqState->prevOffset[0]; 1012 } 1013 } else { 1014 seqState->prevOffset[2] = seqState->prevOffset[1]; 1015 seqState->prevOffset[1] = seqState->prevOffset[0]; 1016 seqState->prevOffset[0] = offset; 1017 } 1018 seq.offset = offset; 1019 } 1020 1021 seq.matchLength = mlBase + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */ 1022 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32)) 1023 BIT_reloadDStream(&seqState->DStream); 1024 if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog))) 1025 BIT_reloadDStream(&seqState->DStream); 1026 /* Verify that there is enough bits to read the rest of the data in 64-bit mode. */ 1027 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64); 1028 1029 seq.litLength = llBase + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */ 1030 if (MEM_32bits()) 1031 BIT_reloadDStream(&seqState->DStream); 1032 1033 { size_t const pos = seqState->pos + seq.litLength; 1034 const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart; 1035 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. 1036 * No consequence though : no memory access will occur, overly large offset will be detected in ZSTD_execSequenceLong() */ 1037 seqState->pos = pos + seq.matchLength; 1038 } 1039 1040 /* ANS state update */ 1041 ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */ 1042 ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */ 1043 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */ 1044 ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */ 1045 1046 return seq; 1047 } 1048 1049 FORCE_INLINE_TEMPLATE size_t 1050 ZSTD_decompressSequencesLong_body( 1051 ZSTD_DCtx* dctx, 1052 void* dst, size_t maxDstSize, 1053 const void* seqStart, size_t seqSize, int nbSeq, 1054 const ZSTD_longOffset_e isLongOffset) 1055 { 1056 const BYTE* ip = (const BYTE*)seqStart; 1057 const BYTE* const iend = ip + seqSize; 1058 BYTE* const ostart = (BYTE* const)dst; 1059 BYTE* const oend = ostart + maxDstSize; 1060 BYTE* op = ostart; 1061 const BYTE* litPtr = dctx->litPtr; 1062 const BYTE* const litEnd = litPtr + dctx->litSize; 1063 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart); 1064 const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart); 1065 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 1066 1067 /* Regen sequences */ 1068 if (nbSeq) { 1069 #define STORED_SEQS 4 1070 #define STORED_SEQS_MASK (STORED_SEQS-1) 1071 #define ADVANCED_SEQS 4 1072 seq_t sequences[STORED_SEQS]; 1073 int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS); 1074 seqState_t seqState; 1075 int seqNb; 1076 dctx->fseEntropy = 1; 1077 { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; } 1078 seqState.prefixStart = prefixStart; 1079 seqState.pos = (size_t)(op-prefixStart); 1080 seqState.dictEnd = dictEnd; 1081 assert(iend >= ip); 1082 RETURN_ERROR_IF( 1083 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)), 1084 corruption_detected); 1085 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr); 1086 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr); 1087 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr); 1088 1089 /* prepare in advance */ 1090 for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) { 1091 sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, isLongOffset); 1092 PREFETCH_L1(sequences[seqNb].match); PREFETCH_L1(sequences[seqNb].match + sequences[seqNb].matchLength - 1); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */ 1093 } 1094 RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected); 1095 1096 /* decode and decompress */ 1097 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) { 1098 seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, isLongOffset); 1099 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd); 1100 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 1101 PREFETCH_L1(sequence.match); PREFETCH_L1(sequence.match + sequence.matchLength - 1); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */ 1102 sequences[seqNb & STORED_SEQS_MASK] = sequence; 1103 op += oneSeqSize; 1104 } 1105 RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected); 1106 1107 /* finish queue */ 1108 seqNb -= seqAdvance; 1109 for ( ; seqNb<nbSeq ; seqNb++) { 1110 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[seqNb&STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd); 1111 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 1112 op += oneSeqSize; 1113 } 1114 1115 /* save reps for next block */ 1116 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); } 1117 } 1118 1119 /* last literal segment */ 1120 { size_t const lastLLSize = litEnd - litPtr; 1121 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall); 1122 memcpy(op, litPtr, lastLLSize); 1123 op += lastLLSize; 1124 } 1125 1126 return op-ostart; 1127 } 1128 1129 static size_t 1130 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx, 1131 void* dst, size_t maxDstSize, 1132 const void* seqStart, size_t seqSize, int nbSeq, 1133 const ZSTD_longOffset_e isLongOffset) 1134 { 1135 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 1136 } 1137 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */ 1138 1139 1140 1141 #if DYNAMIC_BMI2 1142 1143 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 1144 static TARGET_ATTRIBUTE("bmi2") size_t 1145 DONT_VECTORIZE 1146 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx, 1147 void* dst, size_t maxDstSize, 1148 const void* seqStart, size_t seqSize, int nbSeq, 1149 const ZSTD_longOffset_e isLongOffset) 1150 { 1151 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 1152 } 1153 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */ 1154 1155 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 1156 static TARGET_ATTRIBUTE("bmi2") size_t 1157 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx, 1158 void* dst, size_t maxDstSize, 1159 const void* seqStart, size_t seqSize, int nbSeq, 1160 const ZSTD_longOffset_e isLongOffset) 1161 { 1162 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 1163 } 1164 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */ 1165 1166 #endif /* DYNAMIC_BMI2 */ 1167 1168 typedef size_t (*ZSTD_decompressSequences_t)( 1169 ZSTD_DCtx* dctx, 1170 void* dst, size_t maxDstSize, 1171 const void* seqStart, size_t seqSize, int nbSeq, 1172 const ZSTD_longOffset_e isLongOffset); 1173 1174 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 1175 static size_t 1176 ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, 1177 const void* seqStart, size_t seqSize, int nbSeq, 1178 const ZSTD_longOffset_e isLongOffset) 1179 { 1180 DEBUGLOG(5, "ZSTD_decompressSequences"); 1181 #if DYNAMIC_BMI2 1182 if (dctx->bmi2) { 1183 return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 1184 } 1185 #endif 1186 return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 1187 } 1188 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */ 1189 1190 1191 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 1192 /* ZSTD_decompressSequencesLong() : 1193 * decompression function triggered when a minimum share of offsets is considered "long", 1194 * aka out of cache. 1195 * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance". 1196 * This function will try to mitigate main memory latency through the use of prefetching */ 1197 static size_t 1198 ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx, 1199 void* dst, size_t maxDstSize, 1200 const void* seqStart, size_t seqSize, int nbSeq, 1201 const ZSTD_longOffset_e isLongOffset) 1202 { 1203 DEBUGLOG(5, "ZSTD_decompressSequencesLong"); 1204 #if DYNAMIC_BMI2 1205 if (dctx->bmi2) { 1206 return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 1207 } 1208 #endif 1209 return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset); 1210 } 1211 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */ 1212 1213 1214 1215 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 1216 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 1217 /* ZSTD_getLongOffsetsShare() : 1218 * condition : offTable must be valid 1219 * @return : "share" of long offsets (arbitrarily defined as > (1<<23)) 1220 * compared to maximum possible of (1<<OffFSELog) */ 1221 static unsigned 1222 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable) 1223 { 1224 const void* ptr = offTable; 1225 U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog; 1226 const ZSTD_seqSymbol* table = offTable + 1; 1227 U32 const max = 1 << tableLog; 1228 U32 u, total = 0; 1229 DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog); 1230 1231 assert(max <= (1 << OffFSELog)); /* max not too large */ 1232 for (u=0; u<max; u++) { 1233 if (table[u].nbAdditionalBits > 22) total += 1; 1234 } 1235 1236 assert(tableLog <= OffFSELog); 1237 total <<= (OffFSELog - tableLog); /* scale to OffFSELog */ 1238 1239 return total; 1240 } 1241 #endif 1242 1243 1244 size_t 1245 ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx, 1246 void* dst, size_t dstCapacity, 1247 const void* src, size_t srcSize, const int frame) 1248 { /* blockType == blockCompressed */ 1249 const BYTE* ip = (const BYTE*)src; 1250 /* isLongOffset must be true if there are long offsets. 1251 * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN. 1252 * We don't expect that to be the case in 64-bit mode. 1253 * In block mode, window size is not known, so we have to be conservative. 1254 * (note: but it could be evaluated from current-lowLimit) 1255 */ 1256 ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN)))); 1257 DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize); 1258 1259 RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong); 1260 1261 /* Decode literals section */ 1262 { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize); 1263 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize); 1264 if (ZSTD_isError(litCSize)) return litCSize; 1265 ip += litCSize; 1266 srcSize -= litCSize; 1267 } 1268 1269 /* Build Decoding Tables */ 1270 { 1271 /* These macros control at build-time which decompressor implementation 1272 * we use. If neither is defined, we do some inspection and dispatch at 1273 * runtime. 1274 */ 1275 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 1276 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 1277 int usePrefetchDecoder = dctx->ddictIsCold; 1278 #endif 1279 int nbSeq; 1280 size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize); 1281 if (ZSTD_isError(seqHSize)) return seqHSize; 1282 ip += seqHSize; 1283 srcSize -= seqHSize; 1284 1285 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 1286 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 1287 if ( !usePrefetchDecoder 1288 && (!frame || (dctx->fParams.windowSize > (1<<24))) 1289 && (nbSeq>ADVANCED_SEQS) ) { /* could probably use a larger nbSeq limit */ 1290 U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr); 1291 U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */ 1292 usePrefetchDecoder = (shareLongOffsets >= minShare); 1293 } 1294 #endif 1295 1296 dctx->ddictIsCold = 0; 1297 1298 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 1299 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 1300 if (usePrefetchDecoder) 1301 #endif 1302 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 1303 return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset); 1304 #endif 1305 1306 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 1307 /* else */ 1308 return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset); 1309 #endif 1310 } 1311 } 1312 1313 1314 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx, 1315 void* dst, size_t dstCapacity, 1316 const void* src, size_t srcSize) 1317 { 1318 size_t dSize; 1319 ZSTD_checkContinuity(dctx, dst); 1320 dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0); 1321 dctx->previousDstEnd = (char*)dst + dSize; 1322 return dSize; 1323 } 1324