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