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