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
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 */
ZSTD_decodeLiteralsBlock(ZSTD_DCtx * dctx,const void * src,size_t srcSize)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 ZSTD_FALLTHROUGH;
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 ZSTD_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 ZSTD_memcpy(dctx->litBuffer, istart+lhSize, litSize);
195 dctx->litPtr = dctx->litBuffer;
196 dctx->litSize = litSize;
197 ZSTD_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 ZSTD_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/release/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
ZSTD_buildSeqTable_rle(ZSTD_seqSymbol * dt,U32 baseValue,U32 nbAddBits)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 FORCE_INLINE_TEMPLATE
ZSTD_buildFSETable_body(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U32 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize)368 void ZSTD_buildFSETable_body(ZSTD_seqSymbol* dt,
369 const short* normalizedCounter, unsigned maxSymbolValue,
370 const U32* baseValue, const U32* nbAdditionalBits,
371 unsigned tableLog, void* wksp, size_t wkspSize)
372 {
373 ZSTD_seqSymbol* const tableDecode = dt+1;
374 U32 const maxSV1 = maxSymbolValue + 1;
375 U32 const tableSize = 1 << tableLog;
376
377 U16* symbolNext = (U16*)wksp;
378 BYTE* spread = (BYTE*)(symbolNext + MaxSeq + 1);
379 U32 highThreshold = tableSize - 1;
380
381
382 /* Sanity Checks */
383 assert(maxSymbolValue <= MaxSeq);
384 assert(tableLog <= MaxFSELog);
385 assert(wkspSize >= ZSTD_BUILD_FSE_TABLE_WKSP_SIZE);
386 (void)wkspSize;
387 /* Init, lay down lowprob symbols */
388 { ZSTD_seqSymbol_header DTableH;
389 DTableH.tableLog = tableLog;
390 DTableH.fastMode = 1;
391 { S16 const largeLimit= (S16)(1 << (tableLog-1));
392 U32 s;
393 for (s=0; s<maxSV1; s++) {
394 if (normalizedCounter[s]==-1) {
395 tableDecode[highThreshold--].baseValue = s;
396 symbolNext[s] = 1;
397 } else {
398 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
399 assert(normalizedCounter[s]>=0);
400 symbolNext[s] = (U16)normalizedCounter[s];
401 } } }
402 ZSTD_memcpy(dt, &DTableH, sizeof(DTableH));
403 }
404
405 /* Spread symbols */
406 assert(tableSize <= 512);
407 /* Specialized symbol spreading for the case when there are
408 * no low probability (-1 count) symbols. When compressing
409 * small blocks we avoid low probability symbols to hit this
410 * case, since header decoding speed matters more.
411 */
412 if (highThreshold == tableSize - 1) {
413 size_t const tableMask = tableSize-1;
414 size_t const step = FSE_TABLESTEP(tableSize);
415 /* First lay down the symbols in order.
416 * We use a uint64_t to lay down 8 bytes at a time. This reduces branch
417 * misses since small blocks generally have small table logs, so nearly
418 * all symbols have counts <= 8. We ensure we have 8 bytes at the end of
419 * our buffer to handle the over-write.
420 */
421 {
422 U64 const add = 0x0101010101010101ull;
423 size_t pos = 0;
424 U64 sv = 0;
425 U32 s;
426 for (s=0; s<maxSV1; ++s, sv += add) {
427 int i;
428 int const n = normalizedCounter[s];
429 MEM_write64(spread + pos, sv);
430 for (i = 8; i < n; i += 8) {
431 MEM_write64(spread + pos + i, sv);
432 }
433 pos += n;
434 }
435 }
436 /* Now we spread those positions across the table.
437 * The benefit of doing it in two stages is that we avoid the the
438 * variable size inner loop, which caused lots of branch misses.
439 * Now we can run through all the positions without any branch misses.
440 * We unroll the loop twice, since that is what emperically worked best.
441 */
442 {
443 size_t position = 0;
444 size_t s;
445 size_t const unroll = 2;
446 assert(tableSize % unroll == 0); /* FSE_MIN_TABLELOG is 5 */
447 for (s = 0; s < (size_t)tableSize; s += unroll) {
448 size_t u;
449 for (u = 0; u < unroll; ++u) {
450 size_t const uPosition = (position + (u * step)) & tableMask;
451 tableDecode[uPosition].baseValue = spread[s + u];
452 }
453 position = (position + (unroll * step)) & tableMask;
454 }
455 assert(position == 0);
456 }
457 } else {
458 U32 const tableMask = tableSize-1;
459 U32 const step = FSE_TABLESTEP(tableSize);
460 U32 s, position = 0;
461 for (s=0; s<maxSV1; s++) {
462 int i;
463 int const n = normalizedCounter[s];
464 for (i=0; i<n; i++) {
465 tableDecode[position].baseValue = s;
466 position = (position + step) & tableMask;
467 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
468 } }
469 assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
470 }
471
472 /* Build Decoding table */
473 {
474 U32 u;
475 for (u=0; u<tableSize; u++) {
476 U32 const symbol = tableDecode[u].baseValue;
477 U32 const nextState = symbolNext[symbol]++;
478 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
479 tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
480 assert(nbAdditionalBits[symbol] < 255);
481 tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
482 tableDecode[u].baseValue = baseValue[symbol];
483 }
484 }
485 }
486
487 /* Avoids the FORCE_INLINE of the _body() function. */
ZSTD_buildFSETable_body_default(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U32 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize)488 static void ZSTD_buildFSETable_body_default(ZSTD_seqSymbol* dt,
489 const short* normalizedCounter, unsigned maxSymbolValue,
490 const U32* baseValue, const U32* nbAdditionalBits,
491 unsigned tableLog, void* wksp, size_t wkspSize)
492 {
493 ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue,
494 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
495 }
496
497 #if DYNAMIC_BMI2
ZSTD_buildFSETable_body_bmi2(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U32 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize)498 TARGET_ATTRIBUTE("bmi2") static void ZSTD_buildFSETable_body_bmi2(ZSTD_seqSymbol* dt,
499 const short* normalizedCounter, unsigned maxSymbolValue,
500 const U32* baseValue, const U32* nbAdditionalBits,
501 unsigned tableLog, void* wksp, size_t wkspSize)
502 {
503 ZSTD_buildFSETable_body(dt, normalizedCounter, maxSymbolValue,
504 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
505 }
506 #endif
507
ZSTD_buildFSETable(ZSTD_seqSymbol * dt,const short * normalizedCounter,unsigned maxSymbolValue,const U32 * baseValue,const U32 * nbAdditionalBits,unsigned tableLog,void * wksp,size_t wkspSize,int bmi2)508 void ZSTD_buildFSETable(ZSTD_seqSymbol* dt,
509 const short* normalizedCounter, unsigned maxSymbolValue,
510 const U32* baseValue, const U32* nbAdditionalBits,
511 unsigned tableLog, void* wksp, size_t wkspSize, int bmi2)
512 {
513 #if DYNAMIC_BMI2
514 if (bmi2) {
515 ZSTD_buildFSETable_body_bmi2(dt, normalizedCounter, maxSymbolValue,
516 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
517 return;
518 }
519 #endif
520 (void)bmi2;
521 ZSTD_buildFSETable_body_default(dt, normalizedCounter, maxSymbolValue,
522 baseValue, nbAdditionalBits, tableLog, wksp, wkspSize);
523 }
524
525
526 /*! ZSTD_buildSeqTable() :
527 * @return : nb bytes read from src,
528 * 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 U32 * nbAdditionalBits,const ZSTD_seqSymbol * defaultTable,U32 flagRepeatTable,int ddictIsCold,int nbSeq,U32 * wksp,size_t wkspSize,int bmi2)529 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
530 symbolEncodingType_e type, unsigned max, U32 maxLog,
531 const void* src, size_t srcSize,
532 const U32* baseValue, const U32* nbAdditionalBits,
533 const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
534 int ddictIsCold, int nbSeq, U32* wksp, size_t wkspSize,
535 int bmi2)
536 {
537 switch(type)
538 {
539 case set_rle :
540 RETURN_ERROR_IF(!srcSize, srcSize_wrong, "");
541 RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected, "");
542 { U32 const symbol = *(const BYTE*)src;
543 U32 const baseline = baseValue[symbol];
544 U32 const nbBits = nbAdditionalBits[symbol];
545 ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
546 }
547 *DTablePtr = DTableSpace;
548 return 1;
549 case set_basic :
550 *DTablePtr = defaultTable;
551 return 0;
552 case set_repeat:
553 RETURN_ERROR_IF(!flagRepeatTable, corruption_detected, "");
554 /* prefetch FSE table if used */
555 if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
556 const void* const pStart = *DTablePtr;
557 size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
558 PREFETCH_AREA(pStart, pSize);
559 }
560 return 0;
561 case set_compressed :
562 { unsigned tableLog;
563 S16 norm[MaxSeq+1];
564 size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
565 RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected, "");
566 RETURN_ERROR_IF(tableLog > maxLog, corruption_detected, "");
567 ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog, wksp, wkspSize, bmi2);
568 *DTablePtr = DTableSpace;
569 return headerSize;
570 }
571 default :
572 assert(0);
573 RETURN_ERROR(GENERIC, "impossible");
574 }
575 }
576
ZSTD_decodeSeqHeaders(ZSTD_DCtx * dctx,int * nbSeqPtr,const void * src,size_t srcSize)577 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
578 const void* src, size_t srcSize)
579 {
580 const BYTE* const istart = (const BYTE*)src;
581 const BYTE* const iend = istart + srcSize;
582 const BYTE* ip = istart;
583 int nbSeq;
584 DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
585
586 /* check */
587 RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong, "");
588
589 /* SeqHead */
590 nbSeq = *ip++;
591 if (!nbSeq) {
592 *nbSeqPtr=0;
593 RETURN_ERROR_IF(srcSize != 1, srcSize_wrong, "");
594 return 1;
595 }
596 if (nbSeq > 0x7F) {
597 if (nbSeq == 0xFF) {
598 RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong, "");
599 nbSeq = MEM_readLE16(ip) + LONGNBSEQ;
600 ip+=2;
601 } else {
602 RETURN_ERROR_IF(ip >= iend, srcSize_wrong, "");
603 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
604 }
605 }
606 *nbSeqPtr = nbSeq;
607
608 /* FSE table descriptors */
609 RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong, ""); /* minimum possible size: 1 byte for symbol encoding types */
610 { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
611 symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
612 symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
613 ip++;
614
615 /* Build DTables */
616 { size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
617 LLtype, MaxLL, LLFSELog,
618 ip, iend-ip,
619 LL_base, LL_bits,
620 LL_defaultDTable, dctx->fseEntropy,
621 dctx->ddictIsCold, nbSeq,
622 dctx->workspace, sizeof(dctx->workspace),
623 dctx->bmi2);
624 RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected, "ZSTD_buildSeqTable failed");
625 ip += llhSize;
626 }
627
628 { size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
629 OFtype, MaxOff, OffFSELog,
630 ip, iend-ip,
631 OF_base, OF_bits,
632 OF_defaultDTable, dctx->fseEntropy,
633 dctx->ddictIsCold, nbSeq,
634 dctx->workspace, sizeof(dctx->workspace),
635 dctx->bmi2);
636 RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected, "ZSTD_buildSeqTable failed");
637 ip += ofhSize;
638 }
639
640 { size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
641 MLtype, MaxML, MLFSELog,
642 ip, iend-ip,
643 ML_base, ML_bits,
644 ML_defaultDTable, dctx->fseEntropy,
645 dctx->ddictIsCold, nbSeq,
646 dctx->workspace, sizeof(dctx->workspace),
647 dctx->bmi2);
648 RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected, "ZSTD_buildSeqTable failed");
649 ip += mlhSize;
650 }
651 }
652
653 return ip-istart;
654 }
655
656
657 typedef struct {
658 size_t litLength;
659 size_t matchLength;
660 size_t offset;
661 const BYTE* match;
662 } seq_t;
663
664 typedef struct {
665 size_t state;
666 const ZSTD_seqSymbol* table;
667 } ZSTD_fseState;
668
669 typedef struct {
670 BIT_DStream_t DStream;
671 ZSTD_fseState stateLL;
672 ZSTD_fseState stateOffb;
673 ZSTD_fseState stateML;
674 size_t prevOffset[ZSTD_REP_NUM];
675 const BYTE* prefixStart;
676 const BYTE* dictEnd;
677 size_t pos;
678 } seqState_t;
679
680 /*! ZSTD_overlapCopy8() :
681 * Copies 8 bytes from ip to op and updates op and ip where ip <= op.
682 * If the offset is < 8 then the offset is spread to at least 8 bytes.
683 *
684 * Precondition: *ip <= *op
685 * Postcondition: *op - *op >= 8
686 */
ZSTD_overlapCopy8(BYTE ** op,BYTE const ** ip,size_t offset)687 HINT_INLINE void ZSTD_overlapCopy8(BYTE** op, BYTE const** ip, size_t offset) {
688 assert(*ip <= *op);
689 if (offset < 8) {
690 /* close range match, overlap */
691 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
692 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
693 int const sub2 = dec64table[offset];
694 (*op)[0] = (*ip)[0];
695 (*op)[1] = (*ip)[1];
696 (*op)[2] = (*ip)[2];
697 (*op)[3] = (*ip)[3];
698 *ip += dec32table[offset];
699 ZSTD_copy4(*op+4, *ip);
700 *ip -= sub2;
701 } else {
702 ZSTD_copy8(*op, *ip);
703 }
704 *ip += 8;
705 *op += 8;
706 assert(*op - *ip >= 8);
707 }
708
709 /*! ZSTD_safecopy() :
710 * Specialized version of memcpy() that is allowed to READ up to WILDCOPY_OVERLENGTH past the input buffer
711 * and write up to 16 bytes past oend_w (op >= oend_w is allowed).
712 * This function is only called in the uncommon case where the sequence is near the end of the block. It
713 * should be fast for a single long sequence, but can be slow for several short sequences.
714 *
715 * @param ovtype controls the overlap detection
716 * - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
717 * - ZSTD_overlap_src_before_dst: The src and dst may overlap and may be any distance apart.
718 * The src buffer must be before the dst buffer.
719 */
ZSTD_safecopy(BYTE * op,BYTE * const oend_w,BYTE const * ip,ptrdiff_t length,ZSTD_overlap_e ovtype)720 static void ZSTD_safecopy(BYTE* op, BYTE* const oend_w, BYTE const* ip, ptrdiff_t length, ZSTD_overlap_e ovtype) {
721 ptrdiff_t const diff = op - ip;
722 BYTE* const oend = op + length;
723
724 assert((ovtype == ZSTD_no_overlap && (diff <= -8 || diff >= 8 || op >= oend_w)) ||
725 (ovtype == ZSTD_overlap_src_before_dst && diff >= 0));
726
727 if (length < 8) {
728 /* Handle short lengths. */
729 while (op < oend) *op++ = *ip++;
730 return;
731 }
732 if (ovtype == ZSTD_overlap_src_before_dst) {
733 /* Copy 8 bytes and ensure the offset >= 8 when there can be overlap. */
734 assert(length >= 8);
735 ZSTD_overlapCopy8(&op, &ip, diff);
736 assert(op - ip >= 8);
737 assert(op <= oend);
738 }
739
740 if (oend <= oend_w) {
741 /* No risk of overwrite. */
742 ZSTD_wildcopy(op, ip, length, ovtype);
743 return;
744 }
745 if (op <= oend_w) {
746 /* Wildcopy until we get close to the end. */
747 assert(oend > oend_w);
748 ZSTD_wildcopy(op, ip, oend_w - op, ovtype);
749 ip += oend_w - op;
750 op = oend_w;
751 }
752 /* Handle the leftovers. */
753 while (op < oend) *op++ = *ip++;
754 }
755
756 /* ZSTD_execSequenceEnd():
757 * This version handles cases that are near the end of the output buffer. It requires
758 * more careful checks to make sure there is no overflow. By separating out these hard
759 * and unlikely cases, we can speed up the common cases.
760 *
761 * NOTE: This function needs to be fast for a single long sequence, but doesn't need
762 * to be optimized for many small sequences, since those fall into ZSTD_execSequence().
763 */
764 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)765 size_t ZSTD_execSequenceEnd(BYTE* op,
766 BYTE* const oend, seq_t sequence,
767 const BYTE** litPtr, const BYTE* const litLimit,
768 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
769 {
770 BYTE* const oLitEnd = op + sequence.litLength;
771 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
772 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
773 const BYTE* match = oLitEnd - sequence.offset;
774 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
775
776 /* bounds checks : careful of address space overflow in 32-bit mode */
777 RETURN_ERROR_IF(sequenceLength > (size_t)(oend - op), dstSize_tooSmall, "last match must fit within dstBuffer");
778 RETURN_ERROR_IF(sequence.litLength > (size_t)(litLimit - *litPtr), corruption_detected, "try to read beyond literal buffer");
779 assert(op < op + sequenceLength);
780 assert(oLitEnd < op + sequenceLength);
781
782 /* copy literals */
783 ZSTD_safecopy(op, oend_w, *litPtr, sequence.litLength, ZSTD_no_overlap);
784 op = oLitEnd;
785 *litPtr = iLitEnd;
786
787 /* copy Match */
788 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
789 /* offset beyond prefix */
790 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected, "");
791 match = dictEnd - (prefixStart-match);
792 if (match + sequence.matchLength <= dictEnd) {
793 ZSTD_memmove(oLitEnd, match, sequence.matchLength);
794 return sequenceLength;
795 }
796 /* span extDict & currentPrefixSegment */
797 { size_t const length1 = dictEnd - match;
798 ZSTD_memmove(oLitEnd, match, length1);
799 op = oLitEnd + length1;
800 sequence.matchLength -= length1;
801 match = prefixStart;
802 } }
803 ZSTD_safecopy(op, oend_w, match, sequence.matchLength, ZSTD_overlap_src_before_dst);
804 return sequenceLength;
805 }
806
807 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)808 size_t ZSTD_execSequence(BYTE* op,
809 BYTE* const oend, seq_t sequence,
810 const BYTE** litPtr, const BYTE* const litLimit,
811 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
812 {
813 BYTE* const oLitEnd = op + sequence.litLength;
814 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
815 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
816 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH; /* risk : address space underflow on oend=NULL */
817 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
818 const BYTE* match = oLitEnd - sequence.offset;
819
820 assert(op != NULL /* Precondition */);
821 assert(oend_w < oend /* No underflow */);
822 /* Handle edge cases in a slow path:
823 * - Read beyond end of literals
824 * - Match end is within WILDCOPY_OVERLIMIT of oend
825 * - 32-bit mode and the match length overflows
826 */
827 if (UNLIKELY(
828 iLitEnd > litLimit ||
829 oMatchEnd > oend_w ||
830 (MEM_32bits() && (size_t)(oend - op) < sequenceLength + WILDCOPY_OVERLENGTH)))
831 return ZSTD_execSequenceEnd(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
832
833 /* Assumptions (everything else goes into ZSTD_execSequenceEnd()) */
834 assert(op <= oLitEnd /* No overflow */);
835 assert(oLitEnd < oMatchEnd /* Non-zero match & no overflow */);
836 assert(oMatchEnd <= oend /* No underflow */);
837 assert(iLitEnd <= litLimit /* Literal length is in bounds */);
838 assert(oLitEnd <= oend_w /* Can wildcopy literals */);
839 assert(oMatchEnd <= oend_w /* Can wildcopy matches */);
840
841 /* Copy Literals:
842 * Split out litLength <= 16 since it is nearly always true. +1.6% on gcc-9.
843 * We likely don't need the full 32-byte wildcopy.
844 */
845 assert(WILDCOPY_OVERLENGTH >= 16);
846 ZSTD_copy16(op, (*litPtr));
847 if (UNLIKELY(sequence.litLength > 16)) {
848 ZSTD_wildcopy(op+16, (*litPtr)+16, sequence.litLength-16, ZSTD_no_overlap);
849 }
850 op = oLitEnd;
851 *litPtr = iLitEnd; /* update for next sequence */
852
853 /* Copy Match */
854 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
855 /* offset beyond prefix -> go into extDict */
856 RETURN_ERROR_IF(UNLIKELY(sequence.offset > (size_t)(oLitEnd - virtualStart)), corruption_detected, "");
857 match = dictEnd + (match - prefixStart);
858 if (match + sequence.matchLength <= dictEnd) {
859 ZSTD_memmove(oLitEnd, match, sequence.matchLength);
860 return sequenceLength;
861 }
862 /* span extDict & currentPrefixSegment */
863 { size_t const length1 = dictEnd - match;
864 ZSTD_memmove(oLitEnd, match, length1);
865 op = oLitEnd + length1;
866 sequence.matchLength -= length1;
867 match = prefixStart;
868 } }
869 /* Match within prefix of 1 or more bytes */
870 assert(op <= oMatchEnd);
871 assert(oMatchEnd <= oend_w);
872 assert(match >= prefixStart);
873 assert(sequence.matchLength >= 1);
874
875 /* Nearly all offsets are >= WILDCOPY_VECLEN bytes, which means we can use wildcopy
876 * without overlap checking.
877 */
878 if (LIKELY(sequence.offset >= WILDCOPY_VECLEN)) {
879 /* We bet on a full wildcopy for matches, since we expect matches to be
880 * longer than literals (in general). In silesia, ~10% of matches are longer
881 * than 16 bytes.
882 */
883 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength, ZSTD_no_overlap);
884 return sequenceLength;
885 }
886 assert(sequence.offset < WILDCOPY_VECLEN);
887
888 /* Copy 8 bytes and spread the offset to be >= 8. */
889 ZSTD_overlapCopy8(&op, &match, sequence.offset);
890
891 /* If the match length is > 8 bytes, then continue with the wildcopy. */
892 if (sequence.matchLength > 8) {
893 assert(op < oMatchEnd);
894 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst);
895 }
896 return sequenceLength;
897 }
898
899 static void
ZSTD_initFseState(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD,const ZSTD_seqSymbol * dt)900 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt)
901 {
902 const void* ptr = dt;
903 const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
904 DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
905 DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
906 (U32)DStatePtr->state, DTableH->tableLog);
907 BIT_reloadDStream(bitD);
908 DStatePtr->table = dt + 1;
909 }
910
911 FORCE_INLINE_TEMPLATE void
ZSTD_updateFseState(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD)912 ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD)
913 {
914 ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
915 U32 const nbBits = DInfo.nbBits;
916 size_t const lowBits = BIT_readBits(bitD, nbBits);
917 DStatePtr->state = DInfo.nextState + lowBits;
918 }
919
920 FORCE_INLINE_TEMPLATE void
ZSTD_updateFseStateWithDInfo(ZSTD_fseState * DStatePtr,BIT_DStream_t * bitD,ZSTD_seqSymbol const DInfo)921 ZSTD_updateFseStateWithDInfo(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, ZSTD_seqSymbol const DInfo)
922 {
923 U32 const nbBits = DInfo.nbBits;
924 size_t const lowBits = BIT_readBits(bitD, nbBits);
925 DStatePtr->state = DInfo.nextState + lowBits;
926 }
927
928 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
929 * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
930 * bits before reloading. This value is the maximum number of bytes we read
931 * after reloading when we are decoding long offsets.
932 */
933 #define LONG_OFFSETS_MAX_EXTRA_BITS_32 \
934 (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32 \
935 ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32 \
936 : 0)
937
938 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e;
939 typedef enum { ZSTD_p_noPrefetch=0, ZSTD_p_prefetch=1 } ZSTD_prefetch_e;
940
941 FORCE_INLINE_TEMPLATE seq_t
ZSTD_decodeSequence(seqState_t * seqState,const ZSTD_longOffset_e longOffsets,const ZSTD_prefetch_e prefetch)942 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets, const ZSTD_prefetch_e prefetch)
943 {
944 seq_t seq;
945 ZSTD_seqSymbol const llDInfo = seqState->stateLL.table[seqState->stateLL.state];
946 ZSTD_seqSymbol const mlDInfo = seqState->stateML.table[seqState->stateML.state];
947 ZSTD_seqSymbol const ofDInfo = seqState->stateOffb.table[seqState->stateOffb.state];
948 U32 const llBase = llDInfo.baseValue;
949 U32 const mlBase = mlDInfo.baseValue;
950 U32 const ofBase = ofDInfo.baseValue;
951 BYTE const llBits = llDInfo.nbAdditionalBits;
952 BYTE const mlBits = mlDInfo.nbAdditionalBits;
953 BYTE const ofBits = ofDInfo.nbAdditionalBits;
954 BYTE const totalBits = llBits+mlBits+ofBits;
955
956 /* sequence */
957 { size_t offset;
958 if (ofBits > 1) {
959 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
960 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
961 assert(ofBits <= MaxOff);
962 if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
963 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
964 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
965 BIT_reloadDStream(&seqState->DStream);
966 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
967 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32); /* to avoid another reload */
968 } else {
969 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
970 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
971 }
972 seqState->prevOffset[2] = seqState->prevOffset[1];
973 seqState->prevOffset[1] = seqState->prevOffset[0];
974 seqState->prevOffset[0] = offset;
975 } else {
976 U32 const ll0 = (llBase == 0);
977 if (LIKELY((ofBits == 0))) {
978 if (LIKELY(!ll0))
979 offset = seqState->prevOffset[0];
980 else {
981 offset = seqState->prevOffset[1];
982 seqState->prevOffset[1] = seqState->prevOffset[0];
983 seqState->prevOffset[0] = offset;
984 }
985 } else {
986 offset = ofBase + ll0 + BIT_readBitsFast(&seqState->DStream, 1);
987 { size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
988 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
989 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
990 seqState->prevOffset[1] = seqState->prevOffset[0];
991 seqState->prevOffset[0] = offset = temp;
992 } } }
993 seq.offset = offset;
994 }
995
996 seq.matchLength = mlBase;
997 if (mlBits > 0)
998 seq.matchLength += BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/);
999
1000 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
1001 BIT_reloadDStream(&seqState->DStream);
1002 if (MEM_64bits() && UNLIKELY(totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
1003 BIT_reloadDStream(&seqState->DStream);
1004 /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
1005 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
1006
1007 seq.litLength = llBase;
1008 if (llBits > 0)
1009 seq.litLength += BIT_readBitsFast(&seqState->DStream, llBits/*>0*/);
1010
1011 if (MEM_32bits())
1012 BIT_reloadDStream(&seqState->DStream);
1013
1014 DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
1015 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
1016
1017 if (prefetch == ZSTD_p_prefetch) {
1018 size_t const pos = seqState->pos + seq.litLength;
1019 const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
1020 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.
1021 * No consequence though : no memory access will occur, offset is only used for prefetching */
1022 seqState->pos = pos + seq.matchLength;
1023 }
1024
1025 /* ANS state update
1026 * gcc-9.0.0 does 2.5% worse with ZSTD_updateFseStateWithDInfo().
1027 * clang-9.2.0 does 7% worse with ZSTD_updateFseState().
1028 * Naturally it seems like ZSTD_updateFseStateWithDInfo() should be the
1029 * better option, so it is the default for other compilers. But, if you
1030 * measure that it is worse, please put up a pull request.
1031 */
1032 {
1033 #if !defined(__clang__)
1034 const int kUseUpdateFseState = 1;
1035 #else
1036 const int kUseUpdateFseState = 0;
1037 #endif
1038 if (kUseUpdateFseState) {
1039 ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
1040 ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
1041 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
1042 ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
1043 } else {
1044 ZSTD_updateFseStateWithDInfo(&seqState->stateLL, &seqState->DStream, llDInfo); /* <= 9 bits */
1045 ZSTD_updateFseStateWithDInfo(&seqState->stateML, &seqState->DStream, mlDInfo); /* <= 9 bits */
1046 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
1047 ZSTD_updateFseStateWithDInfo(&seqState->stateOffb, &seqState->DStream, ofDInfo); /* <= 8 bits */
1048 }
1049 }
1050
1051 return seq;
1052 }
1053
1054 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
ZSTD_dictionaryIsActive(ZSTD_DCtx const * dctx,BYTE const * prefixStart,BYTE const * oLitEnd)1055 MEM_STATIC int ZSTD_dictionaryIsActive(ZSTD_DCtx const* dctx, BYTE const* prefixStart, BYTE const* oLitEnd)
1056 {
1057 size_t const windowSize = dctx->fParams.windowSize;
1058 /* No dictionary used. */
1059 if (dctx->dictContentEndForFuzzing == NULL) return 0;
1060 /* Dictionary is our prefix. */
1061 if (prefixStart == dctx->dictContentBeginForFuzzing) return 1;
1062 /* Dictionary is not our ext-dict. */
1063 if (dctx->dictEnd != dctx->dictContentEndForFuzzing) return 0;
1064 /* Dictionary is not within our window size. */
1065 if ((size_t)(oLitEnd - prefixStart) >= windowSize) return 0;
1066 /* Dictionary is active. */
1067 return 1;
1068 }
1069
ZSTD_assertValidSequence(ZSTD_DCtx const * dctx,BYTE const * op,BYTE const * oend,seq_t const seq,BYTE const * prefixStart,BYTE const * virtualStart)1070 MEM_STATIC void ZSTD_assertValidSequence(
1071 ZSTD_DCtx const* dctx,
1072 BYTE const* op, BYTE const* oend,
1073 seq_t const seq,
1074 BYTE const* prefixStart, BYTE const* virtualStart)
1075 {
1076 #if DEBUGLEVEL >= 1
1077 size_t const windowSize = dctx->fParams.windowSize;
1078 size_t const sequenceSize = seq.litLength + seq.matchLength;
1079 BYTE const* const oLitEnd = op + seq.litLength;
1080 DEBUGLOG(6, "Checking sequence: litL=%u matchL=%u offset=%u",
1081 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
1082 assert(op <= oend);
1083 assert((size_t)(oend - op) >= sequenceSize);
1084 assert(sequenceSize <= ZSTD_BLOCKSIZE_MAX);
1085 if (ZSTD_dictionaryIsActive(dctx, prefixStart, oLitEnd)) {
1086 size_t const dictSize = (size_t)((char const*)dctx->dictContentEndForFuzzing - (char const*)dctx->dictContentBeginForFuzzing);
1087 /* Offset must be within the dictionary. */
1088 assert(seq.offset <= (size_t)(oLitEnd - virtualStart));
1089 assert(seq.offset <= windowSize + dictSize);
1090 } else {
1091 /* Offset must be within our window. */
1092 assert(seq.offset <= windowSize);
1093 }
1094 #else
1095 (void)dctx, (void)op, (void)oend, (void)seq, (void)prefixStart, (void)virtualStart;
1096 #endif
1097 }
1098 #endif
1099
1100 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1101 FORCE_INLINE_TEMPLATE size_t
1102 DONT_VECTORIZE
ZSTD_decompressSequences_body(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1103 ZSTD_decompressSequences_body( ZSTD_DCtx* dctx,
1104 void* dst, size_t maxDstSize,
1105 const void* seqStart, size_t seqSize, int nbSeq,
1106 const ZSTD_longOffset_e isLongOffset,
1107 const int frame)
1108 {
1109 const BYTE* ip = (const BYTE*)seqStart;
1110 const BYTE* const iend = ip + seqSize;
1111 BYTE* const ostart = (BYTE*)dst;
1112 BYTE* const oend = ostart + maxDstSize;
1113 BYTE* op = ostart;
1114 const BYTE* litPtr = dctx->litPtr;
1115 const BYTE* const litEnd = litPtr + dctx->litSize;
1116 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1117 const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
1118 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1119 DEBUGLOG(5, "ZSTD_decompressSequences_body");
1120 (void)frame;
1121
1122 /* Regen sequences */
1123 if (nbSeq) {
1124 seqState_t seqState;
1125 size_t error = 0;
1126 dctx->fseEntropy = 1;
1127 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1128 RETURN_ERROR_IF(
1129 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1130 corruption_detected, "");
1131 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1132 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1133 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1134 assert(dst != NULL);
1135
1136 ZSTD_STATIC_ASSERT(
1137 BIT_DStream_unfinished < BIT_DStream_completed &&
1138 BIT_DStream_endOfBuffer < BIT_DStream_completed &&
1139 BIT_DStream_completed < BIT_DStream_overflow);
1140
1141 #if defined(__x86_64__)
1142 /* Align the decompression loop to 32 + 16 bytes.
1143 *
1144 * zstd compiled with gcc-9 on an Intel i9-9900k shows 10% decompression
1145 * speed swings based on the alignment of the decompression loop. This
1146 * performance swing is caused by parts of the decompression loop falling
1147 * out of the DSB. The entire decompression loop should fit in the DSB,
1148 * when it can't we get much worse performance. You can measure if you've
1149 * hit the good case or the bad case with this perf command for some
1150 * compressed file test.zst:
1151 *
1152 * perf stat -e cycles -e instructions -e idq.all_dsb_cycles_any_uops \
1153 * -e idq.all_mite_cycles_any_uops -- ./zstd -tq test.zst
1154 *
1155 * If you see most cycles served out of the MITE you've hit the bad case.
1156 * If you see most cycles served out of the DSB you've hit the good case.
1157 * If it is pretty even then you may be in an okay case.
1158 *
1159 * I've been able to reproduce this issue on the following CPUs:
1160 * - Kabylake: Macbook Pro (15-inch, 2019) 2.4 GHz Intel Core i9
1161 * Use Instruments->Counters to get DSB/MITE cycles.
1162 * I never got performance swings, but I was able to
1163 * go from the good case of mostly DSB to half of the
1164 * cycles served from MITE.
1165 * - Coffeelake: Intel i9-9900k
1166 *
1167 * I haven't been able to reproduce the instability or DSB misses on any
1168 * of the following CPUS:
1169 * - Haswell
1170 * - Broadwell: Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GH
1171 * - Skylake
1172 *
1173 * If you are seeing performance stability this script can help test.
1174 * It tests on 4 commits in zstd where I saw performance change.
1175 *
1176 * https://gist.github.com/terrelln/9889fc06a423fd5ca6e99351564473f4
1177 */
1178 __asm__(".p2align 5");
1179 __asm__("nop");
1180 __asm__(".p2align 4");
1181 #endif
1182 for ( ; ; ) {
1183 seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_noPrefetch);
1184 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
1185 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1186 assert(!ZSTD_isError(oneSeqSize));
1187 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequence, prefixStart, vBase);
1188 #endif
1189 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
1190 BIT_reloadDStream(&(seqState.DStream));
1191 op += oneSeqSize;
1192 /* gcc and clang both don't like early returns in this loop.
1193 * Instead break and check for an error at the end of the loop.
1194 */
1195 if (UNLIKELY(ZSTD_isError(oneSeqSize))) {
1196 error = oneSeqSize;
1197 break;
1198 }
1199 if (UNLIKELY(!--nbSeq)) break;
1200 }
1201
1202 /* check if reached exact end */
1203 DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
1204 if (ZSTD_isError(error)) return error;
1205 RETURN_ERROR_IF(nbSeq, corruption_detected, "");
1206 RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected, "");
1207 /* save reps for next block */
1208 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1209 }
1210
1211 /* last literal segment */
1212 { size_t const lastLLSize = litEnd - litPtr;
1213 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, "");
1214 if (op != NULL) {
1215 ZSTD_memcpy(op, litPtr, lastLLSize);
1216 op += lastLLSize;
1217 }
1218 }
1219
1220 return op-ostart;
1221 }
1222
1223 static size_t
ZSTD_decompressSequences_default(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1224 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx,
1225 void* dst, size_t maxDstSize,
1226 const void* seqStart, size_t seqSize, int nbSeq,
1227 const ZSTD_longOffset_e isLongOffset,
1228 const int frame)
1229 {
1230 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1231 }
1232 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1233
1234 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1235 FORCE_INLINE_TEMPLATE size_t
ZSTD_decompressSequencesLong_body(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1236 ZSTD_decompressSequencesLong_body(
1237 ZSTD_DCtx* dctx,
1238 void* dst, size_t maxDstSize,
1239 const void* seqStart, size_t seqSize, int nbSeq,
1240 const ZSTD_longOffset_e isLongOffset,
1241 const int frame)
1242 {
1243 const BYTE* ip = (const BYTE*)seqStart;
1244 const BYTE* const iend = ip + seqSize;
1245 BYTE* const ostart = (BYTE*)dst;
1246 BYTE* const oend = ostart + maxDstSize;
1247 BYTE* op = ostart;
1248 const BYTE* litPtr = dctx->litPtr;
1249 const BYTE* const litEnd = litPtr + dctx->litSize;
1250 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1251 const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1252 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1253 (void)frame;
1254
1255 /* Regen sequences */
1256 if (nbSeq) {
1257 #define STORED_SEQS 4
1258 #define STORED_SEQS_MASK (STORED_SEQS-1)
1259 #define ADVANCED_SEQS 4
1260 seq_t sequences[STORED_SEQS];
1261 int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1262 seqState_t seqState;
1263 int seqNb;
1264 dctx->fseEntropy = 1;
1265 { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1266 seqState.prefixStart = prefixStart;
1267 seqState.pos = (size_t)(op-prefixStart);
1268 seqState.dictEnd = dictEnd;
1269 assert(dst != NULL);
1270 assert(iend >= ip);
1271 RETURN_ERROR_IF(
1272 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1273 corruption_detected, "");
1274 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1275 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1276 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1277
1278 /* prepare in advance */
1279 for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1280 sequences[seqNb] = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_prefetch);
1281 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 */
1282 }
1283 RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected, "");
1284
1285 /* decode and decompress */
1286 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1287 seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset, ZSTD_p_prefetch);
1288 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1289 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1290 assert(!ZSTD_isError(oneSeqSize));
1291 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], prefixStart, dictStart);
1292 #endif
1293 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1294 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 */
1295 sequences[seqNb & STORED_SEQS_MASK] = sequence;
1296 op += oneSeqSize;
1297 }
1298 RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected, "");
1299
1300 /* finish queue */
1301 seqNb -= seqAdvance;
1302 for ( ; seqNb<nbSeq ; seqNb++) {
1303 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[seqNb&STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1304 #if defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION) && defined(FUZZING_ASSERT_VALID_SEQUENCE)
1305 assert(!ZSTD_isError(oneSeqSize));
1306 if (frame) ZSTD_assertValidSequence(dctx, op, oend, sequences[seqNb&STORED_SEQS_MASK], prefixStart, dictStart);
1307 #endif
1308 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1309 op += oneSeqSize;
1310 }
1311
1312 /* save reps for next block */
1313 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1314 }
1315
1316 /* last literal segment */
1317 { size_t const lastLLSize = litEnd - litPtr;
1318 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall, "");
1319 if (op != NULL) {
1320 ZSTD_memcpy(op, litPtr, lastLLSize);
1321 op += lastLLSize;
1322 }
1323 }
1324
1325 return op-ostart;
1326 }
1327
1328 static size_t
ZSTD_decompressSequencesLong_default(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1329 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx,
1330 void* dst, size_t maxDstSize,
1331 const void* seqStart, size_t seqSize, int nbSeq,
1332 const ZSTD_longOffset_e isLongOffset,
1333 const int frame)
1334 {
1335 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1336 }
1337 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1338
1339
1340
1341 #if DYNAMIC_BMI2
1342
1343 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1344 static TARGET_ATTRIBUTE("bmi2") size_t
1345 DONT_VECTORIZE
ZSTD_decompressSequences_bmi2(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1346 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1347 void* dst, size_t maxDstSize,
1348 const void* seqStart, size_t seqSize, int nbSeq,
1349 const ZSTD_longOffset_e isLongOffset,
1350 const int frame)
1351 {
1352 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1353 }
1354 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1355
1356 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1357 static TARGET_ATTRIBUTE("bmi2") size_t
ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1358 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1359 void* dst, size_t maxDstSize,
1360 const void* seqStart, size_t seqSize, int nbSeq,
1361 const ZSTD_longOffset_e isLongOffset,
1362 const int frame)
1363 {
1364 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1365 }
1366 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1367
1368 #endif /* DYNAMIC_BMI2 */
1369
1370 typedef size_t (*ZSTD_decompressSequences_t)(
1371 ZSTD_DCtx* dctx,
1372 void* dst, size_t maxDstSize,
1373 const void* seqStart, size_t seqSize, int nbSeq,
1374 const ZSTD_longOffset_e isLongOffset,
1375 const int frame);
1376
1377 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1378 static size_t
ZSTD_decompressSequences(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1379 ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1380 const void* seqStart, size_t seqSize, int nbSeq,
1381 const ZSTD_longOffset_e isLongOffset,
1382 const int frame)
1383 {
1384 DEBUGLOG(5, "ZSTD_decompressSequences");
1385 #if DYNAMIC_BMI2
1386 if (dctx->bmi2) {
1387 return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1388 }
1389 #endif
1390 return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1391 }
1392 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1393
1394
1395 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1396 /* ZSTD_decompressSequencesLong() :
1397 * decompression function triggered when a minimum share of offsets is considered "long",
1398 * aka out of cache.
1399 * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance".
1400 * This function will try to mitigate main memory latency through the use of prefetching */
1401 static size_t
ZSTD_decompressSequencesLong(ZSTD_DCtx * dctx,void * dst,size_t maxDstSize,const void * seqStart,size_t seqSize,int nbSeq,const ZSTD_longOffset_e isLongOffset,const int frame)1402 ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx,
1403 void* dst, size_t maxDstSize,
1404 const void* seqStart, size_t seqSize, int nbSeq,
1405 const ZSTD_longOffset_e isLongOffset,
1406 const int frame)
1407 {
1408 DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1409 #if DYNAMIC_BMI2
1410 if (dctx->bmi2) {
1411 return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1412 }
1413 #endif
1414 return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset, frame);
1415 }
1416 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1417
1418
1419
1420 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1421 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1422 /* ZSTD_getLongOffsetsShare() :
1423 * condition : offTable must be valid
1424 * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1425 * compared to maximum possible of (1<<OffFSELog) */
1426 static unsigned
ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol * offTable)1427 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable)
1428 {
1429 const void* ptr = offTable;
1430 U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1431 const ZSTD_seqSymbol* table = offTable + 1;
1432 U32 const max = 1 << tableLog;
1433 U32 u, total = 0;
1434 DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1435
1436 assert(max <= (1 << OffFSELog)); /* max not too large */
1437 for (u=0; u<max; u++) {
1438 if (table[u].nbAdditionalBits > 22) total += 1;
1439 }
1440
1441 assert(tableLog <= OffFSELog);
1442 total <<= (OffFSELog - tableLog); /* scale to OffFSELog */
1443
1444 return total;
1445 }
1446 #endif
1447
1448 size_t
ZSTD_decompressBlock_internal(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize,const int frame)1449 ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
1450 void* dst, size_t dstCapacity,
1451 const void* src, size_t srcSize, const int frame)
1452 { /* blockType == blockCompressed */
1453 const BYTE* ip = (const BYTE*)src;
1454 /* isLongOffset must be true if there are long offsets.
1455 * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1456 * We don't expect that to be the case in 64-bit mode.
1457 * In block mode, window size is not known, so we have to be conservative.
1458 * (note: but it could be evaluated from current-lowLimit)
1459 */
1460 ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN))));
1461 DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1462
1463 RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong, "");
1464
1465 /* Decode literals section */
1466 { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1467 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1468 if (ZSTD_isError(litCSize)) return litCSize;
1469 ip += litCSize;
1470 srcSize -= litCSize;
1471 }
1472
1473 /* Build Decoding Tables */
1474 {
1475 /* These macros control at build-time which decompressor implementation
1476 * we use. If neither is defined, we do some inspection and dispatch at
1477 * runtime.
1478 */
1479 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1480 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1481 int usePrefetchDecoder = dctx->ddictIsCold;
1482 #endif
1483 int nbSeq;
1484 size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1485 if (ZSTD_isError(seqHSize)) return seqHSize;
1486 ip += seqHSize;
1487 srcSize -= seqHSize;
1488
1489 RETURN_ERROR_IF(dst == NULL && nbSeq > 0, dstSize_tooSmall, "NULL not handled");
1490
1491 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1492 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1493 if ( !usePrefetchDecoder
1494 && (!frame || (dctx->fParams.windowSize > (1<<24)))
1495 && (nbSeq>ADVANCED_SEQS) ) { /* could probably use a larger nbSeq limit */
1496 U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1497 U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1498 usePrefetchDecoder = (shareLongOffsets >= minShare);
1499 }
1500 #endif
1501
1502 dctx->ddictIsCold = 0;
1503
1504 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1505 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1506 if (usePrefetchDecoder)
1507 #endif
1508 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1509 return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame);
1510 #endif
1511
1512 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1513 /* else */
1514 return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset, frame);
1515 #endif
1516 }
1517 }
1518
1519
ZSTD_checkContinuity(ZSTD_DCtx * dctx,const void * dst,size_t dstSize)1520 void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize)
1521 {
1522 if (dst != dctx->previousDstEnd && dstSize > 0) { /* not contiguous */
1523 dctx->dictEnd = dctx->previousDstEnd;
1524 dctx->virtualStart = (const char*)dst - ((const char*)(dctx->previousDstEnd) - (const char*)(dctx->prefixStart));
1525 dctx->prefixStart = dst;
1526 dctx->previousDstEnd = dst;
1527 }
1528 }
1529
1530
ZSTD_decompressBlock(ZSTD_DCtx * dctx,void * dst,size_t dstCapacity,const void * src,size_t srcSize)1531 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1532 void* dst, size_t dstCapacity,
1533 const void* src, size_t srcSize)
1534 {
1535 size_t dSize;
1536 ZSTD_checkContinuity(dctx, dst, dstCapacity);
1537 dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1538 dctx->previousDstEnd = (char*)dst + dSize;
1539 return dSize;
1540 }
1541