2 * Copyright (c) Meta Platforms, Inc. and affiliates.
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.
11 #ifndef ZSTD_CCOMMON_H_MODULE
12 #define ZSTD_CCOMMON_H_MODULE
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 */
19 /*-*************************************
21 ***************************************/
25 #include "debug.h" /* assert, DEBUGLOG, RAWLOG, g_debuglevel */
26 #include "error_private.h"
27 #define ZSTD_STATIC_LINKING_ONLY
29 #define FSE_STATIC_LINKING_ONLY
32 #ifndef XXH_STATIC_LINKING_ONLY
33 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
35 #include "xxhash.h" /* XXH_reset, update, digest */
37 # include "zstd_trace.h"
42 #if defined (__cplusplus)
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
53 /*-*************************************
55 ***************************************/
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)))
63 /*-*************************************
65 ***************************************/
66 #define ZSTD_OPT_NUM (1<<12)
68 #define ZSTD_REP_NUM 3 /* number of repcodes */
69 static UNUSED_ATTR const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
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 };
86 #define ZSTD_FRAMEIDSIZE 4 /* magic number size */
88 #define ZSTD_BLOCKHEADERSIZE 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 = ZSTD_BLOCKHEADERSIZE;
90 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
92 #define ZSTD_FRAMECHECKSUMSIZE 4
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
98 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
100 #define LONGNBSEQ 0x7F00
106 #define MaxLit ((1<<Litbits) - 1)
109 #define DefaultMaxOff 28
111 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
115 #define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
119 #define ZSTD_MAX_HUF_HEADER_SIZE 128 /* header + <= 127 byte tree description */
120 /* Each table cannot take more than #symbols * FSELog bits */
121 #define ZSTD_MAX_FSE_HEADERS_SIZE (((MaxML + 1) * MLFSELog + (MaxLL + 1) * LLFSELog + (MaxOff + 1) * OffFSELog + 7) / 8)
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,
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,
137 #define LL_DEFAULTNORMLOG 6 /* for static allocation */
138 static UNUSED_ATTR const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
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,
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,
158 #define ML_DEFAULTNORMLOG 6 /* for static allocation */
159 static UNUSED_ATTR const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
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,
167 #define OF_DEFAULTNORMLOG 5 /* for static allocation */
168 static UNUSED_ATTR const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
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));
178 ZSTD_memcpy(dst, src, 8);
181 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
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);
195 /* ZSTD_memmove is not inlined properly by gcc */
197 ZSTD_memcpy(copy16_buf, src, 16);
198 ZSTD_memcpy(dst, copy16_buf, 16);
201 #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; }
203 #define WILDCOPY_OVERLENGTH 32
204 #define WILDCOPY_VECLEN 16
208 ZSTD_overlap_src_before_dst
209 /* ZSTD_overlap_dst_before_src, */
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.
219 MEM_STATIC FORCE_INLINE_ATTR
220 void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
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;
227 if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) {
228 /* Handle short offset copies. */
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.
241 if (16 >= length) return;
252 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
254 size_t const length = MIN(dstCapacity, srcSize);
256 ZSTD_memcpy(dst, src, length);
261 /* define "workspace is too large" as this number of times larger than needed */
262 #define ZSTD_WORKSPACETOOLARGE_FACTOR 3
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
271 /* Controls whether the input/output buffer is buffered or stable. */
273 ZSTD_bm_buffered = 0, /* Buffer the input/output */
274 ZSTD_bm_stable = 1 /* ZSTD_inBuffer/ZSTD_outBuffer is stable */
278 /*-*******************************************
279 * Private declarations
280 *********************************************/
281 typedef struct seqDef_s {
282 U32 offBase; /* offBase == Offset + ZSTD_REP_NUM, or repcode 1,2,3 */
284 U16 mlBase; /* mlBase == matchLength - MINMATCH */
287 /* Controls whether seqStore has a single "long" litLength or matchLength. See seqStore_t. */
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;
295 seqDef* sequencesStart;
296 seqDef* sequences; /* ptr to end of sequences */
298 BYTE* lit; /* ptr to end of literals */
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.
309 ZSTD_longLengthType_e longLengthType;
310 U32 longLengthPos; /* Index of the sequence to apply long length modification to */
316 } ZSTD_sequenceLength;
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.
322 MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const* seqStore, seqDef const* seq)
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;
331 if (seqStore->longLengthType == ZSTD_llt_matchLength) {
332 seqLen.matchLength += 0x10000;
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`
346 size_t compressedSize;
347 unsigned long long decompressedBound;
348 } ZSTD_frameSizeInfo; /* decompress & legacy */
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) */
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) */
362 blockType_e blockType;
365 } blockProperties_t; /* declared here for decompress and fullbench */
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);
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_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
377 const void* src, size_t srcSize);
380 * @returns true iff the CPU supports dynamic BMI2 dispatch.
382 MEM_STATIC int ZSTD_cpuSupportsBmi2(void)
384 ZSTD_cpuid_t cpuid = ZSTD_cpuid();
385 return ZSTD_cpuid_bmi1(cpuid) && ZSTD_cpuid_bmi2(cpuid);
388 #if defined (__cplusplus)
392 #endif /* ZSTD_CCOMMON_H_MODULE */