1 /* ******************************************* 1
2 * huff0 huffman codec,
3 * part of Finite State Entropy library
4 * Copyright (c) Yann Collet, Facebook, Inc.
5 *
6 * You can contact the author at :
7 * - Source repository : https://github.com/Cy
8 *
9 * This source code is licensed under both the
10 * LICENSE file in the root directory of this
11 * in the COPYING file in the root directory o
12 * You may select, at your option, one of the
13 **********************************************
14
15
16 #ifndef HUF_H_298734234
17 #define HUF_H_298734234
18
19 /* *** Dependencies *** */
20 #include "zstd_deps.h" /* size_t */
21
22
23 /* *** library symbols visibility *** */
24 /* Note : when linking with -fvisibility=hidde
25 * HUF symbols remain "private" (intern
26 * Set macro FSE_DLL_EXPORT to 1 if you
27 #if defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPORT
28 # define HUF_PUBLIC_API __attribute__ ((visib
29 #elif defined(FSE_DLL_EXPORT) && (FSE_DLL_EXPO
30 # define HUF_PUBLIC_API __declspec(dllexport)
31 #elif defined(FSE_DLL_IMPORT) && (FSE_DLL_IMPO
32 # define HUF_PUBLIC_API __declspec(dllimport)
33 #else
34 # define HUF_PUBLIC_API
35 #endif
36
37
38 /* ========================== */
39 /* *** simple functions *** */
40 /* ========================== */
41
42 /* HUF_compress() :
43 * Compress content from buffer 'src', of siz
44 * 'dst' buffer must be already allocated.
45 * Compression runs faster if `dstCapacity` >
46 * `srcSize` must be <= `HUF_BLOCKSIZE_MAX` ==
47 * @return : size of compressed data (<= `dstC
48 * Special values : if return == 0, srcData i
49 * if HUF_isError(return), c
50 */
51 HUF_PUBLIC_API size_t HUF_compress(void* dst,
52 const void* src,
53
54 /* HUF_decompress() :
55 * Decompress HUF data from buffer 'cSrc', of
56 * into already allocated buffer 'dst', of mi
57 * `originalSize` : **must** be the ***exact**
58 * Note : in contrast with FSE, HUF_decompres
59 * RLE (cSrcSize==1) and uncompressed
60 * because it knows size to regenerate
61 * @return : size of regenerated data (== orig
62 * or an error code, which can be te
63 */
64 HUF_PUBLIC_API size_t HUF_decompress(void* dst
65 const void* cSr
66
67
68 /* *** Tool functions *** */
69 #define HUF_BLOCKSIZE_MAX (128 * 1024)
70 HUF_PUBLIC_API size_t HUF_compressBound(size_t
71
72 /* Error Management */
73 HUF_PUBLIC_API unsigned HUF_isError(size_t
74 HUF_PUBLIC_API const char* HUF_getErrorName(si
75
76
77 /* *** Advanced function *** */
78
79 /* HUF_compress2() :
80 * Same as HUF_compress(), but offers control
81 * `maxSymbolValue` must be <= HUF_SYMBOLVALUE
82 * `tableLog` must be `<= HUF_TABLELOG_MAX` .
83 HUF_PUBLIC_API size_t HUF_compress2 (void* dst
84 const void* src
85 unsigned maxSym
86
87 /* HUF_compress4X_wksp() :
88 * Same as HUF_compress2(), but uses external
89 * `workspace` must be at least as large as HU
90 #define HUF_WORKSPACE_SIZE ((8 << 10) + 512 /*
91 #define HUF_WORKSPACE_SIZE_U64 (HUF_WORKSPACE_
92 HUF_PUBLIC_API size_t HUF_compress4X_wksp (voi
93 const voi
94 unsigned
95 void* wor
96
97 #endif /* HUF_H_298734234 */
98
99 /* *******************************************
100 * WARNING !!
101 * The following section contains advanced an
102 * which shall never be used in the context o
103 * because they are not guaranteed to remain
104 * Only consider them in association with sta
105 * *******************************************
106 #if !defined(HUF_H_HUF_STATIC_LINKING_ONLY)
107 #define HUF_H_HUF_STATIC_LINKING_ONLY
108
109 /* *** Dependencies *** */
110 #include "mem.h" /* U32 */
111 #define FSE_STATIC_LINKING_ONLY
112 #include "fse.h"
113
114
115 /* *** Constants *** */
116 #define HUF_TABLELOG_MAX 12 /* max r
117 #define HUF_TABLELOG_DEFAULT 11 /* defau
118 #define HUF_SYMBOLVALUE_MAX 255
119
120 #define HUF_TABLELOG_ABSOLUTEMAX 12 /* absol
121 #if (HUF_TABLELOG_MAX > HUF_TABLELOG_ABSOLUTEM
122 # error "HUF_TABLELOG_MAX is too large !"
123 #endif
124
125
126 /* ****************************************
127 * Static allocation
128 ******************************************/
129 /* HUF buffer bounds */
130 #define HUF_CTABLEBOUND 129
131 #define HUF_BLOCKBOUND(size) (size + (size>>8)
132 #define HUF_COMPRESSBOUND(size) (HUF_CTABLEBOU
133
134 /* static allocation of HUF's Compression Tabl
135 /* this is a private definition, just exposed
136 typedef size_t HUF_CElt; /* consider it an i
137 #define HUF_CTABLE_SIZE_ST(maxSymbolValue) (
138 #define HUF_CTABLE_SIZE(maxSymbolValue)
139 #define HUF_CREATE_STATIC_CTABLE(name, maxSymb
140 HUF_CElt name[HUF_CTABLE_SIZE_ST(maxSymbol
141
142 /* static allocation of HUF's DTable */
143 typedef U32 HUF_DTable;
144 #define HUF_DTABLE_SIZE(maxTableLog) (1 + (1
145 #define HUF_CREATE_STATIC_DTABLEX1(DTable, max
146 HUF_DTable DTable[HUF_DTABLE_SIZE((max
147 #define HUF_CREATE_STATIC_DTABLEX2(DTable, max
148 HUF_DTable DTable[HUF_DTABLE_SIZE(maxT
149
150
151 /* ****************************************
152 * Advanced decompression functions
153 ******************************************/
154 size_t HUF_decompress4X1 (void* dst, size_t ds
155 #ifndef HUF_FORCE_DECOMPRESS_X1
156 size_t HUF_decompress4X2 (void* dst, size_t ds
157 #endif
158
159 size_t HUF_decompress4X_DCtx (HUF_DTable* dctx
160 size_t HUF_decompress4X_hufOnly(HUF_DTable* dc
161 size_t HUF_decompress4X_hufOnly_wksp(HUF_DTabl
162 size_t HUF_decompress4X1_DCtx(HUF_DTable* dctx
163 size_t HUF_decompress4X1_DCtx_wksp(HUF_DTable*
164 #ifndef HUF_FORCE_DECOMPRESS_X1
165 size_t HUF_decompress4X2_DCtx(HUF_DTable* dctx
166 size_t HUF_decompress4X2_DCtx_wksp(HUF_DTable*
167 #endif
168
169
170 /* ****************************************
171 * HUF detailed API
172 * ****************************************/
173
174 /*! HUF_compress() does the following:
175 * 1. count symbol occurrence from source[] i
176 * 2. (optional) refine tableLog using HUF_op
177 * 3. build Huffman table from count using HU
178 * 4. save Huffman table to memory buffer usi
179 * 5. encode the data stream using HUF_compre
180 *
181 * The following API allows targeting specifi
182 * For example, it's possible to compress sev
183 * or to save and regenerate 'CTable' using e
184 */
185 unsigned HUF_optimalTableLog(unsigned maxTable
186 size_t HUF_buildCTable (HUF_CElt* CTable, cons
187 size_t HUF_writeCTable (void* dst, size_t maxD
188 size_t HUF_writeCTable_wksp(void* dst, size_t
189 size_t HUF_compress4X_usingCTable(void* dst, s
190 size_t HUF_compress4X_usingCTable_bmi2(void* d
191 size_t HUF_estimateCompressedSize(const HUF_CE
192 int HUF_validateCTable(const HUF_CElt* CTable,
193
194 typedef enum {
195 HUF_repeat_none, /*< Cannot use the previo
196 HUF_repeat_check, /*< Can use the previous
197 HUF_repeat_valid /*< Can use the previous
198 } HUF_repeat;
199 /* HUF_compress4X_repeat() :
200 * Same as HUF_compress4X_wksp(), but conside
201 * If it uses hufTable it does not modify huf
202 * If it doesn't, it sets *repeat = HUF_repea
203 * If preferRepeat then the old table will al
204 * If suspectUncompressible then some samplin
205 size_t HUF_compress4X_repeat(void* dst, size_t
206 const void* src, size_t
207 unsigned maxSymbolValue
208 void* workSpace, size_t
209 HUF_CElt* hufTable, HUF
210
211 /* HUF_buildCTable_wksp() :
212 * Same as HUF_buildCTable(), but using exter
213 * `workSpace` must be aligned on 4-bytes boun
214 */
215 #define HUF_CTABLE_WORKSPACE_SIZE_U32 (2*HUF_S
216 #define HUF_CTABLE_WORKSPACE_SIZE (HUF_CTABLE_
217 size_t HUF_buildCTable_wksp (HUF_CElt* tree,
218 const unsigned* count,
219 void* workSpace,
220
221 /*! HUF_readStats() :
222 * Read compact Huffman tree, saved by HUF_wr
223 * `huffWeight` is destination buffer.
224 * @return : size read from `src` , or an erro
225 * Note : Needed by HUF_readCTable() and HUF_
226 size_t HUF_readStats(BYTE* huffWeight, size_t
227 U32* rankStats, U32* nbSy
228 const void* src, size_t s
229
230 /*! HUF_readStats_wksp() :
231 * Same as HUF_readStats() but takes an extern
232 * 4-byte aligned and its size must be >= HUF_
233 * If the CPU has BMI2 support, pass bmi2=1, o
234 */
235 #define HUF_READ_STATS_WORKSPACE_SIZE_U32 FSE_
236 #define HUF_READ_STATS_WORKSPACE_SIZE (HUF_REA
237 size_t HUF_readStats_wksp(BYTE* huffWeight, si
238 U32* rankStats, U32*
239 const void* src, siz
240 void* workspace, siz
241 int bmi2);
242
243 /* HUF_readCTable() :
244 * Loading a CTable saved with HUF_writeCTabl
245 size_t HUF_readCTable (HUF_CElt* CTable, unsig
246
247 /* HUF_getNbBitsFromCTable() :
248 * Read nbBits from CTable symbolTable, for s
249 * Note 1 : is not inlined, as HUF_CElt defin
250 U32 HUF_getNbBitsFromCTable(const HUF_CElt* sy
251
252 /*
253 * HUF_decompress() does the following:
254 * 1. select the decompression algorithm (X1,
255 * 2. build Huffman table from save, using HUF
256 * 3. decode 1 or 4 segments in parallel using
257 */
258
259 /* HUF_selectDecoder() :
260 * Tells which decoder is likely to decode fa
261 * based on a set of pre-computed metrics.
262 * @return : 0==HUF_decompress4X1, 1==HUF_deco
263 * Assumption : 0 < dstSize <= 128 KB */
264 U32 HUF_selectDecoder (size_t dstSize, size_t
265
266 /*
267 * The minimum workspace size for the `workSp
268 * HUF_readDTableX1_wksp() and HUF_readDTable
269 *
270 * The space used depends on HUF_TABLELOG_MAX
271 * HUF_TABLE_LOG_MAX=12 to ~1850 bytes when H
272 * Buffer overflow errors may potentially occ
273 * a required workspace size greater than tha
274 * macro.
275 */
276 #define HUF_DECOMPRESS_WORKSPACE_SIZE ((2 << 1
277 #define HUF_DECOMPRESS_WORKSPACE_SIZE_U32 (HUF
278
279 #ifndef HUF_FORCE_DECOMPRESS_X2
280 size_t HUF_readDTableX1 (HUF_DTable* DTable, c
281 size_t HUF_readDTableX1_wksp (HUF_DTable* DTab
282 #endif
283 #ifndef HUF_FORCE_DECOMPRESS_X1
284 size_t HUF_readDTableX2 (HUF_DTable* DTable, c
285 size_t HUF_readDTableX2_wksp (HUF_DTable* DTab
286 #endif
287
288 size_t HUF_decompress4X_usingDTable(void* dst,
289 #ifndef HUF_FORCE_DECOMPRESS_X2
290 size_t HUF_decompress4X1_usingDTable(void* dst
291 #endif
292 #ifndef HUF_FORCE_DECOMPRESS_X1
293 size_t HUF_decompress4X2_usingDTable(void* dst
294 #endif
295
296
297 /* ====================== */
298 /* single stream variants */
299 /* ====================== */
300
301 size_t HUF_compress1X (void* dst, size_t dstSi
302 size_t HUF_compress1X_wksp (void* dst, size_t
303 size_t HUF_compress1X_usingCTable(void* dst, s
304 size_t HUF_compress1X_usingCTable_bmi2(void* d
305 /* HUF_compress1X_repeat() :
306 * Same as HUF_compress1X_wksp(), but conside
307 * If it uses hufTable it does not modify huf
308 * If it doesn't, it sets *repeat = HUF_repea
309 * If preferRepeat then the old table will al
310 * If suspectUncompressible then some samplin
311 size_t HUF_compress1X_repeat(void* dst, size_t
312 const void* src, size_t
313 unsigned maxSymbolValue
314 void* workSpace, size_t
315 HUF_CElt* hufTable, HUF
316
317 size_t HUF_decompress1X1 (void* dst, size_t ds
318 #ifndef HUF_FORCE_DECOMPRESS_X1
319 size_t HUF_decompress1X2 (void* dst, size_t ds
320 #endif
321
322 size_t HUF_decompress1X_DCtx (HUF_DTable* dctx
323 size_t HUF_decompress1X_DCtx_wksp (HUF_DTable*
324 #ifndef HUF_FORCE_DECOMPRESS_X2
325 size_t HUF_decompress1X1_DCtx(HUF_DTable* dctx
326 size_t HUF_decompress1X1_DCtx_wksp(HUF_DTable*
327 #endif
328 #ifndef HUF_FORCE_DECOMPRESS_X1
329 size_t HUF_decompress1X2_DCtx(HUF_DTable* dctx
330 size_t HUF_decompress1X2_DCtx_wksp(HUF_DTable*
331 #endif
332
333 size_t HUF_decompress1X_usingDTable(void* dst,
334 #ifndef HUF_FORCE_DECOMPRESS_X2
335 size_t HUF_decompress1X1_usingDTable(void* dst
336 #endif
337 #ifndef HUF_FORCE_DECOMPRESS_X1
338 size_t HUF_decompress1X2_usingDTable(void* dst
339 #endif
340
341 /* BMI2 variants.
342 * If the CPU has BMI2 support, pass bmi2=1, o
343 */
344 size_t HUF_decompress1X_usingDTable_bmi2(void*
345 #ifndef HUF_FORCE_DECOMPRESS_X2
346 size_t HUF_decompress1X1_DCtx_wksp_bmi2(HUF_DT
347 #endif
348 size_t HUF_decompress4X_usingDTable_bmi2(void*
349 size_t HUF_decompress4X_hufOnly_wksp_bmi2(HUF_
350 #ifndef HUF_FORCE_DECOMPRESS_X2
351 size_t HUF_readDTableX1_wksp_bmi2(HUF_DTable*
352 #endif
353 #ifndef HUF_FORCE_DECOMPRESS_X1
354 size_t HUF_readDTableX2_wksp_bmi2(HUF_DTable*
355 #endif
356
357 #endif /* HUF_STATIC_LINKING_ONLY */
358
359
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.