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