]>
Commit | Line | Data |
---|---|---|
8509f22a MB |
1 | /* SPDX-License-Identifier: (GPL-2.0 or BSD-3-Clause-Clear) */ |
2 | /** | |
3 | * Copyright (c) 2016-present, Yann Collet, Facebook, Inc. | |
4 | * All rights reserved. | |
5 | */ | |
6 | ||
7 | #ifndef ZSTD_CCOMMON_H_MODULE | |
8 | #define ZSTD_CCOMMON_H_MODULE | |
9 | ||
10 | /*-******************************************************* | |
11 | * Compiler specifics | |
12 | *********************************************************/ | |
13 | #define FORCE_INLINE static __always_inline | |
14 | #define FORCE_NOINLINE static noinline | |
15 | ||
16 | /*-************************************* | |
17 | * Dependencies | |
18 | ***************************************/ | |
19 | #include "error_private.h" | |
20 | #include "mem.h" | |
21 | #include <linux/compiler.h> | |
22 | #include <linux/kernel.h> | |
23 | #include <linux/xxhash.h> | |
24 | #include <linux/zstd.h> | |
25 | ||
26 | /*-************************************* | |
27 | * shared macros | |
28 | ***************************************/ | |
29 | #define MIN(a, b) ((a) < (b) ? (a) : (b)) | |
30 | #define MAX(a, b) ((a) > (b) ? (a) : (b)) | |
31 | #define CHECK_F(f) \ | |
32 | { \ | |
33 | size_t const errcod = f; \ | |
34 | if (ERR_isError(errcod)) \ | |
35 | return errcod; \ | |
36 | } /* check and Forward error code */ | |
37 | #define CHECK_E(f, e) \ | |
38 | { \ | |
39 | size_t const errcod = f; \ | |
40 | if (ERR_isError(errcod)) \ | |
41 | return ERROR(e); \ | |
42 | } /* check and send Error code */ | |
43 | #define ZSTD_STATIC_ASSERT(c) \ | |
44 | { \ | |
45 | enum { ZSTD_static_assert = 1 / (int)(!!(c)) }; \ | |
46 | } | |
47 | ||
48 | /*-************************************* | |
49 | * Common constants | |
50 | ***************************************/ | |
51 | #define ZSTD_OPT_NUM (1 << 12) | |
52 | #define ZSTD_DICT_MAGIC 0xEC30A437 /* v0.7+ */ | |
53 | ||
54 | #define ZSTD_REP_NUM 3 /* number of repcodes */ | |
55 | #define ZSTD_REP_CHECK (ZSTD_REP_NUM) /* number of repcodes to check by the optimal parser */ | |
56 | #define ZSTD_REP_MOVE (ZSTD_REP_NUM - 1) | |
57 | #define ZSTD_REP_MOVE_OPT (ZSTD_REP_NUM) | |
58 | static const U32 repStartValue[ZSTD_REP_NUM] = {1, 4, 8}; | |
59 | ||
60 | #define KB *(1 << 10) | |
61 | #define MB *(1 << 20) | |
62 | #define GB *(1U << 30) | |
63 | ||
64 | #define BIT7 128 | |
65 | #define BIT6 64 | |
66 | #define BIT5 32 | |
67 | #define BIT4 16 | |
68 | #define BIT1 2 | |
69 | #define BIT0 1 | |
70 | ||
71 | #define ZSTD_WINDOWLOG_ABSOLUTEMIN 10 | |
72 | static const size_t ZSTD_fcs_fieldSize[4] = {0, 2, 4, 8}; | |
73 | static const size_t ZSTD_did_fieldSize[4] = {0, 1, 2, 4}; | |
74 | ||
75 | #define ZSTD_BLOCKHEADERSIZE 3 /* C standard doesn't allow `static const` variable to be init using another `static const` variable */ | |
76 | static const size_t ZSTD_blockHeaderSize = ZSTD_BLOCKHEADERSIZE; | |
77 | typedef enum { bt_raw, bt_rle, bt_compressed, bt_reserved } blockType_e; | |
78 | ||
79 | #define MIN_SEQUENCES_SIZE 1 /* nbSeq==0 */ | |
80 | #define MIN_CBLOCK_SIZE (1 /*litCSize*/ + 1 /* RLE or RAW */ + MIN_SEQUENCES_SIZE /* nbSeq==0 */) /* for a non-null block */ | |
81 | ||
82 | #define HufLog 12 | |
83 | typedef enum { set_basic, set_rle, set_compressed, set_repeat } symbolEncodingType_e; | |
84 | ||
85 | #define LONGNBSEQ 0x7F00 | |
86 | ||
87 | #define MINMATCH 3 | |
88 | #define EQUAL_READ32 4 | |
89 | ||
90 | #define Litbits 8 | |
91 | #define MaxLit ((1 << Litbits) - 1) | |
92 | #define MaxML 52 | |
93 | #define MaxLL 35 | |
94 | #define MaxOff 28 | |
95 | #define MaxSeq MAX(MaxLL, MaxML) /* Assumption : MaxOff < MaxLL,MaxML */ | |
96 | #define MLFSELog 9 | |
97 | #define LLFSELog 9 | |
98 | #define OffFSELog 8 | |
99 | ||
100 | 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}; | |
101 | 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}; | |
102 | #define LL_DEFAULTNORMLOG 6 /* for static allocation */ | |
103 | static const U32 LL_defaultNormLog = LL_DEFAULTNORMLOG; | |
104 | ||
105 | 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, | |
106 | 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}; | |
107 | 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, | |
108 | 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}; | |
109 | #define ML_DEFAULTNORMLOG 6 /* for static allocation */ | |
110 | static const U32 ML_defaultNormLog = ML_DEFAULTNORMLOG; | |
111 | ||
112 | 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}; | |
113 | #define OF_DEFAULTNORMLOG 5 /* for static allocation */ | |
114 | static const U32 OF_defaultNormLog = OF_DEFAULTNORMLOG; | |
115 | ||
116 | /*-******************************************* | |
117 | * Shared functions to include for inlining | |
118 | *********************************************/ | |
119 | ZSTD_STATIC void ZSTD_copy8(void *dst, const void *src) { | |
120 | memcpy(dst, src, 8); | |
121 | } | |
122 | /*! ZSTD_wildcopy() : | |
123 | * custom version of memcpy(), can copy up to 7 bytes too many (8 bytes if length==0) */ | |
124 | #define WILDCOPY_OVERLENGTH 8 | |
125 | ZSTD_STATIC void ZSTD_wildcopy(void *dst, const void *src, ptrdiff_t length) | |
126 | { | |
127 | const BYTE* ip = (const BYTE*)src; | |
128 | BYTE* op = (BYTE*)dst; | |
129 | BYTE* const oend = op + length; | |
130 | /* Work around https://gcc.gnu.org/bugzilla/show_bug.cgi?id=81388. | |
131 | * Avoid the bad case where the loop only runs once by handling the | |
132 | * special case separately. This doesn't trigger the bug because it | |
133 | * doesn't involve pointer/integer overflow. | |
134 | */ | |
135 | if (length <= 8) | |
136 | return ZSTD_copy8(dst, src); | |
137 | do { | |
138 | ZSTD_copy8(op, ip); | |
139 | op += 8; | |
140 | ip += 8; | |
141 | } while (op < oend); | |
142 | } | |
143 | ||
144 | /*-******************************************* | |
145 | * Private interfaces | |
146 | *********************************************/ | |
147 | typedef struct ZSTD_stats_s ZSTD_stats_t; | |
148 | ||
149 | typedef struct { | |
150 | U32 off; | |
151 | U32 len; | |
152 | } ZSTD_match_t; | |
153 | ||
154 | typedef struct { | |
155 | U32 price; | |
156 | U32 off; | |
157 | U32 mlen; | |
158 | U32 litlen; | |
159 | U32 rep[ZSTD_REP_NUM]; | |
160 | } ZSTD_optimal_t; | |
161 | ||
162 | typedef struct seqDef_s { | |
163 | U32 offset; | |
164 | U16 litLength; | |
165 | U16 matchLength; | |
166 | } seqDef; | |
167 | ||
168 | typedef struct { | |
169 | seqDef *sequencesStart; | |
170 | seqDef *sequences; | |
171 | BYTE *litStart; | |
172 | BYTE *lit; | |
173 | BYTE *llCode; | |
174 | BYTE *mlCode; | |
175 | BYTE *ofCode; | |
176 | U32 longLengthID; /* 0 == no longLength; 1 == Lit.longLength; 2 == Match.longLength; */ | |
177 | U32 longLengthPos; | |
178 | /* opt */ | |
179 | ZSTD_optimal_t *priceTable; | |
180 | ZSTD_match_t *matchTable; | |
181 | U32 *matchLengthFreq; | |
182 | U32 *litLengthFreq; | |
183 | U32 *litFreq; | |
184 | U32 *offCodeFreq; | |
185 | U32 matchLengthSum; | |
186 | U32 matchSum; | |
187 | U32 litLengthSum; | |
188 | U32 litSum; | |
189 | U32 offCodeSum; | |
190 | U32 log2matchLengthSum; | |
191 | U32 log2matchSum; | |
192 | U32 log2litLengthSum; | |
193 | U32 log2litSum; | |
194 | U32 log2offCodeSum; | |
195 | U32 factor; | |
196 | U32 staticPrices; | |
197 | U32 cachedPrice; | |
198 | U32 cachedLitLength; | |
199 | const BYTE *cachedLiterals; | |
200 | } seqStore_t; | |
201 | ||
202 | const seqStore_t *ZSTD_getSeqStore(const ZSTD_CCtx *ctx); | |
203 | void ZSTD_seqToCodes(const seqStore_t *seqStorePtr); | |
204 | int ZSTD_isSkipFrame(ZSTD_DCtx *dctx); | |
205 | ||
206 | /*= Custom memory allocation functions */ | |
207 | typedef void *(*ZSTD_allocFunction)(void *opaque, size_t size); | |
208 | typedef void (*ZSTD_freeFunction)(void *opaque, void *address); | |
209 | typedef struct { | |
210 | ZSTD_allocFunction customAlloc; | |
211 | ZSTD_freeFunction customFree; | |
212 | void *opaque; | |
213 | } ZSTD_customMem; | |
214 | ||
215 | void *ZSTD_malloc(size_t size, ZSTD_customMem customMem); | |
216 | void ZSTD_free(void *ptr, ZSTD_customMem customMem); | |
217 | ||
218 | /*====== stack allocation ======*/ | |
219 | ||
220 | typedef struct { | |
221 | void *ptr; | |
222 | const void *end; | |
223 | } ZSTD_stack; | |
224 | ||
225 | #define ZSTD_ALIGN(x) ALIGN(x, sizeof(size_t)) | |
226 | #define ZSTD_PTR_ALIGN(p) PTR_ALIGN(p, sizeof(size_t)) | |
227 | ||
228 | ZSTD_customMem ZSTD_initStack(void *workspace, size_t workspaceSize); | |
229 | ||
230 | void *ZSTD_stackAllocAll(void *opaque, size_t *size); | |
231 | void *ZSTD_stackAlloc(void *opaque, size_t size); | |
232 | void ZSTD_stackFree(void *opaque, void *address); | |
233 | ||
234 | /*====== common function ======*/ | |
235 | ||
236 | ZSTD_STATIC U32 ZSTD_highbit32(U32 val) { return 31 - __builtin_clz(val); } | |
237 | ||
238 | /* hidden functions */ | |
239 | ||
240 | /* ZSTD_invalidateRepCodes() : | |
241 | * ensures next compression will not use repcodes from previous block. | |
242 | * Note : only works with regular variant; | |
243 | * do not use with extDict variant ! */ | |
244 | void ZSTD_invalidateRepCodes(ZSTD_CCtx *cctx); | |
245 | ||
246 | size_t ZSTD_freeCCtx(ZSTD_CCtx *cctx); | |
247 | size_t ZSTD_freeDCtx(ZSTD_DCtx *dctx); | |
248 | size_t ZSTD_freeCDict(ZSTD_CDict *cdict); | |
249 | size_t ZSTD_freeDDict(ZSTD_DDict *cdict); | |
250 | size_t ZSTD_freeCStream(ZSTD_CStream *zcs); | |
251 | size_t ZSTD_freeDStream(ZSTD_DStream *zds); | |
252 | ||
253 | #endif /* ZSTD_CCOMMON_H_MODULE */ |