]>
Commit | Line | Data |
---|---|---|
9f95a23c TL |
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++) { | |
f67539c2 | 683 | literal = load_u32(current); |
9f95a23c TL |
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++) { | |
f67539c2 | 703 | literal = load_u32(next_hash); |
9f95a23c TL |
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); | |
f67539c2 TL |
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 | } | |
9f95a23c TL |
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 | } |