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 "huff_codes.h"
31 #include "huffman.h"
32 #include "flatten_ll.h"
33
34 /* The order code length codes are written in the dynamic code header. This is
35 * defined in RFC 1951 page 13 */
36 static const uint8_t code_length_code_order[] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
37 11, 4, 12, 3, 13, 2, 14, 1, 15 };
38
39 static const uint32_t len_code_extra_bits[] = { 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x1, 0x1,
40 0x1, 0x1, 0x2, 0x2, 0x2, 0x2, 0x3, 0x3, 0x3, 0x3,
41 0x4, 0x4, 0x4, 0x4, 0x5, 0x5, 0x5, 0x5, 0x0 };
42
43 static const uint32_t dist_code_extra_bits[] = { 0x0, 0x0, 0x0, 0x0, 0x1, 0x1, 0x2, 0x2, 0x3, 0x3,
44 0x4, 0x4, 0x5, 0x5, 0x6, 0x6, 0x7, 0x7, 0x8, 0x8,
45 0x9, 0x9, 0xa, 0xa, 0xb, 0xb, 0xc, 0xc, 0xd, 0xd };
46
47 static struct hufftables_icf static_hufftables = {
48 .lit_len_table = { { { { .code_and_extra = 0x00c, .length2 = 0x8 } } },
49 { { { .code_and_extra = 0x08c, .length2 = 0x8 } } },
50 { { { .code_and_extra = 0x04c, .length2 = 0x8 } } },
51 { { { .code_and_extra = 0x0cc, .length2 = 0x8 } } },
52 { { { .code_and_extra = 0x02c, .length2 = 0x8 } } },
53 { { { .code_and_extra = 0x0ac, .length2 = 0x8 } } },
54 { { { .code_and_extra = 0x06c, .length2 = 0x8 } } },
55 { { { .code_and_extra = 0x0ec, .length2 = 0x8 } } },
56 { { { .code_and_extra = 0x01c, .length2 = 0x8 } } },
57 { { { .code_and_extra = 0x09c, .length2 = 0x8 } } },
58 { { { .code_and_extra = 0x05c, .length2 = 0x8 } } },
59 { { { .code_and_extra = 0x0dc, .length2 = 0x8 } } },
60 { { { .code_and_extra = 0x03c, .length2 = 0x8 } } },
61 { { { .code_and_extra = 0x0bc, .length2 = 0x8 } } },
62 { { { .code_and_extra = 0x07c, .length2 = 0x8 } } },
63 { { { .code_and_extra = 0x0fc, .length2 = 0x8 } } },
64 { { { .code_and_extra = 0x002, .length2 = 0x8 } } },
65 { { { .code_and_extra = 0x082, .length2 = 0x8 } } },
66 { { { .code_and_extra = 0x042, .length2 = 0x8 } } },
67 { { { .code_and_extra = 0x0c2, .length2 = 0x8 } } },
68 { { { .code_and_extra = 0x022, .length2 = 0x8 } } },
69 { { { .code_and_extra = 0x0a2, .length2 = 0x8 } } },
70 { { { .code_and_extra = 0x062, .length2 = 0x8 } } },
71 { { { .code_and_extra = 0x0e2, .length2 = 0x8 } } },
72 { { { .code_and_extra = 0x012, .length2 = 0x8 } } },
73 { { { .code_and_extra = 0x092, .length2 = 0x8 } } },
74 { { { .code_and_extra = 0x052, .length2 = 0x8 } } },
75 { { { .code_and_extra = 0x0d2, .length2 = 0x8 } } },
76 { { { .code_and_extra = 0x032, .length2 = 0x8 } } },
77 { { { .code_and_extra = 0x0b2, .length2 = 0x8 } } },
78 { { { .code_and_extra = 0x072, .length2 = 0x8 } } },
79 { { { .code_and_extra = 0x0f2, .length2 = 0x8 } } },
80 { { { .code_and_extra = 0x00a, .length2 = 0x8 } } },
81 { { { .code_and_extra = 0x08a, .length2 = 0x8 } } },
82 { { { .code_and_extra = 0x04a, .length2 = 0x8 } } },
83 { { { .code_and_extra = 0x0ca, .length2 = 0x8 } } },
84 { { { .code_and_extra = 0x02a, .length2 = 0x8 } } },
85 { { { .code_and_extra = 0x0aa, .length2 = 0x8 } } },
86 { { { .code_and_extra = 0x06a, .length2 = 0x8 } } },
87 { { { .code_and_extra = 0x0ea, .length2 = 0x8 } } },
88 { { { .code_and_extra = 0x01a, .length2 = 0x8 } } },
89 { { { .code_and_extra = 0x09a, .length2 = 0x8 } } },
90 { { { .code_and_extra = 0x05a, .length2 = 0x8 } } },
91 { { { .code_and_extra = 0x0da, .length2 = 0x8 } } },
92 { { { .code_and_extra = 0x03a, .length2 = 0x8 } } },
93 { { { .code_and_extra = 0x0ba, .length2 = 0x8 } } },
94 { { { .code_and_extra = 0x07a, .length2 = 0x8 } } },
95 { { { .code_and_extra = 0x0fa, .length2 = 0x8 } } },
96 { { { .code_and_extra = 0x006, .length2 = 0x8 } } },
97 { { { .code_and_extra = 0x086, .length2 = 0x8 } } },
98 { { { .code_and_extra = 0x046, .length2 = 0x8 } } },
99 { { { .code_and_extra = 0x0c6, .length2 = 0x8 } } },
100 { { { .code_and_extra = 0x026, .length2 = 0x8 } } },
101 { { { .code_and_extra = 0x0a6, .length2 = 0x8 } } },
102 { { { .code_and_extra = 0x066, .length2 = 0x8 } } },
103 { { { .code_and_extra = 0x0e6, .length2 = 0x8 } } },
104 { { { .code_and_extra = 0x016, .length2 = 0x8 } } },
105 { { { .code_and_extra = 0x096, .length2 = 0x8 } } },
106 { { { .code_and_extra = 0x056, .length2 = 0x8 } } },
107 { { { .code_and_extra = 0x0d6, .length2 = 0x8 } } },
108 { { { .code_and_extra = 0x036, .length2 = 0x8 } } },
109 { { { .code_and_extra = 0x0b6, .length2 = 0x8 } } },
110 { { { .code_and_extra = 0x076, .length2 = 0x8 } } },
111 { { { .code_and_extra = 0x0f6, .length2 = 0x8 } } },
112 { { { .code_and_extra = 0x00e, .length2 = 0x8 } } },
113 { { { .code_and_extra = 0x08e, .length2 = 0x8 } } },
114 { { { .code_and_extra = 0x04e, .length2 = 0x8 } } },
115 { { { .code_and_extra = 0x0ce, .length2 = 0x8 } } },
116 { { { .code_and_extra = 0x02e, .length2 = 0x8 } } },
117 { { { .code_and_extra = 0x0ae, .length2 = 0x8 } } },
118 { { { .code_and_extra = 0x06e, .length2 = 0x8 } } },
119 { { { .code_and_extra = 0x0ee, .length2 = 0x8 } } },
120 { { { .code_and_extra = 0x01e, .length2 = 0x8 } } },
121 { { { .code_and_extra = 0x09e, .length2 = 0x8 } } },
122 { { { .code_and_extra = 0x05e, .length2 = 0x8 } } },
123 { { { .code_and_extra = 0x0de, .length2 = 0x8 } } },
124 { { { .code_and_extra = 0x03e, .length2 = 0x8 } } },
125 { { { .code_and_extra = 0x0be, .length2 = 0x8 } } },
126 { { { .code_and_extra = 0x07e, .length2 = 0x8 } } },
127 { { { .code_and_extra = 0x0fe, .length2 = 0x8 } } },
128 { { { .code_and_extra = 0x001, .length2 = 0x8 } } },
129 { { { .code_and_extra = 0x081, .length2 = 0x8 } } },
130 { { { .code_and_extra = 0x041, .length2 = 0x8 } } },
131 { { { .code_and_extra = 0x0c1, .length2 = 0x8 } } },
132 { { { .code_and_extra = 0x021, .length2 = 0x8 } } },
133 { { { .code_and_extra = 0x0a1, .length2 = 0x8 } } },
134 { { { .code_and_extra = 0x061, .length2 = 0x8 } } },
135 { { { .code_and_extra = 0x0e1, .length2 = 0x8 } } },
136 { { { .code_and_extra = 0x011, .length2 = 0x8 } } },
137 { { { .code_and_extra = 0x091, .length2 = 0x8 } } },
138 { { { .code_and_extra = 0x051, .length2 = 0x8 } } },
139 { { { .code_and_extra = 0x0d1, .length2 = 0x8 } } },
140 { { { .code_and_extra = 0x031, .length2 = 0x8 } } },
141 { { { .code_and_extra = 0x0b1, .length2 = 0x8 } } },
142 { { { .code_and_extra = 0x071, .length2 = 0x8 } } },
143 { { { .code_and_extra = 0x0f1, .length2 = 0x8 } } },
144 { { { .code_and_extra = 0x009, .length2 = 0x8 } } },
145 { { { .code_and_extra = 0x089, .length2 = 0x8 } } },
146 { { { .code_and_extra = 0x049, .length2 = 0x8 } } },
147 { { { .code_and_extra = 0x0c9, .length2 = 0x8 } } },
148 { { { .code_and_extra = 0x029, .length2 = 0x8 } } },
149 { { { .code_and_extra = 0x0a9, .length2 = 0x8 } } },
150 { { { .code_and_extra = 0x069, .length2 = 0x8 } } },
151 { { { .code_and_extra = 0x0e9, .length2 = 0x8 } } },
152 { { { .code_and_extra = 0x019, .length2 = 0x8 } } },
153 { { { .code_and_extra = 0x099, .length2 = 0x8 } } },
154 { { { .code_and_extra = 0x059, .length2 = 0x8 } } },
155 { { { .code_and_extra = 0x0d9, .length2 = 0x8 } } },
156 { { { .code_and_extra = 0x039, .length2 = 0x8 } } },
157 { { { .code_and_extra = 0x0b9, .length2 = 0x8 } } },
158 { { { .code_and_extra = 0x079, .length2 = 0x8 } } },
159 { { { .code_and_extra = 0x0f9, .length2 = 0x8 } } },
160 { { { .code_and_extra = 0x005, .length2 = 0x8 } } },
161 { { { .code_and_extra = 0x085, .length2 = 0x8 } } },
162 { { { .code_and_extra = 0x045, .length2 = 0x8 } } },
163 { { { .code_and_extra = 0x0c5, .length2 = 0x8 } } },
164 { { { .code_and_extra = 0x025, .length2 = 0x8 } } },
165 { { { .code_and_extra = 0x0a5, .length2 = 0x8 } } },
166 { { { .code_and_extra = 0x065, .length2 = 0x8 } } },
167 { { { .code_and_extra = 0x0e5, .length2 = 0x8 } } },
168 { { { .code_and_extra = 0x015, .length2 = 0x8 } } },
169 { { { .code_and_extra = 0x095, .length2 = 0x8 } } },
170 { { { .code_and_extra = 0x055, .length2 = 0x8 } } },
171 { { { .code_and_extra = 0x0d5, .length2 = 0x8 } } },
172 { { { .code_and_extra = 0x035, .length2 = 0x8 } } },
173 { { { .code_and_extra = 0x0b5, .length2 = 0x8 } } },
174 { { { .code_and_extra = 0x075, .length2 = 0x8 } } },
175 { { { .code_and_extra = 0x0f5, .length2 = 0x8 } } },
176 { { { .code_and_extra = 0x00d, .length2 = 0x8 } } },
177 { { { .code_and_extra = 0x08d, .length2 = 0x8 } } },
178 { { { .code_and_extra = 0x04d, .length2 = 0x8 } } },
179 { { { .code_and_extra = 0x0cd, .length2 = 0x8 } } },
180 { { { .code_and_extra = 0x02d, .length2 = 0x8 } } },
181 { { { .code_and_extra = 0x0ad, .length2 = 0x8 } } },
182 { { { .code_and_extra = 0x06d, .length2 = 0x8 } } },
183 { { { .code_and_extra = 0x0ed, .length2 = 0x8 } } },
184 { { { .code_and_extra = 0x01d, .length2 = 0x8 } } },
185 { { { .code_and_extra = 0x09d, .length2 = 0x8 } } },
186 { { { .code_and_extra = 0x05d, .length2 = 0x8 } } },
187 { { { .code_and_extra = 0x0dd, .length2 = 0x8 } } },
188 { { { .code_and_extra = 0x03d, .length2 = 0x8 } } },
189 { { { .code_and_extra = 0x0bd, .length2 = 0x8 } } },
190 { { { .code_and_extra = 0x07d, .length2 = 0x8 } } },
191 { { { .code_and_extra = 0x0fd, .length2 = 0x8 } } },
192 { { { .code_and_extra = 0x013, .length2 = 0x9 } } },
193 { { { .code_and_extra = 0x113, .length2 = 0x9 } } },
194 { { { .code_and_extra = 0x093, .length2 = 0x9 } } },
195 { { { .code_and_extra = 0x193, .length2 = 0x9 } } },
196 { { { .code_and_extra = 0x053, .length2 = 0x9 } } },
197 { { { .code_and_extra = 0x153, .length2 = 0x9 } } },
198 { { { .code_and_extra = 0x0d3, .length2 = 0x9 } } },
199 { { { .code_and_extra = 0x1d3, .length2 = 0x9 } } },
200 { { { .code_and_extra = 0x033, .length2 = 0x9 } } },
201 { { { .code_and_extra = 0x133, .length2 = 0x9 } } },
202 { { { .code_and_extra = 0x0b3, .length2 = 0x9 } } },
203 { { { .code_and_extra = 0x1b3, .length2 = 0x9 } } },
204 { { { .code_and_extra = 0x073, .length2 = 0x9 } } },
205 { { { .code_and_extra = 0x173, .length2 = 0x9 } } },
206 { { { .code_and_extra = 0x0f3, .length2 = 0x9 } } },
207 { { { .code_and_extra = 0x1f3, .length2 = 0x9 } } },
208 { { { .code_and_extra = 0x00b, .length2 = 0x9 } } },
209 { { { .code_and_extra = 0x10b, .length2 = 0x9 } } },
210 { { { .code_and_extra = 0x08b, .length2 = 0x9 } } },
211 { { { .code_and_extra = 0x18b, .length2 = 0x9 } } },
212 { { { .code_and_extra = 0x04b, .length2 = 0x9 } } },
213 { { { .code_and_extra = 0x14b, .length2 = 0x9 } } },
214 { { { .code_and_extra = 0x0cb, .length2 = 0x9 } } },
215 { { { .code_and_extra = 0x1cb, .length2 = 0x9 } } },
216 { { { .code_and_extra = 0x02b, .length2 = 0x9 } } },
217 { { { .code_and_extra = 0x12b, .length2 = 0x9 } } },
218 { { { .code_and_extra = 0x0ab, .length2 = 0x9 } } },
219 { { { .code_and_extra = 0x1ab, .length2 = 0x9 } } },
220 { { { .code_and_extra = 0x06b, .length2 = 0x9 } } },
221 { { { .code_and_extra = 0x16b, .length2 = 0x9 } } },
222 { { { .code_and_extra = 0x0eb, .length2 = 0x9 } } },
223 { { { .code_and_extra = 0x1eb, .length2 = 0x9 } } },
224 { { { .code_and_extra = 0x01b, .length2 = 0x9 } } },
225 { { { .code_and_extra = 0x11b, .length2 = 0x9 } } },
226 { { { .code_and_extra = 0x09b, .length2 = 0x9 } } },
227 { { { .code_and_extra = 0x19b, .length2 = 0x9 } } },
228 { { { .code_and_extra = 0x05b, .length2 = 0x9 } } },
229 { { { .code_and_extra = 0x15b, .length2 = 0x9 } } },
230 { { { .code_and_extra = 0x0db, .length2 = 0x9 } } },
231 { { { .code_and_extra = 0x1db, .length2 = 0x9 } } },
232 { { { .code_and_extra = 0x03b, .length2 = 0x9 } } },
233 { { { .code_and_extra = 0x13b, .length2 = 0x9 } } },
234 { { { .code_and_extra = 0x0bb, .length2 = 0x9 } } },
235 { { { .code_and_extra = 0x1bb, .length2 = 0x9 } } },
236 { { { .code_and_extra = 0x07b, .length2 = 0x9 } } },
237 { { { .code_and_extra = 0x17b, .length2 = 0x9 } } },
238 { { { .code_and_extra = 0x0fb, .length2 = 0x9 } } },
239 { { { .code_and_extra = 0x1fb, .length2 = 0x9 } } },
240 { { { .code_and_extra = 0x007, .length2 = 0x9 } } },
241 { { { .code_and_extra = 0x107, .length2 = 0x9 } } },
242 { { { .code_and_extra = 0x087, .length2 = 0x9 } } },
243 { { { .code_and_extra = 0x187, .length2 = 0x9 } } },
244 { { { .code_and_extra = 0x047, .length2 = 0x9 } } },
245 { { { .code_and_extra = 0x147, .length2 = 0x9 } } },
246 { { { .code_and_extra = 0x0c7, .length2 = 0x9 } } },
247 { { { .code_and_extra = 0x1c7, .length2 = 0x9 } } },
248 { { { .code_and_extra = 0x027, .length2 = 0x9 } } },
249 { { { .code_and_extra = 0x127, .length2 = 0x9 } } },
250 { { { .code_and_extra = 0x0a7, .length2 = 0x9 } } },
251 { { { .code_and_extra = 0x1a7, .length2 = 0x9 } } },
252 { { { .code_and_extra = 0x067, .length2 = 0x9 } } },
253 { { { .code_and_extra = 0x167, .length2 = 0x9 } } },
254 { { { .code_and_extra = 0x0e7, .length2 = 0x9 } } },
255 { { { .code_and_extra = 0x1e7, .length2 = 0x9 } } },
256 { { { .code_and_extra = 0x017, .length2 = 0x9 } } },
257 { { { .code_and_extra = 0x117, .length2 = 0x9 } } },
258 { { { .code_and_extra = 0x097, .length2 = 0x9 } } },
259 { { { .code_and_extra = 0x197, .length2 = 0x9 } } },
260 { { { .code_and_extra = 0x057, .length2 = 0x9 } } },
261 { { { .code_and_extra = 0x157, .length2 = 0x9 } } },
262 { { { .code_and_extra = 0x0d7, .length2 = 0x9 } } },
263 { { { .code_and_extra = 0x1d7, .length2 = 0x9 } } },
264 { { { .code_and_extra = 0x037, .length2 = 0x9 } } },
265 { { { .code_and_extra = 0x137, .length2 = 0x9 } } },
266 { { { .code_and_extra = 0x0b7, .length2 = 0x9 } } },
267 { { { .code_and_extra = 0x1b7, .length2 = 0x9 } } },
268 { { { .code_and_extra = 0x077, .length2 = 0x9 } } },
269 { { { .code_and_extra = 0x177, .length2 = 0x9 } } },
270 { { { .code_and_extra = 0x0f7, .length2 = 0x9 } } },
271 { { { .code_and_extra = 0x1f7, .length2 = 0x9 } } },
272 { { { .code_and_extra = 0x00f, .length2 = 0x9 } } },
273 { { { .code_and_extra = 0x10f, .length2 = 0x9 } } },
274 { { { .code_and_extra = 0x08f, .length2 = 0x9 } } },
275 { { { .code_and_extra = 0x18f, .length2 = 0x9 } } },
276 { { { .code_and_extra = 0x04f, .length2 = 0x9 } } },
277 { { { .code_and_extra = 0x14f, .length2 = 0x9 } } },
278 { { { .code_and_extra = 0x0cf, .length2 = 0x9 } } },
279 { { { .code_and_extra = 0x1cf, .length2 = 0x9 } } },
280 { { { .code_and_extra = 0x02f, .length2 = 0x9 } } },
281 { { { .code_and_extra = 0x12f, .length2 = 0x9 } } },
282 { { { .code_and_extra = 0x0af, .length2 = 0x9 } } },
283 { { { .code_and_extra = 0x1af, .length2 = 0x9 } } },
284 { { { .code_and_extra = 0x06f, .length2 = 0x9 } } },
285 { { { .code_and_extra = 0x16f, .length2 = 0x9 } } },
286 { { { .code_and_extra = 0x0ef, .length2 = 0x9 } } },
287 { { { .code_and_extra = 0x1ef, .length2 = 0x9 } } },
288 { { { .code_and_extra = 0x01f, .length2 = 0x9 } } },
289 { { { .code_and_extra = 0x11f, .length2 = 0x9 } } },
290 { { { .code_and_extra = 0x09f, .length2 = 0x9 } } },
291 { { { .code_and_extra = 0x19f, .length2 = 0x9 } } },
292 { { { .code_and_extra = 0x05f, .length2 = 0x9 } } },
293 { { { .code_and_extra = 0x15f, .length2 = 0x9 } } },
294 { { { .code_and_extra = 0x0df, .length2 = 0x9 } } },
295 { { { .code_and_extra = 0x1df, .length2 = 0x9 } } },
296 { { { .code_and_extra = 0x03f, .length2 = 0x9 } } },
297 { { { .code_and_extra = 0x13f, .length2 = 0x9 } } },
298 { { { .code_and_extra = 0x0bf, .length2 = 0x9 } } },
299 { { { .code_and_extra = 0x1bf, .length2 = 0x9 } } },
300 { { { .code_and_extra = 0x07f, .length2 = 0x9 } } },
301 { { { .code_and_extra = 0x17f, .length2 = 0x9 } } },
302 { { { .code_and_extra = 0x0ff, .length2 = 0x9 } } },
303 { { { .code_and_extra = 0x1ff, .length2 = 0x9 } } },
304 { { { .code_and_extra = 0x000, .length2 = 0x7 } } },
305 { { { .code_and_extra = 0x040, .length2 = 0x7 } } },
306 { { { .code_and_extra = 0x020, .length2 = 0x7 } } },
307 { { { .code_and_extra = 0x060, .length2 = 0x7 } } },
308 { { { .code_and_extra = 0x010, .length2 = 0x7 } } },
309 { { { .code_and_extra = 0x050, .length2 = 0x7 } } },
310 { { { .code_and_extra = 0x030, .length2 = 0x7 } } },
311 { { { .code_and_extra = 0x070, .length2 = 0x7 } } },
312 { { { .code_and_extra = 0x008, .length2 = 0x7 } } },
313 { { { .code_and_extra = 0x048, .length2 = 0x7 } } },
314 { { { .code_and_extra = 0x028, .length2 = 0x7 } } },
315 { { { .code_and_extra = 0x068, .length2 = 0x7 } } },
316 { { { .code_and_extra = 0x018, .length2 = 0x7 } } },
317 { { { .code_and_extra = 0x058, .length2 = 0x7 } } },
318 { { { .code_and_extra = 0x038, .length2 = 0x7 } } },
319 { { { .code_and_extra = 0x078, .length2 = 0x7 } } },
320 { { { .code_and_extra = 0x004, .length2 = 0x7 } } },
321 { { { .code_and_extra = 0x044, .length2 = 0x7 } } },
322 { { { .code_and_extra = 0x024, .length2 = 0x7 } } },
323 { { { .code_and_extra = 0x064, .length2 = 0x7 } } },
324 { { { .code_and_extra = 0x014, .length2 = 0x7 } } },
325 { { { .code_and_extra = 0x054, .length2 = 0x7 } } },
326 { { { .code_and_extra = 0x034, .length2 = 0x7 } } },
327 { { { .code_and_extra = 0x074, .length2 = 0x7 } } },
328 { { { .code_and_extra = 0x003, .length2 = 0x8 } } },
329 { { { .code_and_extra = 0x083, .length2 = 0x8 } } },
330 { { { .code_and_extra = 0x043, .length2 = 0x8 } } },
331 { { { .code_and_extra = 0x0c3, .length2 = 0x8 } } },
332 { { { .code_and_extra = 0x023, .length2 = 0x8 } } },
333 { { { .code_and_extra = 0x0a3, .length2 = 0x8 } } },
334 { { { .code_and_extra = 0x063, .length2 = 0x8 } } },
335 { { { .code_and_extra = 0x0e3, .length2 = 0x8 } } },
336 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
337 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
338 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
339 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
340 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
341 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
342 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
343 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
344 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
345 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
346 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
347 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
348 { { { .code_and_extra = 0x000, .length2 = 0x0 } } },
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 .dist_table = { { { { .code_and_extra = 0x000, .length2 = 0x5 } } },
562 { { { .code_and_extra = 0x010, .length2 = 0x5 } } },
563 { { { .code_and_extra = 0x008, .length2 = 0x5 } } },
564 { { { .code_and_extra = 0x018, .length2 = 0x5 } } },
565 { { { .code_and_extra = 0x10004, .length2 = 0x5 } } },
566 { { { .code_and_extra = 0x10014, .length2 = 0x5 } } },
567 { { { .code_and_extra = 0x2000c, .length2 = 0x5 } } },
568 { { { .code_and_extra = 0x2001c, .length2 = 0x5 } } },
569 { { { .code_and_extra = 0x30002, .length2 = 0x5 } } },
570 { { { .code_and_extra = 0x30012, .length2 = 0x5 } } },
571 { { { .code_and_extra = 0x4000a, .length2 = 0x5 } } },
572 { { { .code_and_extra = 0x4001a, .length2 = 0x5 } } },
573 { { { .code_and_extra = 0x50006, .length2 = 0x5 } } },
574 { { { .code_and_extra = 0x50016, .length2 = 0x5 } } },
575 { { { .code_and_extra = 0x6000e, .length2 = 0x5 } } },
576 { { { .code_and_extra = 0x6001e, .length2 = 0x5 } } },
577 { { { .code_and_extra = 0x70001, .length2 = 0x5 } } },
578 { { { .code_and_extra = 0x70011, .length2 = 0x5 } } },
579 { { { .code_and_extra = 0x80009, .length2 = 0x5 } } },
580 { { { .code_and_extra = 0x80019, .length2 = 0x5 } } },
581 { { { .code_and_extra = 0x90005, .length2 = 0x5 } } },
582 { { { .code_and_extra = 0x90015, .length2 = 0x5 } } },
583 { { { .code_and_extra = 0xa000d, .length2 = 0x5 } } },
584 { { { .code_and_extra = 0xa001d, .length2 = 0x5 } } },
585 { { { .code_and_extra = 0xb0003, .length2 = 0x5 } } },
586 { { { .code_and_extra = 0xb0013, .length2 = 0x5 } } },
587 { { { .code_and_extra = 0xc000b, .length2 = 0x5 } } },
588 { { { .code_and_extra = 0xc001b, .length2 = 0x5 } } },
589 { { { .code_and_extra = 0xd0007, .length2 = 0x5 } } },
590 { { { .code_and_extra = 0xd0017, .length2 = 0x5 } } },
591 { { { .code_and_extra = 0x000, .length2 = 0x0 } } } }
592 };
593
594 extern uint32_t
595 build_huff_tree(struct heap_tree *heap, uint64_t heap_size, uint64_t node_ptr);
596 extern void
597 build_heap(uint64_t *heap, uint64_t heap_size);
598
599 static uint32_t
600 convert_dist_to_dist_sym(uint32_t dist);
601 static uint32_t
602 convert_length_to_len_sym(uint32_t length);
603
604 static const uint8_t bitrev8[0x100] = {
605 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70,
606 0xF0, 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8,
607 0x78, 0xF8, 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34,
608 0xB4, 0x74, 0xF4, 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC,
609 0x3C, 0xBC, 0x7C, 0xFC, 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52,
610 0xD2, 0x32, 0xB2, 0x72, 0xF2, 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A,
611 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16,
612 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
613 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61,
614 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9,
615 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, 0x05, 0x85, 0x45, 0xC5, 0x25,
616 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, 0x0D, 0x8D, 0x4D, 0xCD,
617 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, 0x03, 0x83, 0x43,
618 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, 0x0B, 0x8B,
619 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, 0x07,
620 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
621 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F,
622 0xFF
623 };
624
625 // bit reverse low order LENGTH bits in code, and return result in low order bits
626 static inline uint16_t
bit_reverse(uint16_t code,uint32_t length)627 bit_reverse(uint16_t code, uint32_t length)
628 {
629 code = (bitrev8[code & 0x00FF] << 8) | (bitrev8[code >> 8]);
630 return (code >> (16 - length));
631 }
632
633 void
isal_update_histogram_base(uint8_t * start_stream,int length,struct isal_huff_histogram * histogram)634 isal_update_histogram_base(uint8_t *start_stream, int length, struct isal_huff_histogram *histogram)
635 {
636 uint32_t literal = 0, hash;
637 uint16_t seen, *last_seen = histogram->hash_table;
638 uint8_t *current, *end_stream, *next_hash, *end;
639 uint32_t match_length;
640 uint32_t dist;
641 uint64_t *lit_len_histogram = histogram->lit_len_histogram;
642 uint64_t *dist_histogram = histogram->dist_histogram;
643
644 if (length <= 0)
645 return;
646
647 end_stream = start_stream + length;
648 memset(last_seen, 0, sizeof(histogram->hash_table)); /* Initialize last_seen to be 0. */
649 for (current = start_stream; current < end_stream - 3; current++) {
650 literal = load_le_u32(current);
651 hash = compute_hash(literal) & LVL0_HASH_MASK;
652 seen = last_seen[hash];
653 last_seen[hash] = (current - start_stream) & 0xFFFF;
654 dist = (current - start_stream - seen) & 0xFFFF;
655 if (dist - 1 < D - 1) {
656 assert(start_stream <= current - dist);
657 match_length = compare258(current - dist, current, end_stream - current);
658 if (match_length >= SHORTEST_MATCH) {
659 next_hash = current;
660 #ifdef ISAL_LIMIT_HASH_UPDATE
661 end = next_hash + 3;
662 #else
663 end = next_hash + match_length;
664 #endif
665 if (end > end_stream - 3)
666 end = end_stream - 3;
667 next_hash++;
668 for (; next_hash < end; next_hash++) {
669 literal = load_le_u32(next_hash);
670 hash = compute_hash(literal) & LVL0_HASH_MASK;
671 last_seen[hash] = (next_hash - start_stream) & 0xFFFF;
672 }
673
674 dist_histogram[convert_dist_to_dist_sym(dist)] += 1;
675 lit_len_histogram[convert_length_to_len_sym(match_length)] += 1;
676 current += match_length - 1;
677 continue;
678 }
679 }
680 lit_len_histogram[literal & 0xFF] += 1;
681 }
682
683 for (; current < end_stream; current++)
684 lit_len_histogram[*current] += 1;
685
686 lit_len_histogram[256] += 1;
687 return;
688 }
689
690 /**
691 * @brief Returns the deflate symbol value for a look back distance.
692 */
693 static uint32_t
convert_dist_to_dist_sym(uint32_t dist)694 convert_dist_to_dist_sym(uint32_t dist)
695 {
696 assert(dist <= 32768 && dist > 0);
697 if (dist <= 32768) {
698 uint32_t msb = dist > 4 ? bsr(dist - 1) - 2 : 0;
699 return (msb * 2) + ((dist - 1) >> msb);
700 } else {
701 return ~0;
702 }
703 }
704
705 /**
706 * @brief Returns the deflate symbol value for a repeat length.
707 */
708 static uint32_t
convert_length_to_len_sym(uint32_t length)709 convert_length_to_len_sym(uint32_t length)
710 {
711 assert(length > 2 && length < 259);
712
713 /* Based on tables on page 11 in RFC 1951 */
714 if (length < 11)
715 return 257 + length - 3;
716 else if (length < 19)
717 return 261 + (length - 3) / 2;
718 else if (length < 35)
719 return 265 + (length - 3) / 4;
720 else if (length < 67)
721 return 269 + (length - 3) / 8;
722 else if (length < 131)
723 return 273 + (length - 3) / 16;
724 else if (length < 258)
725 return 277 + (length - 3) / 32;
726 else
727 return 285;
728 }
729
730 // Upon return, codes[] contains the code lengths,
731 // and bl_count is the count of the lengths
732
733 /* Init heap with the histogram, and return the histogram size */
734 static inline uint32_t
init_heap32(struct heap_tree * heap_space,uint32_t * histogram,uint32_t hist_size)735 init_heap32(struct heap_tree *heap_space, uint32_t *histogram, uint32_t hist_size)
736 {
737 uint32_t heap_size, i;
738
739 memset(heap_space, 0, sizeof(struct heap_tree));
740
741 heap_size = 0;
742 for (i = 0; i < hist_size; i++) {
743 if (histogram[i] != 0)
744 heap_space->heap[++heap_size] =
745 (((uint64_t) histogram[i]) << FREQ_SHIFT) | i;
746 }
747
748 // make sure heap has at least two elements in it
749 if (heap_size < 2) {
750 if (heap_size == 0) {
751 heap_space->heap[1] = 1ULL << FREQ_SHIFT;
752 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
753 heap_size = 2;
754 } else {
755 // heap size == 1
756 if (histogram[0] == 0)
757 heap_space->heap[2] = 1ULL << FREQ_SHIFT;
758 else
759 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
760 heap_size = 2;
761 }
762 }
763
764 build_heap(heap_space->heap, heap_size);
765
766 return heap_size;
767 }
768
769 static inline uint32_t
init_heap64(struct heap_tree * heap_space,uint64_t * histogram,uint64_t hist_size)770 init_heap64(struct heap_tree *heap_space, uint64_t *histogram, uint64_t hist_size)
771 {
772 uint32_t heap_size, i;
773
774 memset(heap_space, 0, sizeof(struct heap_tree));
775
776 heap_size = 0;
777 for (i = 0; i < hist_size; i++) {
778 if (histogram[i] != 0)
779 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
780 }
781
782 // make sure heap has at least two elements in it
783 if (heap_size < 2) {
784 if (heap_size == 0) {
785 heap_space->heap[1] = 1ULL << FREQ_SHIFT;
786 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
787 heap_size = 2;
788 } else {
789 // heap size == 1
790 if (histogram[0] == 0)
791 heap_space->heap[2] = 1ULL << FREQ_SHIFT;
792 else
793 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
794 heap_size = 2;
795 }
796 }
797
798 build_heap(heap_space->heap, heap_size);
799
800 return heap_size;
801 }
802
803 static inline uint32_t
init_heap64_semi_complete(struct heap_tree * heap_space,uint64_t * histogram,uint64_t hist_size,uint64_t complete_start)804 init_heap64_semi_complete(struct heap_tree *heap_space, uint64_t *histogram, uint64_t hist_size,
805 uint64_t complete_start)
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 < complete_start; i++) {
813 if (histogram[i] != 0)
814 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
815 }
816
817 for (; i < hist_size; i++)
818 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
819
820 // make sure heap has at least two elements in it
821 if (heap_size < 2) {
822 if (heap_size == 0) {
823 heap_space->heap[1] = 1ULL << FREQ_SHIFT;
824 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
825 heap_size = 2;
826 } else {
827 // heap size == 1
828 if (histogram[0] == 0)
829 heap_space->heap[2] = 1ULL << FREQ_SHIFT;
830 else
831 heap_space->heap[2] = (1ULL << FREQ_SHIFT) | 1;
832 heap_size = 2;
833 }
834 }
835
836 build_heap(heap_space->heap, heap_size);
837
838 return heap_size;
839 }
840
841 static inline uint32_t
init_heap64_complete(struct heap_tree * heap_space,uint64_t * histogram,uint64_t hist_size)842 init_heap64_complete(struct heap_tree *heap_space, uint64_t *histogram, uint64_t hist_size)
843 {
844 uint32_t heap_size, i;
845
846 memset(heap_space, 0, sizeof(struct heap_tree));
847
848 heap_size = 0;
849 for (i = 0; i < hist_size; i++)
850 heap_space->heap[++heap_size] = ((histogram[i]) << FREQ_SHIFT) | i;
851
852 build_heap(heap_space->heap, heap_size);
853
854 return heap_size;
855 }
856
857 static inline uint32_t
fix_code_lens(struct heap_tree * heap_space,uint32_t root_node,uint32_t * bl_count,uint32_t max_code_len)858 fix_code_lens(struct heap_tree *heap_space, uint32_t root_node, uint32_t *bl_count,
859 uint32_t max_code_len)
860 {
861 struct tree_node *tree = heap_space->tree;
862 uint64_t *code_len_count = heap_space->code_len_count;
863 uint32_t i, j, k, child, depth, code_len;
864
865 // compute code lengths and code length counts
866 code_len = 0;
867 j = root_node;
868 for (i = root_node; i <= HEAP_TREE_NODE_START; i++) {
869 child = tree[i].child;
870 if (child > MAX_HISTHEAP_SIZE) {
871 depth = 1 + tree[i].depth;
872
873 tree[child].depth = depth;
874 tree[child - 1].depth = depth;
875 } else {
876 tree[j++] = tree[i];
877 depth = tree[i].depth;
878 while (code_len < depth) {
879 code_len++;
880 code_len_count[code_len] = 0;
881 }
882 code_len_count[depth]++;
883 }
884 }
885
886 if (code_len > max_code_len) {
887 while (code_len > max_code_len) {
888 assert(code_len_count[code_len] > 1);
889 for (i = max_code_len - 1; i != 0; i--)
890 if (code_len_count[i] != 0)
891 break;
892 assert(i != 0);
893 code_len_count[i]--;
894 code_len_count[i + 1] += 2;
895 code_len_count[code_len - 1]++;
896 code_len_count[code_len] -= 2;
897 if (code_len_count[code_len] == 0)
898 code_len--;
899 }
900
901 bl_count[0] = 0;
902 for (i = 1; i <= code_len; i++)
903 bl_count[i] = code_len_count[i];
904 for (; i <= max_code_len; i++)
905 bl_count[i] = 0;
906
907 for (k = 1; code_len_count[k] == 0; k++)
908 ;
909 for (i = root_node; i < j; i++) {
910 tree[i].depth = k;
911 code_len_count[k]--;
912 for (; code_len_count[k] == 0; k++)
913 ;
914 }
915 } else {
916 bl_count[0] = 0;
917 for (i = 1; i <= code_len; i++)
918 bl_count[i] = code_len_count[i];
919 for (; i <= max_code_len; i++)
920 bl_count[i] = 0;
921 }
922
923 return j;
924 }
925
926 static inline void
gen_huff_code_lens(struct heap_tree * heap_space,uint32_t heap_size,uint32_t * bl_count,struct huff_code * codes,uint32_t codes_count,uint32_t max_code_len)927 gen_huff_code_lens(struct heap_tree *heap_space, uint32_t heap_size, uint32_t *bl_count,
928 struct huff_code *codes, uint32_t codes_count, uint32_t max_code_len)
929 {
930 struct tree_node *tree = heap_space->tree;
931 uint32_t root_node = HEAP_TREE_NODE_START, node_ptr;
932 uint32_t end_node;
933
934 root_node = build_huff_tree(heap_space, heap_size, root_node);
935
936 end_node = fix_code_lens(heap_space, root_node, bl_count, max_code_len);
937
938 memset(codes, 0, codes_count * sizeof(*codes));
939 for (node_ptr = root_node; node_ptr < end_node; node_ptr++)
940 codes[tree[node_ptr].child].length = tree[node_ptr].depth;
941 }
942
943 /**
944 * @brief Determines the code each element of a deflate compliant huffman tree and stores
945 * it in a lookup table
946 * @requires table has been initialized to already contain the code length for each element.
947 * @param table: A lookup table used to store the codes.
948 * @param table_length: The length of table.
949 * @param count: a histogram representing the number of occurrences of codes of a given length
950 */
951 static inline uint32_t
set_huff_codes(struct huff_code * huff_code_table,int table_length,uint32_t * count)952 set_huff_codes(struct huff_code *huff_code_table, int table_length, uint32_t *count)
953 {
954 /* Uses the algorithm mentioned in the deflate standard, Rfc 1951. */
955 int i;
956 uint16_t code = 0;
957 uint16_t next_code[MAX_HUFF_TREE_DEPTH + 1];
958 uint32_t max_code = 0;
959
960 next_code[0] = code;
961
962 for (i = 1; i < MAX_HUFF_TREE_DEPTH + 1; i++)
963 next_code[i] = (next_code[i - 1] + count[i - 1]) << 1;
964
965 for (i = 0; i < table_length; i++) {
966 if (huff_code_table[i].length != 0) {
967 huff_code_table[i].code = bit_reverse(next_code[huff_code_table[i].length],
968 huff_code_table[i].length);
969 next_code[huff_code_table[i].length] += 1;
970 max_code = i;
971 }
972 }
973
974 return max_code;
975 }
976
977 // on input, codes contain the code lengths
978 // on output, code contains:
979 // 23:16 code length
980 // 15:0 code value in low order bits
981 // returns max code value
982 static inline uint32_t
set_dist_huff_codes(struct huff_code * codes,uint32_t * bl_count)983 set_dist_huff_codes(struct huff_code *codes, uint32_t *bl_count)
984 {
985 uint32_t code, code_len, bits, i;
986 uint32_t next_code[MAX_DEFLATE_CODE_LEN + 1];
987 uint32_t max_code = 0;
988 const uint32_t num_codes = DIST_LEN;
989
990 code = bl_count[0] = 0;
991 for (bits = 1; bits <= MAX_HUFF_TREE_DEPTH; bits++) {
992 code = (code + bl_count[bits - 1]) << 1;
993 next_code[bits] = code;
994 }
995 for (i = 0; i < num_codes; i++) {
996 code_len = codes[i].length;
997 if (code_len != 0) {
998 codes[i].code = bit_reverse(next_code[code_len], code_len);
999 codes[i].extra_bit_count = dist_code_extra_bits[i];
1000 next_code[code_len] += 1;
1001 max_code = i;
1002 }
1003 }
1004 return max_code;
1005 }
1006
1007 /**
1008 * @brief Creates the header for run length encoded huffman trees.
1009 * @param header: the output header.
1010 * @param lookup_table: a huffman lookup table.
1011 * @param huffman_rep: a run length encoded huffman tree.
1012 * @extra_bits: extra bits associated with the corresponding spot in huffman_rep
1013 * @param huffman_rep_length: the length of huffman_rep.
1014 * @param end_of_block: Value determining whether end of block header is produced or not;
1015 * 0 corresponds to not end of block and all other inputs correspond to end of block.
1016 * @param hclen: Length of huffman code for huffman codes minus 4.
1017 * @param hlit: Length of literal/length table minus 257.
1018 * @param hdist: Length of distance table minus 1.
1019 */
1020 static int
create_huffman_header(struct BitBuf2 * header_bitbuf,struct huff_code * lookup_table,struct rl_code * huffman_rep,uint16_t huffman_rep_length,uint32_t end_of_block,uint32_t hclen,uint32_t hlit,uint32_t hdist)1021 create_huffman_header(struct BitBuf2 *header_bitbuf, struct huff_code *lookup_table,
1022 struct rl_code *huffman_rep, uint16_t huffman_rep_length,
1023 uint32_t end_of_block, uint32_t hclen, uint32_t hlit, uint32_t hdist)
1024 {
1025 /* hlit, hdist, hclen are as defined in the deflate standard, head is the
1026 * first three deflate header bits.*/
1027 int i;
1028 uint64_t bit_count;
1029 uint64_t data;
1030 struct huff_code huffman_value;
1031 const uint32_t extra_bits[3] = { 2, 3, 7 };
1032
1033 bit_count = buffer_bits_used(header_bitbuf);
1034
1035 data = (end_of_block ? 5 : 4) | (hlit << 3) | (hdist << 8) | (hclen << 13);
1036 data |= ((lookup_table[code_length_code_order[0]].length) << DYN_HDR_START_LEN);
1037 write_bits(header_bitbuf, data, DYN_HDR_START_LEN + 3);
1038 data = 0;
1039 for (i = hclen + 3; i >= 1; i--)
1040 data = (data << 3) | lookup_table[code_length_code_order[i]].length;
1041
1042 write_bits(header_bitbuf, data, (hclen + 3) * 3);
1043
1044 for (i = 0; i < huffman_rep_length; i++) {
1045 huffman_value = lookup_table[huffman_rep[i].code];
1046
1047 write_bits(header_bitbuf, (uint64_t) huffman_value.code,
1048 (uint32_t) huffman_value.length);
1049
1050 if (huffman_rep[i].code > 15) {
1051 write_bits(header_bitbuf, (uint64_t) huffman_rep[i].extra_bits,
1052 (uint32_t) extra_bits[huffman_rep[i].code - 16]);
1053 }
1054 }
1055 bit_count = buffer_bits_used(header_bitbuf) - bit_count;
1056
1057 return bit_count;
1058 }
1059
1060 /**
1061 * @brief Creates the dynamic huffman deflate header.
1062 * @returns Returns the length of header in bits.
1063 * @requires This function requires header is large enough to store the whole header.
1064 * @param header: The output header.
1065 * @param lit_huff_table: A literal/length code huffman lookup table.\
1066 * @param dist_huff_table: A distance huffman code lookup table.
1067 * @param end_of_block: Value determining whether end of block header is produced or not;
1068 * 0 corresponds to not end of block and all other inputs correspond to end of block.
1069 */
1070 static inline int
create_header(struct BitBuf2 * header_bitbuf,struct rl_code * huffman_rep,uint32_t length,uint64_t * histogram,uint32_t hlit,uint32_t hdist,uint32_t end_of_block)1071 create_header(struct BitBuf2 *header_bitbuf, struct rl_code *huffman_rep, uint32_t length,
1072 uint64_t *histogram, uint32_t hlit, uint32_t hdist, uint32_t end_of_block)
1073 {
1074 int i;
1075
1076 uint32_t heap_size;
1077 struct heap_tree heap_space;
1078 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
1079 struct huff_code lookup_table[HUFF_LEN];
1080
1081 /* hlit, hdist, and hclen are defined in RFC 1951 page 13 */
1082 uint32_t hclen;
1083 uint64_t bit_count;
1084
1085 /* Create a huffman tree to encode run length encoded representation. */
1086 heap_size = init_heap64(&heap_space, histogram, HUFF_LEN);
1087 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1088 (struct huff_code *) lookup_table, HUFF_LEN, 7);
1089 set_huff_codes(lookup_table, HUFF_LEN, code_len_count);
1090
1091 /* Calculate hclen */
1092 for (i = CODE_LEN_CODES - 1; i > 3; i--) /* i must be at least 4 */
1093 if (lookup_table[code_length_code_order[i]].length != 0)
1094 break;
1095
1096 hclen = i - 3;
1097
1098 /* Generate actual header. */
1099 bit_count = create_huffman_header(header_bitbuf, lookup_table, huffman_rep, length,
1100 end_of_block, hclen, hlit, hdist);
1101
1102 return bit_count;
1103 }
1104
1105 static inline struct rl_code *
write_rl(struct rl_code * pout,uint16_t last_len,uint32_t run_len,uint64_t * counts)1106 write_rl(struct rl_code *pout, uint16_t last_len, uint32_t run_len, 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,struct rl_code * out)1190 rl_encode(uint16_t *codes, uint32_t num_codes, uint64_t *counts, 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 /**
1215 * @brief Creates a two table representation of huffman codes.
1216 * @param code_table: output table containing the code
1217 * @param code_size_table: output table containing the code length
1218 * @param length: the length of hufftable
1219 * @param hufftable: a huffman lookup table
1220 */
1221 static void
create_code_tables(uint16_t * code_table,uint8_t * code_length_table,uint32_t length,struct huff_code * hufftable)1222 create_code_tables(uint16_t *code_table, uint8_t *code_length_table, uint32_t length,
1223 struct huff_code *hufftable)
1224 {
1225 int i;
1226 for (i = 0; i < length; i++) {
1227 code_table[i] = hufftable[i].code;
1228 code_length_table[i] = hufftable[i].length;
1229 }
1230 }
1231
1232 /**
1233 * @brief Creates a packed representation of length huffman codes.
1234 * @details In packed_table, bits 32:8 contain the extra bits appended to the huffman
1235 * code and bits 8:0 contain the code length.
1236 * @param packed_table: the output table
1237 * @param length: the length of lit_len_hufftable
1238 * @param lit_len_hufftable: a literal/length huffman lookup table
1239 */
1240 static void
create_packed_len_table(uint32_t * packed_table,struct huff_code * lit_len_hufftable)1241 create_packed_len_table(uint32_t *packed_table, struct huff_code *lit_len_hufftable)
1242 {
1243 int i, count = 0;
1244 uint16_t extra_bits;
1245 uint16_t extra_bits_count = 0;
1246
1247 /* Gain extra bits is the next place where the number of extra bits in
1248 * length codes increases. */
1249 uint16_t gain_extra_bits = LEN_EXTRA_BITS_START;
1250
1251 for (i = 257; i < LIT_LEN - 1; i++) {
1252 for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) {
1253 if (count > 254)
1254 break;
1255 packed_table[count++] =
1256 (extra_bits << (lit_len_hufftable[i].length + LENGTH_BITS)) |
1257 (lit_len_hufftable[i].code << LENGTH_BITS) |
1258 (lit_len_hufftable[i].length + extra_bits_count);
1259 }
1260
1261 if (i == gain_extra_bits) {
1262 gain_extra_bits += LEN_EXTRA_BITS_INTERVAL;
1263 extra_bits_count += 1;
1264 }
1265 }
1266
1267 packed_table[count] = (lit_len_hufftable[LIT_LEN - 1].code << LENGTH_BITS) |
1268 (lit_len_hufftable[LIT_LEN - 1].length);
1269 }
1270
1271 /**
1272 * @brief Creates a packed representation of distance huffman codes.
1273 * @details In packed_table, bits 32:8 contain the extra bits appended to the huffman
1274 * code and bits 8:0 contain the code length.
1275 * @param packed_table: the output table
1276 * @param length: the length of lit_len_hufftable
1277 * @param dist_hufftable: a distance huffman lookup table
1278 */
1279 static void
create_packed_dist_table(uint32_t * packed_table,uint32_t length,struct huff_code * dist_hufftable)1280 create_packed_dist_table(uint32_t *packed_table, uint32_t length, struct huff_code *dist_hufftable)
1281 {
1282 int i, count = 0;
1283 uint16_t extra_bits;
1284 uint16_t extra_bits_count = 0;
1285
1286 /* Gain extra bits is the next place where the number of extra bits in
1287 * distance codes increases. */
1288 uint16_t gain_extra_bits = DIST_EXTRA_BITS_START;
1289
1290 for (i = 0; i < DIST_LEN; i++) {
1291 for (extra_bits = 0; extra_bits < (1 << extra_bits_count); extra_bits++) {
1292 if (count >= length)
1293 return;
1294
1295 packed_table[count++] =
1296 (extra_bits << (dist_hufftable[i].length + LENGTH_BITS)) |
1297 (dist_hufftable[i].code << LENGTH_BITS) |
1298 (dist_hufftable[i].length + extra_bits_count);
1299 }
1300
1301 if (i == gain_extra_bits) {
1302 gain_extra_bits += DIST_EXTRA_BITS_INTERVAL;
1303 extra_bits_count += 1;
1304 }
1305 }
1306 }
1307
1308 /**
1309 * @brief Checks to see if the hufftable is usable by igzip
1310 *
1311 * @param lit_len_hufftable: literal/length huffman code
1312 * @param dist_hufftable: distance huffman code
1313 * @returns Returns 0 if the table is usable
1314 */
1315 static int
are_hufftables_useable(struct huff_code * lit_len_hufftable,struct huff_code * dist_hufftable)1316 are_hufftables_useable(struct huff_code *lit_len_hufftable, struct huff_code *dist_hufftable)
1317 {
1318 int max_lit_code_len = 0, max_len_code_len = 0, max_dist_code_len = 0;
1319 int dist_extra_bits = 0, len_extra_bits = 0;
1320 int gain_dist_extra_bits = DIST_EXTRA_BITS_START;
1321 int gain_len_extra_bits = LEN_EXTRA_BITS_START;
1322 int max_code_len;
1323 int i;
1324
1325 for (i = 0; i < LIT_LEN; i++)
1326 if (lit_len_hufftable[i].length > max_lit_code_len)
1327 max_lit_code_len = lit_len_hufftable[i].length;
1328
1329 for (i = 257; i < LIT_LEN - 1; i++) {
1330 if (lit_len_hufftable[i].length + len_extra_bits > max_len_code_len)
1331 max_len_code_len = lit_len_hufftable[i].length + len_extra_bits;
1332
1333 if (i == gain_len_extra_bits) {
1334 gain_len_extra_bits += LEN_EXTRA_BITS_INTERVAL;
1335 len_extra_bits += 1;
1336 }
1337 }
1338
1339 for (i = 0; i < DIST_LEN; i++) {
1340 if (dist_hufftable[i].length + dist_extra_bits > max_dist_code_len)
1341 max_dist_code_len = dist_hufftable[i].length + dist_extra_bits;
1342
1343 if (i == gain_dist_extra_bits) {
1344 gain_dist_extra_bits += DIST_EXTRA_BITS_INTERVAL;
1345 dist_extra_bits += 1;
1346 }
1347 }
1348
1349 max_code_len = max_lit_code_len + max_len_code_len + max_dist_code_len;
1350
1351 /* Some versions of igzip can write up to one literal, one length and one
1352 * distance code at the same time. This checks to make sure that is
1353 * always writeable in bitbuf*/
1354 return (max_code_len > MAX_BITBUF_BIT_WRITE);
1355 }
1356
1357 int
isal_create_hufftables(struct isal_hufftables * hufftables,struct isal_huff_histogram * histogram)1358 isal_create_hufftables(struct isal_hufftables *hufftables, struct isal_huff_histogram *histogram)
1359 {
1360 struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN];
1361 uint64_t bit_count;
1362 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE);
1363 struct heap_tree heap_space;
1364 uint32_t heap_size;
1365 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
1366 struct BitBuf2 header_bitbuf;
1367 uint32_t max_lit_len_sym;
1368 uint32_t max_dist_sym;
1369 uint32_t hlit, hdist, i;
1370 uint16_t combined_table[LIT_LEN + DIST_LEN];
1371 uint64_t count_histogram[HUFF_LEN];
1372 struct rl_code rl_huff[LIT_LEN + DIST_LEN];
1373 uint32_t rl_huff_len;
1374
1375 uint32_t *dist_table = hufftables->dist_table;
1376 uint32_t *len_table = hufftables->len_table;
1377 uint16_t *lit_table = hufftables->lit_table;
1378 uint16_t *dcodes = hufftables->dcodes;
1379 uint8_t *lit_table_sizes = hufftables->lit_table_sizes;
1380 uint8_t *dcodes_sizes = hufftables->dcodes_sizes;
1381 uint64_t *lit_len_histogram = histogram->lit_len_histogram;
1382 uint64_t *dist_histogram = histogram->dist_histogram;
1383
1384 memset(hufftables, 0, sizeof(struct isal_hufftables));
1385
1386 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN);
1387 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1388 (struct huff_code *) lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN);
1389 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1390
1391 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
1392 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1393 (struct huff_code *) dist_huff_table, max_dist, MAX_DEFLATE_CODE_LEN);
1394 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
1395
1396 if (are_hufftables_useable(lit_huff_table, dist_huff_table)) {
1397 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN);
1398 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1399 (struct huff_code *) lit_huff_table, LIT_LEN,
1400 MAX_SAFE_LIT_CODE_LEN);
1401 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1402
1403 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
1404 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1405 (struct huff_code *) dist_huff_table, max_dist,
1406 MAX_SAFE_DIST_CODE_LEN);
1407 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
1408 }
1409
1410 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET,
1411 dist_huff_table + DCODE_OFFSET);
1412
1413 create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table);
1414
1415 create_packed_len_table(len_table, lit_huff_table);
1416 create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table);
1417
1418 set_buf(&header_bitbuf, hufftables->deflate_hdr, sizeof(hufftables->deflate_hdr));
1419 init(&header_bitbuf);
1420
1421 hlit = max_lit_len_sym - 256;
1422 hdist = max_dist_sym;
1423
1424 /* Run length encode the length and distance huffman codes */
1425 memset(count_histogram, 0, sizeof(count_histogram));
1426 for (i = 0; i < 257 + hlit; i++)
1427 combined_table[i] = lit_huff_table[i].length;
1428 for (i = 0; i < 1 + hdist; i++)
1429 combined_table[i + hlit + 257] = dist_huff_table[i].length;
1430 rl_huff_len = rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff);
1431
1432 /* Create header */
1433 bit_count = create_header(&header_bitbuf, rl_huff, rl_huff_len, count_histogram, hlit,
1434 hdist, LAST_BLOCK);
1435 flush(&header_bitbuf);
1436
1437 hufftables->deflate_hdr_count = bit_count / 8;
1438 hufftables->deflate_hdr_extra_bits = bit_count % 8;
1439
1440 return 0;
1441 }
1442
1443 int
isal_create_hufftables_subset(struct isal_hufftables * hufftables,struct isal_huff_histogram * histogram)1444 isal_create_hufftables_subset(struct isal_hufftables *hufftables,
1445 struct isal_huff_histogram *histogram)
1446 {
1447 struct huff_code lit_huff_table[LIT_LEN], dist_huff_table[DIST_LEN];
1448 uint64_t bit_count;
1449 int max_dist = convert_dist_to_dist_sym(IGZIP_HIST_SIZE);
1450 struct heap_tree heap_space;
1451 uint32_t heap_size;
1452 uint32_t code_len_count[MAX_HUFF_TREE_DEPTH + 1];
1453 struct BitBuf2 header_bitbuf;
1454 uint32_t max_lit_len_sym;
1455 uint32_t max_dist_sym;
1456 uint32_t hlit, hdist, i;
1457 uint16_t combined_table[LIT_LEN + DIST_LEN];
1458 uint64_t count_histogram[HUFF_LEN];
1459 struct rl_code rl_huff[LIT_LEN + DIST_LEN];
1460 uint32_t rl_huff_len;
1461
1462 uint32_t *dist_table = hufftables->dist_table;
1463 uint32_t *len_table = hufftables->len_table;
1464 uint16_t *lit_table = hufftables->lit_table;
1465 uint16_t *dcodes = hufftables->dcodes;
1466 uint8_t *lit_table_sizes = hufftables->lit_table_sizes;
1467 uint8_t *dcodes_sizes = hufftables->dcodes_sizes;
1468 uint64_t *lit_len_histogram = histogram->lit_len_histogram;
1469 uint64_t *dist_histogram = histogram->dist_histogram;
1470
1471 memset(hufftables, 0, sizeof(struct isal_hufftables));
1472
1473 heap_size = init_heap64_semi_complete(&heap_space, lit_len_histogram, LIT_LEN,
1474 ISAL_DEF_LIT_SYMBOLS);
1475 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1476 (struct huff_code *) lit_huff_table, LIT_LEN, MAX_DEFLATE_CODE_LEN);
1477 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1478
1479 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
1480 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1481 (struct huff_code *) dist_huff_table, max_dist, MAX_DEFLATE_CODE_LEN);
1482 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
1483
1484 if (are_hufftables_useable(lit_huff_table, dist_huff_table)) {
1485 heap_size = init_heap64_complete(&heap_space, lit_len_histogram, LIT_LEN);
1486 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1487 (struct huff_code *) lit_huff_table, LIT_LEN,
1488 MAX_SAFE_LIT_CODE_LEN);
1489 max_lit_len_sym = set_huff_codes(lit_huff_table, LIT_LEN, code_len_count);
1490
1491 heap_size = init_heap64_complete(&heap_space, dist_histogram, DIST_LEN);
1492 gen_huff_code_lens(&heap_space, heap_size, code_len_count,
1493 (struct huff_code *) dist_huff_table, max_dist,
1494 MAX_SAFE_DIST_CODE_LEN);
1495 max_dist_sym = set_huff_codes(dist_huff_table, DIST_LEN, code_len_count);
1496 }
1497
1498 create_code_tables(dcodes, dcodes_sizes, DIST_LEN - DCODE_OFFSET,
1499 dist_huff_table + DCODE_OFFSET);
1500
1501 create_code_tables(lit_table, lit_table_sizes, IGZIP_LIT_TABLE_SIZE, lit_huff_table);
1502
1503 create_packed_len_table(len_table, lit_huff_table);
1504 create_packed_dist_table(dist_table, IGZIP_DIST_TABLE_SIZE, dist_huff_table);
1505
1506 set_buf(&header_bitbuf, hufftables->deflate_hdr, sizeof(hufftables->deflate_hdr));
1507 init(&header_bitbuf);
1508
1509 hlit = max_lit_len_sym - 256;
1510 hdist = max_dist_sym;
1511
1512 /* Run length encode the length and distance huffman codes */
1513 memset(count_histogram, 0, sizeof(count_histogram));
1514 for (i = 0; i < 257 + hlit; i++)
1515 combined_table[i] = lit_huff_table[i].length;
1516 for (i = 0; i < 1 + hdist; i++)
1517 combined_table[i + hlit + 257] = dist_huff_table[i].length;
1518 rl_huff_len = rl_encode(combined_table, hlit + 257 + hdist + 1, count_histogram, rl_huff);
1519
1520 /* Create header */
1521 bit_count = create_header(&header_bitbuf, rl_huff, rl_huff_len, count_histogram, hlit,
1522 hdist, LAST_BLOCK);
1523 flush(&header_bitbuf);
1524
1525 hufftables->deflate_hdr_count = bit_count / 8;
1526 hufftables->deflate_hdr_extra_bits = bit_count % 8;
1527
1528 return 0;
1529 }
1530
1531 static void
expand_hufftables_icf(struct hufftables_icf * hufftables)1532 expand_hufftables_icf(struct hufftables_icf *hufftables)
1533 {
1534 uint32_t i, eb, j, k, len, code;
1535 struct huff_code orig[21], *p_code;
1536 struct huff_code *lit_len_codes = hufftables->lit_len_table;
1537 struct huff_code *dist_codes = hufftables->dist_table;
1538
1539 for (i = 0; i < 21; i++)
1540 orig[i] = lit_len_codes[i + 265];
1541
1542 p_code = &lit_len_codes[265];
1543
1544 i = 0;
1545 for (eb = 1; eb < 6; eb++) {
1546 for (k = 0; k < 4; k++) {
1547 len = orig[i].length;
1548 code = orig[i++].code;
1549 for (j = 0; j < (1u << eb); j++) {
1550 p_code->code_and_extra = code | (j << len);
1551 p_code->length = len + eb;
1552 p_code++;
1553 }
1554 } // end for k
1555 } // end for eb
1556 // fix up last record
1557 p_code[-1] = orig[i];
1558
1559 dist_codes[DIST_LEN].code_and_extra = 0;
1560 dist_codes[DIST_LEN].length = 0;
1561 }
1562
1563 uint64_t
create_hufftables_icf(struct BitBuf2 * bb,struct hufftables_icf * hufftables,struct isal_mod_hist * hist,uint32_t end_of_block)1564 create_hufftables_icf(struct BitBuf2 *bb, struct hufftables_icf *hufftables,
1565 struct isal_mod_hist *hist, uint32_t end_of_block)
1566 {
1567 uint32_t bl_count[MAX_DEFLATE_CODE_LEN + 1];
1568 uint32_t max_ll_code, max_d_code;
1569 struct heap_tree heap_space;
1570 uint32_t heap_size;
1571 struct rl_code cl_tokens[LIT_LEN + DIST_LEN];
1572 uint32_t num_cl_tokens;
1573 uint64_t cl_counts[CODE_LEN_CODES];
1574 uint16_t combined_table[LIT_LEN + DIST_LEN];
1575 int i;
1576 uint64_t compressed_len = 0;
1577 uint64_t static_compressed_len = 3; /* The static header size */
1578 struct BitBuf2 bb_tmp;
1579
1580 struct huff_code *ll_codes = hufftables->lit_len_table;
1581 struct huff_code *d_codes = hufftables->dist_table;
1582 uint32_t *ll_hist = hist->ll_hist;
1583 uint32_t *d_hist = hist->d_hist;
1584 struct huff_code *static_ll_codes = static_hufftables.lit_len_table;
1585 struct huff_code *static_d_codes = static_hufftables.dist_table;
1586
1587 memcpy(&bb_tmp, bb, sizeof(struct BitBuf2));
1588
1589 flatten_ll(hist->ll_hist);
1590
1591 // make sure EOB is present
1592 if (ll_hist[256] == 0)
1593 ll_hist[256] = 1;
1594
1595 heap_size = init_heap32(&heap_space, ll_hist, LIT_LEN);
1596 gen_huff_code_lens(&heap_space, heap_size, bl_count, ll_codes, LIT_LEN,
1597 MAX_DEFLATE_CODE_LEN);
1598 max_ll_code = set_huff_codes(ll_codes, LIT_LEN, bl_count);
1599
1600 heap_size = init_heap32(&heap_space, d_hist, DIST_LEN);
1601 gen_huff_code_lens(&heap_space, heap_size, bl_count, d_codes, DIST_LEN,
1602 MAX_DEFLATE_CODE_LEN);
1603 max_d_code = set_dist_huff_codes(d_codes, bl_count);
1604
1605 assert(max_ll_code >= 256); // must be EOB code
1606 assert(max_d_code != 0);
1607
1608 /* Run length encode the length and distance huffman codes */
1609 memset(cl_counts, 0, sizeof(cl_counts));
1610
1611 for (i = 0; i <= 256; i++) {
1612 combined_table[i] = ll_codes[i].length;
1613 compressed_len += ll_codes[i].length * ll_hist[i];
1614 static_compressed_len += static_ll_codes[i].length * ll_hist[i];
1615 }
1616
1617 for (; i < max_ll_code + 1; i++) {
1618 combined_table[i] = ll_codes[i].length;
1619 compressed_len += (ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i];
1620 static_compressed_len +=
1621 (static_ll_codes[i].length + len_code_extra_bits[i - 257]) * ll_hist[i];
1622 }
1623
1624 for (i = 0; i < max_d_code + 1; i++) {
1625 combined_table[i + max_ll_code + 1] = d_codes[i].length;
1626 compressed_len += (d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i];
1627 static_compressed_len +=
1628 (static_d_codes[i].length + dist_code_extra_bits[i]) * d_hist[i];
1629 }
1630
1631 if (static_compressed_len > compressed_len) {
1632 num_cl_tokens = rl_encode(combined_table, max_ll_code + max_d_code + 2, cl_counts,
1633 cl_tokens);
1634
1635 /* Create header */
1636 create_header(bb, cl_tokens, num_cl_tokens, cl_counts, max_ll_code - 256,
1637 max_d_code, end_of_block);
1638 compressed_len += 8 * buffer_used(bb) + bb->m_bit_count;
1639 }
1640
1641 /* Substitute in static block since it creates smaller block */
1642 if (static_compressed_len <= compressed_len) {
1643 memcpy(hufftables, &static_hufftables, sizeof(struct hufftables_icf));
1644 memcpy(bb, &bb_tmp, sizeof(struct BitBuf2));
1645 end_of_block = end_of_block ? 1 : 0;
1646 write_bits(bb, 0x2 | end_of_block, 3);
1647 compressed_len = static_compressed_len;
1648 }
1649
1650 expand_hufftables_icf(hufftables);
1651 return compressed_len;
1652 }
1653