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