1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
10 | |
11 | |
12 | |
13 | |
14 | |
15 | |
16 | |
17 | |
18 | |
19 | |
20 | |
21 | |
22 | |
23 | |
24 | |
25 | |
26 | |
27 | |
28 | |
29 | |
30 | #include <immintrin.h> |
31 | #include <stdint.h> |
32 | #include <string.h> |
33 | #include <assert.h> |
34 | #include "igzip_lib.h" |
35 | #include "huff_codes.h" |
36 | #include "huffman.h" |
37 | #include "bitbuf2.h" |
38 | #include "flatten_ll.h" |
39 | |
40 | |
41 | |
42 | static const uint8_t code_length_code_order[] = |
43 | { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; |
44 | |
45 | const uint32_t len_code_extra_bits[] = { |
46 | 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, |
47 | 0x1, 0x1, 0x1, 0x1, 0x2, 0x2, 0x2, 0x2, |
48 | 0x3, 0x3, 0x3, 0x3, 0x4, 0x4, 0x4, 0x4, |
49 | 0x5, 0x5, 0x5, 0x5, 0x0 |
50 | }; |
51 | |
52 | const uint32_t dist_code_extra_bits[] = { |
53 | 0x0, 0x0, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, |
54 | 0x3, 0x3, 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, |
55 | 0x7, 0x7, 0x8, 0x8, 0x9, 0x9, 0xa, 0xa, |
56 | 0xb, 0xb, 0xc, 0xc, 0xd, 0xd |
57 | }; |
58 | |
59 | struct hufftables_icf static_hufftables = { |
60 | .lit_len_table = { |
61 | {.code_and_extra = 0x00c,.length2 = 0x8}, |
62 | {.code_and_extra = 0x08c,.length2 = 0x8}, |
63 | {.code_and_extra = 0x04c,.length2 = 0x8}, |
64 | {.code_and_extra = 0x0cc,.length2 = 0x8}, |
65 | {.code_and_extra = 0x02c,.length2 = 0x8}, |
66 | {.code_and_extra = 0x0ac,.length2 = 0x8}, |
67 | {.code_and_extra = 0x06c,.length2 = 0x8}, |
68 | {.code_and_extra = 0x0ec,.length2 = 0x8}, |
69 | {.code_and_extra = 0x01c,.length2 = 0x8}, |
70 | {.code_and_extra = 0x09c,.length2 = 0x8}, |
71 | {.code_and_extra = 0x05c,.length2 = 0x8}, |
72 | {.code_and_extra = 0x0dc,.length2 = 0x8}, |
73 | {.code_and_extra = 0x03c,.length2 = 0x8}, |
74 | {.code_and_extra = 0x0bc,.length2 = 0x8}, |
75 | {.code_and_extra = 0x07c,.length2 = 0x8}, |
76 | {.code_and_extra = 0x0fc,.length2 = 0x8}, |
77 | {.code_and_extra = 0x002,.length2 = 0x8}, |
78 | {.code_and_extra = 0x082,.length2 = 0x8}, |
79 | {.code_and_extra = 0x042,.length2 = 0x8}, |
80 | {.code_and_extra = 0x0c2,.length2 = 0x8}, |
81 | {.code_and_extra = 0x022,.length2 = 0x8}, |
82 | {.code_and_extra = 0x0a2,.length2 = 0x8}, |
83 | {.code_and_extra = 0x062,.length2 = 0x8}, |
84 | {.code_and_extra = 0x0e2,.length2 = 0x8}, |
85 | {.code_and_extra = 0x012,.length2 = 0x8}, |
86 | {.code_and_extra = 0x092,.length2 = 0x8}, |
87 | {.code_and_extra = 0x052,.length2 = 0x8}, |
88 | {.code_and_extra = 0x0d2,.length2 = 0x8}, |
89 | {.code_and_extra = 0x032,.length2 = 0x8}, |
90 | {.code_and_extra = 0x0b2,.length2 = 0x8}, |
91 | {.code_and_extra = 0x072,.length2 = 0x8}, |
92 | {.code_and_extra = 0x0f2,.length2 = 0x8}, |
93 | {.code_and_extra = 0x00a,.length2 = 0x8}, |
94 | {.code_and_extra = 0x08a,.length2 = 0x8}, |
95 | {.code_and_extra = 0x04a,.length2 = 0x8}, |
96 | {.code_and_extra = 0x0ca,.length2 = 0x8}, |
97 | {.code_and_extra = 0x02a,.length2 = 0x8}, |
98 | {.code_and_extra = 0x0aa,.length2 = 0x8}, |
99 | {.code_and_extra = 0x06a,.length2 = 0x8}, |
100 | {.code_and_extra = 0x0ea,.length2 = 0x8}, |
101 | {.code_and_extra = 0x01a,.length2 = 0x8}, |
102 | {.code_and_extra = 0x09a,.length2 = 0x8}, |
103 | {.code_and_extra = 0x05a,.length2 = 0x8}, |
104 | {.code_and_extra = 0x0da,.length2 = 0x8}, |
105 | {.code_and_extra = 0x03a,.length2 = 0x8}, |
106 | {.code_and_extra = 0x0ba,.length2 = 0x8}, |
107 | {.code_and_extra = 0x07a,.length2 = 0x8}, |
108 | {.code_and_extra = 0x0fa,.length2 = 0x8}, |
109 | {.code_and_extra = 0x006,.length2 = 0x8}, |
110 | {.code_and_extra = 0x086,.length2 = 0x8}, |
111 | {.code_and_extra = 0x046,.length2 = 0x8}, |
112 | {.code_and_extra = 0x0c6,.length2 = 0x8}, |
113 | {.code_and_extra = 0x026,.length2 = 0x8}, |
114 | {.code_and_extra = 0x0a6,.length2 = 0x8}, |
115 | {.code_and_extra = 0x066,.length2 = 0x8}, |
116 | {.code_and_extra = 0x0e6,.length2 = 0x8}, |
117 | {.code_and_extra = 0x016,.length2 = 0x8}, |
118 | {.code_and_extra = 0x096,.length2 = 0x8}, |
119 | {.code_and_extra = 0x056,.length2 = 0x8}, |
120 | {.code_and_extra = 0x0d6,.length2 = 0x8}, |
121 | {.code_and_extra = 0x036,.length2 = 0x8}, |
122 | {.code_and_extra = 0x0b6,.length2 = 0x8}, |
123 | {.code_and_extra = 0x076,.length2 = 0x8}, |
124 | {.code_and_extra = 0x0f6,.length2 = 0x8}, |
125 | {.code_and_extra = 0x00e,.length2 = 0x8}, |
126 | {.code_and_extra = 0x08e,.length2 = 0x8}, |
127 | {.code_and_extra = 0x04e,.length2 = 0x8}, |
128 | {.code_and_extra = 0x0ce,.length2 = 0x8}, |
129 | {.code_and_extra = 0x02e,.length2 = 0x8}, |
130 | {.code_and_extra = 0x0ae,.length2 = 0x8}, |
131 | {.code_and_extra = 0x06e,.length2 = 0x8}, |
132 | {.code_and_extra = 0x0ee,.length2 = 0x8}, |
133 | {.code_and_extra = 0x01e,.length2 = 0x8}, |
134 | {.code_and_extra = 0x09e,.length2 = 0x8}, |
135 | {.code_and_extra = 0x05e,.length2 = 0x8}, |
136 | {.code_and_extra = 0x0de,.length2 = 0x8}, |
137 | {.code_and_extra = 0x03e,.length2 = 0x8}, |
138 | {.code_and_extra = 0x0be,.length2 = 0x8}, |
139 | {.code_and_extra = 0x07e,.length2 = 0x8}, |
140 | {.code_and_extra = 0x0fe,.length2 = 0x8}, |
141 | {.code_and_extra = 0x001,.length2 = 0x8}, |
142 | {.code_and_extra = 0x081,.length2 = 0x8}, |
143 | {.code_and_extra = 0x041,.length2 = 0x8}, |
144 | {.code_and_extra = 0x0c1,.length2 = 0x8}, |
145 | {.code_and_extra = 0x021,.length2 = 0x8}, |
146 | {.code_and_extra = 0x0a1,.length2 = 0x8}, |
147 | {.code_and_extra = 0x061,.length2 = 0x8}, |
148 | {.code_and_extra = 0x0e1,.length2 = 0x8}, |
149 | {.code_and_extra = 0x011,.length2 = 0x8}, |
150 | {.code_and_extra = 0x091,.length2 = 0x8}, |
151 | {.code_and_extra = 0x051,.length2 = 0x8}, |
152 | {.code_and_extra = 0x0d1,.length2 = 0x8}, |
153 | {.code_and_extra = 0x031,.length2 = 0x8}, |
154 | {.code_and_extra = 0x0b1,.length2 = 0x8}, |
155 | {.code_and_extra = 0x071,.length2 = 0x8}, |
156 | {.code_and_extra = 0x0f1,.length2 = 0x8}, |
157 | {.code_and_extra = 0x009,.length2 = 0x8}, |
158 | {.code_and_extra = 0x089,.length2 = 0x8}, |
159 | {.code_and_extra = 0x049,.length2 = 0x8}, |
160 | {.code_and_extra = 0x0c9,.length2 = 0x8}, |
161 | {.code_and_extra = 0x029,.length2 = 0x8}, |
162 | {.code_and_extra = 0x0a9,.length2 = 0x8}, |
163 | {.code_and_extra = 0x069,.length2 = 0x8}, |
164 | {.code_and_extra = 0x0e9,.length2 = 0x8}, |
165 | {.code_and_extra = 0x019,.length2 = 0x8}, |
166 | {.code_and_extra = 0x099,.length2 = 0x8}, |
167 | {.code_and_extra = 0x059,.length2 = 0x8}, |
168 | {.code_and_extra = 0x0d9,.length2 = 0x8}, |
169 | {.code_and_extra = 0x039,.length2 = 0x8}, |
170 | {.code_and_extra = 0x0b9,.length2 = 0x8}, |
171 | {.code_and_extra = 0x079,.length2 = 0x8}, |
172 | {.code_and_extra = 0x0f9,.length2 = 0x8}, |
173 | {.code_and_extra = 0x005,.length2 = 0x8}, |
174 | {.code_and_extra = 0x085,.length2 = 0x8}, |
175 | {.code_and_extra = 0x045,.length2 = 0x8}, |
176 | {.code_and_extra = 0x0c5,.length2 = 0x8}, |
177 | {.code_and_extra = 0x025,.length2 = 0x8}, |
178 | {.code_and_extra = 0x0a5,.length2 = 0x8}, |
179 | {.code_and_extra = 0x065,.length2 = 0x8}, |
180 | {.code_and_extra = 0x0e5,.length2 = 0x8}, |
181 | {.code_and_extra = 0x015,.length2 = 0x8}, |
182 | {.code_and_extra = 0x095,.length2 = 0x8}, |
183 | {.code_and_extra = 0x055,.length2 = 0x8}, |
184 | {.code_and_extra = 0x0d5,.length2 = 0x8}, |
185 | {.code_and_extra = 0x035,.length2 = 0x8}, |
186 | {.code_and_extra = 0x0b5,.length2 = 0x8}, |
187 | {.code_and_extra = 0x075,.length2 = 0x8}, |
188 | {.code_and_extra = 0x0f5,.length2 = 0x8}, |
189 | {.code_and_extra = 0x00d,.length2 = 0x8}, |
190 | {.code_and_extra = 0x08d,.length2 = 0x8}, |
191 | {.code_and_extra = 0x04d,.length2 = 0x8}, |
192 | {.code_and_extra = 0x0cd,.length2 = 0x8}, |
193 | {.code_and_extra = 0x02d,.length2 = 0x8}, |
194 | {.code_and_extra = 0x0ad,.length2 = 0x8}, |
195 | {.code_and_extra = 0x06d,.length2 = 0x8}, |
196 | {.code_and_extra = 0x0ed,.length2 = 0x8}, |
197 | {.code_and_extra = 0x01d,.length2 = 0x8}, |
198 | {.code_and_extra = 0x09d,.length2 = 0x8}, |
199 | {.code_and_extra = 0x05d,.length2 = 0x8}, |
200 | {.code_and_extra = 0x0dd,.length2 = 0x8}, |
201 | {.code_and_extra = 0x03d,.length2 = 0x8}, |
202 | {.code_and_extra = 0x0bd,.length2 = 0x8}, |
203 | {.code_and_extra = 0x07d,.length2 = 0x8}, |
204 | {.code_and_extra = 0x0fd,.length2 = 0x8}, |
205 | {.code_and_extra = 0x013,.length2 = 0x9}, |
206 | {.code_and_extra = 0x113,.length2 = 0x9}, |
207 | {.code_and_extra = 0x093,.length2 = 0x9}, |
208 | {.code_and_extra = 0x193,.length2 = 0x9}, |
209 | {.code_and_extra = 0x053,.length2 = 0x9}, |
210 | {.code_and_extra = 0x153,.length2 = 0x9}, |
211 | {.code_and_extra = 0x0d3,.length2 = 0x9}, |
212 | {.code_and_extra = 0x1d3,.length2 = 0x9}, |
213 | {.code_and_extra = 0x033,.length2 = 0x9}, |
214 | {.code_and_extra = 0x133,.length2 = 0x9}, |
215 | {.code_and_extra = 0x0b3,.length2 = 0x9}, |
216 | {.code_and_extra = 0x1b3,.length2 = 0x9}, |
217 | {.code_and_extra = 0x073,.length2 = 0x9}, |
218 | {.code_and_extra = 0x173,.length2 = 0x9}, |
219 | {.code_and_extra = 0x0f3,.length2 = 0x9}, |
220 | {.code_and_extra = 0x1f3,.length2 = 0x9}, |
221 | {.code_and_extra = 0x00b,.length2 = 0x9}, |
222 | {.code_and_extra = 0x10b,.length2 = 0x9}, |
223 | {.code_and_extra = 0x08b,.length2 = 0x9}, |
224 | {.code_and_extra = 0x18b,.length2 = 0x9}, |
225 | {.code_and_extra = 0x04b,.length2 = 0x9}, |
226 | {.code_and_extra = 0x14b,.length2 = 0x9}, |
227 | {.code_and_extra = 0x0cb,.length2 = 0x9}, |
228 | {.code_and_extra = 0x1cb,.length2 = 0x9}, |
229 | {.code_and_extra = 0x02b,.length2 = 0x9}, |
230 | {.code_and_extra = 0x12b,.length2 = 0x9}, |
231 | {.code_and_extra = 0x0ab,.length2 = 0x9}, |
232 | {.code_and_extra = 0x1ab,.length2 = 0x9}, |
233 | {.code_and_extra = 0x06b,.length2 = 0x9}, |
234 | {.code_and_extra = 0x16b,.length2 = 0x9}, |
235 | {.code_and_extra = 0x0eb,.length2 = 0x9}, |
236 | {.code_and_extra = 0x1eb,.length2 = 0x9}, |
237 | {.code_and_extra = 0x01b,.length2 = 0x9}, |
238 | {.code_and_extra = 0x11b,.length2 = 0x9}, |
239 | {.code_and_extra = 0x09b,.length2 = 0x9}, |
240 | {.code_and_extra = 0x19b,.length2 = 0x9}, |
241 | {.code_and_extra = 0x05b,.length2 = 0x9}, |
242 | {.code_and_extra = 0x15b,.length2 = 0x9}, |
243 | {.code_and_extra = 0x0db,.length2 = 0x9}, |
244 | {.code_and_extra = 0x1db,.length2 = 0x9}, |
245 | {.code_and_extra = 0x03b,.length2 = 0x9}, |
246 | {.code_and_extra = 0x13b,.length2 = 0x9}, |
247 | {.code_and_extra = 0x0bb,.length2 = 0x9}, |
248 | {.code_and_extra = 0x1bb,.length2 = 0x9}, |
249 | {.code_and_extra = 0x07b,.length2 = 0x9}, |
250 | {.code_and_extra = 0x17b,.length2 = 0x9}, |
251 | {.code_and_extra = 0x0fb,.length2 = 0x9}, |
252 | {.code_and_extra = 0x1fb,.length2 = 0x9}, |
253 | {.code_and_extra = 0x007,.length2 = 0x9}, |
254 | {.code_and_extra = 0x107,.length2 = 0x9}, |
255 | {.code_and_extra = 0x087,.length2 = 0x9}, |
256 | {.code_and_extra = 0x187,.length2 = 0x9}, |
257 | {.code_and_extra = 0x047,.length2 = 0x9}, |
258 | {.code_and_extra = 0x147,.length2 = 0x9}, |
259 | {.code_and_extra = 0x0c7,.length2 = 0x9}, |
260 | {.code_and_extra = 0x1c7,.length2 = 0x9}, |
261 | {.code_and_extra = 0x027,.length2 = 0x9}, |
262 | {.code_and_extra = 0x127,.length2 = 0x9}, |
263 | {.code_and_extra = 0x0a7,.length2 = 0x9}, |
264 | {.code_and_extra = 0x1a7,.length2 = 0x9}, |
265 | {.code_and_extra = 0x067,.length2 = 0x9}, |
266 | {.code_and_extra = 0x167,.length2 = 0x9}, |
267 | {.code_and_extra = 0x0e7,.length2 = 0x9}, |
268 | {.code_and_extra = 0x1e7,.length2 = 0x9}, |
269 | {.code_and_extra = 0x017,.length2 = 0x9}, |
270 | {.code_and_extra = 0x117,.length2 = 0x9}, |
271 | {.code_and_extra = 0x097,.length2 = 0x9}, |
272 | {.code_and_extra = 0x197,.length2 = 0x9}, |
273 | {.code_and_extra = 0x057,.length2 = 0x9}, |
274 | {.code_and_extra = 0x157,.length2 = 0x9}, |
275 | {.code_and_extra = 0x0d7,.length2 = 0x9}, |
276 | {.code_and_extra = 0x1d7,.length2 = 0x9}, |
277 | {.code_and_extra = 0x037,.length2 = 0x9}, |
278 | {.code_and_extra = 0x137,.length2 = 0x9}, |
279 | {.code_and_extra = 0x0b7,.length2 = 0x9}, |
280 | {.code_and_extra = 0x1b7,.length2 = 0x9}, |
281 | {.code_and_extra = 0x077,.length2 = 0x9}, |
282 | {.code_and_extra = 0x177,.length2 = 0x9}, |
283 | {.code_and_extra = 0x0f7,.length2 = 0x9}, |
284 | {.code_and_extra = 0x1f7,.length2 = 0x9}, |
285 | {.code_and_extra = 0x00f,.length2 = 0x9}, |
286 | {.code_and_extra = 0x10f,.length2 = 0x9}, |
287 | {.code_and_extra = 0x08f,.length2 = 0x9}, |
288 | {.code_and_extra = 0x18f,.length2 = 0x9}, |
289 | {.code_and_extra = 0x04f,.length2 = 0x9}, |
290 | {.code_and_extra = 0x14f,.length2 = 0x9}, |
291 | {.code_and_extra = 0x0cf,.length2 = 0x9}, |
292 | {.code_and_extra = 0x1cf,.length2 = 0x9}, |
293 | {.code_and_extra = 0x02f,.length2 = 0x9}, |
294 | {.code_and_extra = 0x12f,.length2 = 0x9}, |
295 | {.code_and_extra = 0x0af,.length2 = 0x9}, |
296 | {.code_and_extra = 0x1af,.length2 = 0x9}, |
297 | {.code_and_extra = 0x06f,.length2 = 0x9}, |
298 | {.code_and_extra = 0x16f,.length2 = 0x9}, |
299 | {.code_and_extra = 0x0ef,.length2 = 0x9}, |
300 | {.code_and_extra = 0x1ef,.length2 = 0x9}, |
301 | {.code_and_extra = 0x01f,.length2 = 0x9}, |
302 | {.code_and_extra = 0x11f,.length2 = 0x9}, |
303 | {.code_and_extra = 0x09f,.length2 = 0x9}, |
304 | {.code_and_extra = 0x19f,.length2 = 0x9}, |
305 | {.code_and_extra = 0x05f,.length2 = 0x9}, |
306 | {.code_and_extra = 0x15f,.length2 = 0x9}, |
307 | {.code_and_extra = 0x0df,.length2 = 0x9}, |
308 | {.code_and_extra = 0x1df,.length2 = 0x9}, |
309 | {.code_and_extra = 0x03f,.length2 = 0x9}, |
310 | {.code_and_extra = 0x13f,.length2 = 0x9}, |
311 | {.code_and_extra = 0x0bf,.length2 = 0x9}, |
312 | {.code_and_extra = 0x1bf,.length2 = 0x9}, |
313 | {.code_and_extra = 0x07f,.length2 = 0x9}, |
314 | {.code_and_extra = 0x17f,.length2 = 0x9}, |
315 | {.code_and_extra = 0x0ff,.length2 = 0x9}, |
316 | {.code_and_extra = 0x1ff,.length2 = 0x9}, |
317 | {.code_and_extra = 0x000,.length2 = 0x7}, |
318 | {.code_and_extra = 0x040,.length2 = 0x7}, |
319 | {.code_and_extra = 0x020,.length2 = 0x7}, |
320 | {.code_and_extra = 0x060,.length2 = 0x7}, |
321 | {.code_and_extra = 0x010,.length2 = 0x7}, |
322 | {.code_and_extra = 0x050,.length2 = 0x7}, |
323 | {.code_and_extra = 0x030,.length2 = 0x7}, |
324 | {.code_and_extra = 0x070,.length2 = 0x7}, |
325 | {.code_and_extra = 0x008,.length2 = 0x7}, |
326 | {.code_and_extra = 0x048,.length2 = 0x7}, |
327 | {.code_and_extra = 0x028,.length2 = 0x7}, |
328 | {.code_and_extra = 0x068,.length2 = 0x7}, |
329 | {.code_and_extra = 0x018,.length2 = 0x7}, |
330 | {.code_and_extra = 0x058,.length2 = 0x7}, |
331 | {.code_and_extra = 0x038,.length2 = 0x7}, |
332 | {.code_and_extra = 0x078,.length2 = 0x7}, |
333 | {.code_and_extra = 0x004,.length2 = 0x7}, |
334 | {.code_and_extra = 0x044,.length2 = 0x7}, |
335 | {.code_and_extra = 0x024,.length2 = 0x7}, |
336 | {.code_and_extra = 0x064,.length2 = 0x7}, |
337 | {.code_and_extra = 0x014,.length2 = 0x7}, |
338 | {.code_and_extra = 0x054,.length2 = 0x7}, |
339 | {.code_and_extra = 0x034,.length2 = 0x7}, |
340 | {.code_and_extra = 0x074,.length2 = 0x7}, |
341 | {.code_and_extra = 0x003,.length2 = 0x8}, |
342 | {.code_and_extra = 0x083,.length2 = 0x8}, |
343 | {.code_and_extra = 0x043,.length2 = 0x8}, |
344 | {.code_and_extra = 0x0c3,.length2 = 0x8}, |
345 | {.code_and_extra = 0x023,.length2 = 0x8}, |
346 | {.code_and_extra = 0x0a3,.length2 = 0x8}, |
347 | {.code_and_extra = 0x063,.length2 = 0x8}, |
348 | {.code_and_extra = 0x0e3,.length2 = 0x8}, |
349 | {.code_and_extra = 0x000,.length2 = 0x0}, |
350 | {.code_and_extra = 0x000,.length2 = 0x0}, |
351 | {.code_and_extra = 0x000,.length2 = 0x0}, |
352 | {.code_and_extra = 0x000,.length2 = 0x0}, |
353 | {.code_and_extra = 0x000,.length2 = 0x0}, |
354 | {.code_and_extra = 0x000,.length2 = 0x0}, |
355 | {.code_and_extra = 0x000,.length2 = 0x0}, |
356 | {.code_and_extra = 0x000,.length2 = 0x0}, |
357 | {.code_and_extra = 0x000,.length2 = 0x0}, |
358 | {.code_and_extra = 0x000,.length2 = 0x0}, |
359 | {.code_and_extra = 0x000,.length2 = 0x0}, |
360 | {.code_and_extra = 0x000,.length2 = 0x0}, |
361 | {.code_and_extra = 0x000,.length2 = 0x0}, |
362 | {.code_and_extra = 0x000,.length2 = 0x0}, |
363 | {.code_and_extra = 0x000,.length2 = 0x0}, |
364 | {.code_and_extra = 0x000,.length2 = 0x0}, |
365 | {.code_and_extra = 0x000,.length2 = 0x0}, |
366 | {.code_and_extra = 0x000,.length2 = 0x0}, |
367 | {.code_and_extra = 0x000,.length2 = 0x0}, |
368 | {.code_and_extra = 0x000,.length2 = 0x0}, |
369 | {.code_and_extra = 0x000,.length2 = 0x0}, |
370 | {.code_and_extra = 0x000,.length2 = 0x0}, |
371 | {.code_and_extra = 0x000,.length2 = 0x0}, |
372 | {.code_and_extra = 0x000,.length2 = 0x0}, |
373 | {.code_and_extra = 0x000,.length2 = 0x0}, |
374 | {.code_and_extra = 0x000,.length2 = 0x0}, |
375 | {.code_and_extra = 0x000,.length2 = 0x0}, |
376 | {.code_and_extra = 0x000,.length2 = 0x0}, |
377 | {.code_and_extra = 0x000,.length2 = 0x0}, |
378 | {.code_and_extra = 0x000,.length2 = 0x0}, |
379 | {.code_and_extra = 0x000,.length2 = 0x0}, |
380 | {.code_and_extra = 0x000,.length2 = 0x0}, |
381 | {.code_and_extra = 0x000,.length2 = 0x0}, |
382 | {.code_and_extra = 0x000,.length2 = 0x0}, |
383 | {.code_and_extra = 0x000,.length2 = 0x0}, |
384 | {.code_and_extra = 0x000,.length2 = 0x0}, |
385 | {.code_and_extra = 0x000,.length2 = 0x0}, |
386 | {.code_and_extra = 0x000,.length2 = 0x0}, |
387 | {.code_and_extra = 0x000,.length2 = 0x0}, |
388 | {.code_and_extra = 0x000,.length2 = 0x0}, |
389 | {.code_and_extra = 0x000,.length2 = 0x0}, |
390 | {.code_and_extra = 0x000,.length2 = 0x0}, |
391 | {.code_and_extra = 0x000,.length2 = 0x0}, |
392 | {.code_and_extra = 0x000,.length2 = 0x0}, |
393 | {.code_and_extra = 0x000,.length2 = 0x0}, |
394 | {.code_and_extra = 0x000,.length2 = 0x0}, |
395 | {.code_and_extra = 0x000,.length2 = 0x0}, |
396 | {.code_and_extra = 0x000,.length2 = 0x0}, |
397 | {.code_and_extra = 0x000,.length2 = 0x0}, |
398 | {.code_and_extra = 0x000,.length2 = 0x0}, |
399 | {.code_and_extra = 0x000,.length2 = 0x0}, |
400 | {.code_and_extra = 0x000,.length2 = 0x0}, |
401 | {.code_and_extra = 0x000,.length2 = 0x0}, |
402 | {.code_and_extra = 0x000,.length2 = 0x0}, |
403 | {.code_and_extra = 0x000,.length2 = 0x0}, |
404 | {.code_and_extra = 0x000,.length2 = 0x0}, |
405 | {.code_and_extra = 0x000,.length2 = 0x0}, |
406 | {.code_and_extra = 0x000,.length2 = 0x0}, |
407 | {.code_and_extra = 0x000,.length2 = 0x0}, |
408 | {.code_and_extra = 0x000,.length2 = 0x0}, |
409 | {.code_and_extra = 0x000,.length2 = 0x0}, |
410 | {.code_and_extra = 0x000,.length2 = 0x0}, |
411 | {.code_and_extra = 0x000,.length2 = 0x0}, |
412 | {.code_and_extra = 0x000,.length2 = 0x0}, |
413 | {.code_and_extra = 0x000,.length2 = 0x0}, |
414 | {.code_and_extra = 0x000,.length2 = 0x0}, |
415 | {.code_and_extra = 0x000,.length2 = 0x0}, |
416 | {.code_and_extra = 0x000,.length2 = 0x0}, |
417 | {.code_and_extra = 0x000,.length2 = 0x0}, |
418 | {.code_and_extra = 0x000,.length2 = 0x0}, |
419 | {.code_and_extra = 0x000,.length2 = 0x0}, |
420 | {.code_and_extra = 0x000,.length2 = 0x0}, |
421 | {.code_and_extra = 0x000,.length2 = 0x0}, |
422 | {.code_and_extra = 0x000,.length2 = 0x0}, |
423 | {.code_and_extra = 0x000,.length2 = 0x0}, |
424 | {.code_and_extra = 0x000,.length2 = 0x0}, |
425 | {.code_and_extra = 0x000,.length2 = 0x0}, |
426 | {.code_and_extra = 0x000,.length2 = 0x0}, |
427 | {.code_and_extra = 0x000,.length2 = 0x0}, |
428 | {.code_and_extra = 0x000,.length2 = 0x0}, |
429 | {.code_and_extra = 0x000,.length2 = 0x0}, |
430 | {.code_and_extra = 0x000,.length2 = 0x0}, |
431 | {.code_and_extra = 0x000,.length2 = 0x0}, |
432 | {.code_and_extra = 0x000,.length2 = 0x0}, |
433 | {.code_and_extra = 0x000,.length2 = 0x0}, |
434 | {.code_and_extra = 0x000,.length2 = 0x0}, |
435 | {.code_and_extra = 0x000,.length2 = 0x0}, |
436 | {.code_and_extra = 0x000,.length2 = 0x0}, |
437 | {.code_and_extra = 0x000,.length2 = 0x0}, |
438 | {.code_and_extra = 0x000,.length2 = 0x0}, |
439 | {.code_and_extra = 0x000,.length2 = 0x0}, |
440 | {.code_and_extra = 0x000,.length2 = 0x0}, |
441 | {.code_and_extra = 0x000,.length2 = 0x0}, |
442 | {.code_and_extra = 0x000,.length2 = 0x0}, |
443 | {.code_and_extra = 0x000,.length2 = 0x0}, |
444 | {.code_and_extra = 0x000,.length2 = 0x0}, |
445 | {.code_and_extra = 0x000,.length2 = 0x0}, |
446 | {.code_and_extra = 0x000,.length2 = 0x0}, |
447 | {.code_and_extra = 0x000,.length2 = 0x0}, |
448 | {.code_and_extra = 0x000,.length2 = 0x0}, |
449 | {.code_and_extra = 0x000,.length2 = 0x0}, |
450 | {.code_and_extra = 0x000,.length2 = 0x0}, |
451 | {.code_and_extra = 0x000,.length2 = 0x0}, |
452 | {.code_and_extra = 0x000,.length2 = 0x0}, |
453 | {.code_and_extra = 0x000,.length2 = 0x0}, |
454 | {.code_and_extra = 0x000,.length2 = 0x0}, |
455 | {.code_and_extra = 0x000,.length2 = 0x0}, |
456 | {.code_and_extra = 0x000,.length2 = 0x0}, |
457 | {.code_and_extra = 0x000,.length2 = 0x0}, |
458 | {.code_and_extra = 0x000,.length2 = 0x0}, |
459 | {.code_and_extra = 0x000,.length2 = 0x0}, |
460 | {.code_and_extra = 0x000,.length2 = 0x0}, |
461 | {.code_and_extra = 0x000,.length2 = 0x0}, |
462 | {.code_and_extra = 0x000,.length2 = 0x0}, |
463 | {.code_and_extra = 0x000,.length2 = 0x0}, |
464 | {.code_and_extra = 0x000,.length2 = 0x0}, |
465 | {.code_and_extra = 0x000,.length2 = 0x0}, |
466 | {.code_and_extra = 0x000,.length2 = 0x0}, |
467 | {.code_and_extra = 0x000,.length2 = 0x0}, |
468 | {.code_and_extra = 0x000,.length2 = 0x0}, |
469 | {.code_and_extra = 0x000,.length2 = 0x0}, |
470 | {.code_and_extra = 0x000,.length2 = 0x0}, |
471 | {.code_and_extra = 0x000,.length2 = 0x0}, |
472 | {.code_and_extra = 0x000,.length2 = 0x0}, |
473 | {.code_and_extra = 0x000,.length2 = 0x0}, |
474 | {.code_and_extra = 0x000,.length2 = 0x0}, |
475 | {.code_and_extra = 0x000,.length2 = 0x0}, |
476 | {.code_and_extra = 0x000,.length2 = 0x0}, |
477 | {.code_and_extra = 0x000,.length2 = 0x0}, |
478 | {.code_and_extra = 0x000,.length2 = 0x0}, |
479 | {.code_and_extra = 0x000,.length2 = 0x0}, |
480 | {.code_and_extra = 0x000,.length2 = 0x0}, |
481 | {.code_and_extra = 0x000,.length2 = 0x0}, |
482 | {.code_and_extra = 0x000,.length2 = 0x0}, |
483 | {.code_and_extra = 0x000,.length2 = 0x0}, |
484 | {.code_and_extra = 0x000,.length2 = 0x0}, |
485 | {.code_and_extra = 0x000,.length2 = 0x0}, |
486 | {.code_and_extra = 0x000,.length2 = 0x0}, |
487 | {.code_and_extra = 0x000,.length2 = 0x0}, |
488 | {.code_and_extra = 0x000,.length2 = 0x0}, |
489 | {.code_and_extra = 0x000,.length2 = 0x0}, |
490 | {.code_and_extra = 0x000,.length2 = 0x0}, |
491 | {.code_and_extra = 0x000,.length2 = 0x0}, |
492 | {.code_and_extra = 0x000,.length2 = 0x0}, |
493 | {.code_and_extra = 0x000,.length2 = 0x0}, |
494 | {.code_and_extra = 0x000,.length2 = 0x0}, |
495 | {.code_and_extra = 0x000,.length2 = 0x0}, |
496 | {.code_and_extra = 0x000,.length2 = 0x0}, |
497 | {.code_and_extra = 0x000,.length2 = 0x0}, |
498 | {.code_and_extra = 0x000,.length2 = 0x0}, |
499 | {.code_and_extra = 0x000,.length2 = 0x0}, |
500 | {.code_and_extra = 0x000,.length2 = 0x0}, |
501 | {.code_and_extra = 0x000,.length2 = 0x0}, |
502 | {.code_and_extra = 0x000,.length2 = 0x0}, |
503 | {.code_and_extra = 0x000,.length2 = 0x0}, |
504 | {.code_and_extra = 0x000,.length2 = 0x0}, |
505 | {.code_and_extra = 0x000,.length2 = 0x0}, |
506 | {.code_and_extra = 0x000,.length2 = 0x0}, |
507 | {.code_and_extra = 0x000,.length2 = 0x0}, |
508 | {.code_and_extra = 0x000,.length2 = 0x0}, |
509 | {.code_and_extra = 0x000,.length2 = 0x0}, |
510 | {.code_and_extra = 0x000,.length2 = 0x0}, |
511 | {.code_and_extra = 0x000,.length2 = 0x0}, |
512 | {.code_and_extra = 0x000,.length2 = 0x0}, |
513 | {.code_and_extra = 0x000,.length2 = 0x0}, |
514 | {.code_and_extra = 0x000,.length2 = 0x0}, |
515 | {.code_and_extra = 0x000,.length2 = 0x0}, |
516 | {.code_and_extra = 0x000,.length2 = 0x0}, |
517 | {.code_and_extra = 0x000,.length2 = 0x0}, |
518 | {.code_and_extra = 0x000,.length2 = 0x0}, |
519 | {.code_and_extra = 0x000,.length2 = 0x0}, |
520 | {.code_and_extra = 0x000,.length2 = 0x0}, |
521 | {.code_and_extra = 0x000,.length2 = 0x0}, |
522 | {.code_and_extra = 0x000,.length2 = 0x0}, |
523 | {.code_and_extra = 0x000,.length2 = 0x0}, |
524 | {.code_and_extra = 0x000,.length2 = 0x0}, |
525 | {.code_and_extra = 0x000,.length2 = 0x0}, |
526 | {.code_and_extra = 0x000,.length2 = 0x0}, |
527 | {.code_and_extra = 0x000,.length2 = 0x0}, |
528 | {.code_and_extra = 0x000,.length2 = 0x0}, |
529 | {.code_and_extra = 0x000,.length2 = 0x0}, |
530 | {.code_and_extra = 0x000,.length2 = 0x0}, |
531 | {.code_and_extra = 0x000,.length2 = 0x0}, |
532 | {.code_and_extra = 0x000,.length2 = 0x0}, |
533 | {.code_and_extra = 0x000,.length2 = 0x0}, |
534 | {.code_and_extra = 0x000,.length2 = 0x0}, |
535 | {.code_and_extra = 0x000,.length2 = 0x0}, |
536 | {.code_and_extra = 0x000,.length2 = 0x0}, |
537 | {.code_and_extra = 0x000,.length2 = 0x0}, |
538 | {.code_and_extra = 0x000,.length2 = 0x0}, |
539 | {.code_and_extra = 0x000,.length2 = 0x0}, |
540 | {.code_and_extra = 0x000,.length2 = 0x0}, |
541 | {.code_and_extra = 0x000,.length2 = 0x0}, |
542 | {.code_and_extra = 0x000,.length2 = 0x0}, |
543 | {.code_and_extra = 0x000,.length2 = 0x0}, |
544 | {.code_and_extra = 0x000,.length2 = 0x0}, |
545 | {.code_and_extra = 0x000,.length2 = 0x0}, |
546 | {.code_and_extra = 0x000,.length2 = 0x0}, |
547 | {.code_and_extra = 0x000,.length2 = 0x0}, |
548 | {.code_and_extra = 0x000,.length2 = 0x0}, |
549 | {.code_and_extra = 0x000,.length2 = 0x0}, |
550 | {.code_and_extra = 0x000,.length2 = 0x0}, |
551 | {.code_and_extra = 0x000,.length2 = 0x0}, |
552 | {.code_and_extra = 0x000,.length2 = 0x0}, |
553 | {.code_and_extra = 0x000,.length2 = 0x0}, |
554 | {.code_and_extra = 0x000,.length2 = 0x0}, |
555 | {.code_and_extra = 0x000,.length2 = 0x0}, |
556 | {.code_and_extra = 0x000,.length2 = 0x0}, |
557 | {.code_and_extra = 0x000,.length2 = 0x0}, |
558 | {.code_and_extra = 0x000,.length2 = 0x0}, |
559 | {.code_and_extra = 0x000,.length2 = 0x0}, |
560 | {.code_and_extra = 0x000,.length2 = 0x0}, |
561 | {.code_and_extra = 0x000,.length2 = 0x0}, |
562 | {.code_and_extra = 0x000,.length2 = 0x0}, |
563 | {.code_and_extra = 0x000,.length2 = 0x0}, |
564 | {.code_and_extra = 0x000,.length2 = 0x0}, |
565 | {.code_and_extra = 0x000,.length2 = 0x0}, |
566 | {.code_and_extra = 0x000,.length2 = 0x0}, |
567 | {.code_and_extra = 0x000,.length2 = 0x0}, |
568 | {.code_and_extra = 0x000,.length2 = 0x0}, |
569 | {.code_and_extra = 0x000,.length2 = 0x0}, |
570 | {.code_and_extra = 0x000,.length2 = 0x0}, |
571 | {.code_and_extra = 0x000,.length2 = 0x0}, |
572 | {.code_and_extra = 0x000,.length2 = 0x0}, |
573 | {.code_and_extra = 0x000,.length2 = 0x0}}, |
574 | .dist_table = { |
575 | {.code_and_extra = 0x000,.length2 = 0x5}, |
576 | {.code_and_extra = 0x010,.length2 = 0x5}, |
577 | {.code_and_extra = 0x008,.length2 = 0x5}, |
578 | {.code_and_extra = 0x018,.length2 = 0x5}, |
579 | {.code_and_extra = 0x10004,.length2 = 0x5}, |
580 | {.code_and_extra = 0x10014,.length2 = 0x5}, |
581 | {.code_and_extra = 0x2000c,.length2 = 0x5}, |
582 | {.code_and_extra = 0x2001c,.length2 = 0x5}, |
583 | {.code_and_extra = 0x30002,.length2 = 0x5}, |
584 | {.code_and_extra = 0x30012,.length2 = 0x5}, |
585 | {.code_and_extra = 0x4000a,.length2 = 0x5}, |
586 | {.code_and_extra = 0x4001a,.length2 = 0x5}, |
587 | {.code_and_extra = 0x50006,.length2 = 0x5}, |
588 | {.code_and_extra = 0x50016,.length2 = 0x5}, |
589 | {.code_and_extra = 0x6000e,.length2 = 0x5}, |
590 | {.code_and_extra = 0x6001e,.length2 = 0x5}, |
591 | {.code_and_extra = 0x70001,.length2 = 0x5}, |
592 | {.code_and_extra = 0x70011,.length2 = 0x5}, |
593 | {.code_and_extra = 0x80009,.length2 = 0x5}, |
594 | {.code_and_extra = 0x80019,.length2 = 0x5}, |
595 | {.code_and_extra = 0x90005,.length2 = 0x5}, |
596 | {.code_and_extra = 0x90015,.length2 = 0x5}, |
597 | {.code_and_extra = 0xa000d,.length2 = 0x5}, |
598 | {.code_and_extra = 0xa001d,.length2 = 0x5}, |
599 | {.code_and_extra = 0xb0003,.length2 = 0x5}, |
600 | {.code_and_extra = 0xb0013,.length2 = 0x5}, |
601 | {.code_and_extra = 0xc000b,.length2 = 0x5}, |
602 | {.code_and_extra = 0xc001b,.length2 = 0x5}, |
603 | {.code_and_extra = 0xd0007,.length2 = 0x5}, |
604 | {.code_and_extra = 0xd0017,.length2 = 0x5}, |
605 | {.code_and_extra = 0x000,.length2 = 0x0}} |
606 | }; |
607 | |
608 | struct slver { |
609 | uint16_t snum; |
610 | uint8_t ver; |
611 | uint8_t core; |
612 | }; |
613 | |
614 | |
615 | struct slver isal_update_histogram_slver_00010085; |
616 | struct slver isal_update_histogram_slver = { 0x0085, 0x01, 0x00 }; |
617 | |
618 | struct slver isal_create_hufftables_slver_00010086; |
619 | struct slver isal_create_hufftables_slver = { 0x0086, 0x01, 0x00 }; |
620 | |
621 | struct slver isal_create_hufftables_subset_slver_00010087; |
622 | struct slver isal_create_hufftables_subset_slver = { 0x0087, 0x01, 0x00 }; |
623 | |
624 | extern uint32_t build_huff_tree(struct heap_tree *heap, uint64_t heap_size, uint64_t node_ptr); |
625 | extern void build_heap(uint64_t * heap, uint64_t heap_size); |
626 | |
627 | static const uint8_t bitrev8[0x100] = { |
628 | 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, |
629 | 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, |
630 | 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, |
631 | 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, |
632 | 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, |
633 | 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, |
634 | 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, |
635 | 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, |
636 | 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, |
637 | 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, |
638 | 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, |
639 | 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, |
640 | 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, |
641 | 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, |
642 | 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, |
643 | 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, |
644 | 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, |
645 | 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, |
646 | 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, |
647 | 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, |
648 | 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, |
649 | 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, |
650 | 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, |
651 | 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, |
652 | 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, |
653 | 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, |
654 | 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, |
655 | 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, |
656 | 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, |
657 | 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, |
658 | 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, |
659 | 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF |
660 | }; |
661 | |
662 | |
663 | static inline uint16_t bit_reverse(uint16_t code, uint32_t length) |
664 | { |
665 | code = (bitrev8[code & 0x00FF] << 8) | (bitrev8[code >> 8]); |
666 | return (code >> (16 - length)); |
667 | } |
668 | |
669 | void isal_update_histogram_base(uint8_t * start_stream, int length, |
670 | struct isal_huff_histogram *histogram) |
671 | { |
672 | uint32_t literal = 0, hash; |
673 | uint16_t seen, *last_seen = histogram->hash_table; |
674 | uint8_t *current, *end_stream, *next_hash, *end; |
675 | uint32_t match_length; |
676 | uint32_t dist; |
677 | uint64_t *lit_len_histogram = histogram->lit_len_histogram; |
678 | uint64_t *dist_histogram = histogram->dist_histogram; |
679 | |
680 | if (length <= 0) |
681 | return; |
682 | |
683 | end_stream = start_stream + length; |
684 | memset(last_seen, 0, sizeof(histogram->hash_table)); |
685 | for (current = start_stream; current < end_stream - 3; current++) { |
686 | literal = *(uint32_t *) current; |
687 | hash = compute_hash(literal) & HASH_MASK((8 * 1024) - 1); |
688 | seen = last_seen[hash]; |
689 | last_seen[hash] = (current - start_stream) & 0xFFFF; |
690 | dist = (current - start_stream - seen) & 0xFFFF; |
691 | if (dist - 1 < D(32*1024) - 1) { |
692 | assert(start_stream <= current - dist)((void) (0)); |
693 | match_length = |
694 | compare258(current - dist, current, end_stream - current); |
695 | if (match_length >= SHORTEST_MATCH4) { |
696 | next_hash = current; |
697 | #ifdef ISAL_LIMIT_HASH_UPDATE |
698 | end = next_hash + 3; |
699 | #else |
700 | end = next_hash + match_length; |
701 | #endif |
702 | if (end > end_stream - 3) |
703 | end = end_stream - 3; |
704 | next_hash++; |
705 | for (; next_hash < end; next_hash++) { |
706 | literal = *(uint32_t *) next_hash; |
707 | hash = compute_hash(literal) & HASH_MASK((8 * 1024) - 1); |
708 | last_seen[hash] = (next_hash - start_stream) & 0xFFFF; |
709 | } |
710 | |
711 | dist_histogram[convert_dist_to_dist_sym(dist)] += 1; |
712 | lit_len_histogram[convert_length_to_len_sym(match_length)] += |
713 | 1; |
714 | current += match_length - 1; |
715 | continue; |
716 | } |
717 | } |
718 | lit_len_histogram[literal & 0xFF] += 1; |
719 | } |
720 | literal = literal >> 8; |
721 | hash = compute_hash(literal) & HASH_MASK((8 * 1024) - 1); |
722 | seen = last_seen[hash]; |
723 | last_seen[hash] = (current - start_stream) & 0xFFFF; |
724 | dist = (current - start_stream - seen) & 0xFFFF; |
725 | if (dist < D(32*1024)) { |
726 | match_length = compare258(current - dist, current, end_stream - current); |
727 | if (match_length >= SHORTEST_MATCH4) { |
728 | dist_histogram[convert_dist_to_dist_sym(dist)] += 1; |
729 | lit_len_histogram[convert_length_to_len_sym(match_length)] += 1; |
730 | lit_len_histogram[256] += 1; |
731 | return; |
732 | } |
733 | } else |
734 | lit_len_histogram[literal & 0xFF] += 1; |
735 | lit_len_histogram[(literal >> 8) & 0xFF] += 1; |
736 | lit_len_histogram[(literal >> 16) & 0xFF] += 1; |
737 | lit_len_histogram[256] += 1; |
738 | return; |
739 | } |
740 | |
741 | uint32_t convert_dist_to_dist_sym(uint32_t dist) |
742 | { |
743 | assert(dist <= 32768 && dist > 0)((void) (0)); |
744 | if (dist <= 2) |
745 | return dist - 1; |
746 | else if (dist <= 4) |
747 | return 0 + (dist - 1) / 1; |
748 | else if (dist <= 8) |
749 | return 2 + (dist - 1) / 2; |
750 | else if (dist <= 16) |
751 | return 4 + (dist - 1) / 4; |
752 | else if (dist <= 32) |
753 | return 6 + (dist - 1) / 8; |
754 | else if (dist <= 64) |
755 | return 8 + (dist - 1) / 16; |
756 | else if (dist <= 128) |
757 | return 10 + (dist - 1) / 32; |
758 | else if (dist <= 256) |
759 | return 12 + (dist - 1) / 64; |
760 | else if (dist <= 512) |
761 | return 14 + (dist - 1) / 128; |
762 | else if (dist <= 1024) |
763 | return 16 + (dist - 1) / 256; |
764 | else if (dist <= 2048) |
765 | return 18 + (dist - 1) / 512; |
766 | else if (dist <= 4096) |
767 | return 20 + (dist - 1) / 1024; |
768 | else if (dist <= 8192) |
769 | return 22 + (dist - 1) / 2048; |
770 | else if (dist <= 16384) |
771 | return 24 + (dist - 1) / 4096; |
772 | else if (dist <= 32768) |
773 | return 26 + (dist - 1) / 8192; |
774 | else |
775 | return ~0; |
776 | |
777 | } |
778 | |
779 | uint32_t convert_length_to_len_sym(uint32_t length) |
780 | { |
781 | assert(length > 2 && length < 259)((void) (0)); |
782 | |
783 | |
784 | if (length < 11) |
785 | return 257 + length - 3; |
786 | else if (length < 19) |
787 | return 261 + (length - 3) / 2; |
788 | else if (length < 35) |
789 | return 265 + (length - 3) / 4; |
790 | else if (length < 67) |
791 | return 269 + (length - 3) / 8; |
792 | else if (length < 131) |
793 | return 273 + (length - 3) / 16; |
794 | else if (length < 258) |
795 | return 277 + (length - 3) / 32; |
796 | else |
797 | return 285; |
798 | } |
799 | |
800 | |
801 | |
802 | |
803 | |
804 | static inline uint32_t init_heap32(struct heap_tree *heap_space, uint32_t * histogram, |
805 | uint32_t hist_size) |
806 | { |
807 | uint32_t heap_size, i; |
808 | |
809 | memset(heap_space, 0, sizeof(struct heap_tree)); |
810 | |
811 | heap_size = 0; |
812 | for (i = 0; i < hist_size; i++) { |
813 | if (histogram[i] != 0) |
814 | heap_space->heap[++heap_size] = |
815 | (((uint64_t) histogram[i]) << FREQ_SHIFT16) | i; |
816 | } |
817 | |
818 | |
819 | if (heap_size < 2) { |
820 | if (heap_size == 0) { |
821 | heap_space->heap[1] = 1ULL << FREQ_SHIFT16; |
822 | heap_space->heap[2] = (1ULL << FREQ_SHIFT16) | 1; |
823 | heap_size = 2; |
824 | } else { |
825 | |
826 | if (histogram[0] == 0) |
827 | heap_space->heap[2] = 1ULL << FREQ_SHIFT16; |
828 | else |
829 | heap_space->heap[2] = (1ULL << FREQ_SHIFT16) | 1; |
830 | heap_size = 2; |
831 | } |
832 | } |
833 | |
834 | build_heap(heap_space->heap, heap_size); |
835 | |
836 | return heap_size; |
837 | } |
838 | |
839 | static inline uint32_t init_heap64(struct heap_tree *heap_space, uint64_t * histogram, |
840 | uint64_t hist_size) |
841 | { |
842 | uint32_t heap_size, i; |
843 | |
844 | memset(heap_space, 0, sizeof(struct heap_tree)); |
845 | |
846 | heap_size = 0; |
847 | for (i = 0; i < hist_size; i++) { |
848 | if (histogram[i] != 0) |
849 | heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT16) | i; |
850 | } |
851 | |
852 | |
853 | if (heap_size < 2) { |
854 | if (heap_size == 0) { |
855 | heap_space->heap[1] = 1ULL << FREQ_SHIFT16; |
856 | heap_space->heap[2] = (1ULL << FREQ_SHIFT16) | 1; |
857 | heap_size = 2; |
858 | } else { |
859 | |
860 | if (histogram[0] == 0) |
861 | heap_space->heap[2] = 1ULL << FREQ_SHIFT16; |
862 | else |
863 | heap_space->heap[2] = (1ULL << FREQ_SHIFT16) | 1; |
864 | heap_size = 2; |
865 | } |
866 | } |
867 | |
868 | build_heap(heap_space->heap, heap_size); |
869 | |
870 | return heap_size; |
871 | } |
872 | |
873 | static inline uint32_t init_heap64_complete(struct heap_tree *heap_space, uint64_t * histogram, |
874 | uint64_t hist_size) |
875 | { |
876 | uint32_t heap_size, i; |
877 | |
878 | memset(heap_space, 0, sizeof(struct heap_tree)); |
879 | |
880 | heap_size = 0; |
881 | for (i = 0; i < hist_size; i++) |
882 | heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT16) | i; |
883 | |
884 | build_heap(heap_space->heap, heap_size); |
885 | |
886 | return heap_size; |
887 | } |
888 | |
889 | static inline uint32_t fix_code_lens(struct heap_tree *heap_space, uint32_t root_node, |
890 | uint32_t * bl_count, uint32_t max_code_len) |
891 | { |
892 | struct tree_node *tree = heap_space->tree; |
893 | uint64_t *code_len_count = heap_space->code_len_count; |
894 | uint32_t i, j, k, child, depth, code_len; |
895 | |
896 | |
897 | code_len = 0; |
898 | j = root_node; |
899 | for (i = root_node; i <= HEAP_TREE_NODE_START((3*(257 + 29) + 1)-1); i++) { |
900 | child = tree[i].child; |
901 | if (child > MAX_HISTHEAP_SIZE(257 + 29)) { |
902 | depth = 1 + tree[i].depth; |
903 | |
904 | tree[child].depth = depth; |
905 | tree[child - 1].depth = depth; |
906 | } else { |
907 | tree[j++] = tree[i]; |
908 | depth = tree[i].depth; |
909 | while (code_len < depth) { |
910 | code_len++; |
911 | code_len_count[code_len] = 0; |
912 | } |
913 | code_len_count[depth]++; |
914 | } |
915 | } |
916 | |
917 | if (code_len > max_code_len) { |
918 | while (code_len > max_code_len) { |
919 | assert(code_len_count[code_len] > 1)((void) (0)); |
920 | for (i = max_code_len - 1; i != 0; i--) |
921 | if (code_len_count[i] != 0) |
922 | break; |
923 | assert(i != 0)((void) (0)); |
924 | code_len_count[i]--; |
925 | code_len_count[i + 1] += 2; |
926 | code_len_count[code_len - 1]++; |
927 | code_len_count[code_len] -= 2; |
928 | if (code_len_count[code_len] == 0) |
929 | code_len--; |
930 | } |
931 | |
932 | for (i = 1; i <= code_len; i++) |
933 | bl_count[i] = code_len_count[i]; |
934 | for (; i <= max_code_len; i++) |
935 | bl_count[i] = 0; |
936 | |
937 | for (k = 1; code_len_count[k] == 0; k++) ; |
938 | for (i = root_node; i < j; i++) { |
939 | tree[i].depth = k; |
940 | code_len_count[k]--; |
941 | for (; code_len_count[k] == 0; k++) ; |
942 | } |
943 | } else { |
944 | for (i = 1; i <= code_len; i++) |
945 | bl_count[i] = code_len_count[i]; |
946 | for (; i <= max_code_len; i++) |
947 | bl_count[i] = 0; |
948 | } |
949 | |
950 | return j; |
951 | |
952 | } |
953 | |
954 | static inline void |
955 | gen_huff_code_lens(struct heap_tree *heap_space, uint32_t heap_size, uint32_t * bl_count, |
956 | struct huff_code *codes, uint32_t codes_count, uint32_t max_code_len) |
957 | { |
958 | struct tree_node *tree = heap_space->tree; |
959 | uint32_t root_node = HEAP_TREE_NODE_START((3*(257 + 29) + 1)-1), node_ptr; |
960 | uint32_t end_node; |
961 | |
962 | root_node = build_huff_tree(heap_space, heap_size, root_node); |
963 | |
964 | end_node = fix_code_lens(heap_space, root_node, bl_count, max_code_len); |
965 | |
966 | memset(codes, 0, codes_count * sizeof(*codes)); |
967 | for (node_ptr = root_node; node_ptr < end_node; node_ptr++) |
968 | codes[tree[node_ptr].child].length = tree[node_ptr].depth; |
969 | |
970 | } |
971 | |
972 | inline uint32_t set_huff_codes(struct huff_code *huff_code_table, int table_length, |
973 | uint32_t * count) |
974 | { |
975 | |
976 | int i; |
977 | uint16_t code = 0; |
978 | uint16_t next_code[MAX_HUFF_TREE_DEPTH15 + 1]; |
979 | uint32_t max_code = 0; |
980 | |
981 | next_code[0] = code; |
982 | |
983 | for (i = 1; i < MAX_HUFF_TREE_DEPTH15 + 1; i++) |
984 | next_code[i] = (next_code[i - 1] + count[i - 1]) << 1; |
985 | |
986 | for (i = 0; i < table_length; i++) { |
987 | if (huff_code_table[i].length != 0) { |
988 | huff_code_table[i].code = |
989 | bit_reverse(next_code[huff_code_table[i].length], |
990 | huff_code_table[i].length); |
991 | next_code[huff_code_table[i].length] += 1; |
992 | max_code = i; |
993 | } |
994 | } |
995 | |
996 | return max_code; |
997 | } |
998 | |
999 | |
1000 | |
1001 | |
1002 | |
1003 | |
1004 | static inline uint32_t set_dist_huff_codes(struct huff_code *codes, uint32_t * bl_count) |
1005 | { |
1006 | uint32_t code, code_len, bits, i; |
1007 | uint32_t next_code[MAX_DEFLATE_CODE_LEN15 + 1]; |
1008 | uint32_t max_code = 0; |
1009 | const uint32_t num_codes = DIST_LEN30; |
1010 | |
1011 | code = bl_count[0] = 0; |
1012 | for (bits = 1; bits <= MAX_HUFF_TREE_DEPTH15; bits++) { |
1013 | code = (code + bl_count[bits - 1]) << 1; |
1014 | next_code[bits] = code; |
1015 | } |
1016 | for (i = 0; i < num_codes; i++) { |
1017 | code_len = codes[i].length; |
1018 | if (code_len != 0) { |
1019 | codes[i].code = bit_reverse(next_code[code_len], code_len); |
1020 | codes[i].extra_bit_count = dist_code_extra_bits[i]; |
1021 | next_code[code_len] += 1; |
1022 | max_code = i; |
1023 | } |
1024 | } |
1025 | return max_code; |
1026 | } |
1027 | |
1028 | int create_huffman_header(struct BitBuf2 *header_bitbuf, |
1029 | struct huff_code *lookup_table, |
1030 | struct rl_code *huffman_rep, |
1031 | uint16_t huffman_rep_length, uint32_t end_of_block, |
1032 | uint32_t hclen, uint32_t hlit, uint32_t hdist) |
1033 | { |
1034 | |
1035 | |
1036 | int i; |
1037 | uint64_t bit_count; |
1038 | uint64_t data; |
1039 | struct huff_code huffman_value; |
1040 | const uint32_t extra_bits[3] = { 2, 3, 7 }; |
1041 | |
1042 | bit_count = buffer_bits_used(header_bitbuf); |
1043 | |
1044 | data = (end_of_block ? 5 : 4) | (hlit << 3) | (hdist << 8) | (hclen << 13); |
1045 | data |= ((lookup_table[code_length_code_order[0]].length) << DYN_HDR_START_LEN17); |
1046 | write_bits(header_bitbuf, data, DYN_HDR_START_LEN17 + 3); |
1047 | data = 0; |
1048 | for (i = hclen + 3; i >= 1; i--) |
1049 | data = (data << 3) | lookup_table[code_length_code_order[i]].length; |
1050 | |
1051 | write_bits(header_bitbuf, data, (hclen + 3) * 3); |
1052 | |
1053 | for (i = 0; i < huffman_rep_length; i++) { |
1054 | huffman_value = lookup_table[huffman_rep[i].code]; |
1055 | |
1056 | write_bits(header_bitbuf, (uint64_t) huffman_value.code, |
1057 | (uint32_t) huffman_value.length); |
1058 | |
1059 | if (huffman_rep[i].code > 15) { |
1060 | write_bits(header_bitbuf, (uint64_t) huffman_rep[i].extra_bits, |
1061 | (uint32_t) extra_bits[huffman_rep[i].code - 16]); |
1062 | } |
1063 | } |
1064 | bit_count = buffer_bits_used(header_bitbuf) - bit_count; |
1065 | |
1066 | return bit_count; |
1067 | } |
1068 | |
1069 | inline int create_header(struct BitBuf2 *header_bitbuf, struct rl_code *huffman_rep, |
1070 | uint32_t length, uint64_t * histogram, uint32_t hlit, |
1071 | uint32_t hdist, uint32_t end_of_block) |
1072 | { |
1073 | int i; |
1074 | |
1075 | uint32_t heap_size; |
1076 | struct heap_tree heap_space; |
1077 | uint32_t code_len_count[MAX_HUFF_TREE_DEPTH15 + 1]; |
1078 | struct huff_code lookup_table[HUFF_LEN19]; |
1079 | |
1080 | |
1081 | uint32_t hclen; |
1082 | uint64_t bit_count; |
1083 | |
1084 | |
1085 | heap_size = init_heap64(&heap_space, histogram, HUFF_LEN19); |
1086 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1087 | (struct huff_code *)lookup_table, HUFF_LEN19, 7); |
1088 | set_huff_codes(lookup_table, HUFF_LEN19, code_len_count); |
1089 | |
1090 | |
1091 | for (i = CODE_LEN_CODES19 - 1; i > 3; i--) |
1092 | if (lookup_table[code_length_code_order[i]].length != 0) |
1093 | break; |
1094 | |
1095 | hclen = i - 3; |
1096 | |
1097 | |
1098 | bit_count = create_huffman_header(header_bitbuf, lookup_table, huffman_rep, |
1099 | length, end_of_block, hclen, hlit, hdist); |
1100 | |
1101 | return bit_count; |
1102 | } |
1103 | |
1104 | static inline |
1105 | struct rl_code *write_rl(struct rl_code *pout, uint16_t last_len, uint32_t run_len, |
1106 | uint64_t * counts) |
1107 | { |
1108 | if (last_len == 0) { |
1109 | while (run_len > 138) { |
1110 | pout->code = 18; |
1111 | pout->extra_bits = 138 - 11; |
1112 | pout++; |
1113 | run_len -= 138; |
1114 | counts[18]++; |
1115 | } |
1116 | |
1117 | if (run_len > 10) { |
1118 | pout->code = 18; |
1119 | pout->extra_bits = run_len - 11; |
1120 | pout++; |
1121 | counts[18]++; |
1122 | } else if (run_len > 2) { |
1123 | pout->code = 17; |
1124 | pout->extra_bits = run_len - 3; |
1125 | pout++; |
1126 | counts[17]++; |
1127 | } else if (run_len == 1) { |
1128 | pout->code = 0; |
1129 | pout->extra_bits = 0; |
1130 | pout++; |
1131 | counts[0]++; |
1132 | } else { |
1133 | assert(run_len == 2)((void) (0)); |
1134 | pout[0].code = 0; |
1135 | pout[0].extra_bits = 0; |
1136 | pout[1].code = 0; |
1137 | pout[1].extra_bits = 0; |
1138 | pout += 2; |
1139 | counts[0] += 2; |
1140 | } |
1141 | } else { |
1142 | |
1143 | pout->code = last_len; |
1144 | pout->extra_bits = 0; |
1145 | pout++; |
1146 | counts[last_len]++; |
1147 | run_len--; |
1148 | if (run_len != 0) { |
1149 | while (run_len > 6) { |
1150 | pout->code = 16; |
1151 | pout->extra_bits = 6 - 3; |
1152 | pout++; |
1153 | run_len -= 6; |
1154 | counts[16]++; |
1155 | } |
1156 | |
1157 | switch (run_len) { |
1158 | case 1: |
1159 | pout->code = last_len; |
1160 | pout->extra_bits = 0; |
1161 | pout++; |
1162 | counts[last_len]++; |
1163 | break; |
1164 | case 2: |
1165 | pout[0].code = last_len; |
1166 | pout[0].extra_bits = 0; |
1167 | pout[1].code = last_len; |
1168 | pout[1].extra_bits = 0; |
1169 | pout += 2; |
1170 | counts[last_len] += 2; |
1171 | break; |
1172 | default: |
1173 | pout->code = 16; |
1174 | pout->extra_bits = run_len - 3; |
1175 | pout++; |
1176 | counts[16]++; |
1177 | } |
1178 | } |
1179 | } |
1180 | return pout; |
1181 | } |
1182 | |
1183 | |
1184 | |
1185 | |
1186 | |
1187 | |
1188 | |
1189 | static inline uint32_t rl_encode(uint16_t * codes, uint32_t num_codes, uint64_t * counts, |
1190 | struct rl_code *out) |
1191 | { |
1192 | uint32_t i, run_len; |
1193 | uint16_t last_len, len; |
1194 | struct rl_code *pout; |
1195 | |
1196 | pout = out; |
1197 | last_len = codes[0]; |
| 8 | | Assigned value is garbage or undefined |
|
1198 | run_len = 1; |
1199 | for (i = 1; i < num_codes; i++) { |
1200 | len = codes[i]; |
1201 | if (len == last_len) { |
1202 | run_len++; |
1203 | continue; |
1204 | } |
1205 | pout = write_rl(pout, last_len, run_len, counts); |
1206 | last_len = len; |
1207 | run_len = 1; |
1208 | } |
1209 | pout = write_rl(pout, last_len, run_len, counts); |
1210 | |
1211 | return (uint32_t) (pout - out); |
1212 | } |
1213 | |
1214 | void create_code_tables(uint16_t * code_table, uint8_t * code_length_table, uint32_t length, |
1215 | struct huff_code *hufftable) |
1216 | { |
1217 | int i; |
1218 | for (i = 0; i < length; i++) { |
1219 | code_table[i] = hufftable[i].code; |
1220 | code_length_table[i] = hufftable[i].length; |
1221 | } |
1222 | } |
1223 | |
1224 | void create_packed_len_table(uint32_t * packed_table, struct huff_code *lit_len_hufftable) |
1225 | { |
1226 | int i, count = 0; |
1227 | uint16_t extra_bits; |
1228 | uint16_t extra_bits_count = 0; |
1229 | |
1230 | |
1231 | |
1232 | uint16_t gain_extra_bits = LEN_EXTRA_BITS_START264; |
1233 | |
1234 | for (i = 257; i < LIT_LEN(257 + 29) - 1; i++) { |
1235 | for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { |
1236 | if (count > 254) |
1237 | break; |
1238 | packed_table[count++] = |
1239 | (extra_bits << (lit_len_hufftable[i].length + LENGTH_BITS5)) | |
1240 | (lit_len_hufftable[i].code << LENGTH_BITS5) | |
1241 | (lit_len_hufftable[i].length + extra_bits_count); |
1242 | } |
1243 | |
1244 | if (i == gain_extra_bits) { |
1245 | gain_extra_bits += LEN_EXTRA_BITS_INTERVAL4; |
1246 | extra_bits_count += 1; |
1247 | } |
1248 | } |
1249 | |
1250 | packed_table[count] = (lit_len_hufftable[LIT_LEN(257 + 29) - 1].code << LENGTH_BITS5) | |
1251 | (lit_len_hufftable[LIT_LEN(257 + 29) - 1].length); |
1252 | } |
1253 | |
1254 | void create_packed_dist_table(uint32_t * packed_table, uint32_t length, |
1255 | struct huff_code *dist_hufftable) |
1256 | { |
1257 | int i, count = 0; |
1258 | uint16_t extra_bits; |
1259 | uint16_t extra_bits_count = 0; |
1260 | |
1261 | |
1262 | |
1263 | uint16_t gain_extra_bits = DIST_EXTRA_BITS_START3; |
1264 | |
1265 | for (i = 0; i < DIST_LEN30; i++) { |
1266 | for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) { |
1267 | if (count >= length) |
1268 | return; |
1269 | |
1270 | packed_table[count++] = |
1271 | (extra_bits << (dist_hufftable[i].length + LENGTH_BITS5)) | |
1272 | (dist_hufftable[i].code << LENGTH_BITS5) | |
1273 | (dist_hufftable[i].length + extra_bits_count); |
1274 | |
1275 | } |
1276 | |
1277 | if (i == gain_extra_bits) { |
1278 | gain_extra_bits += DIST_EXTRA_BITS_INTERVAL2; |
1279 | extra_bits_count += 1; |
1280 | } |
1281 | } |
1282 | } |
1283 | |
1284 | int are_hufftables_useable(struct huff_code *lit_len_hufftable, |
1285 | struct huff_code *dist_hufftable) |
1286 | { |
1287 | int max_lit_code_len = 0, max_len_code_len = 0, max_dist_code_len = 0; |
1288 | int dist_extra_bits = 0, len_extra_bits = 0; |
1289 | int gain_dist_extra_bits = DIST_EXTRA_BITS_START3; |
1290 | int gain_len_extra_bits = LEN_EXTRA_BITS_START264; |
1291 | int max_code_len; |
1292 | int i; |
1293 | |
1294 | for (i = 0; i < LIT_LEN(257 + 29); i++) |
1295 | if (lit_len_hufftable[i].length > max_lit_code_len) |
1296 | max_lit_code_len = lit_len_hufftable[i].length; |
1297 | |
1298 | for (i = 257; i < LIT_LEN(257 + 29) - 1; i++) { |
1299 | if (lit_len_hufftable[i].length + len_extra_bits > max_len_code_len) |
1300 | max_len_code_len = lit_len_hufftable[i].length + len_extra_bits; |
1301 | |
1302 | if (i == gain_len_extra_bits) { |
1303 | gain_len_extra_bits += LEN_EXTRA_BITS_INTERVAL4; |
1304 | len_extra_bits += 1; |
1305 | } |
1306 | } |
1307 | |
1308 | for (i = 0; i < DIST_LEN30; i++) { |
1309 | if (dist_hufftable[i].length + dist_extra_bits > max_dist_code_len) |
1310 | max_dist_code_len = dist_hufftable[i].length + dist_extra_bits; |
1311 | |
1312 | if (i == gain_dist_extra_bits) { |
1313 | gain_dist_extra_bits += DIST_EXTRA_BITS_INTERVAL2; |
1314 | dist_extra_bits += 1; |
1315 | } |
1316 | } |
1317 | |
1318 | max_code_len = max_lit_code_len + max_len_code_len + max_dist_code_len; |
1319 | |
1320 | |
1321 | |
1322 | |
1323 | return (max_code_len > MAX_BITBUF_BIT_WRITE56); |
1324 | } |
1325 | |
1326 | int isal_create_hufftables(struct isal_hufftables *hufftables, |
1327 | struct isal_huff_histogram *histogram) |
1328 | { |
1329 | struct huff_code lit_huff_table[LIT_LEN(257 + 29)], dist_huff_table[DIST_LEN30]; |
1330 | uint64_t bit_count; |
1331 | int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE(32*1024)); |
1332 | struct heap_tree heap_space; |
1333 | uint32_t heap_size; |
1334 | uint32_t code_len_count[MAX_HUFF_TREE_DEPTH15 + 1]; |
1335 | struct BitBuf2 header_bitbuf; |
1336 | uint32_t max_lit_len_sym; |
1337 | uint32_t max_dist_sym; |
1338 | uint32_t hlit, hdist, i; |
1339 | uint16_t combined_table[LIT_LEN(257 + 29) + DIST_LEN30]; |
1340 | uint64_t count_histogram[HUFF_LEN19]; |
1341 | struct rl_code rl_huff[LIT_LEN(257 + 29) + DIST_LEN30]; |
1342 | uint32_t rl_huff_len; |
1343 | |
1344 | uint32_t *dist_table = hufftables->dist_table; |
1345 | uint32_t *len_table = hufftables->len_table; |
1346 | uint16_t *lit_table = hufftables->lit_table; |
1347 | uint16_t *dcodes = hufftables->dcodes; |
1348 | uint8_t *lit_table_sizes = hufftables->lit_table_sizes; |
1349 | uint8_t *dcodes_sizes = hufftables->dcodes_sizes; |
1350 | uint8_t *deflate_hdr = hufftables->deflate_hdr; |
1351 | uint64_t *lit_len_histogram = histogram->lit_len_histogram; |
1352 | uint64_t *dist_histogram = histogram->dist_histogram; |
1353 | |
1354 | memset(hufftables, 0, sizeof(struct isal_hufftables)); |
1355 | |
1356 | heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN(257 + 29)); |
1357 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1358 | (struct huff_code *)lit_huff_table, LIT_LEN(257 + 29), MAX_DEFLATE_CODE_LEN15); |
1359 | max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN(257 + 29), code_len_count); |
1360 | |
1361 | heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN30); |
1362 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1363 | (struct huff_code *)dist_huff_table, max_dist, |
1364 | MAX_DEFLATE_CODE_LEN15); |
1365 | max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN30, code_len_count); |
1366 | |
1367 | if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { |
1368 | heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN(257 + 29)); |
1369 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1370 | (struct huff_code *)lit_huff_table, LIT_LEN(257 + 29), |
1371 | MAX_SAFE_LIT_CODE_LEN13); |
1372 | max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN(257 + 29), code_len_count); |
1373 | |
1374 | heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN30); |
1375 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1376 | (struct huff_code *)dist_huff_table, max_dist, |
1377 | MAX_SAFE_DIST_CODE_LEN12); |
1378 | max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN30, code_len_count); |
1379 | |
1380 | } |
1381 | |
1382 | create_code_tables(dcodes, dcodes_sizes, DIST_LEN30 - DCODE_OFFSET0, |
1383 | dist_huff_table + DCODE_OFFSET0); |
1384 | |
1385 | create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table); |
1386 | |
1387 | create_packed_len_table(len_table, lit_huff_table); |
1388 | create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table); |
1389 | |
1390 | set_buf(&header_bitbuf, deflate_hdr, sizeof(deflate_hdr)); |
1391 | init(&header_bitbuf); |
1392 | |
1393 | hlit = max_lit_len_sym - 256; |
1394 | hdist = max_dist_sym; |
1395 | |
1396 | |
1397 | memset(count_histogram, 0, sizeof(count_histogram)); |
1398 | for (i = 0; i < 257 + hlit; i++) |
1399 | combined_table[i] = lit_huff_table[i].length; |
1400 | for (i = 0; i < 1 + hdist; i++) |
1401 | combined_table[i + hlit + 257] = dist_huff_table[i].length; |
1402 | rl_huff_len = |
1403 | rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff); |
1404 | |
1405 | |
1406 | bit_count = |
1407 | create_header(&header_bitbuf, rl_huff, rl_huff_len, |
1408 | count_histogram, hlit, hdist, LAST_BLOCK1); |
1409 | flush(&header_bitbuf); |
1410 | |
1411 | hufftables->deflate_hdr_count = bit_count / 8; |
1412 | hufftables->deflate_hdr_extra_bits = bit_count % 8; |
1413 | |
1414 | return 0; |
1415 | } |
1416 | |
1417 | int isal_create_hufftables_subset(struct isal_hufftables *hufftables, |
1418 | struct isal_huff_histogram *histogram) |
1419 | { |
1420 | struct huff_code lit_huff_table[LIT_LEN(257 + 29)], dist_huff_table[DIST_LEN30]; |
1421 | uint64_t bit_count; |
1422 | int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE(32*1024)); |
1423 | struct heap_tree heap_space; |
1424 | uint32_t heap_size; |
1425 | uint32_t code_len_count[MAX_HUFF_TREE_DEPTH15 + 1]; |
1426 | struct BitBuf2 header_bitbuf; |
1427 | uint32_t max_lit_len_sym; |
1428 | uint32_t max_dist_sym; |
1429 | uint32_t hlit, hdist, i; |
1430 | uint16_t combined_table[LIT_LEN(257 + 29) + DIST_LEN30]; |
1431 | uint64_t count_histogram[HUFF_LEN19]; |
1432 | struct rl_code rl_huff[LIT_LEN(257 + 29) + DIST_LEN30]; |
1433 | uint32_t rl_huff_len; |
1434 | |
1435 | uint32_t *dist_table = hufftables->dist_table; |
1436 | uint32_t *len_table = hufftables->len_table; |
1437 | uint16_t *lit_table = hufftables->lit_table; |
1438 | uint16_t *dcodes = hufftables->dcodes; |
1439 | uint8_t *lit_table_sizes = hufftables->lit_table_sizes; |
1440 | uint8_t *dcodes_sizes = hufftables->dcodes_sizes; |
1441 | uint8_t *deflate_hdr = hufftables->deflate_hdr; |
1442 | uint64_t *lit_len_histogram = histogram->lit_len_histogram; |
1443 | uint64_t *dist_histogram = histogram->dist_histogram; |
1444 | |
1445 | memset(hufftables, 0, sizeof(struct isal_hufftables)); |
1446 | |
1447 | heap_size = init_heap64(&heap_space, lit_len_histogram, LIT_LEN(257 + 29)); |
1448 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1449 | (struct huff_code *)lit_huff_table, LIT_LEN(257 + 29), MAX_DEFLATE_CODE_LEN15); |
1450 | max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN(257 + 29), code_len_count); |
1451 | |
1452 | heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN30); |
1453 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1454 | (struct huff_code *)dist_huff_table, max_dist, |
1455 | MAX_DEFLATE_CODE_LEN15); |
1456 | max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN30, code_len_count); |
1457 | |
1458 | if (are_hufftables_useable(lit_huff_table, dist_huff_table)) { |
| 1 | Assuming the condition is false | |
|
| |
1459 | heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN(257 + 29)); |
1460 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1461 | (struct huff_code *)lit_huff_table, LIT_LEN(257 + 29), |
1462 | MAX_SAFE_LIT_CODE_LEN13); |
1463 | max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN(257 + 29), code_len_count); |
1464 | |
1465 | heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN30); |
1466 | gen_huff_code_lens(&heap_space, heap_size, code_len_count, |
1467 | (struct huff_code *)dist_huff_table, max_dist, |
1468 | MAX_SAFE_DIST_CODE_LEN12); |
1469 | max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN30, code_len_count); |
1470 | |
1471 | } |
1472 | |
1473 | create_code_tables(dcodes, dcodes_sizes, DIST_LEN30 - DCODE_OFFSET0, |
1474 | dist_huff_table + DCODE_OFFSET0); |
1475 | |
1476 | create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table); |
1477 | |
1478 | create_packed_len_table(len_table, lit_huff_table); |
1479 | create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table); |
1480 | |
1481 | set_buf(&header_bitbuf, deflate_hdr, sizeof(deflate_hdr)); |
1482 | init(&header_bitbuf); |
1483 | |
1484 | hlit = max_lit_len_sym - 256; |
1485 | hdist = max_dist_sym; |
1486 | |
1487 | |
1488 | memset(count_histogram, 0, sizeof(count_histogram)); |
1489 | for (i = 0; i < 257 + hlit; i++) |
| 3 | | Assuming the condition is false | |
|
| 4 | | Loop condition is false. Execution continues on line 1491 | |
|
1490 | combined_table[i] = lit_huff_table[i].length; |
1491 | for (i = 0; i < 1 + hdist; i++) |
| 5 | | Assuming the condition is false | |
|
| 6 | | Loop condition is false. Execution continues on line 1494 | |
|
1492 | combined_table[i + hlit + 257] = dist_huff_table[i].length; |
1493 | rl_huff_len = |
1494 | rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff); |
| |
1495 | |
1496 | |
1497 | bit_count = |
1498 | create_header(&header_bitbuf, rl_huff, rl_huff_len, |
1499 | count_histogram, hlit, hdist, LAST_BLOCK1); |
1500 | flush(&header_bitbuf); |
1501 | |
1502 | hufftables->deflate_hdr_count = bit_count / 8; |
1503 | hufftables->deflate_hdr_extra_bits = bit_count % 8; |
1504 | |
1505 | return 0; |
1506 | } |
1507 | |
1508 | void expand_hufftables_icf(struct hufftables_icf *hufftables) |
1509 | { |
1510 | uint32_t i, eb, j, k, len, code; |
1511 | struct huff_code orig[21], *p_code; |
1512 | struct huff_code *lit_len_codes = hufftables->lit_len_table; |
1513 | struct huff_code *dist_codes = hufftables->dist_table; |
1514 | |
1515 | for (i = 0; i < 21; i++) |
1516 | orig[i] = lit_len_codes[i + 265]; |
1517 | |
1518 | p_code = &lit_len_codes[265]; |
1519 | |
1520 | i = 0; |
1521 | for (eb = 1; eb < 6; eb++) { |
1522 | for (k = 0; k < 4; k++) { |
1523 | len = orig[i].length; |
1524 | code = orig[i++].code; |
1525 | for (j = 0; j < (1u << eb); j++) { |
1526 | p_code->code_and_extra = code | (j << len); |
1527 | p_code->length = len + eb; |
1528 | p_code++; |
1529 | } |
1530 | } |
1531 | } |
1532 | |
1533 | p_code[-1] = orig[i]; |
1534 | |
1535 | dist_codes[DIST_LEN30].code_and_extra = 0; |
1536 | dist_codes[DIST_LEN30].length = 0; |
1537 | } |
1538 | |
1539 | void |
1540 | create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf *hufftables, |
1541 | struct isal_mod_hist *hist, uint32_t end_of_block) |
1542 | { |
1543 | uint32_t bl_count[MAX_DEFLATE_CODE_LEN15 + 1]; |
1544 | uint32_t max_ll_code, max_d_code; |
1545 | struct heap_tree heap_space; |
1546 | uint32_t heap_size; |
1547 | struct rl_code cl_tokens[LIT_LEN(257 + 29) + DIST_LEN30]; |
1548 | uint32_t num_cl_tokens; |
1549 | uint64_t cl_counts[CODE_LEN_CODES19]; |
1550 | uint16_t combined_table[LIT_LEN(257 + 29) + DIST_LEN30]; |
1551 | int i; |
1552 | uint64_t compressed_len = 0; |
1553 | uint64_t static_compressed_len = 3; |
1554 | struct BitBuf2 bb_tmp; |
1555 | |
1556 | struct huff_code *ll_codes = hufftables->lit_len_table; |
1557 | struct huff_code *d_codes = hufftables->dist_table; |
1558 | uint32_t *ll_hist = hist->ll_hist; |
1559 | uint32_t *d_hist = hist->d_hist; |
1560 | struct huff_code *static_ll_codes = static_hufftables.lit_len_table; |
1561 | struct huff_code *static_d_codes = static_hufftables.dist_table; |
1562 | |
1563 | memcpy(&bb_tmp, bb, sizeof(struct BitBuf2)); |
1564 | |
1565 | flatten_ll(hist->ll_hist); |
1566 | |
1567 | |
1568 | if (ll_hist[256] == 0) |
1569 | ll_hist[256] = 1; |
1570 | |
1571 | heap_size = init_heap32(&heap_space, ll_hist, LIT_LEN(257 + 29)); |
1572 | gen_huff_code_lens(&heap_space, heap_size, bl_count, |
1573 | ll_codes, LIT_LEN(257 + 29), MAX_DEFLATE_CODE_LEN15); |
1574 | max_ll_code = set_huff_codes(ll_codes, LIT_LEN(257 + 29), bl_count); |
1575 | |
1576 | heap_size = init_heap32(&heap_space, d_hist, DIST_LEN30); |
1577 | gen_huff_code_lens(&heap_space, heap_size, bl_count, d_codes, |
1578 | DIST_LEN30, MAX_DEFLATE_CODE_LEN15); |
1579 | max_d_code = set_dist_huff_codes(d_codes, bl_count); |
1580 | |
1581 | assert(max_ll_code >= 256)((void) (0)); |
1582 | assert(max_d_code != 0)((void) (0)); |
1583 | |
1584 | |
1585 | memset(cl_counts, 0, sizeof(cl_counts)); |
1586 | |
1587 | for (i = 0; i <= 256; i++) { |
1588 | combined_table[i] = ll_codes[i].length; |
1589 | compressed_len += ll_codes[i].length * ll_hist[i]; |
1590 | static_compressed_len += static_ll_codes[i].length * ll_hist[i]; |
1591 | } |
1592 | |
1593 | for (; i < max_ll_code + 1; i++) { |
1594 | combined_table[i] = ll_codes[i].length; |
1595 | compressed_len += |
1596 | (ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i]; |
1597 | static_compressed_len += |
1598 | (static_ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i]; |
1599 | } |
1600 | |
1601 | for (i = 0; i < max_d_code + 1; i++) { |
1602 | combined_table[i + max_ll_code + 1] = d_codes[i].length; |
1603 | compressed_len += (d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i]; |
1604 | static_compressed_len += |
1605 | (static_d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i]; |
1606 | } |
1607 | |
1608 | expand_hufftables_icf(hufftables); |
1609 | |
1610 | num_cl_tokens = |
1611 | rl_encode(combined_table, max_ll_code + max_d_code + 2, cl_counts, cl_tokens); |
1612 | |
1613 | |
1614 | create_header(bb, cl_tokens, num_cl_tokens, cl_counts, max_ll_code - 256, max_d_code, |
1615 | end_of_block); |
1616 | compressed_len += 8 * buffer_used(bb) + bb->m_bit_count; |
1617 | |
1618 | if (static_compressed_len < compressed_len) { |
1619 | memcpy(hufftables, &static_hufftables, sizeof(struct hufftables_icf)); |
1620 | expand_hufftables_icf(hufftables); |
1621 | memcpy(bb, &bb_tmp, sizeof(struct BitBuf2)); |
1622 | end_of_block = end_of_block ? 1 : 0; |
1623 | write_bits(bb, 0x2 | end_of_block, 3); |
1624 | } |
1625 | } |