1 /**
2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
3 * All rights reserved.
4 *
5 * This source code is licensed under the BSD-style license found in the
6 * LICENSE file in the root directory of https://github.com/facebook/zstd.
7 * An additional grant of patent rights can be found in the PATENTS file in the
8 * same directory.
9 *
10 * This program is free software; you can redistribute it and/or modify it under
11 * the terms of the GNU General Public License version 2 as published by the
12 * Free Software Foundation. This program is dual-licensed; you may select
13 * either version 2 of the GNU General Public License ("GPL") or BSD license
14 * ("BSD").
15 */
16
17 #ifndef ZSTD_CCOMMON_H_MODULE
18 #define ZSTD_CCOMMON_H_MODULE
19
20 /*-*******************************************************
21 * Compiler specifics
22 *********************************************************/
23 #define FORCE_INLINE static always_inline
24 #define FORCE_NOINLINE static noinline __init
25
26 /*-*************************************
27 * Dependencies
28 ***************************************/
29 #include "error_private.h"
30 #include "mem.h"
31 #ifdef __XEN__
32 #include <xen/compiler.h>
33 #include <xen/xxhash.h>
34 #endif
35
36 #define ALIGN(x, a) ((x + (a) - 1) & ~((a) - 1))
37 #define PTR_ALIGN(p, a) ((typeof(p))ALIGN((unsigned long)(p), (a)))
38
39 typedef enum {
40 ZSTDnit_frameHeader,
41 ZSTDnit_blockHeader,
42 ZSTDnit_block,
43 ZSTDnit_lastBlock,
44 ZSTDnit_checksum,
45 ZSTDnit_skippableFrame
46 } ZSTD_nextInputType_e;
47
48 /**
49 * struct ZSTD_frameParams - zstd frame parameters stored in the frame header
50 * @frameContentSize: The frame content size, or 0 if not present.
51 * @windowSize: The window size, or 0 if the frame is a skippable frame.
52 * @dictID: The dictionary id, or 0 if not present.
53 * @checksumFlag: Whether a checksum was used.
54 */
55 typedef struct {
56 unsigned long long frameContentSize;
57 unsigned int windowSize;
58 unsigned int dictID;
59 unsigned int checksumFlag;
60 } ZSTD_frameParams;
61
62 /**
63 * struct ZSTD_inBuffer - input buffer for streaming
64 * @src: Start of the input buffer.
65 * @size: Size of the input buffer.
66 * @pos: Position where reading stopped. Will be updated.
67 * Necessarily 0 <= pos <= size.
68 */
69 typedef struct ZSTD_inBuffer_s {
70 const void *src;
71 size_t size;
72 size_t pos;
73 } ZSTD_inBuffer;
74
75 /**
76 * struct ZSTD_outBuffer - output buffer for streaming
77 * @dst: Start of the output buffer.
78 * @size: Size of the output buffer.
79 * @pos: Position where writing stopped. Will be updated.
80 * Necessarily 0 <= pos <= size.
81 */
82 typedef struct ZSTD_outBuffer_s {
83 void *dst;
84 size_t size;
85 size_t pos;
86 } ZSTD_outBuffer;
87
88 typedef struct ZSTD_CCtx_s ZSTD_CCtx;
89 typedef struct ZSTD_DCtx_s ZSTD_DCtx;
90
91 typedef struct ZSTD_CDict_s ZSTD_CDict;
92 typedef struct ZSTD_DDict_s ZSTD_DDict;
93
94 typedef struct ZSTD_CStream_s ZSTD_CStream;
95 typedef struct ZSTD_DStream_s ZSTD_DStream;
96
97 /*-*************************************
98 * shared macros
99 ***************************************/
100 #ifndef MIN
101 #define MIN(a, b) ((a) < (b) ? (a) : (b))
102 #define MAX(a, b) ((a) > (b) ? (a) : (b))
103 #endif
104 #define CHECK_F(f) \
105 { \
106 size_t const errcod = f; \
107 if (ERR_isError(errcod)) \
108 return errcod; \
109 } /* check and Forward error code */
110 #define CHECK_E(f, e) \
111 { \
112 size_t const errcod = f; \
113 if (ERR_isError(errcod)) \
114 return ERROR(e); \
115 } /* check and send Error code */
116 #define ZSTD_STATIC_ASSERT(c) \
117 { \
118 enum { ZSTD_static_assert = 1 / (int)(!!(c)) }; \
119 }
120
121 /*-*************************************
122 * Common constants
123 ***************************************/
124 #define ZSTD_MAGICNUMBER 0xFD2FB528 /* >= v0.8.0 */
125 #define ZSTD_MAGIC_SKIPPABLE_START 0x184D2A50U
126
127 #define ZSTD_OPT_NUM (1 << 12)
128 #define ZSTD_DICT_MAGIC 0xEC30A437 /* v0.7+ */
129
130 #define ZSTD_CONTENTSIZE_UNKNOWN (0ULL - 1)
131 #define ZSTD_CONTENTSIZE_ERROR (0ULL - 2)
132
133 #define ZSTD_WINDOWLOG_MAX_32 27
134 #define ZSTD_WINDOWLOG_MAX_64 27
135 #define ZSTD_WINDOWLOG_MAX \
136 ((unsigned int)(sizeof(size_t) == 4 \
137 ? ZSTD_WINDOWLOG_MAX_32 \
138 : ZSTD_WINDOWLOG_MAX_64))
139 #define ZSTD_WINDOWLOG_MIN 10
140 #define ZSTD_HASHLOG_MAX ZSTD_WINDOWLOG_MAX
141 #define ZSTD_HASHLOG_MIN 6
142 #define ZSTD_CHAINLOG_MAX (ZSTD_WINDOWLOG_MAX+1)
143 #define ZSTD_CHAINLOG_MIN ZSTD_HASHLOG_MIN
144 #define ZSTD_HASHLOG3_MAX 17
145 #define ZSTD_SEARCHLOG_MAX (ZSTD_WINDOWLOG_MAX-1)
146 #define ZSTD_SEARCHLOG_MIN 1
147 /* only for ZSTD_fast, other strategies are limited to 6 */
148 #define ZSTD_SEARCHLENGTH_MAX 7
149 /* only for ZSTD_btopt, other strategies are limited to 4 */
150 #define ZSTD_SEARCHLENGTH_MIN 3
151 #define ZSTD_TARGETLENGTH_MIN 4
152 #define ZSTD_TARGETLENGTH_MAX 999
153
154 #define ZSTD_REP_NUM 3 /* number of repcodes */
155 #define ZSTD_REP_CHECK (ZSTD_REP_NUM) /* number of repcodes to check by the optimal parser */
156 #define ZSTD_REP_MOVE (ZSTD_REP_NUM - 1)
157 #define ZSTD_REP_MOVE_OPT (ZSTD_REP_NUM)
158 static const U32 repStartValue[ZSTD_REP_NUM] = {1, 4, 8};
159
160 /* for static allocation */
161 #define ZSTD_FRAMEHEADERSIZE_MAX 18
162 #define ZSTD_FRAMEHEADERSIZE_MIN 6
163 static const size_t ZSTD_frameHeaderSize_prefix = 5;
164 static const size_t ZSTD_frameHeaderSize_min = ZSTD_FRAMEHEADERSIZE_MIN;
165 static const size_t ZSTD_frameHeaderSize_max = ZSTD_FRAMEHEADERSIZE_MAX;
166 /* magic number + skippable frame length */
167 static const size_t ZSTD_skippableHeaderSize = 8;
168
169 #define ZSTD_BLOCKSIZE_ABSOLUTEMAX (128 * 1024)
170
171 #if 0 /* These don't seem to be usable - not sure what their purpose is. */
172 #define KB *(1 << 10)
173 #define MB *(1 << 20)
174 #define GB *(1U << 30)
175 #endif
176
177 #define BIT7 128
178 #define BIT6 64
179 #define BIT5 32
180 #define BIT4 16
181 #define BIT1 2
182 #define BIT0 1
183
184 #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10
185 static const size_t ZSTD_fcs_fieldSize[4] = {0, 2, 4, 8};
186 static const size_t ZSTD_did_fieldSize[4] = {0, 1, 2, 4};
187
188 #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */
189 static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE;
190 typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e;
191
192 #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */
193 #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */
194
195 #define HufLog 12
196 typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e;
197
198 #define LONGNBSEQ 0x7F00
199
200 #define MINMATCH 3
201 #define EQUAL_READ32 4
202
203 #define Litbits 8
204 #define MaxLit ((1 << Litbits) - 1)
205 #define MaxML 52
206 #define MaxLL 35
207 #define MaxOff 28
208 #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */
209 #define MLFSELog 9
210 #define LLFSELog 9
211 #define OffFSELog 8
212
213 static const U32 LL_bits[MaxLL + 1] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
214 static const S16 LL_defaultNorm[MaxLL + 1] = {4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, -1, -1, -1, -1};
215 #define LL_DEFAULTNORMLOG 6 /* for static allocation */
216 static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG;
217
218 static const U32 ML_bits[MaxML + 1] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
219 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
220 static const S16 ML_defaultNorm[MaxML + 1] = {1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
221 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1};
222 #define ML_DEFAULTNORMLOG 6 /* for static allocation */
223 static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG;
224
225 static const S16 OF_defaultNorm[MaxOff + 1] = {1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1};
226 #define OF_DEFAULTNORMLOG 5 /* for static allocation */
227 static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG;
228
229 /*-*******************************************
230 * Shared functions to include for inlining
231 *********************************************/
ZSTD_copy8(void * dst,const void * src)232 ZSTD_STATIC void ZSTD_copy8(void *dst, const void *src) {
233 /*
234 * zstd relies heavily on gcc being able to analyze and inline this
235 * memcpy() call, since it is called in a tight loop. Preboot mode
236 * is compiled in freestanding mode, which stops gcc from analyzing
237 * memcpy(). Use __builtin_memcpy() to tell gcc to analyze this as a
238 * regular memcpy().
239 */
240 __builtin_memcpy(dst, src, 8);
241 }
242 /*! ZSTD_wildcopy() :
243 * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */
244 #define WILDCOPY_OVERLENGTH 8
ZSTD_wildcopy(void * dst,const void * src,ptrdiff_t length)245 ZSTD_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length)
246 {
247 const BYTE* ip = (const BYTE*)src;
248 BYTE* op = (BYTE*)dst;
249 BYTE* const oend = op + length;
250 #if defined(GCC_VERSION) && GCC_VERSION >= 70000 && GCC_VERSION < 70200
251 /*
252 * Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388.
253 * Avoid the bad case where the loop only runs once by handling the
254 * special case separately. This doesn't trigger the bug because it
255 * doesn't involve pointer/integer overflow.
256 */
257 if (length <= 8)
258 return ZSTD_copy8(dst, src);
259 #endif
260 do {
261 ZSTD_copy8(op, ip);
262 op += 8;
263 ip += 8;
264 } while (op < oend);
265 }
266
267 /*-*******************************************
268 * Private interfaces
269 *********************************************/
270 typedef struct ZSTD_stats_s ZSTD_stats_t;
271
272 typedef struct {
273 U32 off;
274 U32 len;
275 } ZSTD_match_t;
276
277 typedef struct {
278 U32 price;
279 U32 off;
280 U32 mlen;
281 U32 litlen;
282 U32 rep[ZSTD_REP_NUM];
283 } ZSTD_optimal_t;
284
285 typedef struct seqDef_s {
286 U32 offset;
287 U16 litLength;
288 U16 matchLength;
289 } seqDef;
290
291 typedef struct {
292 seqDef *sequencesStart;
293 seqDef *sequences;
294 BYTE *litStart;
295 BYTE *lit;
296 BYTE *llCode;
297 BYTE *mlCode;
298 BYTE *ofCode;
299 U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */
300 U32 longLengthPos;
301 /* opt */
302 ZSTD_optimal_t *priceTable;
303 ZSTD_match_t *matchTable;
304 U32 *matchLengthFreq;
305 U32 *litLengthFreq;
306 U32 *litFreq;
307 U32 *offCodeFreq;
308 U32 matchLengthSum;
309 U32 matchSum;
310 U32 litLengthSum;
311 U32 litSum;
312 U32 offCodeSum;
313 U32 log2matchLengthSum;
314 U32 log2matchSum;
315 U32 log2litLengthSum;
316 U32 log2litSum;
317 U32 log2offCodeSum;
318 U32 factor;
319 U32 staticPrices;
320 U32 cachedPrice;
321 U32 cachedLitLength;
322 const BYTE *cachedLiterals;
323 } seqStore_t;
324
325 const seqStore_t *ZSTD_getSeqStore(const ZSTD_CCtx *ctx);
326 void ZSTD_seqToCodes(const seqStore_t *seqStorePtr);
327 int ZSTD_isSkipFrame(ZSTD_DCtx *dctx);
328
329 /*= Custom memory allocation functions */
330 typedef void *(*ZSTD_allocFunction)(void *opaque, size_t size);
331 typedef void (*ZSTD_freeFunction)(void *opaque, void *address);
332 typedef struct {
333 ZSTD_allocFunction customAlloc;
334 ZSTD_freeFunction customFree;
335 void *opaque;
336 } ZSTD_customMem;
337
338 void *ZSTD_malloc(size_t size, ZSTD_customMem customMem);
339 void ZSTD_free(void *ptr, ZSTD_customMem customMem);
340
341 /*====== stack allocation ======*/
342
343 typedef struct {
344 void *ptr;
345 const void *end;
346 } ZSTD_stack;
347
348 #define ZSTD_ALIGN(x) ALIGN(x, sizeof(size_t))
349 #define ZSTD_PTR_ALIGN(p) PTR_ALIGN(p, sizeof(size_t))
350
351 ZSTD_customMem ZSTD_initStack(void *workspace, size_t workspaceSize);
352
353 void *ZSTD_stackAllocAll(void *opaque, size_t *size);
354 void *cf_check ZSTD_stackAlloc(void *opaque, size_t size);
355 void cf_check ZSTD_stackFree(void *opaque, void *address);
356
357 /*====== common function ======*/
358
ZSTD_highbit32(U32 val)359 ZSTD_STATIC U32 ZSTD_highbit32(U32 val) { return 31 - __builtin_clz(val); }
360
361 /* hidden functions */
362
363 /* ZSTD_invalidateRepCodes() :
364 * ensures next compression will not use repcodes from previous block.
365 * Note : only works with regular variant;
366 * do not use with extDict variant ! */
367 void ZSTD_invalidateRepCodes(ZSTD_CCtx *cctx);
368
369 size_t ZSTD_freeCCtx(ZSTD_CCtx *cctx);
370 size_t ZSTD_freeDCtx(ZSTD_DCtx *dctx);
371 size_t ZSTD_freeCDict(ZSTD_CDict *cdict);
372 size_t ZSTD_freeDDict(ZSTD_DDict *cdict);
373 size_t ZSTD_freeCStream(ZSTD_CStream *zcs);
374 size_t ZSTD_freeDStream(ZSTD_DStream *zds);
375
376 #endif /* ZSTD_CCOMMON_H_MODULE */
377