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 #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 /* The order code length codes are written in the dynamic code header. This is
41 * defined in RFC 1951 page 13 */
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 /* Version info */
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 // bit reverse low order LENGTH bits in code, and return result in low order bits
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)); /* Initialize last_seen to be 0. */
685 for (current = start_stream; current < end_stream - 3; current++) {
686 literal = *(uint32_t *) current;
687 hash = compute_hash(literal) & HASH_MASK;
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 - 1) {
692 assert(start_stream <= current - dist);
693 match_length =
694 compare258(current - dist, current, end_stream - current);
695 if (match_length >= SHORTEST_MATCH) {
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;
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;
722 seen = last_seen[hash];
723 last_seen[hash] = (current - start_stream) & 0xFFFF;
724 dist = (current - start_stream - seen) & 0xFFFF;
725 if (dist < D) {
726 match_length = compare258(current - dist, current, end_stream - current);
727 if (match_length >= SHORTEST_MATCH) {
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);
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; /* ~0 is an invalid distance code */
776
777 }
778
779 uint32_t convert_length_to_len_sym(uint32_t length)
780 {
781 assert(length > 2 && length < 259);
782
783 /* Based on tables on page 11 in RFC 1951 */
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 // Upon return, codes[] contains the code lengths,
801 // and bl_count is the count of the lengths
802
803 /* Init heap with the histogram, and return the histogram size */
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_SHIFT) | i;
816 }
817
818 // make sure heap has at least two elements in it
819 if (heap_size < 2) {
820 if (heap_size == 0) {
821 heap_space->heap[1] = 1ULL << FREQ_SHIFT;
822 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
823 heap_size = 2;
824 } else {
825 // heap size == 1
826 if (histogram[0] == 0)
827 heap_space->heap[2] = 1ULL << FREQ_SHIFT;
828 else
829 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 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_SHIFT) | i;
850 }
851
852 // make sure heap has at least two elements in it
853 if (heap_size < 2) {
854 if (heap_size == 0) {
855 heap_space->heap[1] = 1ULL << FREQ_SHIFT;
856 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
857 heap_size = 2;
858 } else {
859 // heap size == 1
860 if (histogram[0] == 0)
861 heap_space->heap[2] = 1ULL << FREQ_SHIFT;
862 else
863 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 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_SHIFT) | 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 // compute code lengths and code length counts
897 code_len = 0;
898 j = root_node;
899 for (i = root_node; i <= HEAP_TREE_NODE_START; i++) {
900 child = tree[i].child;
901 if (child > MAX_HISTHEAP_SIZE) {
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);
920 for (i = max_code_len - 1; i != 0; i--)
921 if (code_len_count[i] != 0)
922 break;
923 assert(i != 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, 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 /* Uses the algorithm mentioned in the deflate standard, Rfc 1951. */
976 int i;
977 uint16_t code = 0;
978 uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1];
979 uint32_t max_code = 0;
980
981 next_code[0] = code;
982
983 for (i = 1; i < MAX_HUFF_TREE_DEPTH + 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 // on input, codes contain the code lengths
1000 // on output, code contains:
1001 // 23:16 code length
1002 // 15:0 code value in low order bits
1003 // returns max code value
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_LEN + 1];
1008 uint32_t max_code = 0;
1009 const uint32_t num_codes = DIST_LEN;
1010
1011 code = bl_count[0] = 0;
1012 for (bits = 1; bits <= MAX_HUFF_TREE_DEPTH; 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 /* hlit, hdist, hclen are as defined in the deflate standard, head is the
1035 * first three deflate header bits.*/
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_LEN);
1046 write_bits(header_bitbuf, data, DYN_HDR_START_LEN + 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_DEPTH + 1];
1078 struct huff_code lookup_table[HUFF_LEN];
1079
1080 /* hlit, hdist, and hclen are defined in RFC 1951 page 13 */
1081 uint32_t hclen;
1082 uint64_t bit_count;
1083
1084 /* Create a huffman tree to encode run length encoded representation. */
1085 heap_size = init_heap64(&heap_space, histogram, HUFF_LEN);
1086 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1087 (struct huff_code *)lookup_table, HUFF_LEN, 7);
1088 set_huff_codes(lookup_table, HUFF_LEN, code_len_count);
1089
1090 /* Calculate hclen */
1091 for (i = CODE_LEN_CODES - 1; i > 3; i--) /* i must be at least 4 */
1092 if (lookup_table[code_length_code_order[i]].length != 0)
1093 break;
1094
1095 hclen = i - 3;
1096
1097 /* Generate actual header. */
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 // 1 <= run_len <= 138
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);
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 // last_len != 0
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 // 1 <= run_len <= 6
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: // 3...6
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 // convert codes into run-length symbols, write symbols into OUT
1184 // generate histogram into COUNTS (assumed to be initialized to 0)
1185 // Format of OUT:
1186 // 4:0 code (0...18)
1187 // 15:8 Extra bits (0...127)
1188 // returns number of symbols in out
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];
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 /* Gain extra bits is the next place where the number of extra bits in
1231 * lenght codes increases. */
1232 uint16_t gain_extra_bits = LEN_EXTRA_BITS_START;
1233
1234 for (i = 257; i < LIT_LEN - 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_BITS)) |
1240 (lit_len_hufftable[i].code << LENGTH_BITS) |
1241 (lit_len_hufftable[i].length + extra_bits_count);
1242 }
1243
1244 if (i == gain_extra_bits) {
1245 gain_extra_bits += LEN_EXTRA_BITS_INTERVAL;
1246 extra_bits_count += 1;
1247 }
1248 }
1249
1250 packed_table[count] = (lit_len_hufftable[LIT_LEN - 1].code << LENGTH_BITS) |
1251 (lit_len_hufftable[LIT_LEN - 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 /* Gain extra bits is the next place where the number of extra bits in
1262 * distance codes increases. */
1263 uint16_t gain_extra_bits = DIST_EXTRA_BITS_START;
1264
1265 for (i = 0; i < DIST_LEN; 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_BITS)) |
1272 (dist_hufftable[i].code << LENGTH_BITS) |
1273 (dist_hufftable[i].length + extra_bits_count);
1274
1275 }
1276
1277 if (i == gain_extra_bits) {
1278 gain_extra_bits += DIST_EXTRA_BITS_INTERVAL;
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_START;
1290 int gain_len_extra_bits = LEN_EXTRA_BITS_START;
1291 int max_code_len;
1292 int i;
1293
1294 for (i = 0; i < LIT_LEN; 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 - 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_INTERVAL;
1304 len_extra_bits += 1;
1305 }
1306 }
1307
1308 for (i = 0; i < DIST_LEN; 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_INTERVAL;
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 /* Some versions of igzip can write upto one literal, one length and one
1321 * distance code at the same time. This checks to make sure that is
1322 * always writeable in bitbuf*/
1323 return (max_code_len > MAX_BITBUF_BIT_WRITE);
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], dist_huff_table[DIST_LEN];
1330 uint64_t bit_count;
1331 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE);
1332 struct heap_tree heap_space;
1333 uint32_t heap_size;
1334 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 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 + DIST_LEN];
1340 uint64_t count_histogram[HUFF_LEN];
1341 struct rl_code rl_huff[LIT_LEN + DIST_LEN];
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);
1357 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1358 (struct huff_code *)lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN);
1359 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1360
1361 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
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_LEN);
1365 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, 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);
1369 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1370 (struct huff_code *)lit_huff_table, LIT_LEN,
1371 MAX_SAFE_LIT_CODE_LEN);
1372 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1373
1374 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
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_LEN);
1378 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
1379
1380 }
1381
1382 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET,
1383 dist_huff_table + DCODE_OFFSET);
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 /* Run length encode the length and distance huffman codes */
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 /* Create header */
1406 bit_count =
1407 create_header(&header_bitbuf, rl_huff, rl_huff_len,
1408 count_histogram, hlit, hdist, LAST_BLOCK);
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], dist_huff_table[DIST_LEN];
1421 uint64_t bit_count;
1422 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE);
1423 struct heap_tree heap_space;
1424 uint32_t heap_size;
1425 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 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 + DIST_LEN];
1431 uint64_t count_histogram[HUFF_LEN];
1432 struct rl_code rl_huff[LIT_LEN + DIST_LEN];
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);
1448 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1449 (struct huff_code *)lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN);
1450 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1451
1452 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
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_LEN);
1456 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
1457
1458 if (are_hufftables_useable(lit_huff_table, dist_huff_table)) {
1459 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN);
1460 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1461 (struct huff_code *)lit_huff_table, LIT_LEN,
1462 MAX_SAFE_LIT_CODE_LEN);
1463 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1464
1465 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
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_LEN);
1469 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
1470
1471 }
1472
1473 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET,
1474 dist_huff_table + DCODE_OFFSET);
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
|
(1) Event suspicious_sizeof: |
Passing argument "deflate_hdr" of type "uint8_t *" and argument "8U /* sizeof (deflate_hdr) */" to function "set_buf" is suspicious. |
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 /* Run length encode the length and distance huffman codes */
1488 memset(count_histogram, 0, sizeof(count_histogram));
1489 for (i = 0; i < 257 + hlit; i++)
1490 combined_table[i] = lit_huff_table[i].length;
1491 for (i = 0; i < 1 + hdist; i++)
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 /* Create header */
1497 bit_count =
1498 create_header(&header_bitbuf, rl_huff, rl_huff_len,
1499 count_histogram, hlit, hdist, LAST_BLOCK);
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 } // end for k
1531 } // end for eb
1532 // fix up last record
1533 p_code[-1] = orig[i];
1534
1535 dist_codes[DIST_LEN].code_and_extra = 0;
1536 dist_codes[DIST_LEN].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_LEN + 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 + DIST_LEN];
1548 uint32_t num_cl_tokens;
1549 uint64_t cl_counts[CODE_LEN_CODES];
1550 uint16_t combined_table[LIT_LEN + DIST_LEN];
1551 int i;
1552 uint64_t compressed_len = 0;
1553 uint64_t static_compressed_len = 3; /* The static header size */
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 // make sure EOB is present
1568 if (ll_hist[256] == 0)
1569 ll_hist[256] = 1;
1570
1571 heap_size = init_heap32(&heap_space, ll_hist, LIT_LEN);
1572 gen_huff_code_lens(&heap_space, heap_size, bl_count,
1573 ll_codes, LIT_LEN, MAX_DEFLATE_CODE_LEN);
1574 max_ll_code = set_huff_codes(ll_codes, LIT_LEN, bl_count);
1575
1576 heap_size = init_heap32(&heap_space, d_hist, DIST_LEN);
1577 gen_huff_code_lens(&heap_space, heap_size, bl_count, d_codes,
1578 DIST_LEN, MAX_DEFLATE_CODE_LEN);
1579 max_d_code = set_dist_huff_codes(d_codes, bl_count);
1580
1581 assert(max_ll_code >= 256); // must be EOB code
1582 assert(max_d_code != 0);
1583
1584 /* Run length encode the length and distance huffman codes */
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 /* Create header */
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 }
1626