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