1 /**********************************************************************
2 Copyright(c) 2011-2016 Intel Corporation All rights reserved.
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
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
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.
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 **********************************************************************/
30 #include <immintrin.h>
34 #include "igzip_lib.h"
35 #include "huff_codes.h"
38 #include "flatten_ll.h"
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 };
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
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
59 struct hufftables_icf static_hufftables
= {
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}},
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}}
615 struct slver isal_update_histogram_slver_00010085
;
616 struct slver isal_update_histogram_slver
= { 0x0085, 0x01, 0x00 };
618 struct slver isal_create_hufftables_slver_00010086
;
619 struct slver isal_create_hufftables_slver
= { 0x0086, 0x01, 0x00 };
621 struct slver isal_create_hufftables_subset_slver_00010087
;
622 struct slver isal_create_hufftables_subset_slver
= { 0x0087, 0x01, 0x00 };
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
);
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
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
)
665 code
= (bitrev8
[code
& 0x00FF] << 8) | (bitrev8
[code
>> 8]);
666 return (code
>> (16 - length
));
669 void isal_update_histogram_base(uint8_t * start_stream
, int length
,
670 struct isal_huff_histogram
*histogram
)
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
;
677 uint64_t *lit_len_histogram
= histogram
->lit_len_histogram
;
678 uint64_t *dist_histogram
= histogram
->dist_histogram
;
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
);
694 compare258(current
- dist
, current
, end_stream
- current
);
695 if (match_length
>= SHORTEST_MATCH
) {
697 #ifdef ISAL_LIMIT_HASH_UPDATE
700 end
= next_hash
+ match_length
;
702 if (end
> end_stream
- 3)
703 end
= end_stream
- 3;
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;
711 dist_histogram
[convert_dist_to_dist_sym(dist
)] += 1;
712 lit_len_histogram
[convert_length_to_len_sym(match_length
)] +=
714 current
+= match_length
- 1;
718 lit_len_histogram
[literal
& 0xFF] += 1;
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;
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;
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;
741 uint32_t convert_dist_to_dist_sym(uint32_t dist
)
743 assert(dist
<= 32768 && dist
> 0);
747 return 0 + (dist
- 1) / 1;
749 return 2 + (dist
- 1) / 2;
751 return 4 + (dist
- 1) / 4;
753 return 6 + (dist
- 1) / 8;
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;
775 return ~0; /* ~0 is an invalid distance code */
779 uint32_t convert_length_to_len_sym(uint32_t length
)
781 assert(length
> 2 && length
< 259);
783 /* Based on tables on page 11 in RFC 1951 */
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;
800 // Upon return, codes[] contains the code lengths,
801 // and bl_count is the count of the lengths
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
,
807 uint32_t heap_size
, i
;
809 memset(heap_space
, 0, sizeof(struct heap_tree
));
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
;
818 // make sure heap has at least two elements in it
820 if (heap_size
== 0) {
821 heap_space
->heap
[1] = 1ULL << FREQ_SHIFT
;
822 heap_space
->heap
[2] = (1ULL << FREQ_SHIFT
) | 1;
826 if (histogram
[0] == 0)
827 heap_space
->heap
[2] = 1ULL << FREQ_SHIFT
;
829 heap_space
->heap
[2] = (1ULL << FREQ_SHIFT
) | 1;
834 build_heap(heap_space
->heap
, heap_size
);
839 static inline uint32_t init_heap64(struct heap_tree
*heap_space
, uint64_t * histogram
,
842 uint32_t heap_size
, i
;
844 memset(heap_space
, 0, sizeof(struct heap_tree
));
847 for (i
= 0; i
< hist_size
; i
++) {
848 if (histogram
[i
] != 0)
849 heap_space
->heap
[++heap_size
] = ((histogram
[i
]) << FREQ_SHIFT
) | i
;
852 // make sure heap has at least two elements in it
854 if (heap_size
== 0) {
855 heap_space
->heap
[1] = 1ULL << FREQ_SHIFT
;
856 heap_space
->heap
[2] = (1ULL << FREQ_SHIFT
) | 1;
860 if (histogram
[0] == 0)
861 heap_space
->heap
[2] = 1ULL << FREQ_SHIFT
;
863 heap_space
->heap
[2] = (1ULL << FREQ_SHIFT
) | 1;
868 build_heap(heap_space
->heap
, heap_size
);
873 static inline uint32_t init_heap64_complete(struct heap_tree
*heap_space
, uint64_t * histogram
,
876 uint32_t heap_size
, i
;
878 memset(heap_space
, 0, sizeof(struct heap_tree
));
881 for (i
= 0; i
< hist_size
; i
++)
882 heap_space
->heap
[++heap_size
] = ((histogram
[i
]) << FREQ_SHIFT
) | i
;
884 build_heap(heap_space
->heap
, heap_size
);
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
)
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
;
896 // compute code lengths and code length counts
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
;
904 tree
[child
].depth
= depth
;
905 tree
[child
- 1].depth
= depth
;
908 depth
= tree
[i
].depth
;
909 while (code_len
< depth
) {
911 code_len_count
[code_len
] = 0;
913 code_len_count
[depth
]++;
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)
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)
932 for (i
= 1; i
<= code_len
; i
++)
933 bl_count
[i
] = code_len_count
[i
];
934 for (; i
<= max_code_len
; i
++)
937 for (k
= 1; code_len_count
[k
] == 0; k
++) ;
938 for (i
= root_node
; i
< j
; i
++) {
941 for (; code_len_count
[k
] == 0; k
++) ;
944 for (i
= 1; i
<= code_len
; i
++)
945 bl_count
[i
] = code_len_count
[i
];
946 for (; i
<= max_code_len
; i
++)
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
)
958 struct tree_node
*tree
= heap_space
->tree
;
959 uint32_t root_node
= HEAP_TREE_NODE_START
, node_ptr
;
962 root_node
= build_huff_tree(heap_space
, heap_size
, root_node
);
964 end_node
= fix_code_lens(heap_space
, root_node
, bl_count
, max_code_len
);
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
;
972 inline uint32_t set_huff_codes(struct huff_code
*huff_code_table
, int table_length
,
975 /* Uses the algorithm mentioned in the deflate standard, Rfc 1951. */
978 uint16_t next_code
[MAX_HUFF_TREE_DEPTH
+ 1];
979 uint32_t max_code
= 0;
983 for (i
= 1; i
< MAX_HUFF_TREE_DEPTH
+ 1; i
++)
984 next_code
[i
] = (next_code
[i
- 1] + count
[i
- 1]) << 1;
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;
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
)
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
;
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
;
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;
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
)
1034 /* hlit, hdist, hclen are as defined in the deflate standard, head is the
1035 * first three deflate header bits.*/
1039 struct huff_code huffman_value
;
1040 const uint32_t extra_bits
[3] = { 2, 3, 7 };
1042 bit_count
= buffer_bits_used(header_bitbuf
);
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);
1048 for (i
= hclen
+ 3; i
>= 1; i
--)
1049 data
= (data
<< 3) | lookup_table
[code_length_code_order
[i
]].length
;
1051 write_bits(header_bitbuf
, data
, (hclen
+ 3) * 3);
1053 for (i
= 0; i
< huffman_rep_length
; i
++) {
1054 huffman_value
= lookup_table
[huffman_rep
[i
].code
];
1056 write_bits(header_bitbuf
, (uint64_t) huffman_value
.code
,
1057 (uint32_t) huffman_value
.length
);
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]);
1064 bit_count
= buffer_bits_used(header_bitbuf
) - bit_count
;
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
)
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
];
1080 /* hlit, hdist, and hclen are defined in RFC 1951 page 13 */
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
);
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)
1097 /* Generate actual header. */
1098 bit_count
= create_huffman_header(header_bitbuf
, lookup_table
, huffman_rep
,
1099 length
, end_of_block
, hclen
, hlit
, hdist
);
1105 struct rl_code
*write_rl(struct rl_code
*pout
, uint16_t last_len
, uint32_t run_len
,
1108 if (last_len
== 0) {
1109 while (run_len
> 138) {
1111 pout
->extra_bits
= 138 - 11;
1116 // 1 <= run_len <= 138
1119 pout
->extra_bits
= run_len
- 11;
1122 } else if (run_len
> 2) {
1124 pout
->extra_bits
= run_len
- 3;
1127 } else if (run_len
== 1) {
1129 pout
->extra_bits
= 0;
1133 assert(run_len
== 2);
1135 pout
[0].extra_bits
= 0;
1137 pout
[1].extra_bits
= 0;
1143 pout
->code
= last_len
;
1144 pout
->extra_bits
= 0;
1149 while (run_len
> 6) {
1151 pout
->extra_bits
= 6 - 3;
1156 // 1 <= run_len <= 6
1159 pout
->code
= last_len
;
1160 pout
->extra_bits
= 0;
1165 pout
[0].code
= last_len
;
1166 pout
[0].extra_bits
= 0;
1167 pout
[1].code
= last_len
;
1168 pout
[1].extra_bits
= 0;
1170 counts
[last_len
] += 2;
1174 pout
->extra_bits
= run_len
- 3;
1183 // convert codes into run-length symbols, write symbols into OUT
1184 // generate histogram into COUNTS (assumed to be initialized to 0)
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
)
1192 uint32_t i
, run_len
;
1193 uint16_t last_len
, len
;
1194 struct rl_code
*pout
;
1197 last_len
= codes
[0];
1199 for (i
= 1; i
< num_codes
; i
++) {
1201 if (len
== last_len
) {
1205 pout
= write_rl(pout
, last_len
, run_len
, counts
);
1209 pout
= write_rl(pout
, last_len
, run_len
, counts
);
1211 return (uint32_t) (pout
- out
);
1214 void create_code_tables(uint16_t * code_table
, uint8_t * code_length_table
, uint32_t length
,
1215 struct huff_code
*hufftable
)
1218 for (i
= 0; i
< length
; i
++) {
1219 code_table
[i
] = hufftable
[i
].code
;
1220 code_length_table
[i
] = hufftable
[i
].length
;
1224 void create_packed_len_table(uint32_t * packed_table
, struct huff_code
*lit_len_hufftable
)
1227 uint16_t extra_bits
;
1228 uint16_t extra_bits_count
= 0;
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
;
1234 for (i
= 257; i
< LIT_LEN
- 1; i
++) {
1235 for (extra_bits
= 0; extra_bits
< (1 << extra_bits_count
); extra_bits
++) {
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
);
1244 if (i
== gain_extra_bits
) {
1245 gain_extra_bits
+= LEN_EXTRA_BITS_INTERVAL
;
1246 extra_bits_count
+= 1;
1250 packed_table
[count
] = (lit_len_hufftable
[LIT_LEN
- 1].code
<< LENGTH_BITS
) |
1251 (lit_len_hufftable
[LIT_LEN
- 1].length
);
1254 void create_packed_dist_table(uint32_t * packed_table
, uint32_t length
,
1255 struct huff_code
*dist_hufftable
)
1258 uint16_t extra_bits
;
1259 uint16_t extra_bits_count
= 0;
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
;
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
)
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
);
1277 if (i
== gain_extra_bits
) {
1278 gain_extra_bits
+= DIST_EXTRA_BITS_INTERVAL
;
1279 extra_bits_count
+= 1;
1284 int are_hufftables_useable(struct huff_code
*lit_len_hufftable
,
1285 struct huff_code
*dist_hufftable
)
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
;
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
;
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
;
1302 if (i
== gain_len_extra_bits
) {
1303 gain_len_extra_bits
+= LEN_EXTRA_BITS_INTERVAL
;
1304 len_extra_bits
+= 1;
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
;
1312 if (i
== gain_dist_extra_bits
) {
1313 gain_dist_extra_bits
+= DIST_EXTRA_BITS_INTERVAL
;
1314 dist_extra_bits
+= 1;
1318 max_code_len
= max_lit_code_len
+ max_len_code_len
+ max_dist_code_len
;
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
);
1326 int isal_create_hufftables(struct isal_hufftables
*hufftables
,
1327 struct isal_huff_histogram
*histogram
)
1329 struct huff_code lit_huff_table
[LIT_LEN
], dist_huff_table
[DIST_LEN
];
1331 int max_dist
= convert_dist_to_dist_sym(IGZIP_HIST_SIZE
);
1332 struct heap_tree heap_space
;
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
;
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
;
1354 memset(hufftables
, 0, sizeof(struct isal_hufftables
));
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
);
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
);
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
);
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
);
1382 create_code_tables(dcodes
, dcodes_sizes
, DIST_LEN
- DCODE_OFFSET
,
1383 dist_huff_table
+ DCODE_OFFSET
);
1385 create_code_tables(lit_table
, lit_table_sizes
, IGZIP_LIT_TABLE_SIZE
, lit_huff_table
);
1387 create_packed_len_table(len_table
, lit_huff_table
);
1388 create_packed_dist_table(dist_table
, IGZIP_DIST_TABLE_SIZE
, dist_huff_table
);
1390 set_buf(&header_bitbuf
, deflate_hdr
, sizeof(deflate_hdr
));
1391 init(&header_bitbuf
);
1393 hlit
= max_lit_len_sym
- 256;
1394 hdist
= max_dist_sym
;
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
;
1403 rl_encode(combined_table
, hlit
+ 257 + hdist
+ 1, count_histogram
, rl_huff
);
1407 create_header(&header_bitbuf
, rl_huff
, rl_huff_len
,
1408 count_histogram
, hlit
, hdist
, LAST_BLOCK
);
1409 flush(&header_bitbuf
);
1411 hufftables
->deflate_hdr_count
= bit_count
/ 8;
1412 hufftables
->deflate_hdr_extra_bits
= bit_count
% 8;
1417 int isal_create_hufftables_subset(struct isal_hufftables
*hufftables
,
1418 struct isal_huff_histogram
*histogram
)
1420 struct huff_code lit_huff_table
[LIT_LEN
], dist_huff_table
[DIST_LEN
];
1422 int max_dist
= convert_dist_to_dist_sym(IGZIP_HIST_SIZE
);
1423 struct heap_tree heap_space
;
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
;
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
;
1445 memset(hufftables
, 0, sizeof(struct isal_hufftables
));
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
);
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
);
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
);
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
);
1473 create_code_tables(dcodes
, dcodes_sizes
, DIST_LEN
- DCODE_OFFSET
,
1474 dist_huff_table
+ DCODE_OFFSET
);
1476 create_code_tables(lit_table
, lit_table_sizes
, IGZIP_LIT_TABLE_SIZE
, lit_huff_table
);
1478 create_packed_len_table(len_table
, lit_huff_table
);
1479 create_packed_dist_table(dist_table
, IGZIP_DIST_TABLE_SIZE
, dist_huff_table
);
1481 set_buf(&header_bitbuf
, deflate_hdr
, sizeof(deflate_hdr
));
1482 init(&header_bitbuf
);
1484 hlit
= max_lit_len_sym
- 256;
1485 hdist
= max_dist_sym
;
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
;
1494 rl_encode(combined_table
, hlit
+ 257 + hdist
+ 1, count_histogram
, rl_huff
);
1498 create_header(&header_bitbuf
, rl_huff
, rl_huff_len
,
1499 count_histogram
, hlit
, hdist
, LAST_BLOCK
);
1500 flush(&header_bitbuf
);
1502 hufftables
->deflate_hdr_count
= bit_count
/ 8;
1503 hufftables
->deflate_hdr_extra_bits
= bit_count
% 8;
1508 void expand_hufftables_icf(struct hufftables_icf
*hufftables
)
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
;
1515 for (i
= 0; i
< 21; i
++)
1516 orig
[i
] = lit_len_codes
[i
+ 265];
1518 p_code
= &lit_len_codes
[265];
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
;
1532 // fix up last record
1533 p_code
[-1] = orig
[i
];
1535 dist_codes
[DIST_LEN
].code_and_extra
= 0;
1536 dist_codes
[DIST_LEN
].length
= 0;
1540 create_hufftables_icf(struct BitBuf2
*bb
, struct hufftables_icf
*hufftables
,
1541 struct isal_mod_hist
*hist
, uint32_t end_of_block
)
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
;
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
];
1552 uint64_t compressed_len
= 0;
1553 uint64_t static_compressed_len
= 3; /* The static header size */
1554 struct BitBuf2 bb_tmp
;
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
;
1563 memcpy(&bb_tmp
, bb
, sizeof(struct BitBuf2
));
1565 flatten_ll(hist
->ll_hist
);
1567 // make sure EOB is present
1568 if (ll_hist
[256] == 0)
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
);
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
);
1581 assert(max_ll_code
>= 256); // must be EOB code
1582 assert(max_d_code
!= 0);
1584 /* Run length encode the length and distance huffman codes */
1585 memset(cl_counts
, 0, sizeof(cl_counts
));
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
];
1593 for (; i
< max_ll_code
+ 1; i
++) {
1594 combined_table
[i
] = ll_codes
[i
].length
;
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
];
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
];
1608 expand_hufftables_icf(hufftables
);
1611 rl_encode(combined_table
, max_ll_code
+ max_d_code
+ 2, cl_counts
, cl_tokens
);
1614 create_header(bb
, cl_tokens
, num_cl_tokens
, cl_counts
, max_ll_code
- 256, max_d_code
,
1616 compressed_len
+= 8 * buffer_used(bb
) + bb
->m_bit_count
;
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);