2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
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.
11 /* zstd_decompress_block :
12 * this module takes care of decompressing _compressed_ block */
14 /*-*******************************************************
16 *********************************************************/
17 #include <string.h> /* memcpy, memmove, memset */
18 #include "compiler.h" /* prefetch */
19 #include "cpu.h" /* bmi2 */
20 #include "mem.h" /* low level memory routines */
21 #define FSE_STATIC_LINKING_ONLY
23 #define HUF_STATIC_LINKING_ONLY
25 #include "zstd_internal.h"
26 #include "zstd_decompress_internal.h" /* ZSTD_DCtx */
27 #include "zstd_ddict.h" /* ZSTD_DDictDictContent */
28 #include "zstd_decompress_block.h"
30 /*_*******************************************************
32 **********************************************************/
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
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!"
44 /*_*******************************************************
46 **********************************************************/
47 static void ZSTD_copy4(void* dst, const void* src) { memcpy(dst, src, 4); }
50 /*-*************************************************************
52 ***************************************************************/
54 /*! ZSTD_getcBlockSize() :
55 * Provides the size of compressed block from block header `src` */
56 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
57 blockProperties_t* bpPtr)
59 RETURN_ERROR_IF(srcSize < ZSTD_blockHeaderSize, srcSize_wrong);
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);
73 /* Hidden declaration for fullbench */
74 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
75 const void* src, size_t srcSize);
76 /*! ZSTD_decodeLiteralsBlock() :
77 * @return : nb of bytes read from src (< srcSize )
78 * note : symbol not declared but exposed for fullbench */
79 size_t ZSTD_decodeLiteralsBlock(ZSTD_DCtx* dctx,
80 const void* src, size_t srcSize) /* note : srcSize < BLOCKSIZE */
82 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock");
83 RETURN_ERROR_IF(srcSize < MIN_CBLOCK_SIZE, corruption_detected);
85 { const BYTE* const istart = (const BYTE*) src;
86 symbolEncodingType_e const litEncType = (symbolEncodingType_e)(istart[0] & 3);
91 DEBUGLOG(5, "set_repeat flag : re-using stats from previous compressed literals block");
92 RETURN_ERROR_IF(dctx->litEntropy==0, dictionary_corrupted);
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;
99 U32 const lhlCode = (istart[0] >> 2) & 3;
100 U32 const lhc = MEM_readLE32(istart);
104 case 0: case 1: default: /* note : default is impossible, since lhlCode into [0..3] */
105 /* 2 - 2 - 10 - 10 */
106 singleStream = !lhlCode;
108 litSize = (lhc >> 4) & 0x3FF;
109 litCSize = (lhc >> 14) & 0x3FF;
112 /* 2 - 2 - 14 - 14 */
114 litSize = (lhc >> 4) & 0x3FFF;
115 litCSize = lhc >> 18;
118 /* 2 - 2 - 18 - 18 */
120 litSize = (lhc >> 4) & 0x3FFFF;
121 litCSize = (lhc >> 22) + ((size_t)istart[4] << 10);
124 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);
125 RETURN_ERROR_IF(litCSize + lhSize > srcSize, corruption_detected);
127 /* prefetch huffman table if cold */
128 if (dctx->ddictIsCold && (litSize > 768 /* heuristic */)) {
129 PREFETCH_AREA(dctx->HUFptr, sizeof(dctx->entropy.hufTable));
132 if (litEncType==set_repeat) {
134 hufSuccess = HUF_decompress1X_usingDTable_bmi2(
135 dctx->litBuffer, litSize, istart+lhSize, litCSize,
136 dctx->HUFptr, dctx->bmi2);
138 hufSuccess = HUF_decompress4X_usingDTable_bmi2(
139 dctx->litBuffer, litSize, istart+lhSize, litCSize,
140 dctx->HUFptr, dctx->bmi2);
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));
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);
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);
163 RETURN_ERROR_IF(HUF_isError(hufSuccess), corruption_detected);
165 dctx->litPtr = dctx->litBuffer;
166 dctx->litSize = litSize;
167 dctx->litEntropy = 1;
168 if (litEncType==set_compressed) dctx->HUFptr = dctx->entropy.hufTable;
169 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
170 return litCSize + lhSize;
174 { size_t litSize, lhSize;
175 U32 const lhlCode = ((istart[0]) >> 2) & 3;
178 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
180 litSize = istart[0] >> 3;
184 litSize = MEM_readLE16(istart) >> 4;
188 litSize = MEM_readLE24(istart) >> 4;
192 if (lhSize+litSize+WILDCOPY_OVERLENGTH > srcSize) { /* risk reading beyond src buffer with wildcopy */
193 RETURN_ERROR_IF(litSize+lhSize > srcSize, corruption_detected);
194 memcpy(dctx->litBuffer, istart+lhSize, litSize);
195 dctx->litPtr = dctx->litBuffer;
196 dctx->litSize = litSize;
197 memset(dctx->litBuffer + dctx->litSize, 0, WILDCOPY_OVERLENGTH);
198 return lhSize+litSize;
200 /* direct reference into compressed stream */
201 dctx->litPtr = istart+lhSize;
202 dctx->litSize = litSize;
203 return lhSize+litSize;
207 { U32 const lhlCode = ((istart[0]) >> 2) & 3;
208 size_t litSize, lhSize;
211 case 0: case 2: default: /* note : default is impossible, since lhlCode into [0..3] */
213 litSize = istart[0] >> 3;
217 litSize = MEM_readLE16(istart) >> 4;
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");
225 RETURN_ERROR_IF(litSize > ZSTD_BLOCKSIZE_MAX, corruption_detected);
226 memset(dctx->litBuffer, istart[lhSize], litSize + WILDCOPY_OVERLENGTH);
227 dctx->litPtr = dctx->litBuffer;
228 dctx->litSize = litSize;
232 RETURN_ERROR(corruption_detected, "impossible");
237 /* Default FSE distribution tables.
238 * These are pre-calculated FSE decoding tables using default distributions as defined in specification :
239 * https://github.com/facebook/zstd/blob/master/doc/zstd_compression_format.md#default-distributions
240 * They were generated programmatically with following method :
241 * - start from default distributions, present in /lib/common/zstd_internal.h
242 * - generate tables normally, using ZSTD_buildFSETable()
243 * - printout the content of tables
244 * - pretify output, report below, test with fuzzer to ensure it's correct */
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 */
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 */
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 */
346 static void ZSTD_buildSeqTable_rle(ZSTD_seqSymbol* dt, U32 baseValue, U32 nbAddBits)
349 ZSTD_seqSymbol_header* const DTableH = (ZSTD_seqSymbol_header*)ptr;
350 ZSTD_seqSymbol* const cell = dt + 1;
352 DTableH->tableLog = 0;
353 DTableH->fastMode = 0;
357 assert(nbAddBits < 255);
358 cell->nbAdditionalBits = (BYTE)nbAddBits;
359 cell->baseValue = baseValue;
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 */
368 ZSTD_buildFSETable(ZSTD_seqSymbol* dt,
369 const short* normalizedCounter, unsigned maxSymbolValue,
370 const U32* baseValue, const U32* nbAdditionalBits,
373 ZSTD_seqSymbol* const tableDecode = dt+1;
374 U16 symbolNext[MaxSeq+1];
376 U32 const maxSV1 = maxSymbolValue + 1;
377 U32 const tableSize = 1 << tableLog;
378 U32 highThreshold = tableSize-1;
381 assert(maxSymbolValue <= MaxSeq);
382 assert(tableLog <= MaxFSELog);
384 /* Init, lay down lowprob symbols */
385 { ZSTD_seqSymbol_header DTableH;
386 DTableH.tableLog = tableLog;
387 DTableH.fastMode = 1;
388 { S16 const largeLimit= (S16)(1 << (tableLog-1));
390 for (s=0; s<maxSV1; s++) {
391 if (normalizedCounter[s]==-1) {
392 tableDecode[highThreshold--].baseValue = s;
395 if (normalizedCounter[s] >= largeLimit) DTableH.fastMode=0;
396 assert(normalizedCounter[s]>=0);
397 symbolNext[s] = (U16)normalizedCounter[s];
399 memcpy(dt, &DTableH, sizeof(DTableH));
403 { U32 const tableMask = tableSize-1;
404 U32 const step = FSE_TABLESTEP(tableSize);
406 for (s=0; s<maxSV1; s++) {
408 for (i=0; i<normalizedCounter[s]; i++) {
409 tableDecode[position].baseValue = s;
410 position = (position + step) & tableMask;
411 while (position > highThreshold) position = (position + step) & tableMask; /* lowprob area */
413 assert(position == 0); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
416 /* Build Decoding table */
418 for (u=0; u<tableSize; u++) {
419 U32 const symbol = tableDecode[u].baseValue;
420 U32 const nextState = symbolNext[symbol]++;
421 tableDecode[u].nbBits = (BYTE) (tableLog - BIT_highbit32(nextState) );
422 tableDecode[u].nextState = (U16) ( (nextState << tableDecode[u].nbBits) - tableSize);
423 assert(nbAdditionalBits[symbol] < 255);
424 tableDecode[u].nbAdditionalBits = (BYTE)nbAdditionalBits[symbol];
425 tableDecode[u].baseValue = baseValue[symbol];
430 /*! ZSTD_buildSeqTable() :
431 * @return : nb bytes read from src,
432 * or an error code if it fails */
433 static size_t ZSTD_buildSeqTable(ZSTD_seqSymbol* DTableSpace, const ZSTD_seqSymbol** DTablePtr,
434 symbolEncodingType_e type, unsigned max, U32 maxLog,
435 const void* src, size_t srcSize,
436 const U32* baseValue, const U32* nbAdditionalBits,
437 const ZSTD_seqSymbol* defaultTable, U32 flagRepeatTable,
438 int ddictIsCold, int nbSeq)
443 RETURN_ERROR_IF(!srcSize, srcSize_wrong);
444 RETURN_ERROR_IF((*(const BYTE*)src) > max, corruption_detected);
445 { U32 const symbol = *(const BYTE*)src;
446 U32 const baseline = baseValue[symbol];
447 U32 const nbBits = nbAdditionalBits[symbol];
448 ZSTD_buildSeqTable_rle(DTableSpace, baseline, nbBits);
450 *DTablePtr = DTableSpace;
453 *DTablePtr = defaultTable;
456 RETURN_ERROR_IF(!flagRepeatTable, corruption_detected);
457 /* prefetch FSE table if used */
458 if (ddictIsCold && (nbSeq > 24 /* heuristic */)) {
459 const void* const pStart = *DTablePtr;
460 size_t const pSize = sizeof(ZSTD_seqSymbol) * (SEQSYMBOL_TABLE_SIZE(maxLog));
461 PREFETCH_AREA(pStart, pSize);
464 case set_compressed :
467 size_t const headerSize = FSE_readNCount(norm, &max, &tableLog, src, srcSize);
468 RETURN_ERROR_IF(FSE_isError(headerSize), corruption_detected);
469 RETURN_ERROR_IF(tableLog > maxLog, corruption_detected);
470 ZSTD_buildFSETable(DTableSpace, norm, max, baseValue, nbAdditionalBits, tableLog);
471 *DTablePtr = DTableSpace;
476 RETURN_ERROR(GENERIC, "impossible");
480 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
481 const void* src, size_t srcSize)
483 const BYTE* const istart = (const BYTE* const)src;
484 const BYTE* const iend = istart + srcSize;
485 const BYTE* ip = istart;
487 DEBUGLOG(5, "ZSTD_decodeSeqHeaders");
490 RETURN_ERROR_IF(srcSize < MIN_SEQUENCES_SIZE, srcSize_wrong);
496 RETURN_ERROR_IF(srcSize != 1, srcSize_wrong);
501 RETURN_ERROR_IF(ip+2 > iend, srcSize_wrong);
502 nbSeq = MEM_readLE16(ip) + LONGNBSEQ, ip+=2;
504 RETURN_ERROR_IF(ip >= iend, srcSize_wrong);
505 nbSeq = ((nbSeq-0x80)<<8) + *ip++;
510 /* FSE table descriptors */
511 RETURN_ERROR_IF(ip+1 > iend, srcSize_wrong); /* minimum possible size: 1 byte for symbol encoding types */
512 { symbolEncodingType_e const LLtype = (symbolEncodingType_e)(*ip >> 6);
513 symbolEncodingType_e const OFtype = (symbolEncodingType_e)((*ip >> 4) & 3);
514 symbolEncodingType_e const MLtype = (symbolEncodingType_e)((*ip >> 2) & 3);
518 { size_t const llhSize = ZSTD_buildSeqTable(dctx->entropy.LLTable, &dctx->LLTptr,
519 LLtype, MaxLL, LLFSELog,
522 LL_defaultDTable, dctx->fseEntropy,
523 dctx->ddictIsCold, nbSeq);
524 RETURN_ERROR_IF(ZSTD_isError(llhSize), corruption_detected);
528 { size_t const ofhSize = ZSTD_buildSeqTable(dctx->entropy.OFTable, &dctx->OFTptr,
529 OFtype, MaxOff, OffFSELog,
532 OF_defaultDTable, dctx->fseEntropy,
533 dctx->ddictIsCold, nbSeq);
534 RETURN_ERROR_IF(ZSTD_isError(ofhSize), corruption_detected);
538 { size_t const mlhSize = ZSTD_buildSeqTable(dctx->entropy.MLTable, &dctx->MLTptr,
539 MLtype, MaxML, MLFSELog,
542 ML_defaultDTable, dctx->fseEntropy,
543 dctx->ddictIsCold, nbSeq);
544 RETURN_ERROR_IF(ZSTD_isError(mlhSize), corruption_detected);
562 const ZSTD_seqSymbol* table;
566 BIT_DStream_t DStream;
567 ZSTD_fseState stateLL;
568 ZSTD_fseState stateOffb;
569 ZSTD_fseState stateML;
570 size_t prevOffset[ZSTD_REP_NUM];
571 const BYTE* prefixStart;
576 /*! ZSTD_overlapCopy8() :
577 * Copies 8 bytes from ip to op and updates op and ip where ip <= op.
578 * If the offset is < 8 then the offset is spread to at least 8 bytes.
580 * Precondition: *ip <= *op
581 * Postcondition: *op - *op >= 8
583 static void ZSTD_overlapCopy8(BYTE** op, BYTE const** ip, size_t offset) {
586 /* close range match, overlap */
587 static const U32 dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; /* added */
588 static const int dec64table[] = { 8, 8, 8, 7, 8, 9,10,11 }; /* subtracted */
589 int const sub2 = dec64table[offset];
594 *ip += dec32table[offset];
595 ZSTD_copy4(*op+4, *ip);
598 ZSTD_copy8(*op, *ip);
602 assert(*op - *ip >= 8);
605 /*! ZSTD_safecopy() :
606 * Specialized version of memcpy() that is allowed to READ up to WILDCOPY_OVERLENGTH past the input buffer
607 * and write up to 16 bytes past oend_w (op >= oend_w is allowed).
608 * This function is only called in the uncommon case where the sequence is near the end of the block. It
609 * should be fast for a single long sequence, but can be slow for several short sequences.
611 * @param ovtype controls the overlap detection
612 * - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
613 * - ZSTD_overlap_src_before_dst: The src and dst may overlap and may be any distance apart.
614 * The src buffer must be before the dst buffer.
616 static void ZSTD_safecopy(BYTE* op, BYTE* const oend_w, BYTE const* ip, ptrdiff_t length, ZSTD_overlap_e ovtype) {
617 ptrdiff_t const diff = op - ip;
618 BYTE* const oend = op + length;
620 assert((ovtype == ZSTD_no_overlap && (diff <= -8 || diff >= 8 || op >= oend_w)) ||
621 (ovtype == ZSTD_overlap_src_before_dst && diff >= 0));
624 /* Handle short lengths. */
625 while (op < oend) *op++ = *ip++;
628 if (ovtype == ZSTD_overlap_src_before_dst) {
629 /* Copy 8 bytes and ensure the offset >= 8 when there can be overlap. */
631 ZSTD_overlapCopy8(&op, &ip, diff);
632 assert(op - ip >= 8);
636 if (oend <= oend_w) {
637 /* No risk of overwrite. */
638 ZSTD_wildcopy(op, ip, length, ovtype);
642 /* Wildcopy until we get close to the end. */
643 assert(oend > oend_w);
644 ZSTD_wildcopy(op, ip, oend_w - op, ovtype);
648 /* Handle the leftovers. */
649 while (op < oend) *op++ = *ip++;
652 /* ZSTD_execSequenceEnd():
653 * This version handles cases that are near the end of the output buffer. It requires
654 * more careful checks to make sure there is no overflow. By separating out these hard
655 * and unlikely cases, we can speed up the common cases.
657 * NOTE: This function needs to be fast for a single long sequence, but doesn't need
658 * to be optimized for many small sequences, since those fall into ZSTD_execSequence().
661 size_t ZSTD_execSequenceEnd(BYTE* op,
662 BYTE* const oend, seq_t sequence,
663 const BYTE** litPtr, const BYTE* const litLimit,
664 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
666 BYTE* const oLitEnd = op + sequence.litLength;
667 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
668 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
669 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
670 const BYTE* match = oLitEnd - sequence.offset;
671 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
674 assert(oLitEnd < oMatchEnd);
675 RETURN_ERROR_IF(oMatchEnd > oend, dstSize_tooSmall, "last match must fit within dstBuffer");
676 RETURN_ERROR_IF(iLitEnd > litLimit, corruption_detected, "try to read beyond literal buffer");
679 ZSTD_safecopy(op, oend_w, *litPtr, sequence.litLength, ZSTD_no_overlap);
684 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
685 /* offset beyond prefix */
686 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected);
687 match = dictEnd - (prefixStart-match);
688 if (match + sequence.matchLength <= dictEnd) {
689 memmove(oLitEnd, match, sequence.matchLength);
690 return sequenceLength;
692 /* span extDict & currentPrefixSegment */
693 { size_t const length1 = dictEnd - match;
694 memmove(oLitEnd, match, length1);
695 op = oLitEnd + length1;
696 sequence.matchLength -= length1;
699 ZSTD_safecopy(op, oend_w, match, sequence.matchLength, ZSTD_overlap_src_before_dst);
700 return sequenceLength;
704 size_t ZSTD_execSequence(BYTE* op,
705 BYTE* const oend, seq_t sequence,
706 const BYTE** litPtr, const BYTE* const litLimit,
707 const BYTE* const prefixStart, const BYTE* const virtualStart, const BYTE* const dictEnd)
709 BYTE* const oLitEnd = op + sequence.litLength;
710 size_t const sequenceLength = sequence.litLength + sequence.matchLength;
711 BYTE* const oMatchEnd = op + sequenceLength; /* risk : address space overflow (32-bits) */
712 BYTE* const oend_w = oend - WILDCOPY_OVERLENGTH;
713 const BYTE* const iLitEnd = *litPtr + sequence.litLength;
714 const BYTE* match = oLitEnd - sequence.offset;
716 /* Errors and uncommon cases handled here. */
717 assert(oLitEnd < oMatchEnd);
718 if (iLitEnd > litLimit || oMatchEnd > oend_w)
719 return ZSTD_execSequenceEnd(op, oend, sequence, litPtr, litLimit, prefixStart, virtualStart, dictEnd);
721 /* Assumptions (everything else goes into ZSTD_execSequenceEnd()) */
722 assert(iLitEnd <= litLimit /* Literal length is in bounds */);
723 assert(oLitEnd <= oend_w /* Can wildcopy literals */);
724 assert(oMatchEnd <= oend_w /* Can wildcopy matches */);
727 * Split out litLength <= 16 since it is nearly always true. +1.6% on gcc-9.
728 * We likely don't need the full 32-byte wildcopy.
730 assert(WILDCOPY_OVERLENGTH >= 16);
731 ZSTD_copy16(op, (*litPtr));
732 if (sequence.litLength > 16) {
733 ZSTD_wildcopy(op+16, (*litPtr)+16, sequence.litLength-16, ZSTD_no_overlap);
736 *litPtr = iLitEnd; /* update for next sequence */
739 if (sequence.offset > (size_t)(oLitEnd - prefixStart)) {
740 /* offset beyond prefix -> go into extDict */
741 RETURN_ERROR_IF(sequence.offset > (size_t)(oLitEnd - virtualStart), corruption_detected);
742 match = dictEnd + (match - prefixStart);
743 if (match + sequence.matchLength <= dictEnd) {
744 memmove(oLitEnd, match, sequence.matchLength);
745 return sequenceLength;
747 /* span extDict & currentPrefixSegment */
748 { size_t const length1 = dictEnd - match;
749 memmove(oLitEnd, match, length1);
750 op = oLitEnd + length1;
751 sequence.matchLength -= length1;
754 /* Match within prefix of 1 or more bytes */
755 assert(op <= oMatchEnd);
756 assert(oMatchEnd <= oend_w);
757 assert(match >= prefixStart);
758 assert(sequence.matchLength >= 1);
760 /* Nearly all offsets are >= WILDCOPY_VECLEN bytes, which means we can use wildcopy
761 * without overlap checking.
763 if (sequence.offset >= WILDCOPY_VECLEN) {
764 /* We bet on a full wildcopy for matches, since we expect matches to be
765 * longer than literals (in general). In silesia, ~10% of matches are longer
768 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength, ZSTD_no_overlap);
769 return sequenceLength;
771 assert(sequence.offset < WILDCOPY_VECLEN);
773 /* Copy 8 bytes and spread the offset to be >= 8. */
774 ZSTD_overlapCopy8(&op, &match, sequence.offset);
776 /* If the match length is > 8 bytes, then continue with the wildcopy. */
777 if (sequence.matchLength > 8) {
778 assert(op < oMatchEnd);
779 ZSTD_wildcopy(op, match, (ptrdiff_t)sequence.matchLength-8, ZSTD_overlap_src_before_dst);
781 return sequenceLength;
785 ZSTD_initFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD, const ZSTD_seqSymbol* dt)
787 const void* ptr = dt;
788 const ZSTD_seqSymbol_header* const DTableH = (const ZSTD_seqSymbol_header*)ptr;
789 DStatePtr->state = BIT_readBits(bitD, DTableH->tableLog);
790 DEBUGLOG(6, "ZSTD_initFseState : val=%u using %u bits",
791 (U32)DStatePtr->state, DTableH->tableLog);
792 BIT_reloadDStream(bitD);
793 DStatePtr->table = dt + 1;
796 FORCE_INLINE_TEMPLATE void
797 ZSTD_updateFseState(ZSTD_fseState* DStatePtr, BIT_DStream_t* bitD)
799 ZSTD_seqSymbol const DInfo = DStatePtr->table[DStatePtr->state];
800 U32 const nbBits = DInfo.nbBits;
801 size_t const lowBits = BIT_readBits(bitD, nbBits);
802 DStatePtr->state = DInfo.nextState + lowBits;
805 /* We need to add at most (ZSTD_WINDOWLOG_MAX_32 - 1) bits to read the maximum
806 * offset bits. But we can only read at most (STREAM_ACCUMULATOR_MIN_32 - 1)
807 * bits before reloading. This value is the maximum number of bytes we read
808 * after reloading when we are decoding long offsets.
810 #define LONG_OFFSETS_MAX_EXTRA_BITS_32 \
811 (ZSTD_WINDOWLOG_MAX_32 > STREAM_ACCUMULATOR_MIN_32 \
812 ? ZSTD_WINDOWLOG_MAX_32 - STREAM_ACCUMULATOR_MIN_32 \
815 typedef enum { ZSTD_lo_isRegularOffset, ZSTD_lo_isLongOffset=1 } ZSTD_longOffset_e;
817 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
818 FORCE_INLINE_TEMPLATE seq_t
819 ZSTD_decodeSequence(seqState_t* seqState, const ZSTD_longOffset_e longOffsets)
822 U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
823 U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
824 U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
825 U32 const totalBits = llBits+mlBits+ofBits;
826 U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
827 U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
828 U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
835 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
836 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
837 assert(ofBits <= MaxOff);
838 if (MEM_32bits() && longOffsets && (ofBits >= STREAM_ACCUMULATOR_MIN_32)) {
839 U32 const extraBits = ofBits - MIN(ofBits, 32 - seqState->DStream.bitsConsumed);
840 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
841 BIT_reloadDStream(&seqState->DStream);
842 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
843 assert(extraBits <= LONG_OFFSETS_MAX_EXTRA_BITS_32); /* to avoid another reload */
845 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits/*>0*/); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
846 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
851 offset += (llBase==0);
853 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
854 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
855 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
856 seqState->prevOffset[1] = seqState->prevOffset[0];
857 seqState->prevOffset[0] = offset = temp;
858 } else { /* offset == 0 */
859 offset = seqState->prevOffset[0];
862 seqState->prevOffset[2] = seqState->prevOffset[1];
863 seqState->prevOffset[1] = seqState->prevOffset[0];
864 seqState->prevOffset[0] = offset;
869 seq.matchLength = mlBase
870 + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits/*>0*/) : 0); /* <= 16 bits */
871 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
872 BIT_reloadDStream(&seqState->DStream);
873 if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
874 BIT_reloadDStream(&seqState->DStream);
875 /* Ensure there are enough bits to read the rest of data in 64-bit mode. */
876 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
878 seq.litLength = llBase
879 + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits/*>0*/) : 0); /* <= 16 bits */
881 BIT_reloadDStream(&seqState->DStream);
883 DEBUGLOG(6, "seq: litL=%u, matchL=%u, offset=%u",
884 (U32)seq.litLength, (U32)seq.matchLength, (U32)seq.offset);
886 /* ANS state update */
887 ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
888 ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
889 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
890 ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
895 FORCE_INLINE_TEMPLATE size_t
897 ZSTD_decompressSequences_body( ZSTD_DCtx* dctx,
898 void* dst, size_t maxDstSize,
899 const void* seqStart, size_t seqSize, int nbSeq,
900 const ZSTD_longOffset_e isLongOffset)
902 const BYTE* ip = (const BYTE*)seqStart;
903 const BYTE* const iend = ip + seqSize;
904 BYTE* const ostart = (BYTE* const)dst;
905 BYTE* const oend = ostart + maxDstSize;
907 const BYTE* litPtr = dctx->litPtr;
908 const BYTE* const litEnd = litPtr + dctx->litSize;
909 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
910 const BYTE* const vBase = (const BYTE*) (dctx->virtualStart);
911 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
912 DEBUGLOG(5, "ZSTD_decompressSequences_body");
914 /* Regen sequences */
917 dctx->fseEntropy = 1;
918 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
920 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
921 corruption_detected);
922 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
923 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
924 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
927 BIT_DStream_unfinished < BIT_DStream_completed &&
928 BIT_DStream_endOfBuffer < BIT_DStream_completed &&
929 BIT_DStream_completed < BIT_DStream_overflow);
931 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && nbSeq ; ) {
933 { seq_t const sequence = ZSTD_decodeSequence(&seqState, isLongOffset);
934 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequence, &litPtr, litEnd, prefixStart, vBase, dictEnd);
935 DEBUGLOG(6, "regenerated sequence size : %u", (U32)oneSeqSize);
936 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
940 /* check if reached exact end */
941 DEBUGLOG(5, "ZSTD_decompressSequences_body: after decode loop, remaining nbSeq : %i", nbSeq);
942 RETURN_ERROR_IF(nbSeq, corruption_detected);
943 RETURN_ERROR_IF(BIT_reloadDStream(&seqState.DStream) < BIT_DStream_completed, corruption_detected);
944 /* save reps for next block */
945 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
948 /* last literal segment */
949 { size_t const lastLLSize = litEnd - litPtr;
950 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall);
951 memcpy(op, litPtr, lastLLSize);
959 ZSTD_decompressSequences_default(ZSTD_DCtx* dctx,
960 void* dst, size_t maxDstSize,
961 const void* seqStart, size_t seqSize, int nbSeq,
962 const ZSTD_longOffset_e isLongOffset)
964 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
966 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
970 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
971 FORCE_INLINE_TEMPLATE seq_t
972 ZSTD_decodeSequenceLong(seqState_t* seqState, ZSTD_longOffset_e const longOffsets)
975 U32 const llBits = seqState->stateLL.table[seqState->stateLL.state].nbAdditionalBits;
976 U32 const mlBits = seqState->stateML.table[seqState->stateML.state].nbAdditionalBits;
977 U32 const ofBits = seqState->stateOffb.table[seqState->stateOffb.state].nbAdditionalBits;
978 U32 const totalBits = llBits+mlBits+ofBits;
979 U32 const llBase = seqState->stateLL.table[seqState->stateLL.state].baseValue;
980 U32 const mlBase = seqState->stateML.table[seqState->stateML.state].baseValue;
981 U32 const ofBase = seqState->stateOffb.table[seqState->stateOffb.state].baseValue;
988 ZSTD_STATIC_ASSERT(ZSTD_lo_isLongOffset == 1);
989 ZSTD_STATIC_ASSERT(LONG_OFFSETS_MAX_EXTRA_BITS_32 == 5);
990 assert(ofBits <= MaxOff);
991 if (MEM_32bits() && longOffsets) {
992 U32 const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN_32-1);
993 offset = ofBase + (BIT_readBitsFast(&seqState->DStream, ofBits - extraBits) << extraBits);
994 if (MEM_32bits() || extraBits) BIT_reloadDStream(&seqState->DStream);
995 if (extraBits) offset += BIT_readBitsFast(&seqState->DStream, extraBits);
997 offset = ofBase + BIT_readBitsFast(&seqState->DStream, ofBits); /* <= (ZSTD_WINDOWLOG_MAX-1) bits */
998 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream);
1003 offset += (llBase==0);
1005 size_t temp = (offset==3) ? seqState->prevOffset[0] - 1 : seqState->prevOffset[offset];
1006 temp += !temp; /* 0 is not valid; input is corrupted; force offset to 1 */
1007 if (offset != 1) seqState->prevOffset[2] = seqState->prevOffset[1];
1008 seqState->prevOffset[1] = seqState->prevOffset[0];
1009 seqState->prevOffset[0] = offset = temp;
1011 offset = seqState->prevOffset[0];
1014 seqState->prevOffset[2] = seqState->prevOffset[1];
1015 seqState->prevOffset[1] = seqState->prevOffset[0];
1016 seqState->prevOffset[0] = offset;
1018 seq.offset = offset;
1021 seq.matchLength = mlBase + ((mlBits>0) ? BIT_readBitsFast(&seqState->DStream, mlBits) : 0); /* <= 16 bits */
1022 if (MEM_32bits() && (mlBits+llBits >= STREAM_ACCUMULATOR_MIN_32-LONG_OFFSETS_MAX_EXTRA_BITS_32))
1023 BIT_reloadDStream(&seqState->DStream);
1024 if (MEM_64bits() && (totalBits >= STREAM_ACCUMULATOR_MIN_64-(LLFSELog+MLFSELog+OffFSELog)))
1025 BIT_reloadDStream(&seqState->DStream);
1026 /* Verify that there is enough bits to read the rest of the data in 64-bit mode. */
1027 ZSTD_STATIC_ASSERT(16+LLFSELog+MLFSELog+OffFSELog < STREAM_ACCUMULATOR_MIN_64);
1029 seq.litLength = llBase + ((llBits>0) ? BIT_readBitsFast(&seqState->DStream, llBits) : 0); /* <= 16 bits */
1031 BIT_reloadDStream(&seqState->DStream);
1033 { size_t const pos = seqState->pos + seq.litLength;
1034 const BYTE* const matchBase = (seq.offset > pos) ? seqState->dictEnd : seqState->prefixStart;
1035 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.
1036 * No consequence though : no memory access will occur, overly large offset will be detected in ZSTD_execSequenceLong() */
1037 seqState->pos = pos + seq.matchLength;
1040 /* ANS state update */
1041 ZSTD_updateFseState(&seqState->stateLL, &seqState->DStream); /* <= 9 bits */
1042 ZSTD_updateFseState(&seqState->stateML, &seqState->DStream); /* <= 9 bits */
1043 if (MEM_32bits()) BIT_reloadDStream(&seqState->DStream); /* <= 18 bits */
1044 ZSTD_updateFseState(&seqState->stateOffb, &seqState->DStream); /* <= 8 bits */
1049 FORCE_INLINE_TEMPLATE size_t
1050 ZSTD_decompressSequencesLong_body(
1052 void* dst, size_t maxDstSize,
1053 const void* seqStart, size_t seqSize, int nbSeq,
1054 const ZSTD_longOffset_e isLongOffset)
1056 const BYTE* ip = (const BYTE*)seqStart;
1057 const BYTE* const iend = ip + seqSize;
1058 BYTE* const ostart = (BYTE* const)dst;
1059 BYTE* const oend = ostart + maxDstSize;
1061 const BYTE* litPtr = dctx->litPtr;
1062 const BYTE* const litEnd = litPtr + dctx->litSize;
1063 const BYTE* const prefixStart = (const BYTE*) (dctx->prefixStart);
1064 const BYTE* const dictStart = (const BYTE*) (dctx->virtualStart);
1065 const BYTE* const dictEnd = (const BYTE*) (dctx->dictEnd);
1067 /* Regen sequences */
1069 #define STORED_SEQS 4
1070 #define STORED_SEQS_MASK (STORED_SEQS-1)
1071 #define ADVANCED_SEQS 4
1072 seq_t sequences[STORED_SEQS];
1073 int const seqAdvance = MIN(nbSeq, ADVANCED_SEQS);
1074 seqState_t seqState;
1076 dctx->fseEntropy = 1;
1077 { int i; for (i=0; i<ZSTD_REP_NUM; i++) seqState.prevOffset[i] = dctx->entropy.rep[i]; }
1078 seqState.prefixStart = prefixStart;
1079 seqState.pos = (size_t)(op-prefixStart);
1080 seqState.dictEnd = dictEnd;
1083 ERR_isError(BIT_initDStream(&seqState.DStream, ip, iend-ip)),
1084 corruption_detected);
1085 ZSTD_initFseState(&seqState.stateLL, &seqState.DStream, dctx->LLTptr);
1086 ZSTD_initFseState(&seqState.stateOffb, &seqState.DStream, dctx->OFTptr);
1087 ZSTD_initFseState(&seqState.stateML, &seqState.DStream, dctx->MLTptr);
1089 /* prepare in advance */
1090 for (seqNb=0; (BIT_reloadDStream(&seqState.DStream) <= BIT_DStream_completed) && (seqNb<seqAdvance); seqNb++) {
1091 sequences[seqNb] = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1092 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 */
1094 RETURN_ERROR_IF(seqNb<seqAdvance, corruption_detected);
1096 /* decode and decompress */
1097 for ( ; (BIT_reloadDStream(&(seqState.DStream)) <= BIT_DStream_completed) && (seqNb<nbSeq) ; seqNb++) {
1098 seq_t const sequence = ZSTD_decodeSequenceLong(&seqState, isLongOffset);
1099 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[(seqNb-ADVANCED_SEQS) & STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1100 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1101 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 */
1102 sequences[seqNb & STORED_SEQS_MASK] = sequence;
1105 RETURN_ERROR_IF(seqNb<nbSeq, corruption_detected);
1108 seqNb -= seqAdvance;
1109 for ( ; seqNb<nbSeq ; seqNb++) {
1110 size_t const oneSeqSize = ZSTD_execSequence(op, oend, sequences[seqNb&STORED_SEQS_MASK], &litPtr, litEnd, prefixStart, dictStart, dictEnd);
1111 if (ZSTD_isError(oneSeqSize)) return oneSeqSize;
1115 /* save reps for next block */
1116 { U32 i; for (i=0; i<ZSTD_REP_NUM; i++) dctx->entropy.rep[i] = (U32)(seqState.prevOffset[i]); }
1119 /* last literal segment */
1120 { size_t const lastLLSize = litEnd - litPtr;
1121 RETURN_ERROR_IF(lastLLSize > (size_t)(oend-op), dstSize_tooSmall);
1122 memcpy(op, litPtr, lastLLSize);
1130 ZSTD_decompressSequencesLong_default(ZSTD_DCtx* dctx,
1131 void* dst, size_t maxDstSize,
1132 const void* seqStart, size_t seqSize, int nbSeq,
1133 const ZSTD_longOffset_e isLongOffset)
1135 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1137 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1143 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1144 static TARGET_ATTRIBUTE("bmi2") size_t
1146 ZSTD_decompressSequences_bmi2(ZSTD_DCtx* dctx,
1147 void* dst, size_t maxDstSize,
1148 const void* seqStart, size_t seqSize, int nbSeq,
1149 const ZSTD_longOffset_e isLongOffset)
1151 return ZSTD_decompressSequences_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1153 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1155 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1156 static TARGET_ATTRIBUTE("bmi2") size_t
1157 ZSTD_decompressSequencesLong_bmi2(ZSTD_DCtx* dctx,
1158 void* dst, size_t maxDstSize,
1159 const void* seqStart, size_t seqSize, int nbSeq,
1160 const ZSTD_longOffset_e isLongOffset)
1162 return ZSTD_decompressSequencesLong_body(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1164 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1166 #endif /* DYNAMIC_BMI2 */
1168 typedef size_t (*ZSTD_decompressSequences_t)(
1170 void* dst, size_t maxDstSize,
1171 const void* seqStart, size_t seqSize, int nbSeq,
1172 const ZSTD_longOffset_e isLongOffset);
1174 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1176 ZSTD_decompressSequences(ZSTD_DCtx* dctx, void* dst, size_t maxDstSize,
1177 const void* seqStart, size_t seqSize, int nbSeq,
1178 const ZSTD_longOffset_e isLongOffset)
1180 DEBUGLOG(5, "ZSTD_decompressSequences");
1183 return ZSTD_decompressSequences_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1186 return ZSTD_decompressSequences_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1188 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG */
1191 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1192 /* ZSTD_decompressSequencesLong() :
1193 * decompression function triggered when a minimum share of offsets is considered "long",
1195 * note : "long" definition seems overloaded here, sometimes meaning "wider than bitstream register", and sometimes meaning "farther than memory cache distance".
1196 * This function will try to mitigate main memory latency through the use of prefetching */
1198 ZSTD_decompressSequencesLong(ZSTD_DCtx* dctx,
1199 void* dst, size_t maxDstSize,
1200 const void* seqStart, size_t seqSize, int nbSeq,
1201 const ZSTD_longOffset_e isLongOffset)
1203 DEBUGLOG(5, "ZSTD_decompressSequencesLong");
1206 return ZSTD_decompressSequencesLong_bmi2(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1209 return ZSTD_decompressSequencesLong_default(dctx, dst, maxDstSize, seqStart, seqSize, nbSeq, isLongOffset);
1211 #endif /* ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT */
1215 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1216 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1217 /* ZSTD_getLongOffsetsShare() :
1218 * condition : offTable must be valid
1219 * @return : "share" of long offsets (arbitrarily defined as > (1<<23))
1220 * compared to maximum possible of (1<<OffFSELog) */
1222 ZSTD_getLongOffsetsShare(const ZSTD_seqSymbol* offTable)
1224 const void* ptr = offTable;
1225 U32 const tableLog = ((const ZSTD_seqSymbol_header*)ptr)[0].tableLog;
1226 const ZSTD_seqSymbol* table = offTable + 1;
1227 U32 const max = 1 << tableLog;
1229 DEBUGLOG(5, "ZSTD_getLongOffsetsShare: (tableLog=%u)", tableLog);
1231 assert(max <= (1 << OffFSELog)); /* max not too large */
1232 for (u=0; u<max; u++) {
1233 if (table[u].nbAdditionalBits > 22) total += 1;
1236 assert(tableLog <= OffFSELog);
1237 total <<= (OffFSELog - tableLog); /* scale to OffFSELog */
1245 ZSTD_decompressBlock_internal(ZSTD_DCtx* dctx,
1246 void* dst, size_t dstCapacity,
1247 const void* src, size_t srcSize, const int frame)
1248 { /* blockType == blockCompressed */
1249 const BYTE* ip = (const BYTE*)src;
1250 /* isLongOffset must be true if there are long offsets.
1251 * Offsets are long if they are larger than 2^STREAM_ACCUMULATOR_MIN.
1252 * We don't expect that to be the case in 64-bit mode.
1253 * In block mode, window size is not known, so we have to be conservative.
1254 * (note: but it could be evaluated from current-lowLimit)
1256 ZSTD_longOffset_e const isLongOffset = (ZSTD_longOffset_e)(MEM_32bits() && (!frame || (dctx->fParams.windowSize > (1ULL << STREAM_ACCUMULATOR_MIN))));
1257 DEBUGLOG(5, "ZSTD_decompressBlock_internal (size : %u)", (U32)srcSize);
1259 RETURN_ERROR_IF(srcSize >= ZSTD_BLOCKSIZE_MAX, srcSize_wrong);
1261 /* Decode literals section */
1262 { size_t const litCSize = ZSTD_decodeLiteralsBlock(dctx, src, srcSize);
1263 DEBUGLOG(5, "ZSTD_decodeLiteralsBlock : %u", (U32)litCSize);
1264 if (ZSTD_isError(litCSize)) return litCSize;
1266 srcSize -= litCSize;
1269 /* Build Decoding Tables */
1271 /* These macros control at build-time which decompressor implementation
1272 * we use. If neither is defined, we do some inspection and dispatch at
1275 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1276 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1277 int usePrefetchDecoder = dctx->ddictIsCold;
1280 size_t const seqHSize = ZSTD_decodeSeqHeaders(dctx, &nbSeq, ip, srcSize);
1281 if (ZSTD_isError(seqHSize)) return seqHSize;
1283 srcSize -= seqHSize;
1285 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1286 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1287 if ( !usePrefetchDecoder
1288 && (!frame || (dctx->fParams.windowSize > (1<<24)))
1289 && (nbSeq>ADVANCED_SEQS) ) { /* could probably use a larger nbSeq limit */
1290 U32 const shareLongOffsets = ZSTD_getLongOffsetsShare(dctx->OFTptr);
1291 U32 const minShare = MEM_64bits() ? 7 : 20; /* heuristic values, correspond to 2.73% and 7.81% */
1292 usePrefetchDecoder = (shareLongOffsets >= minShare);
1296 dctx->ddictIsCold = 0;
1298 #if !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT) && \
1299 !defined(ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG)
1300 if (usePrefetchDecoder)
1302 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_SHORT
1303 return ZSTD_decompressSequencesLong(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1306 #ifndef ZSTD_FORCE_DECOMPRESS_SEQUENCES_LONG
1308 return ZSTD_decompressSequences(dctx, dst, dstCapacity, ip, srcSize, nbSeq, isLongOffset);
1314 size_t ZSTD_decompressBlock(ZSTD_DCtx* dctx,
1315 void* dst, size_t dstCapacity,
1316 const void* src, size_t srcSize)
1319 ZSTD_checkContinuity(dctx, dst);
1320 dSize = ZSTD_decompressBlock_internal(dctx, dst, dstCapacity, src, srcSize, /* frame */ 0);
1321 dctx->previousDstEnd = (char*)dst + dSize;