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