1 | /* |
2 | * Copyright (c) Meta Platforms, Inc. and affiliates. |
3 | * All rights reserved. |
4 | * |
5 | * This source code is licensed under both the BSD-style license (found in the |
6 | * LICENSE file in the root directory of this source tree) and the GPLv2 (found |
7 | * in the COPYING file in the root directory of this source tree). |
8 | * You may select, at your option, one of the above-listed licenses. |
9 | */ |
10 | |
11 | #ifndef ZSTD_CCOMMON_H_MODULE |
12 | #define ZSTD_CCOMMON_H_MODULE |
13 | |
14 | /* this module contains definitions which must be identical |
15 | * across compression, decompression and dictBuilder. |
16 | * It also contains a few functions useful to at least 2 of them |
17 | * and which benefit from being inlined */ |
18 | |
19 | /*-************************************* |
20 | * Dependencies |
21 | ***************************************/ |
22 | #include "compiler.h" |
23 | #include "cpu.h" |
24 | #include "mem.h" |
25 | #include "debug.h" /* assert, DEBUGLOG, RAWLOG, g_debuglevel */ |
26 | #include "error_private.h" |
27 | #define ZSTD_STATIC_LINKING_ONLY |
28 | #include "../zstd.h" |
29 | #define FSE_STATIC_LINKING_ONLY |
30 | #include "fse.h" |
31 | #include "huf.h" |
32 | #ifndef XXH_STATIC_LINKING_ONLY |
33 | # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */ |
34 | #endif |
35 | #include "xxhash.h" /* XXH_reset, update, digest */ |
36 | #ifndef ZSTD_NO_TRACE |
37 | # include "zstd_trace.h" |
38 | #else |
39 | # define ZSTD_TRACE 0 |
40 | #endif |
41 | |
42 | #if defined (__cplusplus) |
43 | extern "C" { |
44 | #endif |
45 | |
46 | /* ---- static assert (debug) --- */ |
47 | #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c) |
48 | #define ZSTD_isError ERR_isError /* for inlining */ |
49 | #define FSE_isError ERR_isError |
50 | #define HUF_isError ERR_isError |
51 | |
52 | |
53 | /*-************************************* |
54 | * shared macros |
55 | ***************************************/ |
56 | #undef MIN |
57 | #undef MAX |
58 | #define MIN(a,b) ((a)<(b) ? (a) : (b)) |
59 | #define MAX(a,b) ((a)>(b) ? (a) : (b)) |
60 | #define BOUNDED(min,val,max) (MAX(min,MIN(val,max))) |
61 | |
62 | |
63 | /*-************************************* |
64 | * Common constants |
65 | ***************************************/ |
66 | #define ZSTD_OPT_NUM (1<<12) |
67 | |
68 | #define ZSTD_REP_NUM 3 /* number of repcodes */ |
69 | static UNUSED_ATTR const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 }; |
70 | |
71 | #define KB *(1 <<10) |
72 | #define MB *(1 <<20) |
73 | #define GB *(1U<<30) |
74 | |
75 | #define BIT7 128 |
76 | #define BIT6 64 |
77 | #define BIT5 32 |
78 | #define BIT4 16 |
79 | #define BIT1 2 |
80 | #define BIT0 1 |
81 | |
82 | #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10 |
83 | static UNUSED_ATTR const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 }; |
84 | static UNUSED_ATTR const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 }; |
85 | |
86 | #define ZSTD_FRAMEIDSIZE 4 /* magic number size */ |
87 | |
88 | #define 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */ |
89 | static UNUSED_ATTR const size_t = ZSTD_BLOCKHEADERSIZE; |
90 | typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e; |
91 | |
92 | #define ZSTD_FRAMECHECKSUMSIZE 4 |
93 | |
94 | #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ |
95 | #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */) /* for a non-null block */ |
96 | #define MIN_LITERALS_FOR_4_STREAMS 6 |
97 | |
98 | typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e; |
99 | |
100 | #define LONGNBSEQ 0x7F00 |
101 | |
102 | #define MINMATCH 3 |
103 | |
104 | #define Litbits 8 |
105 | #define LitHufLog 11 |
106 | #define MaxLit ((1<<Litbits) - 1) |
107 | #define MaxML 52 |
108 | #define MaxLL 35 |
109 | #define DefaultMaxOff 28 |
110 | #define MaxOff 31 |
111 | #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ |
112 | #define MLFSELog 9 |
113 | #define LLFSELog 9 |
114 | #define OffFSELog 8 |
115 | #define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog) |
116 | #define MaxMLBits 16 |
117 | #define MaxLLBits 16 |
118 | |
119 | #define 128 /* header + <= 127 byte tree description */ |
120 | /* Each table cannot take more than #symbols * FSELog bits */ |
121 | #define (((MaxML + 1) * MLFSELog + (MaxLL + 1) * LLFSELog + (MaxOff + 1) * OffFSELog + 7) / 8) |
122 | |
123 | static UNUSED_ATTR const U8 LL_bits[MaxLL+1] = { |
124 | 0, 0, 0, 0, 0, 0, 0, 0, |
125 | 0, 0, 0, 0, 0, 0, 0, 0, |
126 | 1, 1, 1, 1, 2, 2, 3, 3, |
127 | 4, 6, 7, 8, 9,10,11,12, |
128 | 13,14,15,16 |
129 | }; |
130 | static UNUSED_ATTR const S16 LL_defaultNorm[MaxLL+1] = { |
131 | 4, 3, 2, 2, 2, 2, 2, 2, |
132 | 2, 2, 2, 2, 2, 1, 1, 1, |
133 | 2, 2, 2, 2, 2, 2, 2, 2, |
134 | 2, 3, 2, 1, 1, 1, 1, 1, |
135 | -1,-1,-1,-1 |
136 | }; |
137 | #define LL_DEFAULTNORMLOG 6 /* for static allocation */ |
138 | static UNUSED_ATTR const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG; |
139 | |
140 | static UNUSED_ATTR const U8 ML_bits[MaxML+1] = { |
141 | 0, 0, 0, 0, 0, 0, 0, 0, |
142 | 0, 0, 0, 0, 0, 0, 0, 0, |
143 | 0, 0, 0, 0, 0, 0, 0, 0, |
144 | 0, 0, 0, 0, 0, 0, 0, 0, |
145 | 1, 1, 1, 1, 2, 2, 3, 3, |
146 | 4, 4, 5, 7, 8, 9,10,11, |
147 | 12,13,14,15,16 |
148 | }; |
149 | static UNUSED_ATTR const S16 ML_defaultNorm[MaxML+1] = { |
150 | 1, 4, 3, 2, 2, 2, 2, 2, |
151 | 2, 1, 1, 1, 1, 1, 1, 1, |
152 | 1, 1, 1, 1, 1, 1, 1, 1, |
153 | 1, 1, 1, 1, 1, 1, 1, 1, |
154 | 1, 1, 1, 1, 1, 1, 1, 1, |
155 | 1, 1, 1, 1, 1, 1,-1,-1, |
156 | -1,-1,-1,-1,-1 |
157 | }; |
158 | #define ML_DEFAULTNORMLOG 6 /* for static allocation */ |
159 | static UNUSED_ATTR const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG; |
160 | |
161 | static UNUSED_ATTR const S16 OF_defaultNorm[DefaultMaxOff+1] = { |
162 | 1, 1, 1, 1, 1, 1, 2, 2, |
163 | 2, 1, 1, 1, 1, 1, 1, 1, |
164 | 1, 1, 1, 1, 1, 1, 1, 1, |
165 | -1,-1,-1,-1,-1 |
166 | }; |
167 | #define OF_DEFAULTNORMLOG 5 /* for static allocation */ |
168 | static UNUSED_ATTR const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; |
169 | |
170 | |
171 | /*-******************************************* |
172 | * Shared functions to include for inlining |
173 | *********************************************/ |
174 | static void ZSTD_copy8(void* dst, const void* src) { |
175 | #if defined(ZSTD_ARCH_ARM_NEON) |
176 | vst1_u8((uint8_t*)dst, vld1_u8((const uint8_t*)src)); |
177 | #else |
178 | ZSTD_memcpy(dst, src, 8); |
179 | #endif |
180 | } |
181 | #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; } |
182 | |
183 | /* Need to use memmove here since the literal buffer can now be located within |
184 | the dst buffer. In circumstances where the op "catches up" to where the |
185 | literal buffer is, there can be partial overlaps in this call on the final |
186 | copy if the literal is being shifted by less than 16 bytes. */ |
187 | static void ZSTD_copy16(void* dst, const void* src) { |
188 | #if defined(ZSTD_ARCH_ARM_NEON) |
189 | vst1q_u8((uint8_t*)dst, vld1q_u8((const uint8_t*)src)); |
190 | #elif defined(ZSTD_ARCH_X86_SSE2) |
191 | _mm_storeu_si128((__m128i*)dst, _mm_loadu_si128((const __m128i*)src)); |
192 | #elif defined(__clang__) |
193 | ZSTD_memmove(dst, src, 16); |
194 | #else |
195 | /* ZSTD_memmove is not inlined properly by gcc */ |
196 | BYTE copy16_buf[16]; |
197 | ZSTD_memcpy(copy16_buf, src, 16); |
198 | ZSTD_memcpy(dst, copy16_buf, 16); |
199 | #endif |
200 | } |
201 | #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; } |
202 | |
203 | #define WILDCOPY_OVERLENGTH 32 |
204 | #define WILDCOPY_VECLEN 16 |
205 | |
206 | typedef enum { |
207 | ZSTD_no_overlap, |
208 | ZSTD_overlap_src_before_dst |
209 | /* ZSTD_overlap_dst_before_src, */ |
210 | } ZSTD_overlap_e; |
211 | |
212 | /*! ZSTD_wildcopy() : |
213 | * Custom version of ZSTD_memcpy(), can over read/write up to WILDCOPY_OVERLENGTH bytes (if length==0) |
214 | * @param ovtype controls the overlap detection |
215 | * - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart. |
216 | * - ZSTD_overlap_src_before_dst: The src and dst may overlap, but they MUST be at least 8 bytes apart. |
217 | * The src buffer must be before the dst buffer. |
218 | */ |
219 | MEM_STATIC FORCE_INLINE_ATTR |
220 | void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype) |
221 | { |
222 | ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src; |
223 | const BYTE* ip = (const BYTE*)src; |
224 | BYTE* op = (BYTE*)dst; |
225 | BYTE* const oend = op + length; |
226 | |
227 | if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) { |
228 | /* Handle short offset copies. */ |
229 | do { |
230 | COPY8(op, ip) |
231 | } while (op < oend); |
232 | } else { |
233 | assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN); |
234 | /* Separate out the first COPY16() call because the copy length is |
235 | * almost certain to be short, so the branches have different |
236 | * probabilities. Since it is almost certain to be short, only do |
237 | * one COPY16() in the first call. Then, do two calls per loop since |
238 | * at that point it is more likely to have a high trip count. |
239 | */ |
240 | ZSTD_copy16(op, ip); |
241 | if (16 >= length) return; |
242 | op += 16; |
243 | ip += 16; |
244 | do { |
245 | COPY16(op, ip); |
246 | COPY16(op, ip); |
247 | } |
248 | while (op < oend); |
249 | } |
250 | } |
251 | |
252 | MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize) |
253 | { |
254 | size_t const length = MIN(dstCapacity, srcSize); |
255 | if (length > 0) { |
256 | ZSTD_memcpy(dst, src, length); |
257 | } |
258 | return length; |
259 | } |
260 | |
261 | /* define "workspace is too large" as this number of times larger than needed */ |
262 | #define ZSTD_WORKSPACETOOLARGE_FACTOR 3 |
263 | |
264 | /* when workspace is continuously too large |
265 | * during at least this number of times, |
266 | * context's memory usage is considered wasteful, |
267 | * because it's sized to handle a worst case scenario which rarely happens. |
268 | * In which case, resize it down to free some memory */ |
269 | #define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128 |
270 | |
271 | /* Controls whether the input/output buffer is buffered or stable. */ |
272 | typedef enum { |
273 | ZSTD_bm_buffered = 0, /* Buffer the input/output */ |
274 | ZSTD_bm_stable = 1 /* ZSTD_inBuffer/ZSTD_outBuffer is stable */ |
275 | } ZSTD_bufferMode_e; |
276 | |
277 | |
278 | /*-******************************************* |
279 | * Private declarations |
280 | *********************************************/ |
281 | typedef struct seqDef_s { |
282 | U32 offBase; /* offBase == Offset + ZSTD_REP_NUM, or repcode 1,2,3 */ |
283 | U16 litLength; |
284 | U16 mlBase; /* mlBase == matchLength - MINMATCH */ |
285 | } seqDef; |
286 | |
287 | /* Controls whether seqStore has a single "long" litLength or matchLength. See seqStore_t. */ |
288 | typedef enum { |
289 | ZSTD_llt_none = 0, /* no longLengthType */ |
290 | ZSTD_llt_literalLength = 1, /* represents a long literal */ |
291 | ZSTD_llt_matchLength = 2 /* represents a long match */ |
292 | } ZSTD_longLengthType_e; |
293 | |
294 | typedef struct { |
295 | seqDef* sequencesStart; |
296 | seqDef* sequences; /* ptr to end of sequences */ |
297 | BYTE* litStart; |
298 | BYTE* lit; /* ptr to end of literals */ |
299 | BYTE* llCode; |
300 | BYTE* mlCode; |
301 | BYTE* ofCode; |
302 | size_t maxNbSeq; |
303 | size_t maxNbLit; |
304 | |
305 | /* longLengthPos and longLengthType to allow us to represent either a single litLength or matchLength |
306 | * in the seqStore that has a value larger than U16 (if it exists). To do so, we increment |
307 | * the existing value of the litLength or matchLength by 0x10000. |
308 | */ |
309 | ZSTD_longLengthType_e longLengthType; |
310 | U32 longLengthPos; /* Index of the sequence to apply long length modification to */ |
311 | } seqStore_t; |
312 | |
313 | typedef struct { |
314 | U32 litLength; |
315 | U32 matchLength; |
316 | } ZSTD_sequenceLength; |
317 | |
318 | /** |
319 | * Returns the ZSTD_sequenceLength for the given sequences. It handles the decoding of long sequences |
320 | * indicated by longLengthPos and longLengthType, and adds MINMATCH back to matchLength. |
321 | */ |
322 | MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const* seqStore, seqDef const* seq) |
323 | { |
324 | ZSTD_sequenceLength seqLen; |
325 | seqLen.litLength = seq->litLength; |
326 | seqLen.matchLength = seq->mlBase + MINMATCH; |
327 | if (seqStore->longLengthPos == (U32)(seq - seqStore->sequencesStart)) { |
328 | if (seqStore->longLengthType == ZSTD_llt_literalLength) { |
329 | seqLen.litLength += 0x10000; |
330 | } |
331 | if (seqStore->longLengthType == ZSTD_llt_matchLength) { |
332 | seqLen.matchLength += 0x10000; |
333 | } |
334 | } |
335 | return seqLen; |
336 | } |
337 | |
338 | /** |
339 | * Contains the compressed frame size and an upper-bound for the decompressed frame size. |
340 | * Note: before using `compressedSize`, check for errors using ZSTD_isError(). |
341 | * similarly, before using `decompressedBound`, check for errors using: |
342 | * `decompressedBound != ZSTD_CONTENTSIZE_ERROR` |
343 | */ |
344 | typedef struct { |
345 | size_t nbBlocks; |
346 | size_t compressedSize; |
347 | unsigned long long decompressedBound; |
348 | } ZSTD_frameSizeInfo; /* decompress & legacy */ |
349 | |
350 | const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */ |
351 | int ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */ |
352 | |
353 | |
354 | /* ZSTD_invalidateRepCodes() : |
355 | * ensures next compression will not use repcodes from previous block. |
356 | * Note : only works with regular variant; |
357 | * do not use with extDict variant ! */ |
358 | void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */ |
359 | |
360 | |
361 | typedef struct { |
362 | blockType_e blockType; |
363 | U32 lastBlock; |
364 | U32 origSize; |
365 | } blockProperties_t; /* declared here for decompress and fullbench */ |
366 | |
367 | /*! ZSTD_getcBlockSize() : |
368 | * Provides the size of compressed block from block header `src` */ |
369 | /* Used by: decompress, fullbench (does not get its definition from here) */ |
370 | size_t ZSTD_getcBlockSize(const void* src, size_t srcSize, |
371 | blockProperties_t* bpPtr); |
372 | |
373 | /*! ZSTD_decodeSeqHeaders() : |
374 | * decode sequence header from src */ |
375 | /* Used by: decompress, fullbench (does not get its definition from here) */ |
376 | size_t (ZSTD_DCtx* dctx, int* nbSeqPtr, |
377 | const void* src, size_t srcSize); |
378 | |
379 | /** |
380 | * @returns true iff the CPU supports dynamic BMI2 dispatch. |
381 | */ |
382 | MEM_STATIC int ZSTD_cpuSupportsBmi2(void) |
383 | { |
384 | ZSTD_cpuid_t cpuid = ZSTD_cpuid(); |
385 | return ZSTD_cpuid_bmi1(cpuid) && ZSTD_cpuid_bmi2(cpuid); |
386 | } |
387 | |
388 | #if defined (__cplusplus) |
389 | } |
390 | #endif |
391 | |
392 | #endif /* ZSTD_CCOMMON_H_MODULE */ |
393 | |