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