]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /********************************************************************** |
2 | Copyright(c) 2011-2016 Intel Corporation All rights reserved. | |
3 | ||
4 | Redistribution and use in source and binary forms, with or without | |
5 | modification, are permitted provided that the following conditions | |
6 | are met: | |
7 | * Redistributions of source code must retain the above copyright | |
8 | notice, this list of conditions and the following disclaimer. | |
9 | * Redistributions in binary form must reproduce the above copyright | |
10 | notice, this list of conditions and the following disclaimer in | |
11 | the documentation and/or other materials provided with the | |
12 | distribution. | |
13 | * Neither the name of Intel Corporation nor the names of its | |
14 | contributors may be used to endorse or promote products derived | |
15 | from this software without specific prior written permission. | |
16 | ||
17 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
28 | **********************************************************************/ | |
29 | ||
30 | #ifndef _IGZIP_H | |
31 | #define _IGZIP_H | |
32 | ||
33 | /** | |
34 | * @file igzip_lib.h | |
35 | * | |
224ce89b WB |
36 | * @brief This file defines the igzip compression and decompression interface, a |
37 | * high performance deflate compression interface for storage applications. | |
7c673cae FG |
38 | * |
39 | * Deflate is a widely used compression standard that can be used standalone, it | |
40 | * also forms the basis of gzip and zlib compression formats. Igzip supports the | |
41 | * following flush features: | |
42 | * | |
224ce89b | 43 | * - No Flush: The default method where no special flush is performed. |
7c673cae FG |
44 | * |
45 | * - Sync flush: whereby isal_deflate() finishes the current deflate block at | |
46 | * the end of each input buffer. The deflate block is byte aligned by | |
47 | * appending an empty stored block. | |
48 | * | |
49 | * - Full flush: whereby isal_deflate() finishes and aligns the deflate block as | |
50 | * in sync flush but also ensures that subsequent block's history does not | |
51 | * look back beyond this point and new blocks are fully independent. | |
52 | * | |
224ce89b WB |
53 | * Igzip also supports compression levels from ISAL_DEF_MIN_LEVEL to |
54 | * ISAL_DEF_MAX_LEVEL. | |
7c673cae | 55 | * |
224ce89b WB |
56 | * Igzip contains some behaviour configurable at compile time. These |
57 | * configureable options are: | |
7c673cae | 58 | * |
224ce89b WB |
59 | * - IGZIP_HIST_SIZE - Defines the window size. The default value is 32K (note K |
60 | * represents 1024), but 8K is also supported. Powers of 2 which are at most | |
61 | * 32K may also work. | |
7c673cae | 62 | * |
224ce89b WB |
63 | * - LONGER_HUFFTABLES - Defines whether to use a larger hufftables structure |
64 | * which may increase performance with smaller IGZIP_HIST_SIZE values. By | |
65 | * default this optoin is not defined. This define sets IGZIP_HIST_SIZE to be | |
66 | * 8 if IGZIP_HIST_SIZE > 8K. | |
7c673cae | 67 | * |
224ce89b WB |
68 | * As an example, to compile gzip with an 8K window size, in a terminal run |
69 | * @verbatim gmake D="-D IGZIP_HIST_SIZE=8*1024" @endverbatim on Linux and | |
70 | * FreeBSD, or with @verbatim nmake -f Makefile.nmake D="-D | |
71 | * IGZIP_HIST_SIZE=8*1024" @endverbatim on Windows. | |
7c673cae FG |
72 | * |
73 | */ | |
74 | #include <stdint.h> | |
75 | #include "types.h" | |
76 | ||
77 | #ifdef __cplusplus | |
78 | extern "C" { | |
79 | #endif | |
80 | ||
224ce89b WB |
81 | /******************************************************************************/ |
82 | /* Deflate Compression Standard Defines */ | |
83 | /******************************************************************************/ | |
84 | #define IGZIP_K 1024 | |
85 | #define ISAL_DEF_MAX_HDR_SIZE 328 | |
86 | #define ISAL_DEF_MAX_CODE_LEN 15 | |
87 | #define ISAL_DEF_HIST_SIZE (32*IGZIP_K) | |
88 | ||
89 | #define ISAL_DEF_LIT_SYMBOLS 257 | |
90 | #define ISAL_DEF_LEN_SYMBOLS 29 | |
91 | #define ISAL_DEF_DIST_SYMBOLS 30 | |
92 | #define ISAL_DEF_LIT_LEN_SYMBOLS (ISAL_DEF_LIT_SYMBOLS + ISAL_DEF_LEN_SYMBOLS) | |
93 | ||
94 | #define ISAL_LOOK_AHEAD (18 * 16) /* Max repeat length, rounded up to 32 byte boundary */ | |
95 | ||
96 | /******************************************************************************/ | |
97 | /* Deflate Implemenation Specific Defines */ | |
98 | /******************************************************************************/ | |
99 | /* Note IGZIP_HIST_SIZE must be a power of two */ | |
100 | #ifndef IGZIP_HIST_SIZE | |
101 | #define IGZIP_HIST_SIZE ISAL_DEF_HIST_SIZE | |
7c673cae FG |
102 | #endif |
103 | ||
224ce89b WB |
104 | #if (IGZIP_HIST_SIZE > ISAL_DEF_HIST_SIZE) |
105 | #undef IGZIP_HIST_SIZE | |
106 | #define IGZIP_HIST_SIZE ISAL_DEF_HIST_SIZE | |
7c673cae FG |
107 | #endif |
108 | ||
224ce89b WB |
109 | #ifdef LONGER_HUFFTABLE |
110 | #if (IGZIP_HIST_SIZE > 8 * IGZIP_K) | |
111 | #undef IGZIP_HIST_SIZE | |
112 | #define IGZIP_HIST_SIZE (8 * IGZIP_K) | |
113 | #endif | |
7c673cae FG |
114 | #endif |
115 | ||
224ce89b | 116 | #define ISAL_LIMIT_HASH_UPDATE |
7c673cae | 117 | |
224ce89b WB |
118 | #ifndef IGZIP_HASH_SIZE |
119 | #define IGZIP_HASH_SIZE (8 * IGZIP_K) | |
120 | #endif | |
7c673cae FG |
121 | |
122 | #ifdef LONGER_HUFFTABLE | |
224ce89b | 123 | enum {IGZIP_DIST_TABLE_SIZE = 8*1024}; |
7c673cae FG |
124 | |
125 | /* DECODE_OFFSET is dist code index corresponding to DIST_TABLE_SIZE + 1 */ | |
224ce89b | 126 | enum { IGZIP_DECODE_OFFSET = 26 }; |
7c673cae | 127 | #else |
224ce89b | 128 | enum {IGZIP_DIST_TABLE_SIZE = 2}; |
7c673cae | 129 | /* DECODE_OFFSET is dist code index corresponding to DIST_TABLE_SIZE + 1 */ |
224ce89b | 130 | enum { IGZIP_DECODE_OFFSET = 0 }; |
7c673cae | 131 | #endif |
224ce89b WB |
132 | enum {IGZIP_LEN_TABLE_SIZE = 256}; |
133 | enum {IGZIP_LIT_TABLE_SIZE = ISAL_DEF_LIT_SYMBOLS}; | |
7c673cae | 134 | |
224ce89b WB |
135 | #define IGZIP_HUFFTABLE_CUSTOM 0 |
136 | #define IGZIP_HUFFTABLE_DEFAULT 1 | |
137 | #define IGZIP_HUFFTABLE_STATIC 2 | |
7c673cae FG |
138 | |
139 | /* Flush Flags */ | |
140 | #define NO_FLUSH 0 /* Default */ | |
141 | #define SYNC_FLUSH 1 | |
142 | #define FULL_FLUSH 2 | |
143 | #define FINISH_FLUSH 0 /* Deprecated */ | |
144 | ||
224ce89b WB |
145 | /* Gzip Flags */ |
146 | #define IGZIP_DEFLATE 0 /* Default */ | |
147 | #define IGZIP_GZIP 1 | |
148 | #define IGZIP_GZIP_NO_HDR 2 | |
149 | ||
150 | /* Compression Return values */ | |
7c673cae FG |
151 | #define COMP_OK 0 |
152 | #define INVALID_FLUSH -7 | |
153 | #define INVALID_PARAM -8 | |
154 | #define STATELESS_OVERFLOW -1 | |
224ce89b WB |
155 | #define ISAL_INVALID_OPERATION -9 |
156 | #define ISAL_INVALID_LEVEL -4 /* Invalid Compression level set */ | |
157 | ||
7c673cae | 158 | /** |
224ce89b | 159 | * @enum isal_zstate_state |
7c673cae FG |
160 | * @brief Compression State please note ZSTATE_TRL only applies for GZIP compression |
161 | */ | |
162 | ||
163 | ||
164 | /* When the state is set to ZSTATE_NEW_HDR or TMP_ZSTATE_NEW_HEADER, the | |
165 | * hufftable being used for compression may be swapped | |
166 | */ | |
167 | enum isal_zstate_state { | |
168 | ZSTATE_NEW_HDR, //!< Header to be written | |
169 | ZSTATE_HDR, //!< Header state | |
224ce89b | 170 | ZSTATE_CREATE_HDR, //!< Header to be created |
7c673cae FG |
171 | ZSTATE_BODY, //!< Body state |
172 | ZSTATE_FLUSH_READ_BUFFER, //!< Flush buffer | |
224ce89b | 173 | ZSTATE_FLUSH_ICF_BUFFER, |
7c673cae FG |
174 | ZSTATE_SYNC_FLUSH, //!< Write sync flush block |
175 | ZSTATE_FLUSH_WRITE_BUFFER, //!< Flush bitbuf | |
176 | ZSTATE_TRL, //!< Trailer state | |
177 | ZSTATE_END, //!< End state | |
178 | ZSTATE_TMP_NEW_HDR, //!< Temporary Header to be written | |
179 | ZSTATE_TMP_HDR, //!< Temporary Header state | |
224ce89b | 180 | ZSTATE_TMP_CREATE_HDR, //!< Temporary Header to be created state |
7c673cae FG |
181 | ZSTATE_TMP_BODY, //!< Temporary Body state |
182 | ZSTATE_TMP_FLUSH_READ_BUFFER, //!< Flush buffer | |
224ce89b | 183 | ZSTATE_TMP_FLUSH_ICF_BUFFER, |
7c673cae FG |
184 | ZSTATE_TMP_SYNC_FLUSH, //!< Write sync flush block |
185 | ZSTATE_TMP_FLUSH_WRITE_BUFFER, //!< Flush bitbuf | |
186 | ZSTATE_TMP_TRL, //!< Temporary Trailer state | |
187 | ZSTATE_TMP_END //!< Temporary End state | |
188 | }; | |
189 | ||
190 | /* Offset used to switch between TMP states and non-tmp states */ | |
224ce89b WB |
191 | #define ZSTATE_TMP_OFFSET ZSTATE_TMP_HDR - ZSTATE_HDR |
192 | ||
193 | /******************************************************************************/ | |
194 | /* Inflate Implementation Specific Defines */ | |
195 | /******************************************************************************/ | |
196 | #define ISAL_DECODE_LONG_BITS 12 | |
197 | #define ISAL_DECODE_SHORT_BITS 10 | |
198 | ||
199 | /* Current state of decompression */ | |
200 | enum isal_block_state { | |
201 | ISAL_BLOCK_NEW_HDR, /* Just starting a new block */ | |
202 | ISAL_BLOCK_HDR, /* In the middle of reading in a block header */ | |
203 | ISAL_BLOCK_TYPE0, /* Decoding a type 0 block */ | |
204 | ISAL_BLOCK_CODED, /* Decoding a huffman coded block */ | |
205 | ISAL_BLOCK_INPUT_DONE, /* Decompression of input is completed */ | |
206 | ISAL_BLOCK_FINISH /* Decompression of input is completed and all data has been flushed to output */ | |
207 | }; | |
7c673cae | 208 | |
224ce89b WB |
209 | /* Inflate Return values */ |
210 | #define ISAL_DECOMP_OK 0 /* No errors encountered while decompressing */ | |
211 | #define ISAL_END_INPUT 1 /* End of input reached */ | |
212 | #define ISAL_OUT_OVERFLOW 2 /* End of output reached */ | |
213 | #define ISAL_INVALID_BLOCK -1 /* Invalid deflate block found */ | |
214 | #define ISAL_INVALID_SYMBOL -2 /* Invalid deflate symbol found */ | |
215 | #define ISAL_INVALID_LOOKBACK -3 /* Invalid lookback distance found */ | |
216 | ||
217 | /******************************************************************************/ | |
218 | /* Compression structures */ | |
219 | /******************************************************************************/ | |
220 | /** @brief Holds histogram of deflate symbols*/ | |
7c673cae | 221 | struct isal_huff_histogram { |
224ce89b WB |
222 | uint64_t lit_len_histogram[ISAL_DEF_LIT_LEN_SYMBOLS]; //!< Histogram of Literal/Len symbols seen |
223 | uint64_t dist_histogram[ISAL_DEF_DIST_SYMBOLS]; //!< Histogram of Distance Symbols seen | |
224 | uint16_t hash_table[IGZIP_HASH_SIZE]; //!< Tmp space used as a hash table | |
225 | }; | |
226 | ||
227 | struct isal_mod_hist { | |
228 | uint32_t d_hist[30]; | |
229 | uint32_t ll_hist[513]; | |
7c673cae FG |
230 | }; |
231 | ||
224ce89b WB |
232 | #define ISAL_DEF_MIN_LEVEL 0 |
233 | #define ISAL_DEF_MAX_LEVEL 1 | |
234 | ||
235 | /* Defines used set level data sizes */ | |
236 | #define ISAL_DEF_LVL0_REQ 0 | |
237 | #define ISAL_DEF_LVL1_REQ 4 * IGZIP_K /* has to be at least sizeof(struct level_2_buf) */ | |
238 | #define ISAL_DEF_LVL1_TOKEN_SIZE 4 | |
239 | ||
240 | /* Data sizes for level specific data options */ | |
241 | #define ISAL_DEF_LVL0_MIN ISAL_DEF_LVL0_REQ | |
242 | #define ISAL_DEF_LVL0_SMALL ISAL_DEF_LVL0_REQ | |
243 | #define ISAL_DEF_LVL0_MEDIUM ISAL_DEF_LVL0_REQ | |
244 | #define ISAL_DEF_LVL0_LARGE ISAL_DEF_LVL0_REQ | |
245 | #define ISAL_DEF_LVL0_EXTRA_LARGE ISAL_DEF_LVL0_REQ | |
246 | #define ISAL_DEF_LVL0_DEFAULT ISAL_DEF_LVL0_REQ | |
247 | ||
248 | #define ISAL_DEF_LVL1_MIN (ISAL_DEF_LVL1_REQ + ISAL_DEF_LVL1_TOKEN_SIZE * 1 * IGZIP_K) | |
249 | #define ISAL_DEF_LVL1_SMALL (ISAL_DEF_LVL1_REQ + ISAL_DEF_LVL1_TOKEN_SIZE * 16 * IGZIP_K) | |
250 | #define ISAL_DEF_LVL1_MEDIUM (ISAL_DEF_LVL1_REQ + ISAL_DEF_LVL1_TOKEN_SIZE * 32 * IGZIP_K) | |
251 | #define ISAL_DEF_LVL1_LARGE (ISAL_DEF_LVL1_REQ + ISAL_DEF_LVL1_TOKEN_SIZE * 64 * IGZIP_K) | |
252 | #define ISAL_DEF_LVL1_EXTRA_LARGE (ISAL_DEF_LVL1_REQ + ISAL_DEF_LVL1_TOKEN_SIZE * 128 * IGZIP_K) | |
253 | #define ISAL_DEF_LVL1_DEFAULT ISAL_DEF_LVL1_LARGE | |
254 | ||
7c673cae FG |
255 | /** @brief Holds Bit Buffer information*/ |
256 | struct BitBuf2 { | |
257 | uint64_t m_bits; //!< bits in the bit buffer | |
258 | uint32_t m_bit_count; //!< number of valid bits in the bit buffer | |
259 | uint8_t *m_out_buf; //!< current index of buffer to write to | |
260 | uint8_t *m_out_end; //!< end of buffer to write to | |
261 | uint8_t *m_out_start; //!< start of buffer to write to | |
262 | }; | |
263 | ||
264 | /* Variable prefixes: | |
265 | * b_ : Measured wrt the start of the buffer | |
266 | * f_ : Measured wrt the start of the file (aka file_start) | |
267 | */ | |
268 | ||
269 | /** @brief Holds the internal state information for input and output compression streams*/ | |
270 | struct isal_zstate { | |
271 | uint32_t b_bytes_valid; //!< number of bytes of valid data in buffer | |
272 | uint32_t b_bytes_processed; //!< keeps track of the number of bytes processed in isal_zstate.buffer | |
273 | uint8_t *file_start; //!< pointer to where file would logically start | |
224ce89b | 274 | uint32_t crc; //!< Current crc |
7c673cae FG |
275 | struct BitBuf2 bitbuf; //!< Bit Buffer |
276 | enum isal_zstate_state state; //!< Current state in processing the data stream | |
277 | uint32_t count; //!< used for partial header/trailer writes | |
278 | uint8_t tmp_out_buff[16]; //!< temporary array | |
279 | uint32_t tmp_out_start; //!< temporary variable | |
280 | uint32_t tmp_out_end; //!< temporary variable | |
7c673cae FG |
281 | uint32_t has_eob; //!< keeps track of eob on the last deflate block |
282 | uint32_t has_eob_hdr; //!< keeps track of eob hdr (with BFINAL set) | |
224ce89b | 283 | uint32_t has_hist; //!< flag to track if there is match history |
7c673cae | 284 | |
224ce89b | 285 | struct isal_mod_hist hist; |
7c673cae | 286 | |
224ce89b WB |
287 | DECLARE_ALIGNED(uint8_t buffer[2 * IGZIP_HIST_SIZE + ISAL_LOOK_AHEAD], 32); //!< Internal buffer |
288 | DECLARE_ALIGNED(uint16_t head[IGZIP_HASH_SIZE], 16); //!< Hash array | |
7c673cae FG |
289 | |
290 | }; | |
291 | ||
292 | /** @brief Holds the huffman tree used to huffman encode the input stream **/ | |
293 | struct isal_hufftables { | |
294 | ||
224ce89b | 295 | uint8_t deflate_hdr[ISAL_DEF_MAX_HDR_SIZE]; //!< deflate huffman tree header |
7c673cae FG |
296 | uint32_t deflate_hdr_count; //!< Number of whole bytes in deflate_huff_hdr |
297 | uint32_t deflate_hdr_extra_bits; //!< Number of bits in the partial byte in header | |
224ce89b WB |
298 | uint32_t dist_table[IGZIP_DIST_TABLE_SIZE]; //!< bits 4:0 are the code length, bits 31:5 are the code |
299 | uint32_t len_table[IGZIP_LEN_TABLE_SIZE]; //!< bits 4:0 are the code length, bits 31:5 are the code | |
300 | uint16_t lit_table[IGZIP_LIT_TABLE_SIZE]; //!< literal code | |
301 | uint8_t lit_table_sizes[IGZIP_LIT_TABLE_SIZE]; //!< literal code length | |
302 | uint16_t dcodes[30 - IGZIP_DECODE_OFFSET]; //!< distance code | |
303 | uint8_t dcodes_sizes[30 - IGZIP_DECODE_OFFSET]; //!< distance code length | |
7c673cae FG |
304 | |
305 | }; | |
306 | ||
307 | /** @brief Holds stream information*/ | |
308 | struct isal_zstream { | |
309 | uint8_t *next_in; //!< Next input byte | |
310 | uint32_t avail_in; //!< number of bytes available at next_in | |
311 | uint32_t total_in; //!< total number of bytes read so far | |
312 | ||
313 | uint8_t *next_out; //!< Next output byte | |
314 | uint32_t avail_out; //!< number of bytes available at next_out | |
315 | uint32_t total_out; //!< total number of bytes written so far | |
316 | ||
317 | struct isal_hufftables *hufftables; //!< Huffman encoding used when compressing | |
224ce89b WB |
318 | uint32_t level; //!< Compression level to use |
319 | uint32_t level_buf_size; //!< Size of level_buf | |
320 | uint8_t * level_buf; //!< User allocated buffer required for different compression levels | |
7c673cae | 321 | uint32_t end_of_stream; //!< non-zero if this is the last input buffer |
224ce89b WB |
322 | uint32_t flush; //!< Flush type can be NO_FLUSH, SYNC_FLUSH or FULL_FLUSH |
323 | uint32_t gzip_flag; //!< Indicate if gzip compression is to be performed | |
7c673cae FG |
324 | |
325 | struct isal_zstate internal_state; //!< Internal state for this stream | |
326 | }; | |
327 | ||
224ce89b WB |
328 | /******************************************************************************/ |
329 | /* Inflate structures */ | |
330 | /******************************************************************************/ | |
331 | /* | |
332 | * Inflate_huff_code data structures are used to store a Huffman code for fast | |
333 | * lookup. It works by performing a lookup in small_code_lookup that hopefully | |
334 | * yields the correct symbol. Otherwise a lookup into long_code_lookup is | |
335 | * performed to find the correct symbol. The details of how this works follows: | |
336 | * | |
337 | * Let i be some index into small_code_lookup and let e be the associated | |
338 | * element. Bit 15 in e is a flag. If bit 15 is not set, then index i contains | |
339 | * a Huffman code for a symbol which has length at most DECODE_LOOKUP_SIZE. Bits | |
340 | * 0 through 8 are the symbol associated with that code and bits 9 through 12 of | |
341 | * e represent the number of bits in the code. If bit 15 is set, the i | |
342 | * corresponds to the first DECODE_LOOKUP_SIZE bits of a Huffman code which has | |
343 | * length longer than DECODE_LOOKUP_SIZE. In this case, bits 0 through 8 | |
344 | * represent an offset into long_code_lookup table and bits 9 through 12 | |
345 | * represent the maximum length of a Huffman code starting with the bits in the | |
346 | * index i. The offset into long_code_lookup is for an array associated with all | |
347 | * codes which start with the bits in i. | |
348 | * | |
349 | * The elements of long_code_lookup are in the same format as small_code_lookup, | |
350 | * except bit 15 is never set. Let i be a number made up of DECODE_LOOKUP_SIZE | |
351 | * bits. Then all Huffman codes which start with DECODE_LOOKUP_SIZE bits are | |
352 | * stored in an array starting at index h in long_code_lookup. This index h is | |
353 | * stored in bits 0 through 9 at index i in small_code_lookup. The index j is an | |
354 | * index of this array if the number of bits contained in j and i is the number | |
355 | * of bits in the longest huff_code starting with the bits of i. The symbol | |
356 | * stored at index j is the symbol whose huffcode can be found in (j << | |
357 | * DECODE_LOOKUP_SIZE) | i. Note these arrays will be stored sorted in order of | |
358 | * maximum Huffman code length. | |
359 | * | |
360 | * The following are explanations for sizes of the tables: | |
361 | * | |
362 | * Since small_code_lookup is a lookup on DECODE_LOOKUP_SIZE bits, it must have | |
363 | * size 2^DECODE_LOOKUP_SIZE. | |
364 | * | |
365 | * Since deflate Huffman are stored such that the code size and the code value | |
366 | * form an increasing function, At most 2^(15 - DECODE_LOOKUP_SIZE) - 1 elements | |
367 | * of long_code_lookup duplicate an existing symbol. Since there are at most 285 | |
368 | * - DECODE_LOOKUP_SIZE possible symbols contained in long_code lookup. Rounding | |
369 | * this to the nearest 16 byte boundary yields the size of long_code_lookup of | |
370 | * 288 + 2^(15 - DECODE_LOOKUP_SIZE). | |
371 | * | |
372 | * Note that DECODE_LOOKUP_SIZE can be any length even though the offset in | |
373 | * small_lookup_code is 9 bits long because the increasing relationship between | |
374 | * code length and code value forces the maximum offset to be less than 288. | |
375 | */ | |
7c673cae | 376 | |
224ce89b WB |
377 | /* Large lookup table for decoding huffman codes */ |
378 | struct inflate_huff_code_large { | |
379 | uint16_t short_code_lookup[1 << (ISAL_DECODE_LONG_BITS)]; | |
380 | uint16_t long_code_lookup[288 + (1 << (15 - ISAL_DECODE_LONG_BITS))]; | |
381 | }; | |
382 | ||
383 | /* Small lookup table for decoding huffman codes */ | |
384 | struct inflate_huff_code_small { | |
385 | uint16_t short_code_lookup[1 << (ISAL_DECODE_SHORT_BITS)]; | |
386 | uint16_t long_code_lookup[32 + (1 << (15 - ISAL_DECODE_SHORT_BITS))]; | |
387 | }; | |
388 | ||
389 | /** @brief Holds decompression state information*/ | |
390 | struct inflate_state { | |
391 | uint8_t *next_out; //!< Next output Byte | |
392 | uint32_t avail_out; //!< Number of bytes available at next_out | |
393 | uint32_t total_out; //!< Total bytes written out so far | |
394 | uint8_t *next_in; //!< Next input byte | |
395 | uint64_t read_in; //!< Bits buffered to handle unaligned streams | |
396 | uint32_t avail_in; //!< Number of bytes available at next_in | |
397 | int32_t read_in_length; //!< Bits in read_in | |
398 | struct inflate_huff_code_large lit_huff_code; //!< Structure for decoding lit/len symbols | |
399 | struct inflate_huff_code_small dist_huff_code; //!< Structure for decoding dist symbols | |
400 | enum isal_block_state block_state; //!< Current decompression state | |
401 | uint32_t bfinal; //!< Flag identifying final block | |
402 | uint32_t crc_flag; //!< Flag identifying whether to track of crc | |
403 | uint32_t crc; //!< Contains crc of output if crc_flag is set | |
404 | int32_t type0_block_len; //!< Length left to read of type 0 block when outbuffer overflow occured | |
405 | int32_t copy_overflow_length; //!< Length left to copy when outbuffer overflow occured | |
406 | int32_t copy_overflow_distance; //!< Lookback distance when outbuffer overlow occured | |
407 | int32_t tmp_in_size; //!< Number of bytes in tmp_in_buffer | |
408 | int32_t tmp_out_valid; //!< Number of bytes in tmp_out_buffer | |
409 | int32_t tmp_out_processed; //!< Number of bytes processed in tmp_out_buffer | |
410 | uint8_t tmp_in_buffer[ISAL_DEF_MAX_HDR_SIZE]; //!< Temporary buffer containing data from the input stream | |
411 | uint8_t tmp_out_buffer[2 * ISAL_DEF_HIST_SIZE + ISAL_LOOK_AHEAD]; //!< Temporary buffer containing data from the output stream | |
412 | }; | |
413 | ||
414 | /******************************************************************************/ | |
415 | /* Compression functions */ | |
416 | /******************************************************************************/ | |
7c673cae FG |
417 | /** |
418 | * @brief Updates histograms to include the symbols found in the input | |
419 | * stream. Since this function only updates the histograms, it can be called on | |
420 | * multiple streams to get a histogram better representing the desired data | |
421 | * set. When first using histogram it must be initialized by zeroing the | |
422 | * structure. | |
423 | * | |
424 | * @param in_stream: Input stream of data. | |
425 | * @param length: The length of start_stream. | |
426 | * @param histogram: The returned histogram of lit/len/dist symbols. | |
427 | */ | |
428 | void isal_update_histogram(uint8_t * in_stream, int length, struct isal_huff_histogram * histogram); | |
429 | ||
430 | ||
431 | /** | |
432 | * @brief Creates a custom huffman code for the given histograms in which | |
433 | * every literal and repeat length is assigned a code and all possible lookback | |
434 | * distances are assigned a code. | |
435 | * | |
436 | * @param hufftables: the output structure containing the huffman code | |
224ce89b WB |
437 | * @param histogram: histogram containing frequency of literal symbols, |
438 | * repeat lengths and lookback distances | |
7c673cae FG |
439 | * @returns Returns a non zero value if an invalid huffman code was created. |
440 | */ | |
441 | int isal_create_hufftables(struct isal_hufftables * hufftables, | |
442 | struct isal_huff_histogram * histogram); | |
443 | ||
444 | /** | |
445 | * @brief Creates a custom huffman code for the given histograms like | |
446 | * isal_create_hufftables() except literals with 0 frequency in the histogram | |
447 | * are not assigned a code | |
448 | * | |
449 | * @param hufftables: the output structure containing the huffman code | |
224ce89b WB |
450 | * @param histogram: histogram containing frequency of literal symbols, |
451 | * repeat lengths and lookback distances | |
7c673cae FG |
452 | * @returns Returns a non zero value if an invalid huffman code was created. |
453 | */ | |
454 | int isal_create_hufftables_subset(struct isal_hufftables * hufftables, | |
455 | struct isal_huff_histogram * histogram); | |
456 | ||
457 | /** | |
458 | * @brief Initialize compression stream data structure | |
459 | * | |
460 | * @param stream Structure holding state information on the compression streams. | |
461 | * @returns none | |
462 | */ | |
463 | void isal_deflate_init(struct isal_zstream *stream); | |
464 | ||
224ce89b WB |
465 | /** |
466 | * @brief Set stream to use a new Huffman code | |
467 | * | |
468 | * Sets the Huffman code to be used in compression before compression start or | |
469 | * after the sucessful completion of a SYNC_FLUSH or FULL_FLUSH. If type has | |
470 | * value IGZIP_HUFFTABLE_DEFAULT, the stream is set to use the default Huffman | |
471 | * code. If type has value IGZIP_HUFFTABLE_STATIC, the stream is set to use the | |
472 | * deflate standard static Huffman code, or if type has value | |
473 | * IGZIP_HUFFTABLE_CUSTOM, the stream is set to sue the isal_hufftables | |
474 | * structure input to isal_deflate_set_hufftables. | |
475 | * | |
476 | * @param stream: Structure holding state information on the compression stream. | |
477 | * @param hufftables: new huffman code to use if type is set to | |
478 | * IGZIP_HUFFTABLE_CUSTOM. | |
479 | * @param type: Flag specifying what hufftable to use. | |
480 | * | |
481 | * @returns Returns INVALID_OPERATION if the stream was unmodified. This may be | |
482 | * due to the stream being in a state where changing the huffman code is not | |
483 | * allowed or an invalid input is provided. | |
484 | */ | |
485 | int isal_deflate_set_hufftables(struct isal_zstream *stream, | |
486 | struct isal_hufftables *hufftables, int type); | |
487 | ||
488 | /** | |
489 | * @brief Initialize compression stream data structure | |
490 | * | |
491 | * @param stream Structure holding state information on the compression streams. | |
492 | * @returns none | |
493 | */ | |
494 | void isal_deflate_stateless_init(struct isal_zstream *stream); | |
495 | ||
7c673cae FG |
496 | |
497 | /** | |
498 | * @brief Fast data (deflate) compression for storage applications. | |
499 | * | |
224ce89b WB |
500 | * The call to isal_deflate() will take data from the input buffer (updating |
501 | * next_in, avail_in and write a compressed stream to the output buffer | |
502 | * (updating next_out and avail_out). The function returns when either the input | |
503 | * buffer is empty or the output buffer is full. | |
504 | * | |
7c673cae FG |
505 | * On entry to isal_deflate(), next_in points to an input buffer and avail_in |
506 | * indicates the length of that buffer. Similarly next_out points to an empty | |
507 | * output buffer and avail_out indicates the size of that buffer. | |
508 | * | |
509 | * The fields total_in and total_out start at 0 and are updated by | |
510 | * isal_deflate(). These reflect the total number of bytes read or written so far. | |
511 | * | |
7c673cae FG |
512 | * When the last input buffer is passed in, signaled by setting the |
513 | * end_of_stream, the routine will complete compression at the end of the input | |
514 | * buffer, as long as the output buffer is big enough. | |
515 | * | |
224ce89b WB |
516 | * The compression level can be set by setting level to any value between |
517 | * ISAL_DEF_MIN_LEVEL and ISAL_DEF_MAX_LEVEL. When the compression level is | |
518 | * ISAL_DEF_MIN_LEVEL, hufftables can be set to a table trained for the the | |
519 | * specific data type being compressed to achieve better compression. When a | |
520 | * higher compression level is desired, a larger generic memory buffer needs to | |
521 | * be supplied by setting level_buf and level_buf_size to represent the chunk of | |
522 | * memory. For level x, the suggest size for this buffer this buffer is | |
523 | * ISAL_DEFL_LVLx_DEFAULT. The defines ISAL_DEFL_LVLx_MIN, ISAL_DEFL_LVLx_SMALL, | |
524 | * ISAL_DEFL_LVLx_MEDIUM, ISAL_DEFL_LVLx_LARGE, and ISAL_DEFL_LVLx_EXTRA_LARGE | |
525 | * are also provided as other suggested sizes. | |
526 | * | |
7c673cae | 527 | * The equivalent of the zlib FLUSH_SYNC operation is currently supported. |
224ce89b WB |
528 | * Flush types can be NO_FLUSH, SYNC_FLUSH or FULL_FLUSH. Default flush type is |
529 | * NO_FLUSH. A SYNC_ OR FULL_ flush will byte align the deflate block by | |
530 | * appending an empty stored block once all input has been compressed, including | |
531 | * the buffered input. Checking that the out_buffer is not empty or that | |
532 | * internal_state.state = ZSTATE_NEW_HDR is sufficient to guarantee all input | |
533 | * has been flushed. Additionally FULL_FLUSH will ensure look back history does | |
534 | * not include previous blocks so new blocks are fully independent. Switching | |
535 | * between flush types is supported. | |
536 | * | |
537 | * If the gzip_flag is set to IGZIP_GZIP, a generic gzip header and the gzip | |
538 | * trailer are written around the deflate compressed data. If gzip_flag is set | |
539 | * to IGZIP_GZIP_NO_HDR, then only the gzip trailer is written. | |
7c673cae FG |
540 | * |
541 | * @param stream Structure holding state information on the compression streams. | |
542 | * @return COMP_OK (if everything is ok), | |
543 | * INVALID_FLUSH (if an invalid FLUSH is selected), | |
224ce89b | 544 | * ISAL_INVALID_LEVEL (if an invalid compression level is selected). |
7c673cae FG |
545 | */ |
546 | int isal_deflate(struct isal_zstream *stream); | |
547 | ||
548 | ||
549 | /** | |
550 | * @brief Fast data (deflate) stateless compression for storage applications. | |
551 | * | |
552 | * Stateless (one shot) compression routine with a similar interface to | |
553 | * isal_deflate() but operates on entire input buffer at one time. Parameter | |
554 | * avail_out must be large enough to fit the entire compressed output. Max | |
555 | * expansion is limited to the input size plus the header size of a stored/raw | |
556 | * block. | |
557 | * | |
224ce89b WB |
558 | * When the compression level is set to 1, unlike in isal_deflate(), level_buf |
559 | * may be optionally set depending on what what permormance is desired. | |
560 | * | |
561 | * For stateless the flush types NO_FLUSH and FULL_FLUSH are supported. | |
562 | * FULL_FLUSH will byte align the output deflate block so additional blocks can | |
563 | * be easily appended. | |
564 | * | |
565 | * If the gzip_flag is set to IGZIP_GZIP, a generic gzip header and the gzip | |
566 | * trailer are written around the deflate compressed data. If gzip_flag is set | |
567 | * to IGZIP_GZIP_NO_HDR, then only the gzip trailer is written. | |
568 | * | |
7c673cae FG |
569 | * @param stream Structure holding state information on the compression streams. |
570 | * @return COMP_OK (if everything is ok), | |
224ce89b WB |
571 | * INVALID_FLUSH (if an invalid FLUSH is selected), |
572 | * ISAL_INVALID_LEVEL (if an invalid compression level is selected), | |
7c673cae FG |
573 | * STATELESS_OVERFLOW (if output buffer will not fit output). |
574 | */ | |
575 | int isal_deflate_stateless(struct isal_zstream *stream); | |
576 | ||
577 | ||
224ce89b WB |
578 | /******************************************************************************/ |
579 | /* Inflate functions */ | |
580 | /******************************************************************************/ | |
581 | /** | |
582 | * @brief Initialize decompression state data structure | |
583 | * | |
584 | * @param state Structure holding state information on the compression streams. | |
585 | * @returns none | |
586 | */ | |
587 | void isal_inflate_init(struct inflate_state *state); | |
588 | ||
589 | /** | |
590 | * @brief Fast data (deflate) decompression for storage applications. | |
591 | * | |
592 | * On entry to isal_inflate(), next_in points to an input buffer and avail_in | |
593 | * indicates the length of that buffer. Similarly next_out points to an empty | |
594 | * output buffer and avail_out indicates the size of that buffer. | |
595 | * | |
596 | * The field total_out starts at 0 and is updated by isal_inflate(). This | |
597 | * reflects the total number of bytes written so far. | |
598 | * | |
599 | * The call to isal_inflate() will take data from the input buffer (updating | |
600 | * next_in, avail_in and write a decompressed stream to the output buffer | |
601 | * (updating next_out and avail_out). The function returns when the input buffer | |
602 | * is empty, the output buffer is full or invalid data is found. The current | |
603 | * state of the decompression on exit can be read from state->block-state. If | |
604 | * the crc_flag is set, the gzip crc of the output is stored in state->crc. | |
605 | * | |
606 | * @param state Structure holding state information on the compression streams. | |
607 | * @return ISAL_DECOMP_OK (if everything is ok), | |
608 | * ISAL_END_INPUT (if all input was decompressed), | |
609 | * ISAL_OUT_OVERFLOW (if output buffer ran out of space), | |
610 | * ISAL_INVALID_BLOCK, | |
611 | * ISAL_INVALID_SYMBOL, | |
612 | * ISAL_INVALID_LOOKBACK. | |
613 | */ | |
614 | int isal_inflate(struct inflate_state *state); | |
615 | ||
616 | /** | |
617 | * @brief Fast data (deflate) stateless decompression for storage applications. | |
618 | * | |
619 | * Stateless (one shot) decompression routine with a similar interface to | |
620 | * isal_inflate() but operates on entire input buffer at one time. Parameter | |
621 | * avail_out must be large enough to fit the entire decompressed output. | |
622 | * | |
623 | * @param state Structure holding state information on the compression streams. | |
624 | * @return ISAL_DECOMP_OK (if everything is ok), | |
625 | * ISAL_END_INPUT (if all input was decompressed), | |
626 | * ISAL_OUT_OVERFLOW (if output buffer ran out of space), | |
627 | * ISAL_INVALID_BLOCK, | |
628 | * ISAL_INVALID_SYMBOL, | |
629 | * ISAL_INVALID_LOOKBACK. | |
630 | */ | |
631 | int isal_inflate_stateless(struct inflate_state *state); | |
632 | ||
7c673cae FG |
633 | #ifdef __cplusplus |
634 | } | |
635 | #endif | |
636 | #endif /* ifndef _IGZIP_H */ |