1 /* 2 * Copyright (c) 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 "../common/zstd_deps.h" /* ZSTD_memcpy, ZSTD_memmove, ZSTD_memset */ 18 #include "../common/compiler.h" /* prefetch */ 19 #include "../common/cpu.h" /* bmi2 */ 20 #include "../common/mem.h" /* low level memory routines */ 21 #define FSE_STATIC_LINKING_ONLY 22 #include "../common/fse.h" 23 #define HUF_STATIC_LINKING_ONLY 24 #include "../common/huf.h" 25 #include "../common/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 **********************************************************/ ZSTD_copy4(void * dst,const void * src)47 static void ZSTD_copy4(void* dst, const void* src) { ZSTD_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` */ ZSTD_getcBlockSize(const void * src,size_t srcSize,blockProperties_t * bpPtr)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 /* Allocate buffer for literals, either overlapping current dst, or split between dst and litExtraBuffer, or stored entirely within litExtraBuffer */ ZSTD_allocateLiteralsBuffer(ZSTD_DCtx * dctx,void * const dst,const size_t dstCapacity,const size_t litSize,const streaming_operation streaming,const size_t expectedWriteSize,const unsigned splitImmediately)73 static void ZSTD_allocateLiteralsBuffer(ZSTD_DCtx* dctx, void* const dst, const size_t dstCapacity, const size_t litSize, 74 const streaming_operation streaming, const size_t expectedWriteSize, const unsigned splitImmediately) 75 { 76 if (streaming == not_streaming && dstCapacity > ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH + litSize + WILDCOPY_OVERLENGTH) 77 { 78 /* room for litbuffer to fit without read faulting */ 79 dctx->litBuffer = (BYTE*)dst + ZSTD_BLOCKSIZE_MAX + WILDCOPY_OVERLENGTH; 80 dctx->litBufferEnd = dctx->litBuffer + litSize; 81 dctx->litBufferLocation = ZSTD_in_dst; 82 } 83 else if (litSize > ZSTD_LITBUFFEREXTRASIZE) 84 { 85 /* won't fit in litExtraBuffer, so it will be split between end of dst and extra buffer */ 86 if (splitImmediately) { 87 /* won't fit in litExtraBuffer, so it will be split between end of dst and extra buffer */ 88 dctx->litBuffer = (BYTE*)dst + expectedWriteSize - litSize + ZSTD_LITBUFFEREXTRASIZE - WILDCOPY_OVERLENGTH; 89 dctx->litBufferEnd = dctx->litBuffer + litSize - ZSTD_LITBUFFEREXTRASIZE; 90 } 91 else { 92 /* initially this will be stored entirely in dst during huffman decoding, it will partially shifted to litExtraBuffer after */ 93 dctx->litBuffer = (BYTE*)dst + expectedWriteSize - litSize; 94 dctx->litBufferEnd = (BYTE*)dst + expectedWriteSize; 95 } 96 dctx->litBufferLocation = ZSTD_split; 97 } 98 else 99 { 100 /* fits entirely within litExtraBuffer, so no split is necessary */ 101 dctx->litBuffer = dctx->litExtraBuffer; 102 dctx->litBufferEnd = dctx->litBuffer + litSize; 103 dctx->litBufferLocation = ZSTD_not_in_dst; 104 } 105 } 106 107 /* Hidden declaration for fullbench */ 108 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, 109 const void* src, size_t srcSize, 110 void* dst, size_t dstCapacity, const streaming_operation streaming); 111 /*! ZSTD_decodeLiteralsBlock() : 112 * Where it is possible to do so without being stomped by the output during decompression, the literals block will be stored 113 * in the dstBuffer. If there is room to do so, it will be stored in full in the excess dst space after where the current 114 * block will be output. Otherwise it will be stored at the end of the current dst blockspace, with a small portion being 115 * stored in dctx->litExtraBuffer to help keep it "ahead" of the current output write. 116 * 117 * @return : nb of bytes read from src (< srcSize ) 118 * note : symbol not declared but exposed for fullbench */ ZSTD_decodeLiteralsBlock(ZSTD_DCtx * dctx,const void * src,size_t srcSize,void * dst,size_t dstCapacity,const streaming_operation streaming)119 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx, 120 const void* src, size_t srcSize, /* note : srcSize < BLOCKSIZE */ 121 void* dst, size_t dstCapacity, const streaming_operation streaming) 122 { 123 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock"); 124 RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected, ""); 125 126 { const BYTE* const istart = (const BYTE*) src; 127 symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3); 128 129 switch(litEncType) 130 { 131 case set_repeat: 132 DEBUGLOG(5, "set_repeat flag : re-using stats from previous compressed literals block"); 133 RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted, ""); 134 ZSTD_FALLTHROUGH; 135 136 case set_compressed: 137 RETURN_ERROR_IF(srcSize < 5, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need up to 5 for case 3"); 138 { size_t lhSize, litSize, litCSize; 139 U32 singleStream=0; 140 U32 const lhlCode = (istart[0] >> 2) & 3; 141 U32 const lhc = MEM_readLE32(istart); 142 size_t hufSuccess; 143 size_t expectedWriteSize = MIN(ZSTD_BLOCKSIZE_MAX, dstCapacity); 144 switch(lhlCode) 145 { 146 case 0: case 1: default: /* note : default is impossible, since lhlCode into [0..3] */ 147 /* 2 - 2 - 10 - 10 */ 148 singleStream = !lhlCode; 149 lhSize = 3; 150 litSize = (lhc >> 4) & 0x3FF; 151 litCSize = (lhc >> 14) & 0x3FF; 152 break; 153 case 2: 154 /* 2 - 2 - 14 - 14 */ 155 lhSize = 4; 156 litSize = (lhc >> 4) & 0x3FFF; 157 litCSize = lhc >> 18; 158 break; 159 case 3: 160 /* 2 - 2 - 18 - 18 */ 161 lhSize = 5; 162 litSize = (lhc >> 4) & 0x3FFFF; 163 litCSize = (lhc >> 22) + ((size_t)istart[4] << 10); 164 break; 165 } 166 RETURN_ERROR_IF(litSize > 0 && dst == NULL, dstSize_tooSmall, "NULL not handled"); 167 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected, ""); 168 RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected, ""); 169 RETURN_ERROR_IF(expectedWriteSize < litSize , dstSize_tooSmall, ""); 170 ZSTD_allocateLiteralsBuffer(dctx, dst, dstCapacity, litSize, streaming, expectedWriteSize, 0); 171 172 /* prefetch huffman table if cold */ 173 if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) { 174 PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable)); 175 } 176 177 if (litEncType==set_repeat) { 178 if (singleStream) { 179 hufSuccess = HUF_decompress1X_usingDTable_bmi2( 180 dctx->litBuffer, litSize, istart+lhSize, litCSize, 181 dctx->HUFptr, ZSTD_DCtx_get_bmi2(dctx)); 182 } else { 183 hufSuccess = HUF_decompress4X_usingDTable_bmi2( 184 dctx->litBuffer, litSize, istart+lhSize, litCSize, 185 dctx->HUFptr, ZSTD_DCtx_get_bmi2(dctx)); 186 } 187 } else { 188 if (singleStream) { 189 #if defined(HUF_FORCE_DECOMPRESS_X2) 190 hufSuccess = HUF_decompress1X_DCtx_wksp( 191 dctx->entropy.hufTable, dctx->litBuffer, litSize, 192 istart+lhSize, litCSize, dctx->workspace, 193 sizeof(dctx->workspace)); 194 #else 195 hufSuccess = HUF_decompress1X1_DCtx_wksp_bmi2( 196 dctx->entropy.hufTable, dctx->litBuffer, litSize, 197 istart+lhSize, litCSize, dctx->workspace, 198 sizeof(dctx->workspace), ZSTD_DCtx_get_bmi2(dctx)); 199 #endif 200 } else { 201 hufSuccess = HUF_decompress4X_hufOnly_wksp_bmi2( 202 dctx->entropy.hufTable, dctx->litBuffer, litSize, 203 istart+lhSize, litCSize, dctx->workspace, 204 sizeof(dctx->workspace), ZSTD_DCtx_get_bmi2(dctx)); 205 } 206 } 207 if (dctx->litBufferLocation == ZSTD_split) 208 { 209 ZSTD_memcpy(dctx->litExtraBuffer, dctx->litBufferEnd - ZSTD_LITBUFFEREXTRASIZE, ZSTD_LITBUFFEREXTRASIZE); 210 ZSTD_memmove(dctx->litBuffer + ZSTD_LITBUFFEREXTRASIZE - WILDCOPY_OVERLENGTH, dctx->litBuffer, litSize - ZSTD_LITBUFFEREXTRASIZE); 211 dctx->litBuffer += ZSTD_LITBUFFEREXTRASIZE - WILDCOPY_OVERLENGTH; 212 dctx->litBufferEnd -= WILDCOPY_OVERLENGTH; 213 } 214 215 RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected, ""); 216 217 dctx->litPtr = dctx->litBuffer; 218 dctx->litSize = litSize; 219 dctx->litEntropy = 1; 220 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable; 221 return litCSize + lhSize; 222 } 223 224 case set_basic: 225 { size_t litSize, lhSize; 226 U32 const lhlCode = ((istart[0]) >> 2) & 3; 227 size_t expectedWriteSize = MIN(ZSTD_BLOCKSIZE_MAX, dstCapacity); 228 switch(lhlCode) 229 { 230 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */ 231 lhSize = 1; 232 litSize = istart[0] >> 3; 233 break; 234 case 1: 235 lhSize = 2; 236 litSize = MEM_readLE16(istart) >> 4; 237 break; 238 case 3: 239 lhSize = 3; 240 litSize = MEM_readLE24(istart) >> 4; 241 break; 242 } 243 244 RETURN_ERROR_IF(litSize > 0 && dst == NULL, dstSize_tooSmall, "NULL not handled"); 245 RETURN_ERROR_IF(expectedWriteSize < litSize, dstSize_tooSmall, ""); 246 ZSTD_allocateLiteralsBuffer(dctx, dst, dstCapacity, litSize, streaming, expectedWriteSize, 1); 247 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */ 248 RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected, ""); 249 if (dctx->litBufferLocation == ZSTD_split) 250 { 251 ZSTD_memcpy(dctx->litBuffer, istart + lhSize, litSize - ZSTD_LITBUFFEREXTRASIZE); 252 ZSTD_memcpy(dctx->litExtraBuffer, istart + lhSize + litSize - ZSTD_LITBUFFEREXTRASIZE, ZSTD_LITBUFFEREXTRASIZE); 253 } 254 else 255 { 256 ZSTD_memcpy(dctx->litBuffer, istart + lhSize, litSize); 257 } 258 dctx->litPtr = dctx->litBuffer; 259 dctx->litSize = litSize; 260 return lhSize+litSize; 261 } 262 /* direct reference into compressed stream */ 263 dctx->litPtr = istart+lhSize; 264 dctx->litSize = litSize; 265 dctx->litBufferEnd = dctx->litPtr + litSize; 266 dctx->litBufferLocation = ZSTD_not_in_dst; 267 return lhSize+litSize; 268 } 269 270 case set_rle: 271 { U32 const lhlCode = ((istart[0]) >> 2) & 3; 272 size_t litSize, lhSize; 273 size_t expectedWriteSize = MIN(ZSTD_BLOCKSIZE_MAX, dstCapacity); 274 switch(lhlCode) 275 { 276 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */ 277 lhSize = 1; 278 litSize = istart[0] >> 3; 279 break; 280 case 1: 281 lhSize = 2; 282 litSize = MEM_readLE16(istart) >> 4; 283 break; 284 case 3: 285 lhSize = 3; 286 litSize = MEM_readLE24(istart) >> 4; 287 RETURN_ERROR_IF(srcSize<4, corruption_detected, "srcSize >= MIN_CBLOCK_SIZE == 3; here we need lhSize+1 = 4"); 288 break; 289 } 290 RETURN_ERROR_IF(litSize > 0 && dst == NULL, dstSize_tooSmall, "NULL not handled"); 291 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected, ""); 292 RETURN_ERROR_IF(expectedWriteSize < litSize, dstSize_tooSmall, ""); 293 ZSTD_allocateLiteralsBuffer(dctx, dst, dstCapacity, litSize, streaming, expectedWriteSize, 1); 294 if (dctx->litBufferLocation == ZSTD_split) 295 { 296 ZSTD_memset(dctx->litBuffer, istart[lhSize], litSize - ZSTD_LITBUFFEREXTRASIZE); 297 ZSTD_memset(dctx->litExtraBuffer, istart[lhSize], ZSTD_LITBUFFEREXTRASIZE); 298 } 299 else 300 { 301 ZSTD_memset(dctx->litBuffer, istart[lhSize], litSize); 302 } 303 dctx->litPtr = dctx->litBuffer; 304 dctx->litSize = litSize; 305 return lhSize+1; 306 } 307 default: 308 RETURN_ERROR(corruption_detected, "impossible"); 309 } 310 } 311 } 312 313 /* Default FSE distribution tables. 314 * These are pre-calculated FSE decoding tables using default distributions as defined in specification : 315 * https://github.com/facebook/zstd/blob/release/doc/zstd_compression_format.md#default-distributions 316 * They were generated programmatically with following method : 317 * - start from default distributions, present in /lib/common/zstd_internal.h 318 * - generate tables normally, using ZSTD_buildFSETable() 319 * - printout the content of tables 320 * - pretify output, report below, test with fuzzer to ensure it's correct */ 321 322 /* Default FSE distribution table for Literal Lengths */ 323 static const ZSTD_seqSymbol LL_defaultDTable[(1<<LL_DEFAULTNORMLOG)+1] = { 324 { 1, 1, 1, LL_DEFAULTNORMLOG}, /* header : fastMode, tableLog */ 325 /* nextState, nbAddBits, nbBits, baseVal */ 326 { 0, 0, 4, 0}, { 16, 0, 4, 0}, 327 { 32, 0, 5, 1}, { 0, 0, 5, 3}, 328 { 0, 0, 5, 4}, { 0, 0, 5, 6}, 329 { 0, 0, 5, 7}, { 0, 0, 5, 9}, 330 { 0, 0, 5, 10}, { 0, 0, 5, 12}, 331 { 0, 0, 6, 14}, { 0, 1, 5, 16}, 332 { 0, 1, 5, 20}, { 0, 1, 5, 22}, 333 { 0, 2, 5, 28}, { 0, 3, 5, 32}, 334 { 0, 4, 5, 48}, { 32, 6, 5, 64}, 335 { 0, 7, 5, 128}, { 0, 8, 6, 256}, 336 { 0, 10, 6, 1024}, { 0, 12, 6, 4096}, 337 { 32, 0, 4, 0}, { 0, 0, 4, 1}, 338 { 0, 0, 5, 2}, { 32, 0, 5, 4}, 339 { 0, 0, 5, 5}, { 32, 0, 5, 7}, 340 { 0, 0, 5, 8}, { 32, 0, 5, 10}, 341 { 0, 0, 5, 11}, { 0, 0, 6, 13}, 342 { 32, 1, 5, 16}, { 0, 1, 5, 18}, 343 { 32, 1, 5, 22}, { 0, 2, 5, 24}, 344 { 32, 3, 5, 32}, { 0, 3, 5, 40}, 345 { 0, 6, 4, 64}, { 16, 6, 4, 64}, 346 { 32, 7, 5, 128}, { 0, 9, 6, 512}, 347 { 0, 11, 6, 2048}, { 48, 0, 4, 0}, 348 { 16, 0, 4, 1}, { 32, 0, 5, 2}, 349 { 32, 0, 5, 3}, { 32, 0, 5, 5}, 350 { 32, 0, 5, 6}, { 32, 0, 5, 8}, 351 { 32, 0, 5, 9}, { 32, 0, 5, 11}, 352 { 32, 0, 5, 12}, { 0, 0, 6, 15}, 353 { 32, 1, 5, 18}, { 32, 1, 5, 20}, 354 { 32, 2, 5, 24}, { 32, 2, 5, 28}, 355 { 32, 3, 5, 40}, { 32, 4, 5, 48}, 356 { 0, 16, 6,65536}, { 0, 15, 6,32768}, 357 { 0, 14, 6,16384}, { 0, 13, 6, 8192}, 358 }; /* LL_defaultDTable */ 359 360 /* Default FSE distribution table for Offset Codes */ 361 static const ZSTD_seqSymbol OF_defaultDTable[(1<<OF_DEFAULTNORMLOG)+1] = { 362 { 1, 1, 1, OF_DEFAULTNORMLOG}, /* header : fastMode, tableLog */ 363 /* nextState, nbAddBits, nbBits, baseVal */ 364 { 0, 0, 5, 0}, { 0, 6, 4, 61}, 365 { 0, 9, 5, 509}, { 0, 15, 5,32765}, 366 { 0, 21, 5,2097149}, { 0, 3, 5, 5}, 367 { 0, 7, 4, 125}, { 0, 12, 5, 4093}, 368 { 0, 18, 5,262141}, { 0, 23, 5,8388605}, 369 { 0, 5, 5, 29}, { 0, 8, 4, 253}, 370 { 0, 14, 5,16381}, { 0, 20, 5,1048573}, 371 { 0, 2, 5, 1}, { 16, 7, 4, 125}, 372 { 0, 11, 5, 2045}, { 0, 17, 5,131069}, 373 { 0, 22, 5,4194301}, { 0, 4, 5, 13}, 374 { 16, 8, 4, 253}, { 0, 13, 5, 8189}, 375 { 0, 19, 5,524285}, { 0, 1, 5, 1}, 376 { 16, 6, 4, 61}, { 0, 10, 5, 1021}, 377 { 0, 16, 5,65533}, { 0, 28, 5,268435453}, 378 { 0, 27, 5,134217725}, { 0, 26, 5,67108861}, 379 { 0, 25, 5,33554429}, { 0, 24, 5,16777213}, 380 }; /* OF_defaultDTable */ 381 382 383 /* Default FSE distribution table for Match Lengths */ 384 static const ZSTD_seqSymbol ML_defaultDTable[(1<<ML_DEFAULTNORMLOG)+1] = { 385 { 1, 1, 1, ML_DEFAULTNORMLOG}, /* header : fastMode, tableLog */ 386 /* nextState, nbAddBits, nbBits, baseVal */ 387 { 0, 0, 6, 3}, { 0, 0, 4, 4}, 388 { 32, 0, 5, 5}, { 0, 0, 5, 6}, 389 { 0, 0, 5, 8}, { 0, 0, 5, 9}, 390 { 0, 0, 5, 11}, { 0, 0, 6, 13}, 391 { 0, 0, 6, 16}, { 0, 0, 6, 19}, 392 { 0, 0, 6, 22}, { 0, 0, 6, 25}, 393 { 0, 0, 6, 28}, { 0, 0, 6, 31}, 394 { 0, 0, 6, 34}, { 0, 1, 6, 37}, 395 { 0, 1, 6, 41}, { 0, 2, 6, 47}, 396 { 0, 3, 6, 59}, { 0, 4, 6, 83}, 397 { 0, 7, 6, 131}, { 0, 9, 6, 515}, 398 { 16, 0, 4, 4}, { 0, 0, 4, 5}, 399 { 32, 0, 5, 6}, { 0, 0, 5, 7}, 400 { 32, 0, 5, 9}, { 0, 0, 5, 10}, 401 { 0, 0, 6, 12}, { 0, 0, 6, 15}, 402 { 0, 0, 6, 18}, { 0, 0, 6, 21}, 403 { 0, 0, 6, 24}, { 0, 0, 6, 27}, 404 { 0, 0, 6, 30}, { 0, 0, 6, 33}, 405 { 0, 1, 6, 35}, { 0, 1, 6, 39}, 406 { 0, 2, 6, 43}, { 0, 3, 6, 51}, 407 { 0, 4, 6, 67}, { 0, 5, 6, 99}, 408 { 0, 8, 6, 259}, { 32, 0, 4, 4}, 409 { 48, 0, 4, 4}, { 16, 0, 4, 5}, 410 { 32, 0, 5, 7}, { 32, 0, 5, 8}, 411 { 32, 0, 5, 10}, { 32, 0, 5, 11}, 412 { 0, 0, 6, 14}, { 0, 0, 6, 17}, 413 { 0, 0, 6, 20}, { 0, 0, 6, 23}, 414 { 0, 0, 6, 26}, { 0, 0, 6, 29}, 415 { 0, 0, 6, 32}, { 0, 16, 6,65539}, 416 { 0, 15, 6,32771}, { 0, 14, 6,16387}, 417 { 0, 13, 6, 8195}, { 0, 12, 6, 4099}, 418 { 0, 11, 6, 2051}, { 0, 10, 6, 1027}, 419 }; /* ML_defaultDTable */ 420 421 ZSTD_buildSeqTable_rle(ZSTD_seqSymbol * dt,U32 baseValue,U8 nbAddBits)422 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U8 nbAddBits) 423 { 424 void* ptr = dt; 425 ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr; 426 ZSTD_seqSymbol* const cell = dt + 1; 427 428 DTableH->tableLog = 0; 429 DTableH->fastMode = 0; 430 431 cell->nbBits = 0; 432 cell->nextState = 0; 433 assert(nbAddBits < 255); 434 cell->nbAdditionalBits = nbAddBits; 435 cell->baseValue = baseValue; 436 } 437 438 439 /* ZSTD_buildFSETable() : 440 * generate FSE decoding table for one symbol (ll, ml or off) 441 * cannot fail if input is valid => 442 * all inputs are presumed validated at this stage */ 443 FORCE_INLINE_TEMPLATE ZSTD_buildFSETable_body(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U8 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize)444 void ZSTD_buildFSETable_body(ZSTD_seqSymbol* dt, 445 const short* normalizedCounter, unsigned maxSymbolValue, 446 const U32* baseValue, const U8* nbAdditionalBits, 447 unsigned tableLog, void* wksp, size_t wkspSize) 448 { 449 ZSTD_seqSymbol* const tableDecode = dt+1; 450 U32 const maxSV1 = maxSymbolValue + 1; 451 U32 const tableSize = 1 << tableLog; 452 453 U16* symbolNext = (U16*)wksp; 454 BYTE* spread = (BYTE*)(symbolNext + MaxSeq + 1); 455 U32 highThreshold = tableSize - 1; 456 457 458 /* Sanity Checks */ 459 assert(maxSymbolValue <= MaxSeq); 460 assert(tableLog <= MaxFSELog); 461 assert(wkspSize >= ZSTD_BUILD_FSE_TABLE_WKSP_SIZE); 462 (void)wkspSize; 463 /* Init, lay down lowprob symbols */ 464 { ZSTD_seqSymbol_header DTableH; 465 DTableH.tableLog = tableLog; 466 DTableH.fastMode = 1; 467 { S16 const largeLimit= (S16)(1 << (tableLog-1)); 468 U32 s; 469 for (s=0; s<maxSV1; s++) { 470 if (normalizedCounter[s]==-1) { 471 tableDecode[highThreshold--].baseValue = s; 472 symbolNext[s] = 1; 473 } else { 474 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0; 475 assert(normalizedCounter[s]>=0); 476 symbolNext[s] = (U16)normalizedCounter[s]; 477 } } } 478 ZSTD_memcpy(dt, &DTableH, sizeof(DTableH)); 479 } 480 481 /* Spread symbols */ 482 assert(tableSize <= 512); 483 /* Specialized symbol spreading for the case when there are 484 * no low probability (-1 count) symbols. When compressing 485 * small blocks we avoid low probability symbols to hit this 486 * case, since header decoding speed matters more. 487 */ 488 if (highThreshold == tableSize - 1) { 489 size_t const tableMask = tableSize-1; 490 size_t const step = FSE_TABLESTEP(tableSize); 491 /* First lay down the symbols in order. 492 * We use a uint64_t to lay down 8 bytes at a time. This reduces branch 493 * misses since small blocks generally have small table logs, so nearly 494 * all symbols have counts <= 8. We ensure we have 8 bytes at the end of 495 * our buffer to handle the over-write. 496 */ 497 { 498 U64 const add = 0x0101010101010101ull; 499 size_t pos = 0; 500 U64 sv = 0; 501 U32 s; 502 for (s=0; s<maxSV1; ++s, sv += add) { 503 int i; 504 int const n = normalizedCounter[s]; 505 MEM_write64(spread + pos, sv); 506 for (i = 8; i < n; i += 8) { 507 MEM_write64(spread + pos + i, sv); 508 } 509 pos += n; 510 } 511 } 512 /* Now we spread those positions across the table. 513 * The benefit of doing it in two stages is that we avoid the the 514 * variable size inner loop, which caused lots of branch misses. 515 * Now we can run through all the positions without any branch misses. 516 * We unroll the loop twice, since that is what emperically worked best. 517 */ 518 { 519 size_t position = 0; 520 size_t s; 521 size_t const unroll = 2; 522 assert(tableSize % unroll == 0); /* FSE_MIN_TABLELOG is 5 */ 523 for (s = 0; s < (size_t)tableSize; s += unroll) { 524 size_t u; 525 for (u = 0; u < unroll; ++u) { 526 size_t const uPosition = (position + (u * step)) & tableMask; 527 tableDecode[uPosition].baseValue = spread[s + u]; 528 } 529 position = (position + (unroll * step)) & tableMask; 530 } 531 assert(position == 0); 532 } 533 } else { 534 U32 const tableMask = tableSize-1; 535 U32 const step = FSE_TABLESTEP(tableSize); 536 U32 s, position = 0; 537 for (s=0; s<maxSV1; s++) { 538 int i; 539 int const n = normalizedCounter[s]; 540 for (i=0; i<n; i++) { 541 tableDecode[position].baseValue = s; 542 position = (position + step) & tableMask; 543 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */ 544 } } 545 assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */ 546 } 547 548 /* Build Decoding table */ 549 { 550 U32 u; 551 for (u=0; u<tableSize; u++) { 552 U32 const symbol = tableDecode[u].baseValue; 553 U32 const nextState = symbolNext[symbol]++; 554 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) ); 555 tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize); 556 assert(nbAdditionalBits[symbol] < 255); 557 tableDecode[u].nbAdditionalBits = nbAdditionalBits[symbol]; 558 tableDecode[u].baseValue = baseValue[symbol]; 559 } 560 } 561 } 562 563 /* Avoids the FORCE_INLINE of the _body() function. */ ZSTD_buildFSETable_body_default(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U8 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize)564 static void ZSTD_buildFSETable_body_default(ZSTD_seqSymbol* dt, 565 const short* normalizedCounter, unsigned maxSymbolValue, 566 const U32* baseValue, const U8* nbAdditionalBits, 567 unsigned tableLog, void* wksp, size_t wkspSize) 568 { 569 ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue, 570 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize); 571 } 572 573 #if DYNAMIC_BMI2 ZSTD_buildFSETable_body_bmi2(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U8 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize)574 BMI2_TARGET_ATTRIBUTE static void ZSTD_buildFSETable_body_bmi2(ZSTD_seqSymbol* dt, 575 const short* normalizedCounter, unsigned maxSymbolValue, 576 const U32* baseValue, const U8* nbAdditionalBits, 577 unsigned tableLog, void* wksp, size_t wkspSize) 578 { 579 ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue, 580 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize); 581 } 582 #endif 583 ZSTD_buildFSETable(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U8 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize,int bmi2)584 void ZSTD_buildFSETable(ZSTD_seqSymbol* dt, 585 const short* normalizedCounter, unsigned maxSymbolValue, 586 const U32* baseValue, const U8* nbAdditionalBits, 587 unsigned tableLog, void* wksp, size_t wkspSize, int bmi2) 588 { 589 #if DYNAMIC_BMI2 590 if (bmi2) { 591 ZSTD_buildFSETable_body_bmi2(dt, normalizedCounter, maxSymbolValue, 592 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize); 593 return; 594 } 595 #endif 596 (void)bmi2; 597 ZSTD_buildFSETable_body_default(dt, normalizedCounter, maxSymbolValue, 598 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize); 599 } 600 601 602 /*! ZSTD_buildSeqTable() : 603 * @return : nb bytes read from src, 604 * or an error code if it fails */ ZSTD_buildSeqTable(ZSTD_seqSymbol * DTableSpace,const ZSTD_seqSymbol ** DTablePtr,symbolEncodingType_e type,unsigned max,U32 maxLog,const void * src,size_t srcSize,const U32 * baseValue,const U8 * nbAdditionalBits,const ZSTD_seqSymbol * defaultTable,U32 flagRepeatTable,int ddictIsCold,int nbSeq,U32 * wksp,size_t wkspSize,int bmi2)605 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr, 606 symbolEncodingType_e type, unsigned max, U32 maxLog, 607 const void* src, size_t srcSize, 608 const U32* baseValue, const U8* nbAdditionalBits, 609 const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable, 610 int ddictIsCold, int nbSeq, U32* wksp, size_t wkspSize, 611 int bmi2) 612 { 613 switch(type) 614 { 615 case set_rle : 616 RETURN_ERROR_IF(!srcSize, srcSize_wrong, ""); 617 RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected, ""); 618 { U32 const symbol = *(const BYTE*)src; 619 U32 const baseline = baseValue[symbol]; 620 U8 const nbBits = nbAdditionalBits[symbol]; 621 ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits); 622 } 623 *DTablePtr = DTableSpace; 624 return 1; 625 case set_basic : 626 *DTablePtr = defaultTable; 627 return 0; 628 case set_repeat: 629 RETURN_ERROR_IF(!flagRepeatTable, corruption_detected, ""); 630 /* prefetch FSE table if used */ 631 if (ddictIsCold && (nbSeq > 24 /* heuristic */)) { 632 const void* const pStart = *DTablePtr; 633 size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog)); 634 PREFETCH_AREA(pStart, pSize); 635 } 636 return 0; 637 case set_compressed : 638 { unsigned tableLog; 639 S16 norm[MaxSeq+1]; 640 size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize); 641 RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected, ""); 642 RETURN_ERROR_IF(tableLog > maxLog, corruption_detected, ""); 643 ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog, wksp, wkspSize, bmi2); 644 *DTablePtr = DTableSpace; 645 return headerSize; 646 } 647 default : 648 assert(0); 649 RETURN_ERROR(GENERIC, "impossible"); 650 } 651 } 652 ZSTD_decodeSeqHeaders(ZSTD_DCtx * dctx,int * nbSeqPtr,const void * src,size_t srcSize)653 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr, 654 const void* src, size_t srcSize) 655 { 656 const BYTE* const istart = (const BYTE*)src; 657 const BYTE* const iend = istart + srcSize; 658 const BYTE* ip = istart; 659 int nbSeq; 660 DEBUGLOG(5, "ZSTD_decodeSeqHeaders"); 661 662 /* check */ 663 RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong, ""); 664 665 /* SeqHead */ 666 nbSeq = *ip++; 667 if (!nbSeq) { 668 *nbSeqPtr=0; 669 RETURN_ERROR_IF(srcSize != 1, srcSize_wrong, ""); 670 return 1; 671 } 672 if (nbSeq > 0x7F) { 673 if (nbSeq == 0xFF) { 674 RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong, ""); 675 nbSeq = MEM_readLE16(ip) + LONGNBSEQ; 676 ip+=2; 677 } else { 678 RETURN_ERROR_IF(ip >= iend, srcSize_wrong, ""); 679 nbSeq = ((nbSeq-0x80)<<8) + *ip++; 680 } 681 } 682 *nbSeqPtr = nbSeq; 683 684 /* FSE table descriptors */ 685 RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong, ""); /* minimum possible size: 1 byte for symbol encoding types */ 686 { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6); 687 symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3); 688 symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3); 689 ip++; 690 691 /* Build DTables */ 692 { size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr, 693 LLtype, MaxLL, LLFSELog, 694 ip, iend-ip, 695 LL_base, LL_bits, 696 LL_defaultDTable, dctx->fseEntropy, 697 dctx->ddictIsCold, nbSeq, 698 dctx->workspace, sizeof(dctx->workspace), 699 ZSTD_DCtx_get_bmi2(dctx)); 700 RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected, "ZSTD_buildSeqTable failed"); 701 ip += llhSize; 702 } 703 704 { size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr, 705 OFtype, MaxOff, OffFSELog, 706 ip, iend-ip, 707 OF_base, OF_bits, 708 OF_defaultDTable, dctx->fseEntropy, 709 dctx->ddictIsCold, nbSeq, 710 dctx->workspace, sizeof(dctx->workspace), 711 ZSTD_DCtx_get_bmi2(dctx)); 712 RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected, "ZSTD_buildSeqTable failed"); 713 ip += ofhSize; 714 } 715 716 { size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr, 717 MLtype, MaxML, MLFSELog, 718 ip, iend-ip, 719 ML_base, ML_bits, 720 ML_defaultDTable, dctx->fseEntropy, 721 dctx->ddictIsCold, nbSeq, 722 dctx->workspace, sizeof(dctx->workspace), 723 ZSTD_DCtx_get_bmi2(dctx)); 724 RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected, "ZSTD_buildSeqTable failed"); 725 ip += mlhSize; 726 } 727 } 728 729 return ip-istart; 730 } 731 732 733 typedef struct { 734 size_t litLength; 735 size_t matchLength; 736 size_t offset; 737 } seq_t; 738 739 typedef struct { 740 size_t state; 741 const ZSTD_seqSymbol* table; 742 } ZSTD_fseState; 743 744 typedef struct { 745 BIT_DStream_t DStream; 746 ZSTD_fseState stateLL; 747 ZSTD_fseState stateOffb; 748 ZSTD_fseState stateML; 749 size_t prevOffset[ZSTD_REP_NUM]; 750 } seqState_t; 751 752 /*! ZSTD_overlapCopy8() : 753 * Copies 8 bytes from ip to op and updates op and ip where ip <= op. 754 * If the offset is < 8 then the offset is spread to at least 8 bytes. 755 * 756 * Precondition: *ip <= *op 757 * Postcondition: *op - *op >= 8 758 */ ZSTD_overlapCopy8(BYTE ** op,BYTE const ** ip,size_t offset)759 HINT_INLINE void ZSTD_overlapCopy8(BYTE** op, BYTE const** ip, size_t offset) { 760 assert(*ip <= *op); 761 if (offset < 8) { 762 /* close range match, overlap */ 763 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */ 764 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */ 765 int const sub2 = dec64table[offset]; 766 (*op)[0] = (*ip)[0]; 767 (*op)[1] = (*ip)[1]; 768 (*op)[2] = (*ip)[2]; 769 (*op)[3] = (*ip)[3]; 770 *ip += dec32table[offset]; 771 ZSTD_copy4(*op+4, *ip); 772 *ip -= sub2; 773 } else { 774 ZSTD_copy8(*op, *ip); 775 } 776 *ip += 8; 777 *op += 8; 778 assert(*op - *ip >= 8); 779 } 780 781 /*! ZSTD_safecopy() : 782 * Specialized version of memcpy() that is allowed to READ up to WILDCOPY_OVERLENGTH past the input buffer 783 * and write up to 16 bytes past oend_w (op >= oend_w is allowed). 784 * This function is only called in the uncommon case where the sequence is near the end of the block. It 785 * should be fast for a single long sequence, but can be slow for several short sequences. 786 * 787 * @param ovtype controls the overlap detection 788 * - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart. 789 * - ZSTD_overlap_src_before_dst: The src and dst may overlap and may be any distance apart. 790 * The src buffer must be before the dst buffer. 791 */ ZSTD_safecopy(BYTE * op,const BYTE * const oend_w,BYTE const * ip,ptrdiff_t length,ZSTD_overlap_e ovtype)792 static void ZSTD_safecopy(BYTE* op, const BYTE* const oend_w, BYTE const* ip, ptrdiff_t length, ZSTD_overlap_e ovtype) { 793 ptrdiff_t const diff = op - ip; 794 BYTE* const oend = op + length; 795 796 assert((ovtype == ZSTD_no_overlap && (diff <= -8 || diff >= 8 || op >= oend_w)) || 797 (ovtype == ZSTD_overlap_src_before_dst && diff >= 0)); 798 799 if (length < 8) { 800 /* Handle short lengths. */ 801 while (op < oend) *op++ = *ip++; 802 return; 803 } 804 if (ovtype == ZSTD_overlap_src_before_dst) { 805 /* Copy 8 bytes and ensure the offset >= 8 when there can be overlap. */ 806 assert(length >= 8); 807 ZSTD_overlapCopy8(&op, &ip, diff); 808 length -= 8; 809 assert(op - ip >= 8); 810 assert(op <= oend); 811 } 812 813 if (oend <= oend_w) { 814 /* No risk of overwrite. */ 815 ZSTD_wildcopy(op, ip, length, ovtype); 816 return; 817 } 818 if (op <= oend_w) { 819 /* Wildcopy until we get close to the end. */ 820 assert(oend > oend_w); 821 ZSTD_wildcopy(op, ip, oend_w - op, ovtype); 822 ip += oend_w - op; 823 op += oend_w - op; 824 } 825 /* Handle the leftovers. */ 826 while (op < oend) *op++ = *ip++; 827 } 828 829 /* ZSTD_safecopyDstBeforeSrc(): 830 * This version allows overlap with dst before src, or handles the non-overlap case with dst after src 831 * Kept separate from more common ZSTD_safecopy case to avoid performance impact to the safecopy common case */ ZSTD_safecopyDstBeforeSrc(BYTE * op,BYTE const * ip,ptrdiff_t length)832 static void ZSTD_safecopyDstBeforeSrc(BYTE* op, BYTE const* ip, ptrdiff_t length) { 833 ptrdiff_t const diff = op - ip; 834 BYTE* const oend = op + length; 835 836 if (length < 8 || diff > -8) { 837 /* Handle short lengths, close overlaps, and dst not before src. */ 838 while (op < oend) *op++ = *ip++; 839 return; 840 } 841 842 if (op <= oend - WILDCOPY_OVERLENGTH && diff < -WILDCOPY_VECLEN) { 843 ZSTD_wildcopy(op, ip, oend - WILDCOPY_OVERLENGTH - op, ZSTD_no_overlap); 844 ip += oend - WILDCOPY_OVERLENGTH - op; 845 op += oend - WILDCOPY_OVERLENGTH - op; 846 } 847 848 /* Handle the leftovers. */ 849 while (op < oend) *op++ = *ip++; 850 } 851 852 /* ZSTD_execSequenceEnd(): 853 * This version handles cases that are near the end of the output buffer. It requires 854 * more careful checks to make sure there is no overflow. By separating out these hard 855 * and unlikely cases, we can speed up the common cases. 856 * 857 * NOTE: This function needs to be fast for a single long sequence, but doesn't need 858 * to be optimized for many small sequences, since those fall into ZSTD_execSequence(). 859 */ 860 FORCE_NOINLINE ZSTD_execSequenceEnd(BYTE * op,BYTE * const oend,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const prefixStart,const BYTE * const virtualStart,const BYTE * const dictEnd)861 size_t ZSTD_execSequenceEnd(BYTE* op, 862 BYTE* const oend, seq_t sequence, 863 const BYTE** litPtr, const BYTE* const litLimit, 864 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd) 865 { 866 BYTE* const oLitEnd = op + sequence.litLength; 867 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 868 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 869 const BYTE* match = oLitEnd - sequence.offset; 870 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH; 871 872 /* bounds checks : careful of address space overflow in 32-bit mode */ 873 RETURN_ERROR_IF(sequenceLength > (size_t)(oend - op), dstSize_tooSmall, "last match must fit within dstBuffer"); 874 RETURN_ERROR_IF(sequence.litLength > (size_t)(litLimit - *litPtr), corruption_detected, "try to read beyond literal buffer"); 875 assert(op < op + sequenceLength); 876 assert(oLitEnd < op + sequenceLength); 877 878 /* copy literals */ 879 ZSTD_safecopy(op, oend_w, *litPtr, sequence.litLength, ZSTD_no_overlap); 880 op = oLitEnd; 881 *litPtr = iLitEnd; 882 883 /* copy Match */ 884 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) { 885 /* offset beyond prefix */ 886 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected, ""); 887 match = dictEnd - (prefixStart - match); 888 if (match + sequence.matchLength <= dictEnd) { 889 ZSTD_memmove(oLitEnd, match, sequence.matchLength); 890 return sequenceLength; 891 } 892 /* span extDict & currentPrefixSegment */ 893 { size_t const length1 = dictEnd - match; 894 ZSTD_memmove(oLitEnd, match, length1); 895 op = oLitEnd + length1; 896 sequence.matchLength -= length1; 897 match = prefixStart; 898 } 899 } 900 ZSTD_safecopy(op, oend_w, match, sequence.matchLength, ZSTD_overlap_src_before_dst); 901 return sequenceLength; 902 } 903 904 /* ZSTD_execSequenceEndSplitLitBuffer(): 905 * This version is intended to be used during instances where the litBuffer is still split. It is kept separate to avoid performance impact for the good case. 906 */ 907 FORCE_NOINLINE ZSTD_execSequenceEndSplitLitBuffer(BYTE * op,BYTE * const oend,const BYTE * const oend_w,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const prefixStart,const BYTE * const virtualStart,const BYTE * const dictEnd)908 size_t ZSTD_execSequenceEndSplitLitBuffer(BYTE* op, 909 BYTE* const oend, const BYTE* const oend_w, seq_t sequence, 910 const BYTE** litPtr, const BYTE* const litLimit, 911 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd) 912 { 913 BYTE* const oLitEnd = op + sequence.litLength; 914 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 915 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 916 const BYTE* match = oLitEnd - sequence.offset; 917 918 919 /* bounds checks : careful of address space overflow in 32-bit mode */ 920 RETURN_ERROR_IF(sequenceLength > (size_t)(oend - op), dstSize_tooSmall, "last match must fit within dstBuffer"); 921 RETURN_ERROR_IF(sequence.litLength > (size_t)(litLimit - *litPtr), corruption_detected, "try to read beyond literal buffer"); 922 assert(op < op + sequenceLength); 923 assert(oLitEnd < op + sequenceLength); 924 925 /* copy literals */ 926 RETURN_ERROR_IF(op > *litPtr && op < *litPtr + sequence.litLength, dstSize_tooSmall, "output should not catch up to and overwrite literal buffer"); 927 ZSTD_safecopyDstBeforeSrc(op, *litPtr, sequence.litLength); 928 op = oLitEnd; 929 *litPtr = iLitEnd; 930 931 /* copy Match */ 932 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) { 933 /* offset beyond prefix */ 934 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected, ""); 935 match = dictEnd - (prefixStart - match); 936 if (match + sequence.matchLength <= dictEnd) { 937 ZSTD_memmove(oLitEnd, match, sequence.matchLength); 938 return sequenceLength; 939 } 940 /* span extDict & currentPrefixSegment */ 941 { size_t const length1 = dictEnd - match; 942 ZSTD_memmove(oLitEnd, match, length1); 943 op = oLitEnd + length1; 944 sequence.matchLength -= length1; 945 match = prefixStart; 946 } 947 } 948 ZSTD_safecopy(op, oend_w, match, sequence.matchLength, ZSTD_overlap_src_before_dst); 949 return sequenceLength; 950 } 951 952 HINT_INLINE ZSTD_execSequence(BYTE * op,BYTE * const oend,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const prefixStart,const BYTE * const virtualStart,const BYTE * const dictEnd)953 size_t ZSTD_execSequence(BYTE* op, 954 BYTE* const oend, seq_t sequence, 955 const BYTE** litPtr, const BYTE* const litLimit, 956 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd) 957 { 958 BYTE* const oLitEnd = op + sequence.litLength; 959 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 960 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 961 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH; /* risk : address space underflow on oend=NULL */ 962 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 963 const BYTE* match = oLitEnd - sequence.offset; 964 965 assert(op != NULL /* Precondition */); 966 assert(oend_w < oend /* No underflow */); 967 /* Handle edge cases in a slow path: 968 * - Read beyond end of literals 969 * - Match end is within WILDCOPY_OVERLIMIT of oend 970 * - 32-bit mode and the match length overflows 971 */ 972 if (UNLIKELY( 973 iLitEnd > litLimit || 974 oMatchEnd > oend_w || 975 (MEM_32bits() && (size_t)(oend - op) < sequenceLength + WILDCOPY_OVERLENGTH))) 976 return ZSTD_execSequenceEnd(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd); 977 978 /* Assumptions (everything else goes into ZSTD_execSequenceEnd()) */ 979 assert(op <= oLitEnd /* No overflow */); 980 assert(oLitEnd < oMatchEnd /* Non-zero match & no overflow */); 981 assert(oMatchEnd <= oend /* No underflow */); 982 assert(iLitEnd <= litLimit /* Literal length is in bounds */); 983 assert(oLitEnd <= oend_w /* Can wildcopy literals */); 984 assert(oMatchEnd <= oend_w /* Can wildcopy matches */); 985 986 /* Copy Literals: 987 * Split out litLength <= 16 since it is nearly always true. +1.6% on gcc-9. 988 * We likely don't need the full 32-byte wildcopy. 989 */ 990 assert(WILDCOPY_OVERLENGTH >= 16); 991 ZSTD_copy16(op, (*litPtr)); 992 if (UNLIKELY(sequence.litLength > 16)) { 993 ZSTD_wildcopy(op + 16, (*litPtr) + 16, sequence.litLength - 16, ZSTD_no_overlap); 994 } 995 op = oLitEnd; 996 *litPtr = iLitEnd; /* update for next sequence */ 997 998 /* Copy Match */ 999 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) { 1000 /* offset beyond prefix -> go into extDict */ 1001 RETURN_ERROR_IF(UNLIKELY(sequence.offset > (size_t)(oLitEnd - virtualStart)), corruption_detected, ""); 1002 match = dictEnd + (match - prefixStart); 1003 if (match + sequence.matchLength <= dictEnd) { 1004 ZSTD_memmove(oLitEnd, match, sequence.matchLength); 1005 return sequenceLength; 1006 } 1007 /* span extDict & currentPrefixSegment */ 1008 { size_t const length1 = dictEnd - match; 1009 ZSTD_memmove(oLitEnd, match, length1); 1010 op = oLitEnd + length1; 1011 sequence.matchLength -= length1; 1012 match = prefixStart; 1013 } 1014 } 1015 /* Match within prefix of 1 or more bytes */ 1016 assert(op <= oMatchEnd); 1017 assert(oMatchEnd <= oend_w); 1018 assert(match >= prefixStart); 1019 assert(sequence.matchLength >= 1); 1020 1021 /* Nearly all offsets are >= WILDCOPY_VECLEN bytes, which means we can use wildcopy 1022 * without overlap checking. 1023 */ 1024 if (LIKELY(sequence.offset >= WILDCOPY_VECLEN)) { 1025 /* We bet on a full wildcopy for matches, since we expect matches to be 1026 * longer than literals (in general). In silesia, ~10% of matches are longer 1027 * than 16 bytes. 1028 */ 1029 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength, ZSTD_no_overlap); 1030 return sequenceLength; 1031 } 1032 assert(sequence.offset < WILDCOPY_VECLEN); 1033 1034 /* Copy 8 bytes and spread the offset to be >= 8. */ 1035 ZSTD_overlapCopy8(&op, &match, sequence.offset); 1036 1037 /* If the match length is > 8 bytes, then continue with the wildcopy. */ 1038 if (sequence.matchLength > 8) { 1039 assert(op < oMatchEnd); 1040 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength - 8, ZSTD_overlap_src_before_dst); 1041 } 1042 return sequenceLength; 1043 } 1044 1045 HINT_INLINE ZSTD_execSequenceSplitLitBuffer(BYTE * op,BYTE * const oend,const BYTE * const oend_w,seq_t sequence,const BYTE ** litPtr,const BYTE * const litLimit,const BYTE * const prefixStart,const BYTE * const virtualStart,const BYTE * const dictEnd)1046 size_t ZSTD_execSequenceSplitLitBuffer(BYTE* op, 1047 BYTE* const oend, const BYTE* const oend_w, seq_t sequence, 1048 const BYTE** litPtr, const BYTE* const litLimit, 1049 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd) 1050 { 1051 BYTE* const oLitEnd = op + sequence.litLength; 1052 size_t const sequenceLength = sequence.litLength + sequence.matchLength; 1053 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */ 1054 const BYTE* const iLitEnd = *litPtr + sequence.litLength; 1055 const BYTE* match = oLitEnd - sequence.offset; 1056 1057 assert(op != NULL /* Precondition */); 1058 assert(oend_w < oend /* No underflow */); 1059 /* Handle edge cases in a slow path: 1060 * - Read beyond end of literals 1061 * - Match end is within WILDCOPY_OVERLIMIT of oend 1062 * - 32-bit mode and the match length overflows 1063 */ 1064 if (UNLIKELY( 1065 iLitEnd > litLimit || 1066 oMatchEnd > oend_w || 1067 (MEM_32bits() && (size_t)(oend - op) < sequenceLength + WILDCOPY_OVERLENGTH))) 1068 return ZSTD_execSequenceEndSplitLitBuffer(op, oend, oend_w, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd); 1069 1070 /* Assumptions (everything else goes into ZSTD_execSequenceEnd()) */ 1071 assert(op <= oLitEnd /* No overflow */); 1072 assert(oLitEnd < oMatchEnd /* Non-zero match & no overflow */); 1073 assert(oMatchEnd <= oend /* No underflow */); 1074 assert(iLitEnd <= litLimit /* Literal length is in bounds */); 1075 assert(oLitEnd <= oend_w /* Can wildcopy literals */); 1076 assert(oMatchEnd <= oend_w /* Can wildcopy matches */); 1077 1078 /* Copy Literals: 1079 * Split out litLength <= 16 since it is nearly always true. +1.6% on gcc-9. 1080 * We likely don't need the full 32-byte wildcopy. 1081 */ 1082 assert(WILDCOPY_OVERLENGTH >= 16); 1083 ZSTD_copy16(op, (*litPtr)); 1084 if (UNLIKELY(sequence.litLength > 16)) { 1085 ZSTD_wildcopy(op+16, (*litPtr)+16, sequence.litLength-16, ZSTD_no_overlap); 1086 } 1087 op = oLitEnd; 1088 *litPtr = iLitEnd; /* update for next sequence */ 1089 1090 /* Copy Match */ 1091 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) { 1092 /* offset beyond prefix -> go into extDict */ 1093 RETURN_ERROR_IF(UNLIKELY(sequence.offset > (size_t)(oLitEnd - virtualStart)), corruption_detected, ""); 1094 match = dictEnd + (match - prefixStart); 1095 if (match + sequence.matchLength <= dictEnd) { 1096 ZSTD_memmove(oLitEnd, match, sequence.matchLength); 1097 return sequenceLength; 1098 } 1099 /* span extDict & currentPrefixSegment */ 1100 { size_t const length1 = dictEnd - match; 1101 ZSTD_memmove(oLitEnd, match, length1); 1102 op = oLitEnd + length1; 1103 sequence.matchLength -= length1; 1104 match = prefixStart; 1105 } } 1106 /* Match within prefix of 1 or more bytes */ 1107 assert(op <= oMatchEnd); 1108 assert(oMatchEnd <= oend_w); 1109 assert(match >= prefixStart); 1110 assert(sequence.matchLength >= 1); 1111 1112 /* Nearly all offsets are >= WILDCOPY_VECLEN bytes, which means we can use wildcopy 1113 * without overlap checking. 1114 */ 1115 if (LIKELY(sequence.offset >= WILDCOPY_VECLEN)) { 1116 /* We bet on a full wildcopy for matches, since we expect matches to be 1117 * longer than literals (in general). In silesia, ~10% of matches are longer 1118 * than 16 bytes. 1119 */ 1120 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength, ZSTD_no_overlap); 1121 return sequenceLength; 1122 } 1123 assert(sequence.offset < WILDCOPY_VECLEN); 1124 1125 /* Copy 8 bytes and spread the offset to be >= 8. */ 1126 ZSTD_overlapCopy8(&op, &match, sequence.offset); 1127 1128 /* If the match length is > 8 bytes, then continue with the wildcopy. */ 1129 if (sequence.matchLength > 8) { 1130 assert(op < oMatchEnd); 1131 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst); 1132 } 1133 return sequenceLength; 1134 } 1135 1136 1137 static void ZSTD_initFseState(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD,const ZSTD_seqSymbol * dt)1138 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt) 1139 { 1140 const void* ptr = dt; 1141 const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr; 1142 DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog); 1143 DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits", 1144 (U32)DStatePtr->state, DTableH->tableLog); 1145 BIT_reloadDStream(bitD); 1146 DStatePtr->table = dt + 1; 1147 } 1148 1149 FORCE_INLINE_TEMPLATE void ZSTD_updateFseStateWithDInfo(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD,U16 nextState,U32 nbBits)1150 ZSTD_updateFseStateWithDInfo(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, U16 nextState, U32 nbBits) 1151 { 1152 size_t const lowBits = BIT_readBits(bitD, nbBits); 1153 DStatePtr->state = nextState + lowBits; 1154 } 1155 1156 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum 1157 * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1) 1158 * bits before reloading. This value is the maximum number of bytes we read 1159 * after reloading when we are decoding long offsets. 1160 */ 1161 #define LONG_OFFSETS_MAX_EXTRA_BITS_32 \ 1162 (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32 \ 1163 ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32 \ 1164 : 0) 1165 1166 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e; 1167 1168 FORCE_INLINE_TEMPLATE seq_t ZSTD_decodeSequence(seqState_t * seqState,const ZSTD_longOffset_e longOffsets)1169 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets) 1170 { 1171 seq_t seq; 1172 const ZSTD_seqSymbol* const llDInfo = seqState->stateLL.table + seqState->stateLL.state; 1173 const ZSTD_seqSymbol* const mlDInfo = seqState->stateML.table + seqState->stateML.state; 1174 const ZSTD_seqSymbol* const ofDInfo = seqState->stateOffb.table + seqState->stateOffb.state; 1175 seq.matchLength = mlDInfo->baseValue; 1176 seq.litLength = llDInfo->baseValue; 1177 { U32 const ofBase = ofDInfo->baseValue; 1178 BYTE const llBits = llDInfo->nbAdditionalBits; 1179 BYTE const mlBits = mlDInfo->nbAdditionalBits; 1180 BYTE const ofBits = ofDInfo->nbAdditionalBits; 1181 BYTE const totalBits = llBits+mlBits+ofBits; 1182 1183 U16 const llNext = llDInfo->nextState; 1184 U16 const mlNext = mlDInfo->nextState; 1185 U16 const ofNext = ofDInfo->nextState; 1186 U32 const llnbBits = llDInfo->nbBits; 1187 U32 const mlnbBits = mlDInfo->nbBits; 1188 U32 const ofnbBits = ofDInfo->nbBits; 1189 /* 1190 * As gcc has better branch and block analyzers, sometimes it is only 1191 * valuable to mark likelyness for clang, it gives around 3-4% of 1192 * performance. 1193 */ 1194 1195 /* sequence */ 1196 { size_t offset; 1197 #if defined(__clang__) 1198 if (LIKELY(ofBits > 1)) { 1199 #else 1200 if (ofBits > 1) { 1201 #endif 1202 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1); 1203 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5); 1204 assert(ofBits <= MaxOff); 1205 if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) { 1206 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed); 1207 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits); 1208 BIT_reloadDStream(&seqState->DStream); 1209 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits); 1210 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32); /* to avoid another reload */ 1211 } else { 1212 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */ 1213 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); 1214 } 1215 seqState->prevOffset[2] = seqState->prevOffset[1]; 1216 seqState->prevOffset[1] = seqState->prevOffset[0]; 1217 seqState->prevOffset[0] = offset; 1218 } else { 1219 U32 const ll0 = (llDInfo->baseValue == 0); 1220 if (LIKELY((ofBits == 0))) { 1221 offset = seqState->prevOffset[ll0]; 1222 seqState->prevOffset[1] = seqState->prevOffset[!ll0]; 1223 seqState->prevOffset[0] = offset; 1224 } else { 1225 offset = ofBase + ll0 + BIT_readBitsFast(&seqState->DStream, 1); 1226 { size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset]; 1227 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */ 1228 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1]; 1229 seqState->prevOffset[1] = seqState->prevOffset[0]; 1230 seqState->prevOffset[0] = offset = temp; 1231 } } } 1232 seq.offset = offset; 1233 } 1234 1235 #if defined(__clang__) 1236 if (UNLIKELY(mlBits > 0)) 1237 #else 1238 if (mlBits > 0) 1239 #endif 1240 seq.matchLength += BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/); 1241 1242 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32)) 1243 BIT_reloadDStream(&seqState->DStream); 1244 if (MEM_64bits() && UNLIKELY(totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog))) 1245 BIT_reloadDStream(&seqState->DStream); 1246 /* Ensure there are enough bits to read the rest of data in 64-bit mode. */ 1247 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64); 1248 1249 #if defined(__clang__) 1250 if (UNLIKELY(llBits > 0)) 1251 #else 1252 if (llBits > 0) 1253 #endif 1254 seq.litLength += BIT_readBitsFast(&seqState->DStream, llBits/*>0*/); 1255 1256 if (MEM_32bits()) 1257 BIT_reloadDStream(&seqState->DStream); 1258 1259 DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u", 1260 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset); 1261 1262 ZSTD_updateFseStateWithDInfo(&seqState->stateLL, &seqState->DStream, llNext, llnbBits); /* <= 9 bits */ 1263 ZSTD_updateFseStateWithDInfo(&seqState->stateML, &seqState->DStream, mlNext, mlnbBits); /* <= 9 bits */ 1264 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */ 1265 ZSTD_updateFseStateWithDInfo(&seqState->stateOffb, &seqState->DStream, ofNext, ofnbBits); /* <= 8 bits */ 1266 } 1267 1268 return seq; 1269 } 1270 1271 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION 1272 MEM_STATIC int ZSTD_dictionaryIsActive(ZSTD_DCtx const* dctx, BYTE const* prefixStart, BYTE const* oLitEnd) 1273 { 1274 size_t const windowSize = dctx->fParams.windowSize; 1275 /* No dictionary used. */ 1276 if (dctx->dictContentEndForFuzzing == NULL) return 0; 1277 /* Dictionary is our prefix. */ 1278 if (prefixStart == dctx->dictContentBeginForFuzzing) return 1; 1279 /* Dictionary is not our ext-dict. */ 1280 if (dctx->dictEnd != dctx->dictContentEndForFuzzing) return 0; 1281 /* Dictionary is not within our window size. */ 1282 if ((size_t)(oLitEnd - prefixStart) >= windowSize) return 0; 1283 /* Dictionary is active. */ 1284 return 1; 1285 } 1286 1287 MEM_STATIC void ZSTD_assertValidSequence( 1288 ZSTD_DCtx const* dctx, 1289 BYTE const* op, BYTE const* oend, 1290 seq_t const seq, 1291 BYTE const* prefixStart, BYTE const* virtualStart) 1292 { 1293 #if DEBUGLEVEL >= 1 1294 size_t const windowSize = dctx->fParams.windowSize; 1295 size_t const sequenceSize = seq.litLength + seq.matchLength; 1296 BYTE const* const oLitEnd = op + seq.litLength; 1297 DEBUGLOG(6, "Checking sequence: litL=%u matchL=%u offset=%u", 1298 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset); 1299 assert(op <= oend); 1300 assert((size_t)(oend - op) >= sequenceSize); 1301 assert(sequenceSize <= ZSTD_BLOCKSIZE_MAX); 1302 if (ZSTD_dictionaryIsActive(dctx, prefixStart, oLitEnd)) { 1303 size_t const dictSize = (size_t)((char const*)dctx->dictContentEndForFuzzing - (char const*)dctx->dictContentBeginForFuzzing); 1304 /* Offset must be within the dictionary. */ 1305 assert(seq.offset <= (size_t)(oLitEnd - virtualStart)); 1306 assert(seq.offset <= windowSize + dictSize); 1307 } else { 1308 /* Offset must be within our window. */ 1309 assert(seq.offset <= windowSize); 1310 } 1311 #else 1312 (void)dctx, (void)op, (void)oend, (void)seq, (void)prefixStart, (void)virtualStart; 1313 #endif 1314 } 1315 #endif 1316 1317 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 1318 1319 1320 FORCE_INLINE_TEMPLATE size_t 1321 DONT_VECTORIZE 1322 ZSTD_decompressSequences_bodySplitLitBuffer( ZSTD_DCtx* dctx, 1323 void* dst, size_t maxDstSize, 1324 const void* seqStart, size_t seqSize, int nbSeq, 1325 const ZSTD_longOffset_e isLongOffset, 1326 const int frame) 1327 { 1328 const BYTE* ip = (const BYTE*)seqStart; 1329 const BYTE* const iend = ip + seqSize; 1330 BYTE* const ostart = (BYTE*)dst; 1331 BYTE* const oend = ostart + maxDstSize; 1332 BYTE* op = ostart; 1333 const BYTE* litPtr = dctx->litPtr; 1334 const BYTE* litBufferEnd = dctx->litBufferEnd; 1335 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart); 1336 const BYTE* const vBase = (const BYTE*) (dctx->virtualStart); 1337 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 1338 DEBUGLOG(5, "ZSTD_decompressSequences_bodySplitLitBuffer"); 1339 (void)frame; 1340 1341 /* Regen sequences */ 1342 if (nbSeq) { 1343 seqState_t seqState; 1344 dctx->fseEntropy = 1; 1345 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; } 1346 RETURN_ERROR_IF( 1347 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)), 1348 corruption_detected, ""); 1349 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr); 1350 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr); 1351 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr); 1352 assert(dst != NULL); 1353 1354 ZSTD_STATIC_ASSERT( 1355 BIT_DStream_unfinished < BIT_DStream_completed && 1356 BIT_DStream_endOfBuffer < BIT_DStream_completed && 1357 BIT_DStream_completed < BIT_DStream_overflow); 1358 1359 /* decompress without overrunning litPtr begins */ 1360 { 1361 seq_t sequence = ZSTD_decodeSequence(&seqState, isLongOffset); 1362 /* Align the decompression loop to 32 + 16 bytes. 1363 * 1364 * zstd compiled with gcc-9 on an Intel i9-9900k shows 10% decompression 1365 * speed swings based on the alignment of the decompression loop. This 1366 * performance swing is caused by parts of the decompression loop falling 1367 * out of the DSB. The entire decompression loop should fit in the DSB, 1368 * when it can't we get much worse performance. You can measure if you've 1369 * hit the good case or the bad case with this perf command for some 1370 * compressed file test.zst: 1371 * 1372 * perf stat -e cycles -e instructions -e idq.all_dsb_cycles_any_uops \ 1373 * -e idq.all_mite_cycles_any_uops -- ./zstd -tq test.zst 1374 * 1375 * If you see most cycles served out of the MITE you've hit the bad case. 1376 * If you see most cycles served out of the DSB you've hit the good case. 1377 * If it is pretty even then you may be in an okay case. 1378 * 1379 * This issue has been reproduced on the following CPUs: 1380 * - Kabylake: Macbook Pro (15-inch, 2019) 2.4 GHz Intel Core i9 1381 * Use Instruments->Counters to get DSB/MITE cycles. 1382 * I never got performance swings, but I was able to 1383 * go from the good case of mostly DSB to half of the 1384 * cycles served from MITE. 1385 * - Coffeelake: Intel i9-9900k 1386 * - Coffeelake: Intel i7-9700k 1387 * 1388 * I haven't been able to reproduce the instability or DSB misses on any 1389 * of the following CPUS: 1390 * - Haswell 1391 * - Broadwell: Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GH 1392 * - Skylake 1393 * 1394 * Alignment is done for each of the three major decompression loops: 1395 * - ZSTD_decompressSequences_bodySplitLitBuffer - presplit section of the literal buffer 1396 * - ZSTD_decompressSequences_bodySplitLitBuffer - postsplit section of the literal buffer 1397 * - ZSTD_decompressSequences_body 1398 * Alignment choices are made to minimize large swings on bad cases and influence on performance 1399 * from changes external to this code, rather than to overoptimize on the current commit. 1400 * 1401 * If you are seeing performance stability this script can help test. 1402 * It tests on 4 commits in zstd where I saw performance change. 1403 * 1404 * https://gist.github.com/terrelln/9889fc06a423fd5ca6e99351564473f4 1405 */ 1406 #if defined(__x86_64__) 1407 __asm__(".p2align 6"); 1408 # if __GNUC__ >= 7 1409 /* good for gcc-7, gcc-9, and gcc-11 */ 1410 __asm__("nop"); 1411 __asm__(".p2align 5"); 1412 __asm__("nop"); 1413 __asm__(".p2align 4"); 1414 # if __GNUC__ == 8 || __GNUC__ == 10 1415 /* good for gcc-8 and gcc-10 */ 1416 __asm__("nop"); 1417 __asm__(".p2align 3"); 1418 # endif 1419 # endif 1420 #endif 1421 1422 /* Handle the initial state where litBuffer is currently split between dst and litExtraBuffer */ 1423 for (; litPtr + sequence.litLength <= dctx->litBufferEnd; ) { 1424 size_t const oneSeqSize = ZSTD_execSequenceSplitLitBuffer(op, oend, litPtr + sequence.litLength - WILDCOPY_OVERLENGTH, sequence, &litPtr, litBufferEnd, prefixStart, vBase, dictEnd); 1425 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1426 assert(!ZSTD_isError(oneSeqSize)); 1427 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequence, prefixStart, vBase); 1428 #endif 1429 if (UNLIKELY(ZSTD_isError(oneSeqSize))) 1430 return oneSeqSize; 1431 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize); 1432 op += oneSeqSize; 1433 if (UNLIKELY(!--nbSeq)) 1434 break; 1435 BIT_reloadDStream(&(seqState.DStream)); 1436 sequence = ZSTD_decodeSequence(&seqState, isLongOffset); 1437 } 1438 1439 /* If there are more sequences, they will need to read literals from litExtraBuffer; copy over the remainder from dst and update litPtr and litEnd */ 1440 if (nbSeq > 0) { 1441 const size_t leftoverLit = dctx->litBufferEnd - litPtr; 1442 if (leftoverLit) 1443 { 1444 RETURN_ERROR_IF(leftoverLit > (size_t)(oend - op), dstSize_tooSmall, "remaining lit must fit within dstBuffer"); 1445 ZSTD_safecopyDstBeforeSrc(op, litPtr, leftoverLit); 1446 sequence.litLength -= leftoverLit; 1447 op += leftoverLit; 1448 } 1449 litPtr = dctx->litExtraBuffer; 1450 litBufferEnd = dctx->litExtraBuffer + ZSTD_LITBUFFEREXTRASIZE; 1451 dctx->litBufferLocation = ZSTD_not_in_dst; 1452 { 1453 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litBufferEnd, prefixStart, vBase, dictEnd); 1454 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1455 assert(!ZSTD_isError(oneSeqSize)); 1456 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequence, prefixStart, vBase); 1457 #endif 1458 if (UNLIKELY(ZSTD_isError(oneSeqSize))) 1459 return oneSeqSize; 1460 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize); 1461 op += oneSeqSize; 1462 if (--nbSeq) 1463 BIT_reloadDStream(&(seqState.DStream)); 1464 } 1465 } 1466 } 1467 1468 if (nbSeq > 0) /* there is remaining lit from extra buffer */ 1469 { 1470 1471 #if defined(__x86_64__) 1472 __asm__(".p2align 6"); 1473 __asm__("nop"); 1474 # if __GNUC__ != 7 1475 /* worse for gcc-7 better for gcc-8, gcc-9, and gcc-10 and clang */ 1476 __asm__(".p2align 4"); 1477 __asm__("nop"); 1478 __asm__(".p2align 3"); 1479 # elif __GNUC__ >= 11 1480 __asm__(".p2align 3"); 1481 # else 1482 __asm__(".p2align 5"); 1483 __asm__("nop"); 1484 __asm__(".p2align 3"); 1485 # endif 1486 #endif 1487 1488 for (; ; ) { 1489 seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset); 1490 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litBufferEnd, prefixStart, vBase, dictEnd); 1491 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1492 assert(!ZSTD_isError(oneSeqSize)); 1493 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequence, prefixStart, vBase); 1494 #endif 1495 if (UNLIKELY(ZSTD_isError(oneSeqSize))) 1496 return oneSeqSize; 1497 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize); 1498 op += oneSeqSize; 1499 if (UNLIKELY(!--nbSeq)) 1500 break; 1501 BIT_reloadDStream(&(seqState.DStream)); 1502 } 1503 } 1504 1505 /* check if reached exact end */ 1506 DEBUGLOG(5, "ZSTD_decompressSequences_bodySplitLitBuffer: after decode loop, remaining nbSeq : %i", nbSeq); 1507 RETURN_ERROR_IF(nbSeq, corruption_detected, ""); 1508 RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected, ""); 1509 /* save reps for next block */ 1510 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); } 1511 } 1512 1513 /* last literal segment */ 1514 if (dctx->litBufferLocation == ZSTD_split) /* split hasn't been reached yet, first get dst then copy litExtraBuffer */ 1515 { 1516 size_t const lastLLSize = litBufferEnd - litPtr; 1517 RETURN_ERROR_IF(lastLLSize > (size_t)(oend - op), dstSize_tooSmall, ""); 1518 if (op != NULL) { 1519 ZSTD_memmove(op, litPtr, lastLLSize); 1520 op += lastLLSize; 1521 } 1522 litPtr = dctx->litExtraBuffer; 1523 litBufferEnd = dctx->litExtraBuffer + ZSTD_LITBUFFEREXTRASIZE; 1524 dctx->litBufferLocation = ZSTD_not_in_dst; 1525 } 1526 { size_t const lastLLSize = litBufferEnd - litPtr; 1527 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, ""); 1528 if (op != NULL) { 1529 ZSTD_memcpy(op, litPtr, lastLLSize); 1530 op += lastLLSize; 1531 } 1532 } 1533 1534 return op-ostart; 1535 } 1536 1537 FORCE_INLINE_TEMPLATE size_t 1538 DONT_VECTORIZE 1539 ZSTD_decompressSequences_body(ZSTD_DCtx* dctx, 1540 void* dst, size_t maxDstSize, 1541 const void* seqStart, size_t seqSize, int nbSeq, 1542 const ZSTD_longOffset_e isLongOffset, 1543 const int frame) 1544 { 1545 const BYTE* ip = (const BYTE*)seqStart; 1546 const BYTE* const iend = ip + seqSize; 1547 BYTE* const ostart = (BYTE*)dst; 1548 BYTE* const oend = dctx->litBufferLocation == ZSTD_not_in_dst ? ostart + maxDstSize : dctx->litBuffer; 1549 BYTE* op = ostart; 1550 const BYTE* litPtr = dctx->litPtr; 1551 const BYTE* const litEnd = litPtr + dctx->litSize; 1552 const BYTE* const prefixStart = (const BYTE*)(dctx->prefixStart); 1553 const BYTE* const vBase = (const BYTE*)(dctx->virtualStart); 1554 const BYTE* const dictEnd = (const BYTE*)(dctx->dictEnd); 1555 DEBUGLOG(5, "ZSTD_decompressSequences_body"); 1556 (void)frame; 1557 1558 /* Regen sequences */ 1559 if (nbSeq) { 1560 seqState_t seqState; 1561 dctx->fseEntropy = 1; 1562 { U32 i; for (i = 0; i < ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; } 1563 RETURN_ERROR_IF( 1564 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend - ip)), 1565 corruption_detected, ""); 1566 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr); 1567 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr); 1568 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr); 1569 assert(dst != NULL); 1570 1571 ZSTD_STATIC_ASSERT( 1572 BIT_DStream_unfinished < BIT_DStream_completed && 1573 BIT_DStream_endOfBuffer < BIT_DStream_completed && 1574 BIT_DStream_completed < BIT_DStream_overflow); 1575 1576 #if defined(__x86_64__) 1577 __asm__(".p2align 6"); 1578 __asm__("nop"); 1579 # if __GNUC__ >= 7 1580 __asm__(".p2align 5"); 1581 __asm__("nop"); 1582 __asm__(".p2align 3"); 1583 # else 1584 __asm__(".p2align 4"); 1585 __asm__("nop"); 1586 __asm__(".p2align 3"); 1587 # endif 1588 #endif 1589 1590 for ( ; ; ) { 1591 seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset); 1592 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd); 1593 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1594 assert(!ZSTD_isError(oneSeqSize)); 1595 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequence, prefixStart, vBase); 1596 #endif 1597 if (UNLIKELY(ZSTD_isError(oneSeqSize))) 1598 return oneSeqSize; 1599 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize); 1600 op += oneSeqSize; 1601 if (UNLIKELY(!--nbSeq)) 1602 break; 1603 BIT_reloadDStream(&(seqState.DStream)); 1604 } 1605 1606 /* check if reached exact end */ 1607 DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq); 1608 RETURN_ERROR_IF(nbSeq, corruption_detected, ""); 1609 RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected, ""); 1610 /* save reps for next block */ 1611 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); } 1612 } 1613 1614 /* last literal segment */ 1615 { size_t const lastLLSize = litEnd - litPtr; 1616 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, ""); 1617 if (op != NULL) { 1618 ZSTD_memcpy(op, litPtr, lastLLSize); 1619 op += lastLLSize; 1620 } 1621 } 1622 1623 return op-ostart; 1624 } 1625 1626 static size_t 1627 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx, 1628 void* dst, size_t maxDstSize, 1629 const void* seqStart, size_t seqSize, int nbSeq, 1630 const ZSTD_longOffset_e isLongOffset, 1631 const int frame) 1632 { 1633 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1634 } 1635 1636 static size_t 1637 ZSTD_decompressSequencesSplitLitBuffer_default(ZSTD_DCtx* dctx, 1638 void* dst, size_t maxDstSize, 1639 const void* seqStart, size_t seqSize, int nbSeq, 1640 const ZSTD_longOffset_e isLongOffset, 1641 const int frame) 1642 { 1643 return ZSTD_decompressSequences_bodySplitLitBuffer(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1644 } 1645 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */ 1646 1647 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 1648 1649 FORCE_INLINE_TEMPLATE size_t 1650 ZSTD_prefetchMatch(size_t prefetchPos, seq_t const sequence, 1651 const BYTE* const prefixStart, const BYTE* const dictEnd) 1652 { 1653 prefetchPos += sequence.litLength; 1654 { const BYTE* const matchBase = (sequence.offset > prefetchPos) ? dictEnd : prefixStart; 1655 const BYTE* const match = matchBase + prefetchPos - sequence.offset; /* note : this operation can overflow when seq.offset is really too large, which can only happen when input is corrupted. 1656 * No consequence though : memory address is only used for prefetching, not for dereferencing */ 1657 PREFETCH_L1(match); PREFETCH_L1(match+CACHELINE_SIZE); /* note : it's safe to invoke PREFETCH() on any memory address, including invalid ones */ 1658 } 1659 return prefetchPos + sequence.matchLength; 1660 } 1661 1662 /* This decoding function employs prefetching 1663 * to reduce latency impact of cache misses. 1664 * It's generally employed when block contains a significant portion of long-distance matches 1665 * or when coupled with a "cold" dictionary */ 1666 FORCE_INLINE_TEMPLATE size_t 1667 ZSTD_decompressSequencesLong_body( 1668 ZSTD_DCtx* dctx, 1669 void* dst, size_t maxDstSize, 1670 const void* seqStart, size_t seqSize, int nbSeq, 1671 const ZSTD_longOffset_e isLongOffset, 1672 const int frame) 1673 { 1674 const BYTE* ip = (const BYTE*)seqStart; 1675 const BYTE* const iend = ip + seqSize; 1676 BYTE* const ostart = (BYTE*)dst; 1677 BYTE* const oend = dctx->litBufferLocation == ZSTD_in_dst ? dctx->litBuffer : ostart + maxDstSize; 1678 BYTE* op = ostart; 1679 const BYTE* litPtr = dctx->litPtr; 1680 const BYTE* litBufferEnd = dctx->litBufferEnd; 1681 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart); 1682 const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart); 1683 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd); 1684 (void)frame; 1685 1686 /* Regen sequences */ 1687 if (nbSeq) { 1688 #define STORED_SEQS 8 1689 #define STORED_SEQS_MASK (STORED_SEQS-1) 1690 #define ADVANCED_SEQS STORED_SEQS 1691 seq_t sequences[STORED_SEQS]; 1692 int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS); 1693 seqState_t seqState; 1694 int seqNb; 1695 size_t prefetchPos = (size_t)(op-prefixStart); /* track position relative to prefixStart */ 1696 1697 dctx->fseEntropy = 1; 1698 { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; } 1699 assert(dst != NULL); 1700 assert(iend >= ip); 1701 RETURN_ERROR_IF( 1702 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)), 1703 corruption_detected, ""); 1704 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr); 1705 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr); 1706 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr); 1707 1708 /* prepare in advance */ 1709 for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) { 1710 seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset); 1711 prefetchPos = ZSTD_prefetchMatch(prefetchPos, sequence, prefixStart, dictEnd); 1712 sequences[seqNb] = sequence; 1713 } 1714 RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected, ""); 1715 1716 /* decompress without stomping litBuffer */ 1717 for (; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb < nbSeq); seqNb++) { 1718 seq_t sequence = ZSTD_decodeSequence(&seqState, isLongOffset); 1719 size_t oneSeqSize; 1720 1721 if (dctx->litBufferLocation == ZSTD_split && litPtr + sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK].litLength > dctx->litBufferEnd) 1722 { 1723 /* lit buffer is reaching split point, empty out the first buffer and transition to litExtraBuffer */ 1724 const size_t leftoverLit = dctx->litBufferEnd - litPtr; 1725 if (leftoverLit) 1726 { 1727 RETURN_ERROR_IF(leftoverLit > (size_t)(oend - op), dstSize_tooSmall, "remaining lit must fit within dstBuffer"); 1728 ZSTD_safecopyDstBeforeSrc(op, litPtr, leftoverLit); 1729 sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK].litLength -= leftoverLit; 1730 op += leftoverLit; 1731 } 1732 litPtr = dctx->litExtraBuffer; 1733 litBufferEnd = dctx->litExtraBuffer + ZSTD_LITBUFFEREXTRASIZE; 1734 dctx->litBufferLocation = ZSTD_not_in_dst; 1735 oneSeqSize = ZSTD_execSequence(op, oend, sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litBufferEnd, prefixStart, dictStart, dictEnd); 1736 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1737 assert(!ZSTD_isError(oneSeqSize)); 1738 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK], prefixStart, dictStart); 1739 #endif 1740 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 1741 1742 prefetchPos = ZSTD_prefetchMatch(prefetchPos, sequence, prefixStart, dictEnd); 1743 sequences[seqNb & STORED_SEQS_MASK] = sequence; 1744 op += oneSeqSize; 1745 } 1746 else 1747 { 1748 /* lit buffer is either wholly contained in first or second split, or not split at all*/ 1749 oneSeqSize = dctx->litBufferLocation == ZSTD_split ? 1750 ZSTD_execSequenceSplitLitBuffer(op, oend, litPtr + sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK].litLength - WILDCOPY_OVERLENGTH, sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litBufferEnd, prefixStart, dictStart, dictEnd) : 1751 ZSTD_execSequence(op, oend, sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litBufferEnd, prefixStart, dictStart, dictEnd); 1752 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1753 assert(!ZSTD_isError(oneSeqSize)); 1754 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[(seqNb - ADVANCED_SEQS) & STORED_SEQS_MASK], prefixStart, dictStart); 1755 #endif 1756 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 1757 1758 prefetchPos = ZSTD_prefetchMatch(prefetchPos, sequence, prefixStart, dictEnd); 1759 sequences[seqNb & STORED_SEQS_MASK] = sequence; 1760 op += oneSeqSize; 1761 } 1762 } 1763 RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected, ""); 1764 1765 /* finish queue */ 1766 seqNb -= seqAdvance; 1767 for ( ; seqNb<nbSeq ; seqNb++) { 1768 seq_t *sequence = &(sequences[seqNb&STORED_SEQS_MASK]); 1769 if (dctx->litBufferLocation == ZSTD_split && litPtr + sequence->litLength > dctx->litBufferEnd) 1770 { 1771 const size_t leftoverLit = dctx->litBufferEnd - litPtr; 1772 if (leftoverLit) 1773 { 1774 RETURN_ERROR_IF(leftoverLit > (size_t)(oend - op), dstSize_tooSmall, "remaining lit must fit within dstBuffer"); 1775 ZSTD_safecopyDstBeforeSrc(op, litPtr, leftoverLit); 1776 sequence->litLength -= leftoverLit; 1777 op += leftoverLit; 1778 } 1779 litPtr = dctx->litExtraBuffer; 1780 litBufferEnd = dctx->litExtraBuffer + ZSTD_LITBUFFEREXTRASIZE; 1781 dctx->litBufferLocation = ZSTD_not_in_dst; 1782 { 1783 size_t const oneSeqSize = ZSTD_execSequence(op, oend, *sequence, &litPtr, litBufferEnd, prefixStart, dictStart, dictEnd); 1784 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1785 assert(!ZSTD_isError(oneSeqSize)); 1786 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[seqNb&STORED_SEQS_MASK], prefixStart, dictStart); 1787 #endif 1788 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 1789 op += oneSeqSize; 1790 } 1791 } 1792 else 1793 { 1794 size_t const oneSeqSize = dctx->litBufferLocation == ZSTD_split ? 1795 ZSTD_execSequenceSplitLitBuffer(op, oend, litPtr + sequence->litLength - WILDCOPY_OVERLENGTH, *sequence, &litPtr, litBufferEnd, prefixStart, dictStart, dictEnd) : 1796 ZSTD_execSequence(op, oend, *sequence, &litPtr, litBufferEnd, prefixStart, dictStart, dictEnd); 1797 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE) 1798 assert(!ZSTD_isError(oneSeqSize)); 1799 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[seqNb&STORED_SEQS_MASK], prefixStart, dictStart); 1800 #endif 1801 if (ZSTD_isError(oneSeqSize)) return oneSeqSize; 1802 op += oneSeqSize; 1803 } 1804 } 1805 1806 /* save reps for next block */ 1807 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); } 1808 } 1809 1810 /* last literal segment */ 1811 if (dctx->litBufferLocation == ZSTD_split) /* first deplete literal buffer in dst, then copy litExtraBuffer */ 1812 { 1813 size_t const lastLLSize = litBufferEnd - litPtr; 1814 RETURN_ERROR_IF(lastLLSize > (size_t)(oend - op), dstSize_tooSmall, ""); 1815 if (op != NULL) { 1816 ZSTD_memmove(op, litPtr, lastLLSize); 1817 op += lastLLSize; 1818 } 1819 litPtr = dctx->litExtraBuffer; 1820 litBufferEnd = dctx->litExtraBuffer + ZSTD_LITBUFFEREXTRASIZE; 1821 } 1822 { size_t const lastLLSize = litBufferEnd - litPtr; 1823 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, ""); 1824 if (op != NULL) { 1825 ZSTD_memmove(op, litPtr, lastLLSize); 1826 op += lastLLSize; 1827 } 1828 } 1829 1830 return op-ostart; 1831 } 1832 1833 static size_t 1834 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx, 1835 void* dst, size_t maxDstSize, 1836 const void* seqStart, size_t seqSize, int nbSeq, 1837 const ZSTD_longOffset_e isLongOffset, 1838 const int frame) 1839 { 1840 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1841 } 1842 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */ 1843 1844 1845 1846 #if DYNAMIC_BMI2 1847 1848 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 1849 static BMI2_TARGET_ATTRIBUTE size_t 1850 DONT_VECTORIZE 1851 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx, 1852 void* dst, size_t maxDstSize, 1853 const void* seqStart, size_t seqSize, int nbSeq, 1854 const ZSTD_longOffset_e isLongOffset, 1855 const int frame) 1856 { 1857 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1858 } 1859 static BMI2_TARGET_ATTRIBUTE size_t 1860 DONT_VECTORIZE 1861 ZSTD_decompressSequencesSplitLitBuffer_bmi2(ZSTD_DCtx* dctx, 1862 void* dst, size_t maxDstSize, 1863 const void* seqStart, size_t seqSize, int nbSeq, 1864 const ZSTD_longOffset_e isLongOffset, 1865 const int frame) 1866 { 1867 return ZSTD_decompressSequences_bodySplitLitBuffer(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1868 } 1869 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */ 1870 1871 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 1872 static BMI2_TARGET_ATTRIBUTE size_t 1873 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx, 1874 void* dst, size_t maxDstSize, 1875 const void* seqStart, size_t seqSize, int nbSeq, 1876 const ZSTD_longOffset_e isLongOffset, 1877 const int frame) 1878 { 1879 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1880 } 1881 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */ 1882 1883 #endif /* DYNAMIC_BMI2 */ 1884 1885 typedef size_t (*ZSTD_decompressSequences_t)( 1886 ZSTD_DCtx* dctx, 1887 void* dst, size_t maxDstSize, 1888 const void* seqStart, size_t seqSize, int nbSeq, 1889 const ZSTD_longOffset_e isLongOffset, 1890 const int frame); 1891 1892 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 1893 static size_t 1894 ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, 1895 const void* seqStart, size_t seqSize, int nbSeq, 1896 const ZSTD_longOffset_e isLongOffset, 1897 const int frame) 1898 { 1899 DEBUGLOG(5, "ZSTD_decompressSequences"); 1900 #if DYNAMIC_BMI2 1901 if (ZSTD_DCtx_get_bmi2(dctx)) { 1902 return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1903 } 1904 #endif 1905 return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1906 } 1907 static size_t 1908 ZSTD_decompressSequencesSplitLitBuffer(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize, 1909 const void* seqStart, size_t seqSize, int nbSeq, 1910 const ZSTD_longOffset_e isLongOffset, 1911 const int frame) 1912 { 1913 DEBUGLOG(5, "ZSTD_decompressSequencesSplitLitBuffer"); 1914 #if DYNAMIC_BMI2 1915 if (ZSTD_DCtx_get_bmi2(dctx)) { 1916 return ZSTD_decompressSequencesSplitLitBuffer_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1917 } 1918 #endif 1919 return ZSTD_decompressSequencesSplitLitBuffer_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1920 } 1921 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */ 1922 1923 1924 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 1925 /* ZSTD_decompressSequencesLong() : 1926 * decompression function triggered when a minimum share of offsets is considered "long", 1927 * aka out of cache. 1928 * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance". 1929 * This function will try to mitigate main memory latency through the use of prefetching */ 1930 static size_t 1931 ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx, 1932 void* dst, size_t maxDstSize, 1933 const void* seqStart, size_t seqSize, int nbSeq, 1934 const ZSTD_longOffset_e isLongOffset, 1935 const int frame) 1936 { 1937 DEBUGLOG(5, "ZSTD_decompressSequencesLong"); 1938 #if DYNAMIC_BMI2 1939 if (ZSTD_DCtx_get_bmi2(dctx)) { 1940 return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1941 } 1942 #endif 1943 return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame); 1944 } 1945 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */ 1946 1947 1948 1949 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 1950 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 1951 /* ZSTD_getLongOffsetsShare() : 1952 * condition : offTable must be valid 1953 * @return : "share" of long offsets (arbitrarily defined as > (1<<23)) 1954 * compared to maximum possible of (1<<OffFSELog) */ 1955 static unsigned 1956 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable) 1957 { 1958 const void* ptr = offTable; 1959 U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog; 1960 const ZSTD_seqSymbol* table = offTable + 1; 1961 U32 const max = 1 << tableLog; 1962 U32 u, total = 0; 1963 DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog); 1964 1965 assert(max <= (1 << OffFSELog)); /* max not too large */ 1966 for (u=0; u<max; u++) { 1967 if (table[u].nbAdditionalBits > 22) total += 1; 1968 } 1969 1970 assert(tableLog <= OffFSELog); 1971 total <<= (OffFSELog - tableLog); /* scale to OffFSELog */ 1972 1973 return total; 1974 } 1975 #endif 1976 1977 size_t 1978 ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx, 1979 void* dst, size_t dstCapacity, 1980 const void* src, size_t srcSize, const int frame, const streaming_operation streaming) 1981 { /* blockType == blockCompressed */ 1982 const BYTE* ip = (const BYTE*)src; 1983 /* isLongOffset must be true if there are long offsets. 1984 * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN. 1985 * We don't expect that to be the case in 64-bit mode. 1986 * In block mode, window size is not known, so we have to be conservative. 1987 * (note: but it could be evaluated from current-lowLimit) 1988 */ 1989 ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN)))); 1990 DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize); 1991 1992 RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong, ""); 1993 1994 /* Decode literals section */ 1995 { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize, dst, dstCapacity, streaming); 1996 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize); 1997 if (ZSTD_isError(litCSize)) return litCSize; 1998 ip += litCSize; 1999 srcSize -= litCSize; 2000 } 2001 2002 /* Build Decoding Tables */ 2003 { 2004 /* These macros control at build-time which decompressor implementation 2005 * we use. If neither is defined, we do some inspection and dispatch at 2006 * runtime. 2007 */ 2008 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 2009 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 2010 int usePrefetchDecoder = dctx->ddictIsCold; 2011 #endif 2012 int nbSeq; 2013 size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize); 2014 if (ZSTD_isError(seqHSize)) return seqHSize; 2015 ip += seqHSize; 2016 srcSize -= seqHSize; 2017 2018 RETURN_ERROR_IF(dst == NULL && nbSeq > 0, dstSize_tooSmall, "NULL not handled"); 2019 2020 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 2021 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 2022 if ( !usePrefetchDecoder 2023 && (!frame || (dctx->fParams.windowSize > (1<<24))) 2024 && (nbSeq>ADVANCED_SEQS) ) { /* could probably use a larger nbSeq limit */ 2025 U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr); 2026 U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */ 2027 usePrefetchDecoder = (shareLongOffsets >= minShare); 2028 } 2029 #endif 2030 2031 dctx->ddictIsCold = 0; 2032 2033 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \ 2034 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG) 2035 if (usePrefetchDecoder) 2036 #endif 2037 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT 2038 return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame); 2039 #endif 2040 2041 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG 2042 /* else */ 2043 if (dctx->litBufferLocation == ZSTD_split) 2044 return ZSTD_decompressSequencesSplitLitBuffer(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame); 2045 else 2046 return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame); 2047 #endif 2048 } 2049 } 2050 2051 2052 void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize) 2053 { 2054 if (dst != dctx->previousDstEnd && dstSize > 0) { /* not contiguous */ 2055 dctx->dictEnd = dctx->previousDstEnd; 2056 dctx->virtualStart = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart)); 2057 dctx->prefixStart = dst; 2058 dctx->previousDstEnd = dst; 2059 } 2060 } 2061 2062 2063 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx, 2064 void* dst, size_t dstCapacity, 2065 const void* src, size_t srcSize) 2066 { 2067 size_t dSize; 2068 ZSTD_checkContinuity(dctx, dst, dstCapacity); 2069 dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0, not_streaming); 2070 dctx->previousDstEnd = (char*)dst + dSize; 2071 return dSize; 2072 } 2073