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