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