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