]>
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 HUFF_CODES_H | |
31 | #define HUFF_CODES_H | |
32 | ||
33 | #include <immintrin.h> | |
34 | #include <stdint.h> | |
35 | #include <string.h> | |
36 | #include <assert.h> | |
37 | #include "igzip_lib.h" | |
38 | #include "bitbuf2.h" | |
39 | ||
40 | #ifdef _MSC_VER | |
41 | # include <intrin.h> | |
42 | #else | |
43 | # include <x86intrin.h> | |
44 | #endif | |
45 | ||
224ce89b WB |
46 | #define LIT_LEN ISAL_DEF_LIT_LEN_SYMBOLS |
47 | #define DIST_LEN ISAL_DEF_DIST_SYMBOLS | |
7c673cae FG |
48 | #define CODE_LEN_CODES 19 |
49 | #define HUFF_LEN 19 | |
50 | #ifdef LONGER_HUFFTABLE | |
51 | # define DCODE_OFFSET 26 | |
52 | #else | |
224ce89b | 53 | # define DCODE_OFFSET 0 |
7c673cae FG |
54 | #endif |
55 | #define DYN_HDR_START_LEN 17 | |
56 | #define MAX_HISTHEAP_SIZE LIT_LEN | |
57 | #define MAX_HUFF_TREE_DEPTH 15 | |
224ce89b | 58 | #define D IGZIP_HIST_SIZE /* Amount of history */ |
7c673cae FG |
59 | |
60 | #define MAX_DEFLATE_CODE_LEN 15 | |
61 | #define MAX_SAFE_LIT_CODE_LEN 13 | |
62 | #define MAX_SAFE_DIST_CODE_LEN 12 | |
63 | ||
64 | #define LONG_DIST_TABLE_SIZE 8192 | |
224ce89b | 65 | #define SHORT_DIST_TABLE_SIZE 2 |
7c673cae FG |
66 | #define LEN_TABLE_SIZE 256 |
67 | #define LIT_TABLE_SIZE 257 | |
68 | #define LAST_BLOCK 1 | |
69 | ||
70 | #define LEN_EXTRA_BITS_START 264 | |
71 | #define LEN_EXTRA_BITS_INTERVAL 4 | |
72 | #define DIST_EXTRA_BITS_START 3 | |
73 | #define DIST_EXTRA_BITS_INTERVAL 2 | |
74 | ||
75 | #define INVALID_LIT_LEN_HUFFCODE 1 | |
76 | #define INVALID_DIST_HUFFCODE 1 | |
77 | #define INVALID_HUFFCODE 1 | |
78 | ||
224ce89b WB |
79 | #define HASH_MASK (IGZIP_HASH_SIZE - 1) |
80 | #define SHORTEST_MATCH 4 | |
81 | ||
82 | #define LENGTH_BITS 5 | |
83 | #define FREQ_SHIFT 16 | |
84 | #define FREQ_MASK_HI (0xFFFFFFFFFFFF0000) | |
85 | #define DEPTH_SHIFT 24 | |
86 | #define DEPTH_MASK 0x7F | |
87 | #define DEPTH_MASK_HI (DEPTH_MASK << DEPTH_SHIFT) | |
88 | #define DEPTH_1 (1 << DEPTH_SHIFT) | |
89 | #define HEAP_TREE_SIZE (3*MAX_HISTHEAP_SIZE + 1) | |
90 | #define HEAP_TREE_NODE_START (HEAP_TREE_SIZE-1) | |
91 | #define MAX_BL_CODE_LEN 7 | |
92 | ||
7c673cae FG |
93 | /** |
94 | * @brief Structure used to store huffman codes | |
95 | */ | |
96 | struct huff_code { | |
224ce89b WB |
97 | union { |
98 | struct { | |
99 | uint16_t code; | |
100 | uint8_t extra_bit_count; | |
101 | uint8_t length; | |
102 | }; | |
103 | struct { | |
104 | uint32_t code_and_extra:24; | |
105 | uint32_t length2:8; | |
106 | }; | |
107 | }; | |
7c673cae FG |
108 | }; |
109 | ||
224ce89b WB |
110 | struct tree_node { |
111 | uint32_t child; | |
112 | uint32_t depth; | |
7c673cae FG |
113 | }; |
114 | ||
224ce89b WB |
115 | struct heap_tree { |
116 | union { | |
117 | uint64_t heap[HEAP_TREE_SIZE]; | |
118 | uint64_t code_len_count[MAX_HUFF_TREE_DEPTH + 1]; | |
119 | struct tree_node tree[HEAP_TREE_SIZE]; | |
120 | }; | |
7c673cae FG |
121 | }; |
122 | ||
224ce89b WB |
123 | struct rl_code { |
124 | uint8_t code; | |
125 | uint8_t extra_bits; | |
7c673cae FG |
126 | }; |
127 | ||
224ce89b WB |
128 | struct hufftables_icf { |
129 | struct huff_code dist_table[31]; | |
130 | struct huff_code lit_len_table[513]; | |
7c673cae FG |
131 | }; |
132 | ||
7c673cae FG |
133 | /** |
134 | * @brief Returns the deflate symbol value for a repeat length. | |
135 | */ | |
136 | uint32_t convert_length_to_len_sym(uint32_t length); | |
137 | ||
138 | /** | |
139 | * @brief Returns the deflate symbol value for a look back distance. | |
140 | */ | |
141 | uint32_t convert_dist_to_dist_sym(uint32_t dist); | |
142 | ||
7c673cae FG |
143 | /** |
144 | * @brief Determines the code each element of a deflate compliant huffman tree and stores | |
145 | * it in a lookup table | |
146 | * @requires table has been initialized to already contain the code length for each element. | |
147 | * @param table: A lookup table used to store the codes. | |
148 | * @param table_length: The length of table. | |
149 | * @param count: a histogram representing the number of occurences of codes of a given length | |
150 | */ | |
224ce89b | 151 | uint32_t set_huff_codes(struct huff_code *table, int table_length, uint32_t * count); |
7c673cae FG |
152 | |
153 | /** | |
154 | * @brief Checks if a literal/length huffman table can be stored in the igzip hufftables files. | |
155 | * @param table: A literal/length huffman code lookup table. | |
156 | * @returns index of the first symbol which fails and 0xFFFF otherwise. | |
157 | */ | |
158 | uint16_t valid_lit_huff_table(struct huff_code *huff_code_table); | |
159 | ||
160 | /** | |
161 | * @brief Checks if a distance huffman table can be stored in the igzip hufftables files. | |
162 | * @param table: A distance huffman code lookup table. | |
163 | * @returnsthe index of the first symbol which fails and 0xFFFF otherwise. | |
164 | */ | |
165 | uint16_t valid_dist_huff_table(struct huff_code *huff_code_table); | |
166 | ||
167 | /** | |
168 | * @brief Creates the dynamic huffman deflate header. | |
169 | * @returns Returns the length of header in bits. | |
170 | * @requires This function requires header is large enough to store the whole header. | |
171 | * @param header: The output header. | |
172 | * @param lit_huff_table: A literal/length code huffman lookup table. | |
173 | * @param dist_huff_table: A distance huffman code lookup table. | |
174 | * @param end_of_block: Value determining whether end of block header is produced or not; | |
175 | * 0 corresponds to not end of block and all other inputs correspond to end of block. | |
176 | */ | |
224ce89b WB |
177 | int create_header(struct BitBuf2 *header_bitbuf, struct rl_code *huffman_rep, uint32_t length, |
178 | uint64_t * histogram, uint32_t hlit, uint32_t hdist, uint32_t end_of_block); | |
7c673cae FG |
179 | |
180 | /** | |
181 | * @brief Creates the header for run length encoded huffman trees. | |
182 | * @param header: the output header. | |
183 | * @param lookup_table: a huffman lookup table. | |
184 | * @param huffman_rep: a run length encoded huffman tree. | |
185 | * @extra_bits: extra bits associated with the corresponding spot in huffman_rep | |
186 | * @param huffman_rep_length: the length of huffman_rep. | |
187 | * @param end_of_block: Value determining whether end of block header is produced or not; | |
188 | * 0 corresponds to not end of block and all other inputs correspond to end of block. | |
189 | * @param hclen: Length of huffman code for huffman codes minus 4. | |
190 | * @param hlit: Length of literal/length table minus 257. | |
191 | * @parm hdist: Length of distance table minus 1. | |
192 | */ | |
224ce89b WB |
193 | int create_huffman_header(struct BitBuf2 *header_bitbuf, struct huff_code *lookup_table, |
194 | struct rl_code * huffman_rep, uint16_t huffman_rep_length, | |
195 | uint32_t end_of_block, uint32_t hclen, uint32_t hlit, | |
196 | uint32_t hdist); | |
7c673cae FG |
197 | |
198 | /** | |
199 | * @brief Creates a two table representation of huffman codes. | |
200 | * @param code_table: output table containing the code | |
201 | * @param code_size_table: output table containing the code length | |
202 | * @param length: the lenght of hufftable | |
203 | * @param hufftable: a huffman lookup table | |
204 | */ | |
205 | void create_code_tables(uint16_t * code_table, uint8_t * code_length_table, | |
206 | uint32_t length, struct huff_code *hufftable); | |
207 | ||
208 | /** | |
209 | * @brief Creates a packed representation of length huffman codes. | |
210 | * @details In packed_table, bits 32:8 contain the extra bits appended to the huffman | |
211 | * code and bits 8:0 contain the code length. | |
212 | * @param packed_table: the output table | |
213 | * @param length: the length of lit_len_hufftable | |
214 | * @param lit_len_hufftable: a literal/length huffman lookup table | |
215 | */ | |
216 | void create_packed_len_table(uint32_t * packed_table, struct huff_code *lit_len_hufftable); | |
217 | ||
218 | /** | |
219 | * @brief Creates a packed representation of distance huffman codes. | |
220 | * @details In packed_table, bits 32:8 contain the extra bits appended to the huffman | |
221 | * code and bits 8:0 contain the code length. | |
222 | * @param packed_table: the output table | |
223 | * @param length: the length of lit_len_hufftable | |
224 | * @param dist_hufftable: a distance huffman lookup table | |
225 | */ | |
226 | void create_packed_dist_table(uint32_t * packed_table, uint32_t length, | |
227 | struct huff_code *dist_hufftable); | |
228 | ||
229 | /** | |
230 | * @brief Checks to see if the hufftable is usable by igzip | |
231 | * | |
232 | * @param lit_len_hufftable: literal/lenght huffman code | |
233 | * @param dist_hufftable: distance huffman code | |
234 | * @returns Returns 0 if the table is usable | |
235 | */ | |
236 | int are_hufftables_useable(struct huff_code *lit_len_hufftable, | |
237 | struct huff_code *dist_hufftable); | |
224ce89b WB |
238 | |
239 | /** | |
240 | * @brief Creates a representation of the huffman code from a histogram used to | |
241 | * decompress the intermediate compression format. | |
242 | * | |
243 | * @param bb: bitbuf structure where the header huffman code header is written | |
244 | * @param hufftables: output huffman code representation | |
245 | * @param hist: histogram used to generat huffman code | |
246 | * @param end_of_block: flag whether this is the final huffman code | |
247 | */ | |
248 | void | |
249 | create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf * hufftables, | |
250 | struct isal_mod_hist *hist, uint32_t end_of_block); | |
251 | ||
7c673cae | 252 | #endif |