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