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