1 /*
2 * Copyright (c) Yann Collet, Facebook, Inc.
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 #define HUF_STATIC_LINKING_ONLY
32 #include "huf.h"
33 #ifndef XXH_STATIC_LINKING_ONLY
34 # define XXH_STATIC_LINKING_ONLY /* XXH64_state_t */
35 #endif
36 #include "xxhash.h" /* XXH_reset, update, digest */
37 #ifndef ZSTD_NO_TRACE
38 # include "zstd_trace.h"
39 #else
40 # define ZSTD_TRACE 0
41 #endif
42
43 #if defined (__cplusplus)
44 extern "C" {
45 #endif
46
47 /* ---- static assert (debug) --- */
48 #define ZSTD_STATIC_ASSERT(c) DEBUG_STATIC_ASSERT(c)
49 #define ZSTD_isError ERR_isError /* for inlining */
50 #define FSE_isError ERR_isError
51 #define HUF_isError ERR_isError
52
53
54 /*-*************************************
55 * shared macros
56 ***************************************/
57 #undef MIN
58 #undef MAX
59 #define MIN(a,b) ((a)<(b) ? (a) : (b))
60 #define MAX(a,b) ((a)>(b) ? (a) : (b))
61 #define BOUNDED(min,val,max) (MAX(min,MIN(val,max)))
62
63
64 /*-*************************************
65 * Common constants
66 ***************************************/
67 #define ZSTD_OPT_NUM (1<<12)
68
69 #define ZSTD_REP_NUM 3 /* number of repcodes */
70 #define ZSTD_REP_MOVE (ZSTD_REP_NUM-1)
71 static UNUSED_ATTR const U32 repStartValue[ZSTD_REP_NUM] = { 1, 4, 8 };
72
73 #define KB *(1 <<10)
74 #define MB *(1 <<20)
75 #define GB *(1U<<30)
76
77 #define BIT7 128
78 #define BIT6 64
79 #define BIT5 32
80 #define BIT4 16
81 #define BIT1 2
82 #define BIT0 1
83
84 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
85 static UNUSED_ATTR const size_t ZSTD_fcs_fieldSize[4] = { 0, 2, 4, 8 };
86 static UNUSED_ATTR const size_t ZSTD_did_fieldSize[4] = { 0, 1, 2, 4 };
87
88 #define ZSTD_FRAMEIDSIZE 4 /* magic number size */
89
90 #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
91 static UNUSED_ATTR const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
92 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
93
94 #define ZSTD_FRAMECHECKSUMSIZE 4
95
96 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
97 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
98
99 #define HufLog 12
100 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
101
102 #define LONGNBSEQ 0x7F00
103
104 #define MINMATCH 3
105
106 #define Litbits 8
107 #define MaxLit ((1<<Litbits) - 1)
108 #define MaxML 52
109 #define MaxLL 35
110 #define DefaultMaxOff 28
111 #define MaxOff 31
112 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
113 #define MLFSELog 9
114 #define LLFSELog 9
115 #define OffFSELog 8
116 #define MaxFSELog MAX(MAX(MLFSELog, LLFSELog), OffFSELog)
117
118 #define ZSTD_MAX_HUF_HEADER_SIZE 128 /* header + <= 127 byte tree description */
119 /* Each table cannot take more than #symbols * FSELog bits */
120 #define ZSTD_MAX_FSE_HEADERS_SIZE (((MaxML + 1) * MLFSELog + (MaxLL + 1) * LLFSELog + (MaxOff + 1) * OffFSELog + 7) / 8)
121
122 static UNUSED_ATTR const U8 LL_bits[MaxLL+1] = {
123 0, 0, 0, 0, 0, 0, 0, 0,
124 0, 0, 0, 0, 0, 0, 0, 0,
125 1, 1, 1, 1, 2, 2, 3, 3,
126 4, 6, 7, 8, 9,10,11,12,
127 13,14,15,16
128 };
129 static UNUSED_ATTR const S16 LL_defaultNorm[MaxLL+1] = {
130 4, 3, 2, 2, 2, 2, 2, 2,
131 2, 2, 2, 2, 2, 1, 1, 1,
132 2, 2, 2, 2, 2, 2, 2, 2,
133 2, 3, 2, 1, 1, 1, 1, 1,
134 -1,-1,-1,-1
135 };
136 #define LL_DEFAULTNORMLOG 6 /* for static allocation */
137 static UNUSED_ATTR const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
138
139 static UNUSED_ATTR const U8 ML_bits[MaxML+1] = {
140 0, 0, 0, 0, 0, 0, 0, 0,
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 1, 1, 1, 1, 2, 2, 3, 3,
145 4, 4, 5, 7, 8, 9,10,11,
146 12,13,14,15,16
147 };
148 static UNUSED_ATTR const S16 ML_defaultNorm[MaxML+1] = {
149 1, 4, 3, 2, 2, 2, 2, 2,
150 2, 1, 1, 1, 1, 1, 1, 1,
151 1, 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
156 };
157 #define ML_DEFAULTNORMLOG 6 /* for static allocation */
158 static UNUSED_ATTR const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
159
160 static UNUSED_ATTR const S16 OF_defaultNorm[DefaultMaxOff+1] = {
161 1, 1, 1, 1, 1, 1, 2, 2,
162 2, 1, 1, 1, 1, 1, 1, 1,
163 1, 1, 1, 1, 1, 1, 1, 1,
164 -1,-1,-1,-1,-1
165 };
166 #define OF_DEFAULTNORMLOG 5 /* for static allocation */
167 static UNUSED_ATTR const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
168
169
170 /*-*******************************************
171 * Shared functions to include for inlining
172 *********************************************/
ZSTD_copy8(void * dst,const void * src)173 static void ZSTD_copy8(void* dst, const void* src) {
174 #if defined(ZSTD_ARCH_ARM_NEON)
175 vst1_u8((uint8_t*)dst, vld1_u8((const uint8_t*)src));
176 #else
177 ZSTD_memcpy(dst, src, 8);
178 #endif
179 }
180 #define COPY8(d,s) { ZSTD_copy8(d,s); d+=8; s+=8; }
181
182 /* Need to use memmove here since the literal buffer can now be located within
183 the dst buffer. In circumstances where the op "catches up" to where the
184 literal buffer is, there can be partial overlaps in this call on the final
185 copy if the literal is being shifted by less than 16 bytes. */
ZSTD_copy16(void * dst,const void * src)186 static void ZSTD_copy16(void* dst, const void* src) {
187 #if defined(ZSTD_ARCH_ARM_NEON)
188 vst1q_u8((uint8_t*)dst, vld1q_u8((const uint8_t*)src));
189 #elif defined(ZSTD_ARCH_X86_SSE2)
190 _mm_storeu_si128((__m128i*)dst, _mm_loadu_si128((const __m128i*)src));
191 #elif defined(__clang__)
192 ZSTD_memmove(dst, src, 16);
193 #else
194 /* ZSTD_memmove is not inlined properly by gcc */
195 BYTE copy16_buf[16];
196 ZSTD_memcpy(copy16_buf, src, 16);
197 ZSTD_memcpy(dst, copy16_buf, 16);
198 #endif
199 }
200 #define COPY16(d,s) { ZSTD_copy16(d,s); d+=16; s+=16; }
201
202 #define WILDCOPY_OVERLENGTH 32
203 #define WILDCOPY_VECLEN 16
204
205 typedef enum {
206 ZSTD_no_overlap,
207 ZSTD_overlap_src_before_dst
208 /* ZSTD_overlap_dst_before_src, */
209 } ZSTD_overlap_e;
210
211 /*! ZSTD_wildcopy() :
212 * Custom version of ZSTD_memcpy(), can over read/write up to WILDCOPY_OVERLENGTH bytes (if length==0)
213 * @param ovtype controls the overlap detection
214 * - ZSTD_no_overlap: The source and destination are guaranteed to be at least WILDCOPY_VECLEN bytes apart.
215 * - ZSTD_overlap_src_before_dst: The src and dst may overlap, but they MUST be at least 8 bytes apart.
216 * The src buffer must be before the dst buffer.
217 */
218 MEM_STATIC FORCE_INLINE_ATTR
ZSTD_wildcopy(void * dst,const void * src,ptrdiff_t length,ZSTD_overlap_e const ovtype)219 void ZSTD_wildcopy(void* dst, const void* src, ptrdiff_t length, ZSTD_overlap_e const ovtype)
220 {
221 ptrdiff_t diff = (BYTE*)dst - (const BYTE*)src;
222 const BYTE* ip = (const BYTE*)src;
223 BYTE* op = (BYTE*)dst;
224 BYTE* const oend = op + length;
225
226 if (ovtype == ZSTD_overlap_src_before_dst && diff < WILDCOPY_VECLEN) {
227 /* Handle short offset copies. */
228 do {
229 COPY8(op, ip)
230 } while (op < oend);
231 } else {
232 assert(diff >= WILDCOPY_VECLEN || diff <= -WILDCOPY_VECLEN);
233 /* Separate out the first COPY16() call because the copy length is
234 * almost certain to be short, so the branches have different
235 * probabilities. Since it is almost certain to be short, only do
236 * one COPY16() in the first call. Then, do two calls per loop since
237 * at that point it is more likely to have a high trip count.
238 */
239 #ifdef __aarch64__
240 do {
241 COPY16(op, ip);
242 }
243 while (op < oend);
244 #else
245 ZSTD_copy16(op, ip);
246 if (16 >= length) return;
247 op += 16;
248 ip += 16;
249 do {
250 COPY16(op, ip);
251 COPY16(op, ip);
252 }
253 while (op < oend);
254 #endif
255 }
256 }
257
ZSTD_limitCopy(void * dst,size_t dstCapacity,const void * src,size_t srcSize)258 MEM_STATIC size_t ZSTD_limitCopy(void* dst, size_t dstCapacity, const void* src, size_t srcSize)
259 {
260 size_t const length = MIN(dstCapacity, srcSize);
261 if (length > 0) {
262 ZSTD_memcpy(dst, src, length);
263 }
264 return length;
265 }
266
267 /* define "workspace is too large" as this number of times larger than needed */
268 #define ZSTD_WORKSPACETOOLARGE_FACTOR 3
269
270 /* when workspace is continuously too large
271 * during at least this number of times,
272 * context's memory usage is considered wasteful,
273 * because it's sized to handle a worst case scenario which rarely happens.
274 * In which case, resize it down to free some memory */
275 #define ZSTD_WORKSPACETOOLARGE_MAXDURATION 128
276
277 /* Controls whether the input/output buffer is buffered or stable. */
278 typedef enum {
279 ZSTD_bm_buffered = 0, /* Buffer the input/output */
280 ZSTD_bm_stable = 1 /* ZSTD_inBuffer/ZSTD_outBuffer is stable */
281 } ZSTD_bufferMode_e;
282
283
284 /*-*******************************************
285 * Private declarations
286 *********************************************/
287 typedef struct seqDef_s {
288 U32 offset; /* offset == rawOffset + ZSTD_REP_NUM, or equivalently, offCode + 1 */
289 U16 litLength;
290 U16 matchLength;
291 } seqDef;
292
293 /* Controls whether seqStore has a single "long" litLength or matchLength. See seqStore_t. */
294 typedef enum {
295 ZSTD_llt_none = 0, /* no longLengthType */
296 ZSTD_llt_literalLength = 1, /* represents a long literal */
297 ZSTD_llt_matchLength = 2 /* represents a long match */
298 } ZSTD_longLengthType_e;
299
300 typedef struct {
301 seqDef* sequencesStart;
302 seqDef* sequences; /* ptr to end of sequences */
303 BYTE* litStart;
304 BYTE* lit; /* ptr to end of literals */
305 BYTE* llCode;
306 BYTE* mlCode;
307 BYTE* ofCode;
308 size_t maxNbSeq;
309 size_t maxNbLit;
310
311 /* longLengthPos and longLengthType to allow us to represent either a single litLength or matchLength
312 * in the seqStore that has a value larger than U16 (if it exists). To do so, we increment
313 * the existing value of the litLength or matchLength by 0x10000.
314 */
315 ZSTD_longLengthType_e longLengthType;
316 U32 longLengthPos; /* Index of the sequence to apply long length modification to */
317 } seqStore_t;
318
319 typedef struct {
320 U32 litLength;
321 U32 matchLength;
322 } ZSTD_sequenceLength;
323
324 /**
325 * Returns the ZSTD_sequenceLength for the given sequences. It handles the decoding of long sequences
326 * indicated by longLengthPos and longLengthType, and adds MINMATCH back to matchLength.
327 */
ZSTD_getSequenceLength(seqStore_t const * seqStore,seqDef const * seq)328 MEM_STATIC ZSTD_sequenceLength ZSTD_getSequenceLength(seqStore_t const* seqStore, seqDef const* seq)
329 {
330 ZSTD_sequenceLength seqLen;
331 seqLen.litLength = seq->litLength;
332 seqLen.matchLength = seq->matchLength + MINMATCH;
333 if (seqStore->longLengthPos == (U32)(seq - seqStore->sequencesStart)) {
334 if (seqStore->longLengthType == ZSTD_llt_literalLength) {
335 seqLen.litLength += 0xFFFF;
336 }
337 if (seqStore->longLengthType == ZSTD_llt_matchLength) {
338 seqLen.matchLength += 0xFFFF;
339 }
340 }
341 return seqLen;
342 }
343
344 /**
345 * Contains the compressed frame size and an upper-bound for the decompressed frame size.
346 * Note: before using `compressedSize`, check for errors using ZSTD_isError().
347 * similarly, before using `decompressedBound`, check for errors using:
348 * `decompressedBound != ZSTD_CONTENTSIZE_ERROR`
349 */
350 typedef struct {
351 size_t compressedSize;
352 unsigned long long decompressedBound;
353 } ZSTD_frameSizeInfo; /* decompress & legacy */
354
355 const seqStore_t* ZSTD_getSeqStore(const ZSTD_CCtx* ctx); /* compress & dictBuilder */
356 void ZSTD_seqToCodes(const seqStore_t* seqStorePtr); /* compress, dictBuilder, decodeCorpus (shouldn't get its definition from here) */
357
358 /* custom memory allocation functions */
359 void* ZSTD_customMalloc(size_t size, ZSTD_customMem customMem);
360 void* ZSTD_customCalloc(size_t size, ZSTD_customMem customMem);
361 void ZSTD_customFree(void* ptr, ZSTD_customMem customMem);
362
363
ZSTD_highbit32(U32 val)364 MEM_STATIC U32 ZSTD_highbit32(U32 val) /* compress, dictBuilder, decodeCorpus */
365 {
366 assert(val != 0);
367 {
368 # if defined(_MSC_VER) /* Visual */
369 # if STATIC_BMI2 == 1
370 return _lzcnt_u32(val)^31;
371 # else
372 if (val != 0) {
373 unsigned long r;
374 _BitScanReverse(&r, val);
375 return (unsigned)r;
376 } else {
377 /* Should not reach this code path */
378 __assume(0);
379 }
380 # endif
381 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */
382 return __builtin_clz (val) ^ 31;
383 # elif defined(__ICCARM__) /* IAR Intrinsic */
384 return 31 - __CLZ(val);
385 # else /* Software version */
386 static const U32 DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
387 U32 v = val;
388 v |= v >> 1;
389 v |= v >> 2;
390 v |= v >> 4;
391 v |= v >> 8;
392 v |= v >> 16;
393 return DeBruijnClz[(v * 0x07C4ACDDU) >> 27];
394 # endif
395 }
396 }
397
398 /**
399 * Counts the number of trailing zeros of a `size_t`.
400 * Most compilers should support CTZ as a builtin. A backup
401 * implementation is provided if the builtin isn't supported, but
402 * it may not be terribly efficient.
403 */
ZSTD_countTrailingZeros(size_t val)404 MEM_STATIC unsigned ZSTD_countTrailingZeros(size_t val)
405 {
406 if (MEM_64bits()) {
407 # if defined(_MSC_VER) && defined(_WIN64)
408 # if STATIC_BMI2
409 return _tzcnt_u64(val);
410 # else
411 if (val != 0) {
412 unsigned long r;
413 _BitScanForward64(&r, (U64)val);
414 return (unsigned)r;
415 } else {
416 /* Should not reach this code path */
417 __assume(0);
418 }
419 # endif
420 # elif defined(__GNUC__) && (__GNUC__ >= 4)
421 return __builtin_ctzll((U64)val);
422 # else
423 static const int DeBruijnBytePos[64] = { 0, 1, 2, 7, 3, 13, 8, 19,
424 4, 25, 14, 28, 9, 34, 20, 56,
425 5, 17, 26, 54, 15, 41, 29, 43,
426 10, 31, 38, 35, 21, 45, 49, 57,
427 63, 6, 12, 18, 24, 27, 33, 55,
428 16, 53, 40, 42, 30, 37, 44, 48,
429 62, 11, 23, 32, 52, 39, 36, 47,
430 61, 22, 51, 46, 60, 50, 59, 58 };
431 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
432 # endif
433 } else { /* 32 bits */
434 # if defined(_MSC_VER)
435 if (val != 0) {
436 unsigned long r;
437 _BitScanForward(&r, (U32)val);
438 return (unsigned)r;
439 } else {
440 /* Should not reach this code path */
441 __assume(0);
442 }
443 # elif defined(__GNUC__) && (__GNUC__ >= 3)
444 return __builtin_ctz((U32)val);
445 # else
446 static const int DeBruijnBytePos[32] = { 0, 1, 28, 2, 29, 14, 24, 3,
447 30, 22, 20, 15, 25, 17, 4, 8,
448 31, 27, 13, 23, 21, 19, 16, 7,
449 26, 12, 18, 6, 11, 5, 10, 9 };
450 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
451 # endif
452 }
453 }
454
455
456 /* ZSTD_invalidateRepCodes() :
457 * ensures next compression will not use repcodes from previous block.
458 * Note : only works with regular variant;
459 * do not use with extDict variant ! */
460 void ZSTD_invalidateRepCodes(ZSTD_CCtx* cctx); /* zstdmt, adaptive_compression (shouldn't get this definition from here) */
461
462
463 typedef struct {
464 blockType_e blockType;
465 U32 lastBlock;
466 U32 origSize;
467 } blockProperties_t; /* declared here for decompress and fullbench */
468
469 /*! ZSTD_getcBlockSize() :
470 * Provides the size of compressed block from block header `src` */
471 /* Used by: decompress, fullbench (does not get its definition from here) */
472 size_t ZSTD_getcBlockSize(const void* src, size_t srcSize,
473 blockProperties_t* bpPtr);
474
475 /*! ZSTD_decodeSeqHeaders() :
476 * decode sequence header from src */
477 /* Used by: decompress, fullbench (does not get its definition from here) */
478 size_t ZSTD_decodeSeqHeaders(ZSTD_DCtx* dctx, int* nbSeqPtr,
479 const void* src, size_t srcSize);
480
481 /**
482 * @returns true iff the CPU supports dynamic BMI2 dispatch.
483 */
ZSTD_cpuSupportsBmi2(void)484 MEM_STATIC int ZSTD_cpuSupportsBmi2(void)
485 {
486 ZSTD_cpuid_t cpuid = ZSTD_cpuid();
487 return ZSTD_cpuid_bmi1(cpuid) && ZSTD_cpuid_bmi2(cpuid);
488 }
489
490 #if defined (__cplusplus)
491 }
492 #endif
493
494 #endif /* ZSTD_CCOMMON_H_MODULE */
495