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
12*01826a49SYabin Cui /* zstd_decompress_internal:
13*01826a49SYabin Cui * objects and definitions shared within lib/decompress modules */
14*01826a49SYabin Cui
15*01826a49SYabin Cui #ifndef ZSTD_DECOMPRESS_INTERNAL_H
16*01826a49SYabin Cui #define ZSTD_DECOMPRESS_INTERNAL_H
17*01826a49SYabin Cui
18*01826a49SYabin Cui
19*01826a49SYabin Cui /*-*******************************************************
20*01826a49SYabin Cui * Dependencies
21*01826a49SYabin Cui *********************************************************/
22*01826a49SYabin Cui #include "../common/mem.h" /* BYTE, U16, U32 */
23*01826a49SYabin Cui #include "../common/zstd_internal.h" /* constants : MaxLL, MaxML, MaxOff, LLFSELog, etc. */
24*01826a49SYabin Cui
25*01826a49SYabin Cui
26*01826a49SYabin Cui
27*01826a49SYabin Cui /*-*******************************************************
28*01826a49SYabin Cui * Constants
29*01826a49SYabin Cui *********************************************************/
30*01826a49SYabin Cui static UNUSED_ATTR const U32 LL_base[MaxLL+1] = {
31*01826a49SYabin Cui 0, 1, 2, 3, 4, 5, 6, 7,
32*01826a49SYabin Cui 8, 9, 10, 11, 12, 13, 14, 15,
33*01826a49SYabin Cui 16, 18, 20, 22, 24, 28, 32, 40,
34*01826a49SYabin Cui 48, 64, 0x80, 0x100, 0x200, 0x400, 0x800, 0x1000,
35*01826a49SYabin Cui 0x2000, 0x4000, 0x8000, 0x10000 };
36*01826a49SYabin Cui
37*01826a49SYabin Cui static UNUSED_ATTR const U32 OF_base[MaxOff+1] = {
38*01826a49SYabin Cui 0, 1, 1, 5, 0xD, 0x1D, 0x3D, 0x7D,
39*01826a49SYabin Cui 0xFD, 0x1FD, 0x3FD, 0x7FD, 0xFFD, 0x1FFD, 0x3FFD, 0x7FFD,
40*01826a49SYabin Cui 0xFFFD, 0x1FFFD, 0x3FFFD, 0x7FFFD, 0xFFFFD, 0x1FFFFD, 0x3FFFFD, 0x7FFFFD,
41*01826a49SYabin Cui 0xFFFFFD, 0x1FFFFFD, 0x3FFFFFD, 0x7FFFFFD, 0xFFFFFFD, 0x1FFFFFFD, 0x3FFFFFFD, 0x7FFFFFFD };
42*01826a49SYabin Cui
43*01826a49SYabin Cui static UNUSED_ATTR const U8 OF_bits[MaxOff+1] = {
44*01826a49SYabin Cui 0, 1, 2, 3, 4, 5, 6, 7,
45*01826a49SYabin Cui 8, 9, 10, 11, 12, 13, 14, 15,
46*01826a49SYabin Cui 16, 17, 18, 19, 20, 21, 22, 23,
47*01826a49SYabin Cui 24, 25, 26, 27, 28, 29, 30, 31 };
48*01826a49SYabin Cui
49*01826a49SYabin Cui static UNUSED_ATTR const U32 ML_base[MaxML+1] = {
50*01826a49SYabin Cui 3, 4, 5, 6, 7, 8, 9, 10,
51*01826a49SYabin Cui 11, 12, 13, 14, 15, 16, 17, 18,
52*01826a49SYabin Cui 19, 20, 21, 22, 23, 24, 25, 26,
53*01826a49SYabin Cui 27, 28, 29, 30, 31, 32, 33, 34,
54*01826a49SYabin Cui 35, 37, 39, 41, 43, 47, 51, 59,
55*01826a49SYabin Cui 67, 83, 99, 0x83, 0x103, 0x203, 0x403, 0x803,
56*01826a49SYabin Cui 0x1003, 0x2003, 0x4003, 0x8003, 0x10003 };
57*01826a49SYabin Cui
58*01826a49SYabin Cui
59*01826a49SYabin Cui /*-*******************************************************
60*01826a49SYabin Cui * Decompression types
61*01826a49SYabin Cui *********************************************************/
62*01826a49SYabin Cui typedef struct {
63*01826a49SYabin Cui U32 fastMode;
64*01826a49SYabin Cui U32 tableLog;
65*01826a49SYabin Cui } ZSTD_seqSymbol_header;
66*01826a49SYabin Cui
67*01826a49SYabin Cui typedef struct {
68*01826a49SYabin Cui U16 nextState;
69*01826a49SYabin Cui BYTE nbAdditionalBits;
70*01826a49SYabin Cui BYTE nbBits;
71*01826a49SYabin Cui U32 baseValue;
72*01826a49SYabin Cui } ZSTD_seqSymbol;
73*01826a49SYabin Cui
74*01826a49SYabin Cui #define SEQSYMBOL_TABLE_SIZE(log) (1 + (1 << (log)))
75*01826a49SYabin Cui
76*01826a49SYabin Cui #define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE (sizeof(S16) * (MaxSeq + 1) + (1u << MaxFSELog) + sizeof(U64))
77*01826a49SYabin Cui #define ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32 ((ZSTD_BUILD_FSE_TABLE_WKSP_SIZE + sizeof(U32) - 1) / sizeof(U32))
78*01826a49SYabin Cui #define ZSTD_HUFFDTABLE_CAPACITY_LOG 12
79*01826a49SYabin Cui
80*01826a49SYabin Cui typedef struct {
81*01826a49SYabin Cui ZSTD_seqSymbol LLTable[SEQSYMBOL_TABLE_SIZE(LLFSELog)]; /* Note : Space reserved for FSE Tables */
82*01826a49SYabin Cui ZSTD_seqSymbol OFTable[SEQSYMBOL_TABLE_SIZE(OffFSELog)]; /* is also used as temporary workspace while building hufTable during DDict creation */
83*01826a49SYabin Cui ZSTD_seqSymbol MLTable[SEQSYMBOL_TABLE_SIZE(MLFSELog)]; /* and therefore must be at least HUF_DECOMPRESS_WORKSPACE_SIZE large */
84*01826a49SYabin Cui HUF_DTable hufTable[HUF_DTABLE_SIZE(ZSTD_HUFFDTABLE_CAPACITY_LOG)]; /* can accommodate HUF_decompress4X */
85*01826a49SYabin Cui U32 rep[ZSTD_REP_NUM];
86*01826a49SYabin Cui U32 workspace[ZSTD_BUILD_FSE_TABLE_WKSP_SIZE_U32];
87*01826a49SYabin Cui } ZSTD_entropyDTables_t;
88*01826a49SYabin Cui
89*01826a49SYabin Cui typedef enum { ZSTDds_getFrameHeaderSize, ZSTDds_decodeFrameHeader,
90*01826a49SYabin Cui ZSTDds_decodeBlockHeader, ZSTDds_decompressBlock,
91*01826a49SYabin Cui ZSTDds_decompressLastBlock, ZSTDds_checkChecksum,
92*01826a49SYabin Cui ZSTDds_decodeSkippableHeader, ZSTDds_skipFrame } ZSTD_dStage;
93*01826a49SYabin Cui
94*01826a49SYabin Cui typedef enum { zdss_init=0, zdss_loadHeader,
95*01826a49SYabin Cui zdss_read, zdss_load, zdss_flush } ZSTD_dStreamStage;
96*01826a49SYabin Cui
97*01826a49SYabin Cui typedef enum {
98*01826a49SYabin Cui ZSTD_use_indefinitely = -1, /* Use the dictionary indefinitely */
99*01826a49SYabin Cui ZSTD_dont_use = 0, /* Do not use the dictionary (if one exists free it) */
100*01826a49SYabin Cui ZSTD_use_once = 1 /* Use the dictionary once and set to ZSTD_dont_use */
101*01826a49SYabin Cui } ZSTD_dictUses_e;
102*01826a49SYabin Cui
103*01826a49SYabin Cui /* Hashset for storing references to multiple ZSTD_DDict within ZSTD_DCtx */
104*01826a49SYabin Cui typedef struct {
105*01826a49SYabin Cui const ZSTD_DDict** ddictPtrTable;
106*01826a49SYabin Cui size_t ddictPtrTableSize;
107*01826a49SYabin Cui size_t ddictPtrCount;
108*01826a49SYabin Cui } ZSTD_DDictHashSet;
109*01826a49SYabin Cui
110*01826a49SYabin Cui #ifndef ZSTD_DECODER_INTERNAL_BUFFER
111*01826a49SYabin Cui # define ZSTD_DECODER_INTERNAL_BUFFER (1 << 16)
112*01826a49SYabin Cui #endif
113*01826a49SYabin Cui
114*01826a49SYabin Cui #define ZSTD_LBMIN 64
115*01826a49SYabin Cui #define ZSTD_LBMAX (128 << 10)
116*01826a49SYabin Cui
117*01826a49SYabin Cui /* extra buffer, compensates when dst is not large enough to store litBuffer */
118*01826a49SYabin Cui #define ZSTD_LITBUFFEREXTRASIZE BOUNDED(ZSTD_LBMIN, ZSTD_DECODER_INTERNAL_BUFFER, ZSTD_LBMAX)
119*01826a49SYabin Cui
120*01826a49SYabin Cui typedef enum {
121*01826a49SYabin Cui ZSTD_not_in_dst = 0, /* Stored entirely within litExtraBuffer */
122*01826a49SYabin Cui ZSTD_in_dst = 1, /* Stored entirely within dst (in memory after current output write) */
123*01826a49SYabin Cui ZSTD_split = 2 /* Split between litExtraBuffer and dst */
124*01826a49SYabin Cui } ZSTD_litLocation_e;
125*01826a49SYabin Cui
126*01826a49SYabin Cui struct ZSTD_DCtx_s
127*01826a49SYabin Cui {
128*01826a49SYabin Cui const ZSTD_seqSymbol* LLTptr;
129*01826a49SYabin Cui const ZSTD_seqSymbol* MLTptr;
130*01826a49SYabin Cui const ZSTD_seqSymbol* OFTptr;
131*01826a49SYabin Cui const HUF_DTable* HUFptr;
132*01826a49SYabin Cui ZSTD_entropyDTables_t entropy;
133*01826a49SYabin Cui U32 workspace[HUF_DECOMPRESS_WORKSPACE_SIZE_U32]; /* space needed when building huffman tables */
134*01826a49SYabin Cui const void* previousDstEnd; /* detect continuity */
135*01826a49SYabin Cui const void* prefixStart; /* start of current segment */
136*01826a49SYabin Cui const void* virtualStart; /* virtual start of previous segment if it was just before current one */
137*01826a49SYabin Cui const void* dictEnd; /* end of previous segment */
138*01826a49SYabin Cui size_t expected;
139*01826a49SYabin Cui ZSTD_frameHeader fParams;
140*01826a49SYabin Cui U64 processedCSize;
141*01826a49SYabin Cui U64 decodedSize;
142*01826a49SYabin Cui blockType_e bType; /* used in ZSTD_decompressContinue(), store blockType between block header decoding and block decompression stages */
143*01826a49SYabin Cui ZSTD_dStage stage;
144*01826a49SYabin Cui U32 litEntropy;
145*01826a49SYabin Cui U32 fseEntropy;
146*01826a49SYabin Cui XXH64_state_t xxhState;
147*01826a49SYabin Cui size_t headerSize;
148*01826a49SYabin Cui ZSTD_format_e format;
149*01826a49SYabin Cui ZSTD_forceIgnoreChecksum_e forceIgnoreChecksum; /* User specified: if == 1, will ignore checksums in compressed frame. Default == 0 */
150*01826a49SYabin Cui U32 validateChecksum; /* if == 1, will validate checksum. Is == 1 if (fParams.checksumFlag == 1) and (forceIgnoreChecksum == 0). */
151*01826a49SYabin Cui const BYTE* litPtr;
152*01826a49SYabin Cui ZSTD_customMem customMem;
153*01826a49SYabin Cui size_t litSize;
154*01826a49SYabin Cui size_t rleSize;
155*01826a49SYabin Cui size_t staticSize;
156*01826a49SYabin Cui int isFrameDecompression;
157*01826a49SYabin Cui #if DYNAMIC_BMI2 != 0
158*01826a49SYabin Cui int bmi2; /* == 1 if the CPU supports BMI2 and 0 otherwise. CPU support is determined dynamically once per context lifetime. */
159*01826a49SYabin Cui #endif
160*01826a49SYabin Cui
161*01826a49SYabin Cui /* dictionary */
162*01826a49SYabin Cui ZSTD_DDict* ddictLocal;
163*01826a49SYabin Cui const ZSTD_DDict* ddict; /* set by ZSTD_initDStream_usingDDict(), or ZSTD_DCtx_refDDict() */
164*01826a49SYabin Cui U32 dictID;
165*01826a49SYabin Cui int ddictIsCold; /* if == 1 : dictionary is "new" for working context, and presumed "cold" (not in cpu cache) */
166*01826a49SYabin Cui ZSTD_dictUses_e dictUses;
167*01826a49SYabin Cui ZSTD_DDictHashSet* ddictSet; /* Hash set for multiple ddicts */
168*01826a49SYabin Cui ZSTD_refMultipleDDicts_e refMultipleDDicts; /* User specified: if == 1, will allow references to multiple DDicts. Default == 0 (disabled) */
169*01826a49SYabin Cui int disableHufAsm;
170*01826a49SYabin Cui int maxBlockSizeParam;
171*01826a49SYabin Cui
172*01826a49SYabin Cui /* streaming */
173*01826a49SYabin Cui ZSTD_dStreamStage streamStage;
174*01826a49SYabin Cui char* inBuff;
175*01826a49SYabin Cui size_t inBuffSize;
176*01826a49SYabin Cui size_t inPos;
177*01826a49SYabin Cui size_t maxWindowSize;
178*01826a49SYabin Cui char* outBuff;
179*01826a49SYabin Cui size_t outBuffSize;
180*01826a49SYabin Cui size_t outStart;
181*01826a49SYabin Cui size_t outEnd;
182*01826a49SYabin Cui size_t lhSize;
183*01826a49SYabin Cui #if defined(ZSTD_LEGACY_SUPPORT) && (ZSTD_LEGACY_SUPPORT>=1)
184*01826a49SYabin Cui void* legacyContext;
185*01826a49SYabin Cui U32 previousLegacyVersion;
186*01826a49SYabin Cui U32 legacyVersion;
187*01826a49SYabin Cui #endif
188*01826a49SYabin Cui U32 hostageByte;
189*01826a49SYabin Cui int noForwardProgress;
190*01826a49SYabin Cui ZSTD_bufferMode_e outBufferMode;
191*01826a49SYabin Cui ZSTD_outBuffer expectedOutBuffer;
192*01826a49SYabin Cui
193*01826a49SYabin Cui /* workspace */
194*01826a49SYabin Cui BYTE* litBuffer;
195*01826a49SYabin Cui const BYTE* litBufferEnd;
196*01826a49SYabin Cui ZSTD_litLocation_e litBufferLocation;
197*01826a49SYabin Cui BYTE litExtraBuffer[ZSTD_LITBUFFEREXTRASIZE + WILDCOPY_OVERLENGTH]; /* literal buffer can be split between storage within dst and within this scratch buffer */
198*01826a49SYabin Cui BYTE headerBuffer[ZSTD_FRAMEHEADERSIZE_MAX];
199*01826a49SYabin Cui
200*01826a49SYabin Cui size_t oversizedDuration;
201*01826a49SYabin Cui
202*01826a49SYabin Cui #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
203*01826a49SYabin Cui void const* dictContentBeginForFuzzing;
204*01826a49SYabin Cui void const* dictContentEndForFuzzing;
205*01826a49SYabin Cui #endif
206*01826a49SYabin Cui
207*01826a49SYabin Cui /* Tracing */
208*01826a49SYabin Cui #if ZSTD_TRACE
209*01826a49SYabin Cui ZSTD_TraceCtx traceCtx;
210*01826a49SYabin Cui #endif
211*01826a49SYabin Cui }; /* typedef'd to ZSTD_DCtx within "zstd.h" */
212*01826a49SYabin Cui
ZSTD_DCtx_get_bmi2(const struct ZSTD_DCtx_s * dctx)213*01826a49SYabin Cui MEM_STATIC int ZSTD_DCtx_get_bmi2(const struct ZSTD_DCtx_s *dctx) {
214*01826a49SYabin Cui #if DYNAMIC_BMI2 != 0
215*01826a49SYabin Cui return dctx->bmi2;
216*01826a49SYabin Cui #else
217*01826a49SYabin Cui (void)dctx;
218*01826a49SYabin Cui return 0;
219*01826a49SYabin Cui #endif
220*01826a49SYabin Cui }
221*01826a49SYabin Cui
222*01826a49SYabin Cui /*-*******************************************************
223*01826a49SYabin Cui * Shared internal functions
224*01826a49SYabin Cui *********************************************************/
225*01826a49SYabin Cui
226*01826a49SYabin Cui /*! ZSTD_loadDEntropy() :
227*01826a49SYabin Cui * dict : must point at beginning of a valid zstd dictionary.
228*01826a49SYabin Cui * @return : size of dictionary header (size of magic number + dict ID + entropy tables) */
229*01826a49SYabin Cui size_t ZSTD_loadDEntropy(ZSTD_entropyDTables_t* entropy,
230*01826a49SYabin Cui const void* const dict, size_t const dictSize);
231*01826a49SYabin Cui
232*01826a49SYabin Cui /*! ZSTD_checkContinuity() :
233*01826a49SYabin Cui * check if next `dst` follows previous position, where decompression ended.
234*01826a49SYabin Cui * If yes, do nothing (continue on current segment).
235*01826a49SYabin Cui * If not, classify previous segment as "external dictionary", and start a new segment.
236*01826a49SYabin Cui * This function cannot fail. */
237*01826a49SYabin Cui void ZSTD_checkContinuity(ZSTD_DCtx* dctx, const void* dst, size_t dstSize);
238*01826a49SYabin Cui
239*01826a49SYabin Cui
240*01826a49SYabin Cui #endif /* ZSTD_DECOMPRESS_INTERNAL_H */
241