Gitiles
Code Review Sign In
git01.mediatek.com / haproxy / d5961ad0385896e918032b62673d14566ce614fa / . / src / hpack-huff.c
blob: 23aa5419b015b33b515dddcb918728eea1ef0665 [file] [log] [blame]
Willy Tarreaua004ade2017-05-30 17:22:18 +0200[diff] [blame]1/*
2 * Huffman decoding and encoding for HPACK (RFC7541)
3 *
4 * Copyright (C) 2014-2017 Willy Tarreau <willy@haproxy.org>
5 * Copyright (C) 2017 HAProxy Technologies
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
26 */
27
28#include <stdio.h>
29#include <stdint.h>
30#include <string.h>
31
32#include <common/config.h>
33#include <common/hpack-huff.h>
34
35struct huff {
36 uint32_t c; /* code point */
37 int b; /* bits */
38};
39
40struct rht {
41 uint8_t c; // code or 0 if length > 8 + position*8
42 uint8_t l; // length in bits
43};
44
45/* huffman table as per RFC7541 appendix B */
46static const struct huff ht[257] = {
47 [ 0] = { .c = 0x00001ff8, .b = 13 },
48 [ 1] = { .c = 0x007fffd8, .b = 23 },
49 [ 2] = { .c = 0x0fffffe2, .b = 28 },
50 [ 3] = { .c = 0x0fffffe3, .b = 28 },
51 [ 4] = { .c = 0x0fffffe4, .b = 28 },
52 [ 5] = { .c = 0x0fffffe5, .b = 28 },
53 [ 6] = { .c = 0x0fffffe6, .b = 28 },
54 [ 7] = { .c = 0x0fffffe7, .b = 28 },
55 [ 8] = { .c = 0x0fffffe8, .b = 28 },
56 [ 9] = { .c = 0x00ffffea, .b = 24 },
57 [ 10] = { .c = 0x3ffffffc, .b = 30 },
58 [ 11] = { .c = 0x0fffffe9, .b = 28 },
59 [ 12] = { .c = 0x0fffffea, .b = 28 },
60 [ 13] = { .c = 0x3ffffffd, .b = 30 },
61 [ 14] = { .c = 0x0fffffeb, .b = 28 },
62 [ 15] = { .c = 0x0fffffec, .b = 28 },
63 [ 16] = { .c = 0x0fffffed, .b = 28 },
64 [ 17] = { .c = 0x0fffffee, .b = 28 },
65 [ 18] = { .c = 0x0fffffef, .b = 28 },
66 [ 19] = { .c = 0x0ffffff0, .b = 28 },
67 [ 20] = { .c = 0x0ffffff1, .b = 28 },
68 [ 21] = { .c = 0x0ffffff2, .b = 28 },
69 [ 22] = { .c = 0x3ffffffe, .b = 30 },
70 [ 23] = { .c = 0x0ffffff3, .b = 28 },
71 [ 24] = { .c = 0x0ffffff4, .b = 28 },
72 [ 25] = { .c = 0x0ffffff5, .b = 28 },
73 [ 26] = { .c = 0x0ffffff6, .b = 28 },
74 [ 27] = { .c = 0x0ffffff7, .b = 28 },
75 [ 28] = { .c = 0x0ffffff8, .b = 28 },
76 [ 29] = { .c = 0x0ffffff9, .b = 28 },
77 [ 30] = { .c = 0x0ffffffa, .b = 28 },
78 [ 31] = { .c = 0x0ffffffb, .b = 28 },
79 [ 32] = { .c = 0x00000014, .b = 6 },
80 [ 33] = { .c = 0x000003f8, .b = 10 },
81 [ 34] = { .c = 0x000003f9, .b = 10 },
82 [ 35] = { .c = 0x00000ffa, .b = 12 },
83 [ 36] = { .c = 0x00001ff9, .b = 13 },
84 [ 37] = { .c = 0x00000015, .b = 6 },
85 [ 38] = { .c = 0x000000f8, .b = 8 },
86 [ 39] = { .c = 0x000007fa, .b = 11 },
87 [ 40] = { .c = 0x000003fa, .b = 10 },
88 [ 41] = { .c = 0x000003fb, .b = 10 },
89 [ 42] = { .c = 0x000000f9, .b = 8 },
90 [ 43] = { .c = 0x000007fb, .b = 11 },
91 [ 44] = { .c = 0x000000fa, .b = 8 },
92 [ 45] = { .c = 0x00000016, .b = 6 },
93 [ 46] = { .c = 0x00000017, .b = 6 },
94 [ 47] = { .c = 0x00000018, .b = 6 },
95 [ 48] = { .c = 0x00000000, .b = 5 },
96 [ 49] = { .c = 0x00000001, .b = 5 },
97 [ 50] = { .c = 0x00000002, .b = 5 },
98 [ 51] = { .c = 0x00000019, .b = 6 },
99 [ 52] = { .c = 0x0000001a, .b = 6 },
100 [ 53] = { .c = 0x0000001b, .b = 6 },
101 [ 54] = { .c = 0x0000001c, .b = 6 },
102 [ 55] = { .c = 0x0000001d, .b = 6 },
103 [ 56] = { .c = 0x0000001e, .b = 6 },
104 [ 57] = { .c = 0x0000001f, .b = 6 },
105 [ 58] = { .c = 0x0000005c, .b = 7 },
106 [ 59] = { .c = 0x000000fb, .b = 8 },
107 [ 60] = { .c = 0x00007ffc, .b = 15 },
108 [ 61] = { .c = 0x00000020, .b = 6 },
109 [ 62] = { .c = 0x00000ffb, .b = 12 },
110 [ 63] = { .c = 0x000003fc, .b = 10 },
111 [ 64] = { .c = 0x00001ffa, .b = 13 },
112 [ 65] = { .c = 0x00000021, .b = 6 },
113 [ 66] = { .c = 0x0000005d, .b = 7 },
114 [ 67] = { .c = 0x0000005e, .b = 7 },
115 [ 68] = { .c = 0x0000005f, .b = 7 },
116 [ 69] = { .c = 0x00000060, .b = 7 },
117 [ 70] = { .c = 0x00000061, .b = 7 },
118 [ 71] = { .c = 0x00000062, .b = 7 },
119 [ 72] = { .c = 0x00000063, .b = 7 },
120 [ 73] = { .c = 0x00000064, .b = 7 },
121 [ 74] = { .c = 0x00000065, .b = 7 },
122 [ 75] = { .c = 0x00000066, .b = 7 },
123 [ 76] = { .c = 0x00000067, .b = 7 },
124 [ 77] = { .c = 0x00000068, .b = 7 },
125 [ 78] = { .c = 0x00000069, .b = 7 },
126 [ 79] = { .c = 0x0000006a, .b = 7 },
127 [ 80] = { .c = 0x0000006b, .b = 7 },
128 [ 81] = { .c = 0x0000006c, .b = 7 },
129 [ 82] = { .c = 0x0000006d, .b = 7 },
130 [ 83] = { .c = 0x0000006e, .b = 7 },
131 [ 84] = { .c = 0x0000006f, .b = 7 },
132 [ 85] = { .c = 0x00000070, .b = 7 },
133 [ 86] = { .c = 0x00000071, .b = 7 },
134 [ 87] = { .c = 0x00000072, .b = 7 },
135 [ 88] = { .c = 0x000000fc, .b = 8 },
136 [ 89] = { .c = 0x00000073, .b = 7 },
137 [ 90] = { .c = 0x000000fd, .b = 8 },
138 [ 91] = { .c = 0x00001ffb, .b = 13 },
139 [ 92] = { .c = 0x0007fff0, .b = 19 },
140 [ 93] = { .c = 0x00001ffc, .b = 13 },
141 [ 94] = { .c = 0x00003ffc, .b = 14 },
142 [ 95] = { .c = 0x00000022, .b = 6 },
143 [ 96] = { .c = 0x00007ffd, .b = 15 },
144 [ 97] = { .c = 0x00000003, .b = 5 },
145 [ 98] = { .c = 0x00000023, .b = 6 },
146 [ 99] = { .c = 0x00000004, .b = 5 },
147 [100] = { .c = 0x00000024, .b = 6 },
148 [101] = { .c = 0x00000005, .b = 5 },
149 [102] = { .c = 0x00000025, .b = 6 },
150 [103] = { .c = 0x00000026, .b = 6 },
151 [104] = { .c = 0x00000027, .b = 6 },
152 [105] = { .c = 0x00000006, .b = 5 },
153 [106] = { .c = 0x00000074, .b = 7 },
154 [107] = { .c = 0x00000075, .b = 7 },
155 [108] = { .c = 0x00000028, .b = 6 },
156 [109] = { .c = 0x00000029, .b = 6 },
157 [110] = { .c = 0x0000002a, .b = 6 },
158 [111] = { .c = 0x00000007, .b = 5 },
159 [112] = { .c = 0x0000002b, .b = 6 },
160 [113] = { .c = 0x00000076, .b = 7 },
161 [114] = { .c = 0x0000002c, .b = 6 },
162 [115] = { .c = 0x00000008, .b = 5 },
163 [116] = { .c = 0x00000009, .b = 5 },
164 [117] = { .c = 0x0000002d, .b = 6 },
165 [118] = { .c = 0x00000077, .b = 7 },
166 [119] = { .c = 0x00000078, .b = 7 },
167 [120] = { .c = 0x00000079, .b = 7 },
168 [121] = { .c = 0x0000007a, .b = 7 },
169 [122] = { .c = 0x0000007b, .b = 7 },
170 [123] = { .c = 0x00007ffe, .b = 15 },
171 [124] = { .c = 0x000007fc, .b = 11 },
172 [125] = { .c = 0x00003ffd, .b = 14 },
173 [126] = { .c = 0x00001ffd, .b = 13 },
174 [127] = { .c = 0x0ffffffc, .b = 28 },
175 [128] = { .c = 0x000fffe6, .b = 20 },
176 [129] = { .c = 0x003fffd2, .b = 22 },
177 [130] = { .c = 0x000fffe7, .b = 20 },
178 [131] = { .c = 0x000fffe8, .b = 20 },
179 [132] = { .c = 0x003fffd3, .b = 22 },
180 [133] = { .c = 0x003fffd4, .b = 22 },
181 [134] = { .c = 0x003fffd5, .b = 22 },
182 [135] = { .c = 0x007fffd9, .b = 23 },
183 [136] = { .c = 0x003fffd6, .b = 22 },
184 [137] = { .c = 0x007fffda, .b = 23 },
185 [138] = { .c = 0x007fffdb, .b = 23 },
186 [139] = { .c = 0x007fffdc, .b = 23 },
187 [140] = { .c = 0x007fffdd, .b = 23 },
188 [141] = { .c = 0x007fffde, .b = 23 },
189 [142] = { .c = 0x00ffffeb, .b = 24 },
190 [143] = { .c = 0x007fffdf, .b = 23 },
191 [144] = { .c = 0x00ffffec, .b = 24 },
192 [145] = { .c = 0x00ffffed, .b = 24 },
193 [146] = { .c = 0x003fffd7, .b = 22 },
194 [147] = { .c = 0x007fffe0, .b = 23 },
195 [148] = { .c = 0x00ffffee, .b = 24 },
196 [149] = { .c = 0x007fffe1, .b = 23 },
197 [150] = { .c = 0x007fffe2, .b = 23 },
198 [151] = { .c = 0x007fffe3, .b = 23 },
199 [152] = { .c = 0x007fffe4, .b = 23 },
200 [153] = { .c = 0x001fffdc, .b = 21 },
201 [154] = { .c = 0x003fffd8, .b = 22 },
202 [155] = { .c = 0x007fffe5, .b = 23 },
203 [156] = { .c = 0x003fffd9, .b = 22 },
204 [157] = { .c = 0x007fffe6, .b = 23 },
205 [158] = { .c = 0x007fffe7, .b = 23 },
206 [159] = { .c = 0x00ffffef, .b = 24 },
207 [160] = { .c = 0x003fffda, .b = 22 },
208 [161] = { .c = 0x001fffdd, .b = 21 },
209 [162] = { .c = 0x000fffe9, .b = 20 },
210 [163] = { .c = 0x003fffdb, .b = 22 },
211 [164] = { .c = 0x003fffdc, .b = 22 },
212 [165] = { .c = 0x007fffe8, .b = 23 },
213 [166] = { .c = 0x007fffe9, .b = 23 },
214 [167] = { .c = 0x001fffde, .b = 21 },
215 [168] = { .c = 0x007fffea, .b = 23 },
216 [169] = { .c = 0x003fffdd, .b = 22 },
217 [170] = { .c = 0x003fffde, .b = 22 },
218 [171] = { .c = 0x00fffff0, .b = 24 },
219 [172] = { .c = 0x001fffdf, .b = 21 },
220 [173] = { .c = 0x003fffdf, .b = 22 },
221 [174] = { .c = 0x007fffeb, .b = 23 },
222 [175] = { .c = 0x007fffec, .b = 23 },
223 [176] = { .c = 0x001fffe0, .b = 21 },
224 [177] = { .c = 0x001fffe1, .b = 21 },
225 [178] = { .c = 0x003fffe0, .b = 22 },
226 [179] = { .c = 0x001fffe2, .b = 21 },
227 [180] = { .c = 0x007fffed, .b = 23 },
228 [181] = { .c = 0x003fffe1, .b = 22 },
229 [182] = { .c = 0x007fffee, .b = 23 },
230 [183] = { .c = 0x007fffef, .b = 23 },
231 [184] = { .c = 0x000fffea, .b = 20 },
232 [185] = { .c = 0x003fffe2, .b = 22 },
233 [186] = { .c = 0x003fffe3, .b = 22 },
234 [187] = { .c = 0x003fffe4, .b = 22 },
235 [188] = { .c = 0x007ffff0, .b = 23 },
236 [189] = { .c = 0x003fffe5, .b = 22 },
237 [190] = { .c = 0x003fffe6, .b = 22 },
238 [191] = { .c = 0x007ffff1, .b = 23 },
239 [192] = { .c = 0x03ffffe0, .b = 26 },
240 [193] = { .c = 0x03ffffe1, .b = 26 },
241 [194] = { .c = 0x000fffeb, .b = 20 },
242 [195] = { .c = 0x0007fff1, .b = 19 },
243 [196] = { .c = 0x003fffe7, .b = 22 },
244 [197] = { .c = 0x007ffff2, .b = 23 },
245 [198] = { .c = 0x003fffe8, .b = 22 },
246 [199] = { .c = 0x01ffffec, .b = 25 },
247 [200] = { .c = 0x03ffffe2, .b = 26 },
248 [201] = { .c = 0x03ffffe3, .b = 26 },
249 [202] = { .c = 0x03ffffe4, .b = 26 },
250 [203] = { .c = 0x07ffffde, .b = 27 },
251 [204] = { .c = 0x07ffffdf, .b = 27 },
252 [205] = { .c = 0x03ffffe5, .b = 26 },
253 [206] = { .c = 0x00fffff1, .b = 24 },
254 [207] = { .c = 0x01ffffed, .b = 25 },
255 [208] = { .c = 0x0007fff2, .b = 19 },
256 [209] = { .c = 0x001fffe3, .b = 21 },
257 [210] = { .c = 0x03ffffe6, .b = 26 },
258 [211] = { .c = 0x07ffffe0, .b = 27 },
259 [212] = { .c = 0x07ffffe1, .b = 27 },
260 [213] = { .c = 0x03ffffe7, .b = 26 },
261 [214] = { .c = 0x07ffffe2, .b = 27 },
262 [215] = { .c = 0x00fffff2, .b = 24 },
263 [216] = { .c = 0x001fffe4, .b = 21 },
264 [217] = { .c = 0x001fffe5, .b = 21 },
265 [218] = { .c = 0x03ffffe8, .b = 26 },
266 [219] = { .c = 0x03ffffe9, .b = 26 },
267 [220] = { .c = 0x0ffffffd, .b = 28 },
268 [221] = { .c = 0x07ffffe3, .b = 27 },
269 [222] = { .c = 0x07ffffe4, .b = 27 },
270 [223] = { .c = 0x07ffffe5, .b = 27 },
271 [224] = { .c = 0x000fffec, .b = 20 },
272 [225] = { .c = 0x00fffff3, .b = 24 },
273 [226] = { .c = 0x000fffed, .b = 20 },
274 [227] = { .c = 0x001fffe6, .b = 21 },
275 [228] = { .c = 0x003fffe9, .b = 22 },
276 [229] = { .c = 0x001fffe7, .b = 21 },
277 [230] = { .c = 0x001fffe8, .b = 21 },
278 [231] = { .c = 0x007ffff3, .b = 23 },
279 [232] = { .c = 0x003fffea, .b = 22 },
280 [233] = { .c = 0x003fffeb, .b = 22 },
281 [234] = { .c = 0x01ffffee, .b = 25 },
282 [235] = { .c = 0x01ffffef, .b = 25 },
283 [236] = { .c = 0x00fffff4, .b = 24 },
284 [237] = { .c = 0x00fffff5, .b = 24 },
285 [238] = { .c = 0x03ffffea, .b = 26 },
286 [239] = { .c = 0x007ffff4, .b = 23 },
287 [240] = { .c = 0x03ffffeb, .b = 26 },
288 [241] = { .c = 0x07ffffe6, .b = 27 },
289 [242] = { .c = 0x03ffffec, .b = 26 },
290 [243] = { .c = 0x03ffffed, .b = 26 },
291 [244] = { .c = 0x07ffffe7, .b = 27 },
292 [245] = { .c = 0x07ffffe8, .b = 27 },
293 [246] = { .c = 0x07ffffe9, .b = 27 },
294 [247] = { .c = 0x07ffffea, .b = 27 },
295 [248] = { .c = 0x07ffffeb, .b = 27 },
296 [249] = { .c = 0x0ffffffe, .b = 28 },
297 [250] = { .c = 0x07ffffec, .b = 27 },
298 [251] = { .c = 0x07ffffed, .b = 27 },
299 [252] = { .c = 0x07ffffee, .b = 27 },
300 [253] = { .c = 0x07ffffef, .b = 27 },
301 [254] = { .c = 0x07fffff0, .b = 27 },
302 [255] = { .c = 0x03ffffee, .b = 26 },
303 [256] = { .c = 0x3fffffff, .b = 30 }, /* EOS */
304};
305
306
307/* Reversed huffman codes, generated by contrib/h2/gen-rht.c from the table
308 * above.
309 *
310 * The codes are aligned on the MSB since that's how they appear in the stream.
311 *
312 * Quick summary below of the way the tables work. They're based on how the
313 * prefixes are organized, starting from the MSB.
314 *
315 * These codes fit in a single octet (5 to 8 bits) :
316 * 00/5 08/5 10/5 18/5 20/5 28/5 30/5 38/5
317 * 40/5 48/5
318 *
319 * 50/6 54/6 58/6 5c/6 60/6 64/6 68/6 6c/6
320 * 70/6 74/6 78/6 7c/6 80/6 84/6 88/6 8c/6
321 * 90/6 94/6 98/6 9c/6 a0/6 a4/6 a8/6 ac/6
322 * b0/6 b4/6
323 *
324 * b8/7 ba/7 bc/7 be/7 c0/7 c2/7 c4/7 c6/7
325 * c8/7 ca/7 cc/7 ce/7 d0/7 d2/7 d4/7 d6/7
326 * d8/7 da/7 dc/7 de/7 e0/7 e2/7 e4/7 e6/7
327 * e8/7 ea/7 ec/7 ee/7 f0/7 f2/7 f4/7 f6/7
328 *
329 * f8/8 f9/8 fa/8 fb/8 fc/8 fd/8
330 *
331 * ==> a single 256-symbol table based on the full byte provides a direct
332 * access and the bit count
333 *
334 * These codes fit in two octets (10 to 15 bits, neither 9 nor 16 bits code) :
335 *
336 * fe + 2 bits:
337 * 00/2 40/2 80/2 c0/2
338 *
339 * ff + 2..7 bits :
340 * 00/2
341 * 40/3 60/3 80/3
342 * a0/4 b0/4
343 * c0/5 c8/5 d0/5 d8/5 e0/5 e8/5
344 * f0/6 f4/6
345 * f8/7 fa/7 fc/7
346 *
347 * ==> a single 256-symbol table made of b0.0 and b1.7-1 provides a direct
348 * access and the bit count after a miss on the first one above.
349 *
350 * These ones fit in three octets :
351 * ff fe + 3..5 bits :
352 * 00/3 20/3 40/3 60/4 70/4 80/4 90/4 a0/4
353 * b0/4 c0/4 d0/4
354 * e0/5 e8/5 f0/5 f8/5
355 *
356 * ff ff + 5..8 bits :
357 * 00/5 08/5 10/5 18/5 20/5 28/5 30/5 38/5
358 * 40/5
359 * 48/6 4c/6 50/6 54/6 58/6 5c/6 60/6 64/6
360 * 68/6 6c/6 70/6 74/6 78/6 7c/6 80/6 84/6
361 * 88/6 8c/6 90/6 94/6 98/6 9c/6 a0/6 a4/6
362 * a8/6 ac/6
363 * b0/7 b2/7 b4/7 b6/7 b8/7 ba/7 bc/7 be/7
364 * c0/7 c2/7 c4/7 c6/7 c8/7 ca/7 cc/7 ce/7
365 * d0/7 d2/7 d4/7 d6/7 d8/7 da/7 dc/7 de/7
366 * e0/7 e2/7 e4/7 e6/7 e8/7
367 * ea/8 eb/8 ec/8 ed/8 ee/8 ef/8 f0/8 f1/8
368 * f2/8 f3/8 f4/8 f5/8
369 *
370 * ==> a 32-symbol table has to be applied to 0xfffe
371 * ==> a 256-symbol table has to be applied to 0xffff
372 *
373 * The other ones fit in four octets with 1 to 6 bits in the last one :
374 * ff ff f6 : 00/1 80/1
375 * ff ff f7 : 00/1 80/1
376 * ff ff f8 : 00/2 40/2 80/2 c0/2
377 * ff ff f9 : 00/2 40/2 80/2 c0/2
378 * ff ff fa : 00/2 40/2 80/2 c0/2
379 * ff ff fb : 00/2 40/2 80/2
380 * ff ff fb : c0/3 e0/3
381 * ff ff fc : 00/3 20/3 40/3 60/3 80/3 a0/3 c0/3 e0/3
382 * ff ff fd : 00/3 20/3 40/3 60/3 80/3 a0/3 c0/3 e0/3
383 * ff ff fe : 00/3
384 * ff ff fe : 20/4 30/4 40/4 50/4 60/4 70/4 80/4 90/4 a0/4 b0/4 c0/4 d0/4 e0/4 f0/4
385 * ff ff ff : 00/4 10/4 20/4 30/4 40/4 50/4 60/4 70/4 80/4 90/4 a0/4 b0/4 c0/4 d0/4 e0/4
386 * ff ff ff : f0/6 f4/6 f8/6 fc/6
387 *
388 * ==> a 256-symbol table with b2.0-3,b3.7-4 gives all of them except the
389 * distinction between ffffff{f0,f4,f8,fc} which is rare enough
390 * and can be done by hand when bit count == 30.
391 *
392 *
393 * Code lengths :
394 * 5..8 : 0x00..0xfe
395 * 10..15 : 0xfe
396 * 0xff 0x00..0xfe
397 * 19..20 : 0xff 0xfe 0x00..0xdf
398 * 21 : 0xff 0xfe 0xe0..0xff
399 * 21 : 0xff 0xff 0x00..0x40
400 * 22..24 : 0xff 0xff 0x00..0xf5
401 * 24..28 : 0xff 0xff 0xf5..0xff
402 * 30 : 0xff 0xff 0xff 0xf0..0xff
403 *
404 *
405 * if b0 < 0xfe ==> 5..8 bits (74 codes)
406 * if b0 == 0xfe or 0xff : 10..15
407 * => if b0 == 0xfe || b1 < 0xfe : lookup (b0:0|b1:7..1) (21 codes)
408 *
409 * -- b0 = 0xff --
410 * if b1 == 0xfe : 19..21 bits
411 * => lookup b2:7..3 (15 codes)
412 *
413 * -- b0 = 0xff, b1 = 0xff : 147 codes --
414 * if b2 < 0xf6 : 21..24 bits (76 codes)
415 * if b2 >= 0xf6 : 25..30 bits (71 codes)
416 *
417 * Algorithm:
418 * - if > 24 and < 32, read missing bits.
419 * - if less than 24 bits, read 1 byte. If past end, insert 0xff instead.
420 * - if b0 < 0xfe lookup b0 in table0[0..255]
421 * - else if b0 == 0xfe, manual lookup
422 * - else if b0 == 0xff, lookup b1 in table1[0..255]
423 * ...
424 */
425
426struct rht rht_bit31_24[256] = {
427 [0x00] = { .c = 0x30, .l = 5 },
428 [0x01] = { .c = 0x30, .l = 5 },
429 [0x02] = { .c = 0x30, .l = 5 },
430 [0x03] = { .c = 0x30, .l = 5 },
431 [0x04] = { .c = 0x30, .l = 5 },
432 [0x05] = { .c = 0x30, .l = 5 },
433 [0x06] = { .c = 0x30, .l = 5 },
434 [0x07] = { .c = 0x30, .l = 5 },
435 [0x08] = { .c = 0x31, .l = 5 },
436 [0x09] = { .c = 0x31, .l = 5 },
437 [0x0a] = { .c = 0x31, .l = 5 },
438 [0x0b] = { .c = 0x31, .l = 5 },
439 [0x0c] = { .c = 0x31, .l = 5 },
440 [0x0d] = { .c = 0x31, .l = 5 },
441 [0x0e] = { .c = 0x31, .l = 5 },
442 [0x0f] = { .c = 0x31, .l = 5 },
443 [0x10] = { .c = 0x32, .l = 5 },
444 [0x11] = { .c = 0x32, .l = 5 },
445 [0x12] = { .c = 0x32, .l = 5 },
446 [0x13] = { .c = 0x32, .l = 5 },
447 [0x14] = { .c = 0x32, .l = 5 },
448 [0x15] = { .c = 0x32, .l = 5 },
449 [0x16] = { .c = 0x32, .l = 5 },
450 [0x17] = { .c = 0x32, .l = 5 },
451 [0x18] = { .c = 0x61, .l = 5 },
452 [0x19] = { .c = 0x61, .l = 5 },
453 [0x1a] = { .c = 0x61, .l = 5 },
454 [0x1b] = { .c = 0x61, .l = 5 },
455 [0x1c] = { .c = 0x61, .l = 5 },
456 [0x1d] = { .c = 0x61, .l = 5 },
457 [0x1e] = { .c = 0x61, .l = 5 },
458 [0x1f] = { .c = 0x61, .l = 5 },
459 [0x20] = { .c = 0x63, .l = 5 },
460 [0x21] = { .c = 0x63, .l = 5 },
461 [0x22] = { .c = 0x63, .l = 5 },
462 [0x23] = { .c = 0x63, .l = 5 },
463 [0x24] = { .c = 0x63, .l = 5 },
464 [0x25] = { .c = 0x63, .l = 5 },
465 [0x26] = { .c = 0x63, .l = 5 },
466 [0x27] = { .c = 0x63, .l = 5 },
467 [0x28] = { .c = 0x65, .l = 5 },
468 [0x29] = { .c = 0x65, .l = 5 },
469 [0x2a] = { .c = 0x65, .l = 5 },
470 [0x2b] = { .c = 0x65, .l = 5 },
471 [0x2c] = { .c = 0x65, .l = 5 },
472 [0x2d] = { .c = 0x65, .l = 5 },
473 [0x2e] = { .c = 0x65, .l = 5 },
474 [0x2f] = { .c = 0x65, .l = 5 },
475 [0x30] = { .c = 0x69, .l = 5 },
476 [0x31] = { .c = 0x69, .l = 5 },
477 [0x32] = { .c = 0x69, .l = 5 },
478 [0x33] = { .c = 0x69, .l = 5 },
479 [0x34] = { .c = 0x69, .l = 5 },
480 [0x35] = { .c = 0x69, .l = 5 },
481 [0x36] = { .c = 0x69, .l = 5 },
482 [0x37] = { .c = 0x69, .l = 5 },
483 [0x38] = { .c = 0x6f, .l = 5 },
484 [0x39] = { .c = 0x6f, .l = 5 },
485 [0x3a] = { .c = 0x6f, .l = 5 },
486 [0x3b] = { .c = 0x6f, .l = 5 },
487 [0x3c] = { .c = 0x6f, .l = 5 },
488 [0x3d] = { .c = 0x6f, .l = 5 },
489 [0x3e] = { .c = 0x6f, .l = 5 },
490 [0x3f] = { .c = 0x6f, .l = 5 },
491 [0x40] = { .c = 0x73, .l = 5 },
492 [0x41] = { .c = 0x73, .l = 5 },
493 [0x42] = { .c = 0x73, .l = 5 },
494 [0x43] = { .c = 0x73, .l = 5 },
495 [0x44] = { .c = 0x73, .l = 5 },
496 [0x45] = { .c = 0x73, .l = 5 },
497 [0x46] = { .c = 0x73, .l = 5 },
498 [0x47] = { .c = 0x73, .l = 5 },
499 [0x48] = { .c = 0x74, .l = 5 },
500 [0x49] = { .c = 0x74, .l = 5 },
501 [0x4a] = { .c = 0x74, .l = 5 },
502 [0x4b] = { .c = 0x74, .l = 5 },
503 [0x4c] = { .c = 0x74, .l = 5 },
504 [0x4d] = { .c = 0x74, .l = 5 },
505 [0x4e] = { .c = 0x74, .l = 5 },
506 [0x4f] = { .c = 0x74, .l = 5 },
507 [0x50] = { .c = 0x20, .l = 6 },
508 [0x51] = { .c = 0x20, .l = 6 },
509 [0x52] = { .c = 0x20, .l = 6 },
510 [0x53] = { .c = 0x20, .l = 6 },
511 [0x54] = { .c = 0x25, .l = 6 },
512 [0x55] = { .c = 0x25, .l = 6 },
513 [0x56] = { .c = 0x25, .l = 6 },
514 [0x57] = { .c = 0x25, .l = 6 },
515 [0x58] = { .c = 0x2d, .l = 6 },
516 [0x59] = { .c = 0x2d, .l = 6 },
517 [0x5a] = { .c = 0x2d, .l = 6 },
518 [0x5b] = { .c = 0x2d, .l = 6 },
519 [0x5c] = { .c = 0x2e, .l = 6 },
520 [0x5d] = { .c = 0x2e, .l = 6 },
521 [0x5e] = { .c = 0x2e, .l = 6 },
522 [0x5f] = { .c = 0x2e, .l = 6 },
523 [0x60] = { .c = 0x2f, .l = 6 },
524 [0x61] = { .c = 0x2f, .l = 6 },
525 [0x62] = { .c = 0x2f, .l = 6 },
526 [0x63] = { .c = 0x2f, .l = 6 },
527 [0x64] = { .c = 0x33, .l = 6 },
528 [0x65] = { .c = 0x33, .l = 6 },
529 [0x66] = { .c = 0x33, .l = 6 },
530 [0x67] = { .c = 0x33, .l = 6 },
531 [0x68] = { .c = 0x34, .l = 6 },
532 [0x69] = { .c = 0x34, .l = 6 },
533 [0x6a] = { .c = 0x34, .l = 6 },
534 [0x6b] = { .c = 0x34, .l = 6 },
535 [0x6c] = { .c = 0x35, .l = 6 },
536 [0x6d] = { .c = 0x35, .l = 6 },
537 [0x6e] = { .c = 0x35, .l = 6 },
538 [0x6f] = { .c = 0x35, .l = 6 },
539 [0x70] = { .c = 0x36, .l = 6 },
540 [0x71] = { .c = 0x36, .l = 6 },
541 [0x72] = { .c = 0x36, .l = 6 },
542 [0x73] = { .c = 0x36, .l = 6 },
543 [0x74] = { .c = 0x37, .l = 6 },
544 [0x75] = { .c = 0x37, .l = 6 },
545 [0x76] = { .c = 0x37, .l = 6 },
546 [0x77] = { .c = 0x37, .l = 6 },
547 [0x78] = { .c = 0x38, .l = 6 },
548 [0x79] = { .c = 0x38, .l = 6 },
549 [0x7a] = { .c = 0x38, .l = 6 },
550 [0x7b] = { .c = 0x38, .l = 6 },
551 [0x7c] = { .c = 0x39, .l = 6 },
552 [0x7d] = { .c = 0x39, .l = 6 },
553 [0x7e] = { .c = 0x39, .l = 6 },
554 [0x7f] = { .c = 0x39, .l = 6 },
555 [0x80] = { .c = 0x3d, .l = 6 },
556 [0x81] = { .c = 0x3d, .l = 6 },
557 [0x82] = { .c = 0x3d, .l = 6 },
558 [0x83] = { .c = 0x3d, .l = 6 },
559 [0x84] = { .c = 0x41, .l = 6 },
560 [0x85] = { .c = 0x41, .l = 6 },
561 [0x86] = { .c = 0x41, .l = 6 },
562 [0x87] = { .c = 0x41, .l = 6 },
563 [0x88] = { .c = 0x5f, .l = 6 },
564 [0x89] = { .c = 0x5f, .l = 6 },
565 [0x8a] = { .c = 0x5f, .l = 6 },
566 [0x8b] = { .c = 0x5f, .l = 6 },
567 [0x8c] = { .c = 0x62, .l = 6 },
568 [0x8d] = { .c = 0x62, .l = 6 },
569 [0x8e] = { .c = 0x62, .l = 6 },
570 [0x8f] = { .c = 0x62, .l = 6 },
571 [0x90] = { .c = 0x64, .l = 6 },
572 [0x91] = { .c = 0x64, .l = 6 },
573 [0x92] = { .c = 0x64, .l = 6 },
574 [0x93] = { .c = 0x64, .l = 6 },
575 [0x94] = { .c = 0x66, .l = 6 },
576 [0x95] = { .c = 0x66, .l = 6 },
577 [0x96] = { .c = 0x66, .l = 6 },
578 [0x97] = { .c = 0x66, .l = 6 },
579 [0x98] = { .c = 0x67, .l = 6 },
580 [0x99] = { .c = 0x67, .l = 6 },
581 [0x9a] = { .c = 0x67, .l = 6 },
582 [0x9b] = { .c = 0x67, .l = 6 },
583 [0x9c] = { .c = 0x68, .l = 6 },
584 [0x9d] = { .c = 0x68, .l = 6 },
585 [0x9e] = { .c = 0x68, .l = 6 },
586 [0x9f] = { .c = 0x68, .l = 6 },
587 [0xa0] = { .c = 0x6c, .l = 6 },
588 [0xa1] = { .c = 0x6c, .l = 6 },
589 [0xa2] = { .c = 0x6c, .l = 6 },
590 [0xa3] = { .c = 0x6c, .l = 6 },
591 [0xa4] = { .c = 0x6d, .l = 6 },
592 [0xa5] = { .c = 0x6d, .l = 6 },
593 [0xa6] = { .c = 0x6d, .l = 6 },
594 [0xa7] = { .c = 0x6d, .l = 6 },
595 [0xa8] = { .c = 0x6e, .l = 6 },
596 [0xa9] = { .c = 0x6e, .l = 6 },
597 [0xaa] = { .c = 0x6e, .l = 6 },
598 [0xab] = { .c = 0x6e, .l = 6 },
599 [0xac] = { .c = 0x70, .l = 6 },
600 [0xad] = { .c = 0x70, .l = 6 },
601 [0xae] = { .c = 0x70, .l = 6 },
602 [0xaf] = { .c = 0x70, .l = 6 },
603 [0xb0] = { .c = 0x72, .l = 6 },
604 [0xb1] = { .c = 0x72, .l = 6 },
605 [0xb2] = { .c = 0x72, .l = 6 },
606 [0xb3] = { .c = 0x72, .l = 6 },
607 [0xb4] = { .c = 0x75, .l = 6 },
608 [0xb5] = { .c = 0x75, .l = 6 },
609 [0xb6] = { .c = 0x75, .l = 6 },
610 [0xb7] = { .c = 0x75, .l = 6 },
611 [0xb8] = { .c = 0x3a, .l = 7 },
612 [0xb9] = { .c = 0x3a, .l = 7 },
613 [0xba] = { .c = 0x42, .l = 7 },
614 [0xbb] = { .c = 0x42, .l = 7 },
615 [0xbc] = { .c = 0x43, .l = 7 },
616 [0xbd] = { .c = 0x43, .l = 7 },
617 [0xbe] = { .c = 0x44, .l = 7 },
618 [0xbf] = { .c = 0x44, .l = 7 },
619 [0xc0] = { .c = 0x45, .l = 7 },
620 [0xc1] = { .c = 0x45, .l = 7 },
621 [0xc2] = { .c = 0x46, .l = 7 },
622 [0xc3] = { .c = 0x46, .l = 7 },
623 [0xc4] = { .c = 0x47, .l = 7 },
624 [0xc5] = { .c = 0x47, .l = 7 },
625 [0xc6] = { .c = 0x48, .l = 7 },
626 [0xc7] = { .c = 0x48, .l = 7 },
627 [0xc8] = { .c = 0x49, .l = 7 },
628 [0xc9] = { .c = 0x49, .l = 7 },
629 [0xca] = { .c = 0x4a, .l = 7 },
630 [0xcb] = { .c = 0x4a, .l = 7 },
631 [0xcc] = { .c = 0x4b, .l = 7 },
632 [0xcd] = { .c = 0x4b, .l = 7 },
633 [0xce] = { .c = 0x4c, .l = 7 },
634 [0xcf] = { .c = 0x4c, .l = 7 },
635 [0xd0] = { .c = 0x4d, .l = 7 },
636 [0xd1] = { .c = 0x4d, .l = 7 },
637 [0xd2] = { .c = 0x4e, .l = 7 },
638 [0xd3] = { .c = 0x4e, .l = 7 },
639 [0xd4] = { .c = 0x4f, .l = 7 },
640 [0xd5] = { .c = 0x4f, .l = 7 },
641 [0xd6] = { .c = 0x50, .l = 7 },
642 [0xd7] = { .c = 0x50, .l = 7 },
643 [0xd8] = { .c = 0x51, .l = 7 },
644 [0xd9] = { .c = 0x51, .l = 7 },
645 [0xda] = { .c = 0x52, .l = 7 },
646 [0xdb] = { .c = 0x52, .l = 7 },
647 [0xdc] = { .c = 0x53, .l = 7 },
648 [0xdd] = { .c = 0x53, .l = 7 },
649 [0xde] = { .c = 0x54, .l = 7 },
650 [0xdf] = { .c = 0x54, .l = 7 },
651 [0xe0] = { .c = 0x55, .l = 7 },
652 [0xe1] = { .c = 0x55, .l = 7 },
653 [0xe2] = { .c = 0x56, .l = 7 },
654 [0xe3] = { .c = 0x56, .l = 7 },
655 [0xe4] = { .c = 0x57, .l = 7 },
656 [0xe5] = { .c = 0x57, .l = 7 },
657 [0xe6] = { .c = 0x59, .l = 7 },
658 [0xe7] = { .c = 0x59, .l = 7 },
659 [0xe8] = { .c = 0x6a, .l = 7 },
660 [0xe9] = { .c = 0x6a, .l = 7 },
661 [0xea] = { .c = 0x6b, .l = 7 },
662 [0xeb] = { .c = 0x6b, .l = 7 },
663 [0xec] = { .c = 0x71, .l = 7 },
664 [0xed] = { .c = 0x71, .l = 7 },
665 [0xee] = { .c = 0x76, .l = 7 },
666 [0xef] = { .c = 0x76, .l = 7 },
667 [0xf0] = { .c = 0x77, .l = 7 },
668 [0xf1] = { .c = 0x77, .l = 7 },
669 [0xf2] = { .c = 0x78, .l = 7 },
670 [0xf3] = { .c = 0x78, .l = 7 },
671 [0xf4] = { .c = 0x79, .l = 7 },
672 [0xf5] = { .c = 0x79, .l = 7 },
673 [0xf6] = { .c = 0x7a, .l = 7 },
674 [0xf7] = { .c = 0x7a, .l = 7 },
675 [0xf8] = { .c = 0x26, .l = 8 },
676 [0xf9] = { .c = 0x2a, .l = 8 },
677 [0xfa] = { .c = 0x2c, .l = 8 },
678 [0xfb] = { .c = 0x3b, .l = 8 },
679 [0xfc] = { .c = 0x58, .l = 8 },
680 [0xfd] = { .c = 0x5a, .l = 8 },
681};
682
683struct rht rht_bit24_17[256] = {
684 [0x00] = { .c = 0x21, .l = 10 },
685 [0x01] = { .c = 0x21, .l = 10 },
686 [0x02] = { .c = 0x21, .l = 10 },
687 [0x03] = { .c = 0x21, .l = 10 },
688 [0x04] = { .c = 0x21, .l = 10 },
689 [0x05] = { .c = 0x21, .l = 10 },
690 [0x06] = { .c = 0x21, .l = 10 },
691 [0x07] = { .c = 0x21, .l = 10 },
692 [0x08] = { .c = 0x21, .l = 10 },
693 [0x09] = { .c = 0x21, .l = 10 },
694 [0x0a] = { .c = 0x21, .l = 10 },
695 [0x0b] = { .c = 0x21, .l = 10 },
696 [0x0c] = { .c = 0x21, .l = 10 },
697 [0x0d] = { .c = 0x21, .l = 10 },
698 [0x0e] = { .c = 0x21, .l = 10 },
699 [0x0f] = { .c = 0x21, .l = 10 },
700 [0x10] = { .c = 0x21, .l = 10 },
701 [0x11] = { .c = 0x21, .l = 10 },
702 [0x12] = { .c = 0x21, .l = 10 },
703 [0x13] = { .c = 0x21, .l = 10 },
704 [0x14] = { .c = 0x21, .l = 10 },
705 [0x15] = { .c = 0x21, .l = 10 },
706 [0x16] = { .c = 0x21, .l = 10 },
707 [0x17] = { .c = 0x21, .l = 10 },
708 [0x18] = { .c = 0x21, .l = 10 },
709 [0x19] = { .c = 0x21, .l = 10 },
710 [0x1a] = { .c = 0x21, .l = 10 },
711 [0x1b] = { .c = 0x21, .l = 10 },
712 [0x1c] = { .c = 0x21, .l = 10 },
713 [0x1d] = { .c = 0x21, .l = 10 },
714 [0x1e] = { .c = 0x21, .l = 10 },
715 [0x1f] = { .c = 0x21, .l = 10 },
716 [0x20] = { .c = 0x22, .l = 10 },
717 [0x21] = { .c = 0x22, .l = 10 },
718 [0x22] = { .c = 0x22, .l = 10 },
719 [0x23] = { .c = 0x22, .l = 10 },
720 [0x24] = { .c = 0x22, .l = 10 },
721 [0x25] = { .c = 0x22, .l = 10 },
722 [0x26] = { .c = 0x22, .l = 10 },
723 [0x27] = { .c = 0x22, .l = 10 },
724 [0x28] = { .c = 0x22, .l = 10 },
725 [0x29] = { .c = 0x22, .l = 10 },
726 [0x2a] = { .c = 0x22, .l = 10 },
727 [0x2b] = { .c = 0x22, .l = 10 },
728 [0x2c] = { .c = 0x22, .l = 10 },
729 [0x2d] = { .c = 0x22, .l = 10 },
730 [0x2e] = { .c = 0x22, .l = 10 },
731 [0x2f] = { .c = 0x22, .l = 10 },
732 [0x30] = { .c = 0x22, .l = 10 },
733 [0x31] = { .c = 0x22, .l = 10 },
734 [0x32] = { .c = 0x22, .l = 10 },
735 [0x33] = { .c = 0x22, .l = 10 },
736 [0x34] = { .c = 0x22, .l = 10 },
737 [0x35] = { .c = 0x22, .l = 10 },
738 [0x36] = { .c = 0x22, .l = 10 },
739 [0x37] = { .c = 0x22, .l = 10 },
740 [0x38] = { .c = 0x22, .l = 10 },
741 [0x39] = { .c = 0x22, .l = 10 },
742 [0x3a] = { .c = 0x22, .l = 10 },
743 [0x3b] = { .c = 0x22, .l = 10 },
744 [0x3c] = { .c = 0x22, .l = 10 },
745 [0x3d] = { .c = 0x22, .l = 10 },
746 [0x3e] = { .c = 0x22, .l = 10 },
747 [0x3f] = { .c = 0x22, .l = 10 },
748 [0x40] = { .c = 0x28, .l = 10 },
749 [0x41] = { .c = 0x28, .l = 10 },
750 [0x42] = { .c = 0x28, .l = 10 },
751 [0x43] = { .c = 0x28, .l = 10 },
752 [0x44] = { .c = 0x28, .l = 10 },
753 [0x45] = { .c = 0x28, .l = 10 },
754 [0x46] = { .c = 0x28, .l = 10 },
755 [0x47] = { .c = 0x28, .l = 10 },
756 [0x48] = { .c = 0x28, .l = 10 },
757 [0x49] = { .c = 0x28, .l = 10 },
758 [0x4a] = { .c = 0x28, .l = 10 },
759 [0x4b] = { .c = 0x28, .l = 10 },
760 [0x4c] = { .c = 0x28, .l = 10 },
761 [0x4d] = { .c = 0x28, .l = 10 },
762 [0x4e] = { .c = 0x28, .l = 10 },
763 [0x4f] = { .c = 0x28, .l = 10 },
764 [0x50] = { .c = 0x28, .l = 10 },
765 [0x51] = { .c = 0x28, .l = 10 },
766 [0x52] = { .c = 0x28, .l = 10 },
767 [0x53] = { .c = 0x28, .l = 10 },
768 [0x54] = { .c = 0x28, .l = 10 },
769 [0x55] = { .c = 0x28, .l = 10 },
770 [0x56] = { .c = 0x28, .l = 10 },
771 [0x57] = { .c = 0x28, .l = 10 },
772 [0x58] = { .c = 0x28, .l = 10 },
773 [0x59] = { .c = 0x28, .l = 10 },
774 [0x5a] = { .c = 0x28, .l = 10 },
775 [0x5b] = { .c = 0x28, .l = 10 },
776 [0x5c] = { .c = 0x28, .l = 10 },
777 [0x5d] = { .c = 0x28, .l = 10 },
778 [0x5e] = { .c = 0x28, .l = 10 },
779 [0x5f] = { .c = 0x28, .l = 10 },
780 [0x60] = { .c = 0x29, .l = 10 },
781 [0x61] = { .c = 0x29, .l = 10 },
782 [0x62] = { .c = 0x29, .l = 10 },
783 [0x63] = { .c = 0x29, .l = 10 },
784 [0x64] = { .c = 0x29, .l = 10 },
785 [0x65] = { .c = 0x29, .l = 10 },
786 [0x66] = { .c = 0x29, .l = 10 },
787 [0x67] = { .c = 0x29, .l = 10 },
788 [0x68] = { .c = 0x29, .l = 10 },
789 [0x69] = { .c = 0x29, .l = 10 },
790 [0x6a] = { .c = 0x29, .l = 10 },
791 [0x6b] = { .c = 0x29, .l = 10 },
792 [0x6c] = { .c = 0x29, .l = 10 },
793 [0x6d] = { .c = 0x29, .l = 10 },
794 [0x6e] = { .c = 0x29, .l = 10 },
795 [0x6f] = { .c = 0x29, .l = 10 },
796 [0x70] = { .c = 0x29, .l = 10 },
797 [0x71] = { .c = 0x29, .l = 10 },
798 [0x72] = { .c = 0x29, .l = 10 },
799 [0x73] = { .c = 0x29, .l = 10 },
800 [0x74] = { .c = 0x29, .l = 10 },
801 [0x75] = { .c = 0x29, .l = 10 },
802 [0x76] = { .c = 0x29, .l = 10 },
803 [0x77] = { .c = 0x29, .l = 10 },
804 [0x78] = { .c = 0x29, .l = 10 },
805 [0x79] = { .c = 0x29, .l = 10 },
806 [0x7a] = { .c = 0x29, .l = 10 },
807 [0x7b] = { .c = 0x29, .l = 10 },
808 [0x7c] = { .c = 0x29, .l = 10 },
809 [0x7d] = { .c = 0x29, .l = 10 },
810 [0x7e] = { .c = 0x29, .l = 10 },
811 [0x7f] = { .c = 0x29, .l = 10 },
812 [0x80] = { .c = 0x3f, .l = 10 },
813 [0x81] = { .c = 0x3f, .l = 10 },
814 [0x82] = { .c = 0x3f, .l = 10 },
815 [0x83] = { .c = 0x3f, .l = 10 },
816 [0x84] = { .c = 0x3f, .l = 10 },
817 [0x85] = { .c = 0x3f, .l = 10 },
818 [0x86] = { .c = 0x3f, .l = 10 },
819 [0x87] = { .c = 0x3f, .l = 10 },
820 [0x88] = { .c = 0x3f, .l = 10 },
821 [0x89] = { .c = 0x3f, .l = 10 },
822 [0x8a] = { .c = 0x3f, .l = 10 },
823 [0x8b] = { .c = 0x3f, .l = 10 },
824 [0x8c] = { .c = 0x3f, .l = 10 },
825 [0x8d] = { .c = 0x3f, .l = 10 },
826 [0x8e] = { .c = 0x3f, .l = 10 },
827 [0x8f] = { .c = 0x3f, .l = 10 },
828 [0x90] = { .c = 0x3f, .l = 10 },
829 [0x91] = { .c = 0x3f, .l = 10 },
830 [0x92] = { .c = 0x3f, .l = 10 },
831 [0x93] = { .c = 0x3f, .l = 10 },
832 [0x94] = { .c = 0x3f, .l = 10 },
833 [0x95] = { .c = 0x3f, .l = 10 },
834 [0x96] = { .c = 0x3f, .l = 10 },
835 [0x97] = { .c = 0x3f, .l = 10 },
836 [0x98] = { .c = 0x3f, .l = 10 },
837 [0x99] = { .c = 0x3f, .l = 10 },
838 [0x9a] = { .c = 0x3f, .l = 10 },
839 [0x9b] = { .c = 0x3f, .l = 10 },
840 [0x9c] = { .c = 0x3f, .l = 10 },
841 [0x9d] = { .c = 0x3f, .l = 10 },
842 [0x9e] = { .c = 0x3f, .l = 10 },
843 [0x9f] = { .c = 0x3f, .l = 10 },
844 [0xa0] = { .c = 0x27, .l = 11 },
845 [0xa1] = { .c = 0x27, .l = 11 },
846 [0xa2] = { .c = 0x27, .l = 11 },
847 [0xa3] = { .c = 0x27, .l = 11 },
848 [0xa4] = { .c = 0x27, .l = 11 },
849 [0xa5] = { .c = 0x27, .l = 11 },
850 [0xa6] = { .c = 0x27, .l = 11 },
851 [0xa7] = { .c = 0x27, .l = 11 },
852 [0xa8] = { .c = 0x27, .l = 11 },
853 [0xa9] = { .c = 0x27, .l = 11 },
854 [0xaa] = { .c = 0x27, .l = 11 },
855 [0xab] = { .c = 0x27, .l = 11 },
856 [0xac] = { .c = 0x27, .l = 11 },
857 [0xad] = { .c = 0x27, .l = 11 },
858 [0xae] = { .c = 0x27, .l = 11 },
859 [0xaf] = { .c = 0x27, .l = 11 },
860 [0xb0] = { .c = 0x2b, .l = 11 },
861 [0xb1] = { .c = 0x2b, .l = 11 },
862 [0xb2] = { .c = 0x2b, .l = 11 },
863 [0xb3] = { .c = 0x2b, .l = 11 },
864 [0xb4] = { .c = 0x2b, .l = 11 },
865 [0xb5] = { .c = 0x2b, .l = 11 },
866 [0xb6] = { .c = 0x2b, .l = 11 },
867 [0xb7] = { .c = 0x2b, .l = 11 },
868 [0xb8] = { .c = 0x2b, .l = 11 },
869 [0xb9] = { .c = 0x2b, .l = 11 },
870 [0xba] = { .c = 0x2b, .l = 11 },
871 [0xbb] = { .c = 0x2b, .l = 11 },
872 [0xbc] = { .c = 0x2b, .l = 11 },
873 [0xbd] = { .c = 0x2b, .l = 11 },
874 [0xbe] = { .c = 0x2b, .l = 11 },
875 [0xbf] = { .c = 0x2b, .l = 11 },
876 [0xc0] = { .c = 0x7c, .l = 11 },
877 [0xc1] = { .c = 0x7c, .l = 11 },
878 [0xc2] = { .c = 0x7c, .l = 11 },
879 [0xc3] = { .c = 0x7c, .l = 11 },
880 [0xc4] = { .c = 0x7c, .l = 11 },
881 [0xc5] = { .c = 0x7c, .l = 11 },
882 [0xc6] = { .c = 0x7c, .l = 11 },
883 [0xc7] = { .c = 0x7c, .l = 11 },
884 [0xc8] = { .c = 0x7c, .l = 11 },
885 [0xc9] = { .c = 0x7c, .l = 11 },
886 [0xca] = { .c = 0x7c, .l = 11 },
887 [0xcb] = { .c = 0x7c, .l = 11 },
888 [0xcc] = { .c = 0x7c, .l = 11 },
889 [0xcd] = { .c = 0x7c, .l = 11 },
890 [0xce] = { .c = 0x7c, .l = 11 },
891 [0xcf] = { .c = 0x7c, .l = 11 },
892 [0xd0] = { .c = 0x23, .l = 12 },
893 [0xd1] = { .c = 0x23, .l = 12 },
894 [0xd2] = { .c = 0x23, .l = 12 },
895 [0xd3] = { .c = 0x23, .l = 12 },
896 [0xd4] = { .c = 0x23, .l = 12 },
897 [0xd5] = { .c = 0x23, .l = 12 },
898 [0xd6] = { .c = 0x23, .l = 12 },
899 [0xd7] = { .c = 0x23, .l = 12 },
900 [0xd8] = { .c = 0x3e, .l = 12 },
901 [0xd9] = { .c = 0x3e, .l = 12 },
902 [0xda] = { .c = 0x3e, .l = 12 },
903 [0xdb] = { .c = 0x3e, .l = 12 },
904 [0xdc] = { .c = 0x3e, .l = 12 },
905 [0xdd] = { .c = 0x3e, .l = 12 },
906 [0xde] = { .c = 0x3e, .l = 12 },
907 [0xdf] = { .c = 0x3e, .l = 12 },
908 [0xe0] = { .c = 0x00, .l = 13 },
909 [0xe1] = { .c = 0x00, .l = 13 },
910 [0xe2] = { .c = 0x00, .l = 13 },
911 [0xe3] = { .c = 0x00, .l = 13 },
912 [0xe4] = { .c = 0x24, .l = 13 },
913 [0xe5] = { .c = 0x24, .l = 13 },
914 [0xe6] = { .c = 0x24, .l = 13 },
915 [0xe7] = { .c = 0x24, .l = 13 },
916 [0xe8] = { .c = 0x40, .l = 13 },
917 [0xe9] = { .c = 0x40, .l = 13 },
918 [0xea] = { .c = 0x40, .l = 13 },
919 [0xeb] = { .c = 0x40, .l = 13 },
920 [0xec] = { .c = 0x5b, .l = 13 },
921 [0xed] = { .c = 0x5b, .l = 13 },
922 [0xee] = { .c = 0x5b, .l = 13 },
923 [0xef] = { .c = 0x5b, .l = 13 },
924 [0xf0] = { .c = 0x5d, .l = 13 },
925 [0xf1] = { .c = 0x5d, .l = 13 },
926 [0xf2] = { .c = 0x5d, .l = 13 },
927 [0xf3] = { .c = 0x5d, .l = 13 },
928 [0xf4] = { .c = 0x7e, .l = 13 },
929 [0xf5] = { .c = 0x7e, .l = 13 },
930 [0xf6] = { .c = 0x7e, .l = 13 },
931 [0xf7] = { .c = 0x7e, .l = 13 },
932 [0xf8] = { .c = 0x5e, .l = 14 },
933 [0xf9] = { .c = 0x5e, .l = 14 },
934 [0xfa] = { .c = 0x7d, .l = 14 },
935 [0xfb] = { .c = 0x7d, .l = 14 },
936 [0xfc] = { .c = 0x3c, .l = 15 },
937 [0xfd] = { .c = 0x60, .l = 15 },
938 [0xfe] = { .c = 0x7b, .l = 15 },
939};
940
941struct rht rht_bit15_11_fe[32] = {
942 [0x00] = { .c = 0x5c, .l = 19 },
943 [0x01] = { .c = 0x5c, .l = 19 },
944 [0x02] = { .c = 0x5c, .l = 19 },
945 [0x03] = { .c = 0x5c, .l = 19 },
946 [0x04] = { .c = 0xc3, .l = 19 },
947 [0x05] = { .c = 0xc3, .l = 19 },
948 [0x06] = { .c = 0xc3, .l = 19 },
949 [0x07] = { .c = 0xc3, .l = 19 },
950 [0x08] = { .c = 0xd0, .l = 19 },
951 [0x09] = { .c = 0xd0, .l = 19 },
952 [0x0a] = { .c = 0xd0, .l = 19 },
953 [0x0b] = { .c = 0xd0, .l = 19 },
954 [0x0c] = { .c = 0x80, .l = 20 },
955 [0x0d] = { .c = 0x80, .l = 20 },
956 [0x0e] = { .c = 0x82, .l = 20 },
957 [0x0f] = { .c = 0x82, .l = 20 },
958 [0x10] = { .c = 0x83, .l = 20 },
959 [0x11] = { .c = 0x83, .l = 20 },
960 [0x12] = { .c = 0xa2, .l = 20 },
961 [0x13] = { .c = 0xa2, .l = 20 },
962 [0x14] = { .c = 0xb8, .l = 20 },
963 [0x15] = { .c = 0xb8, .l = 20 },
964 [0x16] = { .c = 0xc2, .l = 20 },
965 [0x17] = { .c = 0xc2, .l = 20 },
966 [0x18] = { .c = 0xe0, .l = 20 },
967 [0x19] = { .c = 0xe0, .l = 20 },
968 [0x1a] = { .c = 0xe2, .l = 20 },
969 [0x1b] = { .c = 0xe2, .l = 20 },
970 [0x1c] = { .c = 0x99, .l = 21 },
971 [0x1d] = { .c = 0xa1, .l = 21 },
972 [0x1e] = { .c = 0xa7, .l = 21 },
973 [0x1f] = { .c = 0xac, .l = 21 },
974};
975
976struct rht rht_bit15_8[256] = {
977 [0x00] = { .c = 0xb0, .l = 21 },
978 [0x01] = { .c = 0xb0, .l = 21 },
979 [0x02] = { .c = 0xb0, .l = 21 },
980 [0x03] = { .c = 0xb0, .l = 21 },
981 [0x04] = { .c = 0xb0, .l = 21 },
982 [0x05] = { .c = 0xb0, .l = 21 },
983 [0x06] = { .c = 0xb0, .l = 21 },
984 [0x07] = { .c = 0xb0, .l = 21 },
985 [0x08] = { .c = 0xb1, .l = 21 },
986 [0x09] = { .c = 0xb1, .l = 21 },
987 [0x0a] = { .c = 0xb1, .l = 21 },
988 [0x0b] = { .c = 0xb1, .l = 21 },
989 [0x0c] = { .c = 0xb1, .l = 21 },
990 [0x0d] = { .c = 0xb1, .l = 21 },
991 [0x0e] = { .c = 0xb1, .l = 21 },
992 [0x0f] = { .c = 0xb1, .l = 21 },
993 [0x10] = { .c = 0xb3, .l = 21 },
994 [0x11] = { .c = 0xb3, .l = 21 },
995 [0x12] = { .c = 0xb3, .l = 21 },
996 [0x13] = { .c = 0xb3, .l = 21 },
997 [0x14] = { .c = 0xb3, .l = 21 },
998 [0x15] = { .c = 0xb3, .l = 21 },
999 [0x16] = { .c = 0xb3, .l = 21 },
1000 [0x17] = { .c = 0xb3, .l = 21 },
1001 [0x18] = { .c = 0xd1, .l = 21 },
1002 [0x19] = { .c = 0xd1, .l = 21 },
1003 [0x1a] = { .c = 0xd1, .l = 21 },
1004 [0x1b] = { .c = 0xd1, .l = 21 },
1005 [0x1c] = { .c = 0xd1, .l = 21 },
1006 [0x1d] = { .c = 0xd1, .l = 21 },
1007 [0x1e] = { .c = 0xd1, .l = 21 },
1008 [0x1f] = { .c = 0xd1, .l = 21 },
1009 [0x20] = { .c = 0xd8, .l = 21 },
1010 [0x21] = { .c = 0xd8, .l = 21 },
1011 [0x22] = { .c = 0xd8, .l = 21 },
1012 [0x23] = { .c = 0xd8, .l = 21 },
1013 [0x24] = { .c = 0xd8, .l = 21 },
1014 [0x25] = { .c = 0xd8, .l = 21 },
1015 [0x26] = { .c = 0xd8, .l = 21 },
1016 [0x27] = { .c = 0xd8, .l = 21 },
1017 [0x28] = { .c = 0xd9, .l = 21 },
1018 [0x29] = { .c = 0xd9, .l = 21 },
1019 [0x2a] = { .c = 0xd9, .l = 21 },
1020 [0x2b] = { .c = 0xd9, .l = 21 },
1021 [0x2c] = { .c = 0xd9, .l = 21 },
1022 [0x2d] = { .c = 0xd9, .l = 21 },
1023 [0x2e] = { .c = 0xd9, .l = 21 },
1024 [0x2f] = { .c = 0xd9, .l = 21 },
1025 [0x30] = { .c = 0xe3, .l = 21 },
1026 [0x31] = { .c = 0xe3, .l = 21 },
1027 [0x32] = { .c = 0xe3, .l = 21 },
1028 [0x33] = { .c = 0xe3, .l = 21 },
1029 [0x34] = { .c = 0xe3, .l = 21 },
1030 [0x35] = { .c = 0xe3, .l = 21 },
1031 [0x36] = { .c = 0xe3, .l = 21 },
1032 [0x37] = { .c = 0xe3, .l = 21 },
1033 [0x38] = { .c = 0xe5, .l = 21 },
1034 [0x39] = { .c = 0xe5, .l = 21 },
1035 [0x3a] = { .c = 0xe5, .l = 21 },
1036 [0x3b] = { .c = 0xe5, .l = 21 },
1037 [0x3c] = { .c = 0xe5, .l = 21 },
1038 [0x3d] = { .c = 0xe5, .l = 21 },
1039 [0x3e] = { .c = 0xe5, .l = 21 },
1040 [0x3f] = { .c = 0xe5, .l = 21 },
1041 [0x40] = { .c = 0xe6, .l = 21 },
1042 [0x41] = { .c = 0xe6, .l = 21 },
1043 [0x42] = { .c = 0xe6, .l = 21 },
1044 [0x43] = { .c = 0xe6, .l = 21 },
1045 [0x44] = { .c = 0xe6, .l = 21 },
1046 [0x45] = { .c = 0xe6, .l = 21 },
1047 [0x46] = { .c = 0xe6, .l = 21 },
1048 [0x47] = { .c = 0xe6, .l = 21 },
1049 [0x48] = { .c = 0x81, .l = 22 },
1050 [0x49] = { .c = 0x81, .l = 22 },
1051 [0x4a] = { .c = 0x81, .l = 22 },
1052 [0x4b] = { .c = 0x81, .l = 22 },
1053 [0x4c] = { .c = 0x84, .l = 22 },
1054 [0x4d] = { .c = 0x84, .l = 22 },
1055 [0x4e] = { .c = 0x84, .l = 22 },
1056 [0x4f] = { .c = 0x84, .l = 22 },
1057 [0x50] = { .c = 0x85, .l = 22 },
1058 [0x51] = { .c = 0x85, .l = 22 },
1059 [0x52] = { .c = 0x85, .l = 22 },
1060 [0x53] = { .c = 0x85, .l = 22 },
1061 [0x54] = { .c = 0x86, .l = 22 },
1062 [0x55] = { .c = 0x86, .l = 22 },
1063 [0x56] = { .c = 0x86, .l = 22 },
1064 [0x57] = { .c = 0x86, .l = 22 },
1065 [0x58] = { .c = 0x88, .l = 22 },
1066 [0x59] = { .c = 0x88, .l = 22 },
1067 [0x5a] = { .c = 0x88, .l = 22 },
1068 [0x5b] = { .c = 0x88, .l = 22 },
1069 [0x5c] = { .c = 0x92, .l = 22 },
1070 [0x5d] = { .c = 0x92, .l = 22 },
1071 [0x5e] = { .c = 0x92, .l = 22 },
1072 [0x5f] = { .c = 0x92, .l = 22 },
1073 [0x60] = { .c = 0x9a, .l = 22 },
1074 [0x61] = { .c = 0x9a, .l = 22 },
1075 [0x62] = { .c = 0x9a, .l = 22 },
1076 [0x63] = { .c = 0x9a, .l = 22 },
1077 [0x64] = { .c = 0x9c, .l = 22 },
1078 [0x65] = { .c = 0x9c, .l = 22 },
1079 [0x66] = { .c = 0x9c, .l = 22 },
1080 [0x67] = { .c = 0x9c, .l = 22 },
1081 [0x68] = { .c = 0xa0, .l = 22 },
1082 [0x69] = { .c = 0xa0, .l = 22 },
1083 [0x6a] = { .c = 0xa0, .l = 22 },
1084 [0x6b] = { .c = 0xa0, .l = 22 },
1085 [0x6c] = { .c = 0xa3, .l = 22 },
1086 [0x6d] = { .c = 0xa3, .l = 22 },
1087 [0x6e] = { .c = 0xa3, .l = 22 },
1088 [0x6f] = { .c = 0xa3, .l = 22 },
1089 [0x70] = { .c = 0xa4, .l = 22 },
1090 [0x71] = { .c = 0xa4, .l = 22 },
1091 [0x72] = { .c = 0xa4, .l = 22 },
1092 [0x73] = { .c = 0xa4, .l = 22 },
1093 [0x74] = { .c = 0xa9, .l = 22 },
1094 [0x75] = { .c = 0xa9, .l = 22 },
1095 [0x76] = { .c = 0xa9, .l = 22 },
1096 [0x77] = { .c = 0xa9, .l = 22 },
1097 [0x78] = { .c = 0xaa, .l = 22 },
1098 [0x79] = { .c = 0xaa, .l = 22 },
1099 [0x7a] = { .c = 0xaa, .l = 22 },
1100 [0x7b] = { .c = 0xaa, .l = 22 },
1101 [0x7c] = { .c = 0xad, .l = 22 },
1102 [0x7d] = { .c = 0xad, .l = 22 },
1103 [0x7e] = { .c = 0xad, .l = 22 },
1104 [0x7f] = { .c = 0xad, .l = 22 },
1105 [0x80] = { .c = 0xb2, .l = 22 },
1106 [0x81] = { .c = 0xb2, .l = 22 },
1107 [0x82] = { .c = 0xb2, .l = 22 },
1108 [0x83] = { .c = 0xb2, .l = 22 },
1109 [0x84] = { .c = 0xb5, .l = 22 },
1110 [0x85] = { .c = 0xb5, .l = 22 },
1111 [0x86] = { .c = 0xb5, .l = 22 },
1112 [0x87] = { .c = 0xb5, .l = 22 },
1113 [0x88] = { .c = 0xb9, .l = 22 },
1114 [0x89] = { .c = 0xb9, .l = 22 },
1115 [0x8a] = { .c = 0xb9, .l = 22 },
1116 [0x8b] = { .c = 0xb9, .l = 22 },
1117 [0x8c] = { .c = 0xba, .l = 22 },
1118 [0x8d] = { .c = 0xba, .l = 22 },
1119 [0x8e] = { .c = 0xba, .l = 22 },
1120 [0x8f] = { .c = 0xba, .l = 22 },
1121 [0x90] = { .c = 0xbb, .l = 22 },
1122 [0x91] = { .c = 0xbb, .l = 22 },
1123 [0x92] = { .c = 0xbb, .l = 22 },
1124 [0x93] = { .c = 0xbb, .l = 22 },
1125 [0x94] = { .c = 0xbd, .l = 22 },
1126 [0x95] = { .c = 0xbd, .l = 22 },
1127 [0x96] = { .c = 0xbd, .l = 22 },
1128 [0x97] = { .c = 0xbd, .l = 22 },
1129 [0x98] = { .c = 0xbe, .l = 22 },
1130 [0x99] = { .c = 0xbe, .l = 22 },
1131 [0x9a] = { .c = 0xbe, .l = 22 },
1132 [0x9b] = { .c = 0xbe, .l = 22 },
1133 [0x9c] = { .c = 0xc4, .l = 22 },
1134 [0x9d] = { .c = 0xc4, .l = 22 },
1135 [0x9e] = { .c = 0xc4, .l = 22 },
1136 [0x9f] = { .c = 0xc4, .l = 22 },
1137 [0xa0] = { .c = 0xc6, .l = 22 },
1138 [0xa1] = { .c = 0xc6, .l = 22 },
1139 [0xa2] = { .c = 0xc6, .l = 22 },
1140 [0xa3] = { .c = 0xc6, .l = 22 },
1141 [0xa4] = { .c = 0xe4, .l = 22 },
1142 [0xa5] = { .c = 0xe4, .l = 22 },
1143 [0xa6] = { .c = 0xe4, .l = 22 },
1144 [0xa7] = { .c = 0xe4, .l = 22 },
1145 [0xa8] = { .c = 0xe8, .l = 22 },
1146 [0xa9] = { .c = 0xe8, .l = 22 },
1147 [0xaa] = { .c = 0xe8, .l = 22 },
1148 [0xab] = { .c = 0xe8, .l = 22 },
1149 [0xac] = { .c = 0xe9, .l = 22 },
1150 [0xad] = { .c = 0xe9, .l = 22 },
1151 [0xae] = { .c = 0xe9, .l = 22 },
1152 [0xaf] = { .c = 0xe9, .l = 22 },
1153 [0xb0] = { .c = 0x01, .l = 23 },
1154 [0xb1] = { .c = 0x01, .l = 23 },
1155 [0xb2] = { .c = 0x87, .l = 23 },
1156 [0xb3] = { .c = 0x87, .l = 23 },
1157 [0xb4] = { .c = 0x89, .l = 23 },
1158 [0xb5] = { .c = 0x89, .l = 23 },
1159 [0xb6] = { .c = 0x8a, .l = 23 },
1160 [0xb7] = { .c = 0x8a, .l = 23 },
1161 [0xb8] = { .c = 0x8b, .l = 23 },
1162 [0xb9] = { .c = 0x8b, .l = 23 },
1163 [0xba] = { .c = 0x8c, .l = 23 },
1164 [0xbb] = { .c = 0x8c, .l = 23 },
1165 [0xbc] = { .c = 0x8d, .l = 23 },
1166 [0xbd] = { .c = 0x8d, .l = 23 },
1167 [0xbe] = { .c = 0x8f, .l = 23 },
1168 [0xbf] = { .c = 0x8f, .l = 23 },
1169 [0xc0] = { .c = 0x93, .l = 23 },
1170 [0xc1] = { .c = 0x93, .l = 23 },
1171 [0xc2] = { .c = 0x95, .l = 23 },
1172 [0xc3] = { .c = 0x95, .l = 23 },
1173 [0xc4] = { .c = 0x96, .l = 23 },
1174 [0xc5] = { .c = 0x96, .l = 23 },
1175 [0xc6] = { .c = 0x97, .l = 23 },
1176 [0xc7] = { .c = 0x97, .l = 23 },
1177 [0xc8] = { .c = 0x98, .l = 23 },
1178 [0xc9] = { .c = 0x98, .l = 23 },
1179 [0xca] = { .c = 0x9b, .l = 23 },
1180 [0xcb] = { .c = 0x9b, .l = 23 },
1181 [0xcc] = { .c = 0x9d, .l = 23 },
1182 [0xcd] = { .c = 0x9d, .l = 23 },
1183 [0xce] = { .c = 0x9e, .l = 23 },
1184 [0xcf] = { .c = 0x9e, .l = 23 },
1185 [0xd0] = { .c = 0xa5, .l = 23 },
1186 [0xd1] = { .c = 0xa5, .l = 23 },
1187 [0xd2] = { .c = 0xa6, .l = 23 },
1188 [0xd3] = { .c = 0xa6, .l = 23 },
1189 [0xd4] = { .c = 0xa8, .l = 23 },
1190 [0xd5] = { .c = 0xa8, .l = 23 },
1191 [0xd6] = { .c = 0xae, .l = 23 },
1192 [0xd7] = { .c = 0xae, .l = 23 },
1193 [0xd8] = { .c = 0xaf, .l = 23 },
1194 [0xd9] = { .c = 0xaf, .l = 23 },
1195 [0xda] = { .c = 0xb4, .l = 23 },
1196 [0xdb] = { .c = 0xb4, .l = 23 },
1197 [0xdc] = { .c = 0xb6, .l = 23 },
1198 [0xdd] = { .c = 0xb6, .l = 23 },
1199 [0xde] = { .c = 0xb7, .l = 23 },
1200 [0xdf] = { .c = 0xb7, .l = 23 },
1201 [0xe0] = { .c = 0xbc, .l = 23 },
1202 [0xe1] = { .c = 0xbc, .l = 23 },
1203 [0xe2] = { .c = 0xbf, .l = 23 },
1204 [0xe3] = { .c = 0xbf, .l = 23 },
1205 [0xe4] = { .c = 0xc5, .l = 23 },
1206 [0xe5] = { .c = 0xc5, .l = 23 },
1207 [0xe6] = { .c = 0xe7, .l = 23 },
1208 [0xe7] = { .c = 0xe7, .l = 23 },
1209 [0xe8] = { .c = 0xef, .l = 23 },
1210 [0xe9] = { .c = 0xef, .l = 23 },
1211 [0xea] = { .c = 0x09, .l = 24 },
1212 [0xeb] = { .c = 0x8e, .l = 24 },
1213 [0xec] = { .c = 0x90, .l = 24 },
1214 [0xed] = { .c = 0x91, .l = 24 },
1215 [0xee] = { .c = 0x94, .l = 24 },
1216 [0xef] = { .c = 0x9f, .l = 24 },
1217 [0xf0] = { .c = 0xab, .l = 24 },
1218 [0xf1] = { .c = 0xce, .l = 24 },
1219 [0xf2] = { .c = 0xd7, .l = 24 },
1220 [0xf3] = { .c = 0xe1, .l = 24 },
1221 [0xf4] = { .c = 0xec, .l = 24 },
1222 [0xf5] = { .c = 0xed, .l = 24 },
1223};
1224
1225struct rht rht_bit11_4[256] = {
1226 [0x60] = { .c = 0xc7, .l = 25 },
1227 [0x61] = { .c = 0xc7, .l = 25 },
1228 [0x62] = { .c = 0xc7, .l = 25 },
1229 [0x63] = { .c = 0xc7, .l = 25 },
1230 [0x64] = { .c = 0xc7, .l = 25 },
1231 [0x65] = { .c = 0xc7, .l = 25 },
1232 [0x66] = { .c = 0xc7, .l = 25 },
1233 [0x67] = { .c = 0xc7, .l = 25 },
1234 [0x68] = { .c = 0xcf, .l = 25 },
1235 [0x69] = { .c = 0xcf, .l = 25 },
1236 [0x6a] = { .c = 0xcf, .l = 25 },
1237 [0x6b] = { .c = 0xcf, .l = 25 },
1238 [0x6c] = { .c = 0xcf, .l = 25 },
1239 [0x6d] = { .c = 0xcf, .l = 25 },
1240 [0x6e] = { .c = 0xcf, .l = 25 },
1241 [0x6f] = { .c = 0xcf, .l = 25 },
1242 [0x70] = { .c = 0xea, .l = 25 },
1243 [0x71] = { .c = 0xea, .l = 25 },
1244 [0x72] = { .c = 0xea, .l = 25 },
1245 [0x73] = { .c = 0xea, .l = 25 },
1246 [0x74] = { .c = 0xea, .l = 25 },
1247 [0x75] = { .c = 0xea, .l = 25 },
1248 [0x76] = { .c = 0xea, .l = 25 },
1249 [0x77] = { .c = 0xea, .l = 25 },
1250 [0x78] = { .c = 0xeb, .l = 25 },
1251 [0x79] = { .c = 0xeb, .l = 25 },
1252 [0x7a] = { .c = 0xeb, .l = 25 },
1253 [0x7b] = { .c = 0xeb, .l = 25 },
1254 [0x7c] = { .c = 0xeb, .l = 25 },
1255 [0x7d] = { .c = 0xeb, .l = 25 },
1256 [0x7e] = { .c = 0xeb, .l = 25 },
1257 [0x7f] = { .c = 0xeb, .l = 25 },
1258 [0x80] = { .c = 0xc0, .l = 26 },
1259 [0x81] = { .c = 0xc0, .l = 26 },
1260 [0x82] = { .c = 0xc0, .l = 26 },
1261 [0x83] = { .c = 0xc0, .l = 26 },
1262 [0x84] = { .c = 0xc1, .l = 26 },
1263 [0x85] = { .c = 0xc1, .l = 26 },
1264 [0x86] = { .c = 0xc1, .l = 26 },
1265 [0x87] = { .c = 0xc1, .l = 26 },
1266 [0x88] = { .c = 0xc8, .l = 26 },
1267 [0x89] = { .c = 0xc8, .l = 26 },
1268 [0x8a] = { .c = 0xc8, .l = 26 },
1269 [0x8b] = { .c = 0xc8, .l = 26 },
1270 [0x8c] = { .c = 0xc9, .l = 26 },
1271 [0x8d] = { .c = 0xc9, .l = 26 },
1272 [0x8e] = { .c = 0xc9, .l = 26 },
1273 [0x8f] = { .c = 0xc9, .l = 26 },
1274 [0x90] = { .c = 0xca, .l = 26 },
1275 [0x91] = { .c = 0xca, .l = 26 },
1276 [0x92] = { .c = 0xca, .l = 26 },
1277 [0x93] = { .c = 0xca, .l = 26 },
1278 [0x94] = { .c = 0xcd, .l = 26 },
1279 [0x95] = { .c = 0xcd, .l = 26 },
1280 [0x96] = { .c = 0xcd, .l = 26 },
1281 [0x97] = { .c = 0xcd, .l = 26 },
1282 [0x98] = { .c = 0xd2, .l = 26 },
1283 [0x99] = { .c = 0xd2, .l = 26 },
1284 [0x9a] = { .c = 0xd2, .l = 26 },
1285 [0x9b] = { .c = 0xd2, .l = 26 },
1286 [0x9c] = { .c = 0xd5, .l = 26 },
1287 [0x9d] = { .c = 0xd5, .l = 26 },
1288 [0x9e] = { .c = 0xd5, .l = 26 },
1289 [0x9f] = { .c = 0xd5, .l = 26 },
1290 [0xa0] = { .c = 0xda, .l = 26 },
1291 [0xa1] = { .c = 0xda, .l = 26 },
1292 [0xa2] = { .c = 0xda, .l = 26 },
1293 [0xa3] = { .c = 0xda, .l = 26 },
1294 [0xa4] = { .c = 0xdb, .l = 26 },
1295 [0xa5] = { .c = 0xdb, .l = 26 },
1296 [0xa6] = { .c = 0xdb, .l = 26 },
1297 [0xa7] = { .c = 0xdb, .l = 26 },
1298 [0xa8] = { .c = 0xee, .l = 26 },
1299 [0xa9] = { .c = 0xee, .l = 26 },
1300 [0xaa] = { .c = 0xee, .l = 26 },
1301 [0xab] = { .c = 0xee, .l = 26 },
1302 [0xac] = { .c = 0xf0, .l = 26 },
1303 [0xad] = { .c = 0xf0, .l = 26 },
1304 [0xae] = { .c = 0xf0, .l = 26 },
1305 [0xaf] = { .c = 0xf0, .l = 26 },
1306 [0xb0] = { .c = 0xf2, .l = 26 },
1307 [0xb1] = { .c = 0xf2, .l = 26 },
1308 [0xb2] = { .c = 0xf2, .l = 26 },
1309 [0xb3] = { .c = 0xf2, .l = 26 },
1310 [0xb4] = { .c = 0xf3, .l = 26 },
1311 [0xb5] = { .c = 0xf3, .l = 26 },
1312 [0xb6] = { .c = 0xf3, .l = 26 },
1313 [0xb7] = { .c = 0xf3, .l = 26 },
1314 [0xb8] = { .c = 0xff, .l = 26 },
1315 [0xb9] = { .c = 0xff, .l = 26 },
1316 [0xba] = { .c = 0xff, .l = 26 },
1317 [0xbb] = { .c = 0xff, .l = 26 },
1318 [0xbc] = { .c = 0xcb, .l = 27 },
1319 [0xbd] = { .c = 0xcb, .l = 27 },
1320 [0xbe] = { .c = 0xcc, .l = 27 },
1321 [0xbf] = { .c = 0xcc, .l = 27 },
1322 [0xc0] = { .c = 0xd3, .l = 27 },
1323 [0xc1] = { .c = 0xd3, .l = 27 },
1324 [0xc2] = { .c = 0xd4, .l = 27 },
1325 [0xc3] = { .c = 0xd4, .l = 27 },
1326 [0xc4] = { .c = 0xd6, .l = 27 },
1327 [0xc5] = { .c = 0xd6, .l = 27 },
1328 [0xc6] = { .c = 0xdd, .l = 27 },
1329 [0xc7] = { .c = 0xdd, .l = 27 },
1330 [0xc8] = { .c = 0xde, .l = 27 },
1331 [0xc9] = { .c = 0xde, .l = 27 },
1332 [0xca] = { .c = 0xdf, .l = 27 },
1333 [0xcb] = { .c = 0xdf, .l = 27 },
1334 [0xcc] = { .c = 0xf1, .l = 27 },
1335 [0xcd] = { .c = 0xf1, .l = 27 },
1336 [0xce] = { .c = 0xf4, .l = 27 },
1337 [0xcf] = { .c = 0xf4, .l = 27 },
1338 [0xd0] = { .c = 0xf5, .l = 27 },
1339 [0xd1] = { .c = 0xf5, .l = 27 },
1340 [0xd2] = { .c = 0xf6, .l = 27 },
1341 [0xd3] = { .c = 0xf6, .l = 27 },
1342 [0xd4] = { .c = 0xf7, .l = 27 },
1343 [0xd5] = { .c = 0xf7, .l = 27 },
1344 [0xd6] = { .c = 0xf8, .l = 27 },
1345 [0xd7] = { .c = 0xf8, .l = 27 },
1346 [0xd8] = { .c = 0xfa, .l = 27 },
1347 [0xd9] = { .c = 0xfa, .l = 27 },
1348 [0xda] = { .c = 0xfb, .l = 27 },
1349 [0xdb] = { .c = 0xfb, .l = 27 },
1350 [0xdc] = { .c = 0xfc, .l = 27 },
1351 [0xdd] = { .c = 0xfc, .l = 27 },
1352 [0xde] = { .c = 0xfd, .l = 27 },
1353 [0xdf] = { .c = 0xfd, .l = 27 },
1354 [0xe0] = { .c = 0xfe, .l = 27 },
1355 [0xe1] = { .c = 0xfe, .l = 27 },
1356 [0xe2] = { .c = 0x02, .l = 28 },
1357 [0xe3] = { .c = 0x03, .l = 28 },
1358 [0xe4] = { .c = 0x04, .l = 28 },
1359 [0xe5] = { .c = 0x05, .l = 28 },
1360 [0xe6] = { .c = 0x06, .l = 28 },
1361 [0xe7] = { .c = 0x07, .l = 28 },
1362 [0xe8] = { .c = 0x08, .l = 28 },
1363 [0xe9] = { .c = 0x0b, .l = 28 },
1364 [0xea] = { .c = 0x0c, .l = 28 },
1365 [0xeb] = { .c = 0x0e, .l = 28 },
1366 [0xec] = { .c = 0x0f, .l = 28 },
1367 [0xed] = { .c = 0x10, .l = 28 },
1368 [0xee] = { .c = 0x11, .l = 28 },
1369 [0xef] = { .c = 0x12, .l = 28 },
1370 [0xf0] = { .c = 0x13, .l = 28 },
1371 [0xf1] = { .c = 0x14, .l = 28 },
1372 [0xf2] = { .c = 0x15, .l = 28 },
1373 [0xf3] = { .c = 0x17, .l = 28 },
1374 [0xf4] = { .c = 0x18, .l = 28 },
1375 [0xf5] = { .c = 0x19, .l = 28 },
1376 [0xf6] = { .c = 0x1a, .l = 28 },
1377 [0xf7] = { .c = 0x1b, .l = 28 },
1378 [0xf8] = { .c = 0x1c, .l = 28 },
1379 [0xf9] = { .c = 0x1d, .l = 28 },
1380 [0xfa] = { .c = 0x1e, .l = 28 },
1381 [0xfb] = { .c = 0x1f, .l = 28 },
1382 [0xfc] = { .c = 0x7f, .l = 28 },
1383 [0xfd] = { .c = 0xdc, .l = 28 },
1384 [0xfe] = { .c = 0xf9, .l = 28 },
1385 [0xff] = { .c = 0x0a, .l = 30 },
1386 /* Note, when l==30, bits 2..3 give 00:0x0a, 01:0x0d, 10:0x16, 11:EOS */
1387};
1388
1389/* huffman-encode string <s> into the huff_tmp buffer and returns the amount
1390 * of output bytes. The caller must ensure the output is large enough (ie at
1391 * least 4 times as long as s).
1392 *
1393 * FIXME: bits are only counted for now, no code is emitted!
1394 */
1395int huff_enc(const char *s, char *out)
1396{
1397 int bits = 0;
1398
1399 while (*s) {
1400 bits += ht[(uint8_t)*s].b;
1401 s++;
1402 }
1403 bits += 7;
1404
1405 /* FIXME: huffman code is not emitted yet. */
1406 //memset(out, 'H', bits / 8);
1407 return bits / 8;
1408}
1409
1410/* pass a huffman string, it will decode it and return the new output size or
1411 * -1 in case of error.
1412 *
1413 * The principle of the decoder is to lookup full bytes in reverse-huffman
1414 * tables. Since we may need up to 30 bits and the word positions are not
1415 * always multiples of 8, we build the code word by shifting the "current"
1416 * 32-bit word and the "next" one of the appropriate amount of bits. Once
1417 * the shift goes beyond 32, words are swapped and the "next" one is refilled
1418 * with new bytes. Shift operations are cheap when done a single time like this.
1419 * On 64-bit platforms it is possible to further improve this by storing both
1420 * of them in a single word.
1421 */
1422int huff_dec(const uint8_t *huff, int hlen, char *out, int olen)
1423{
1424 char *out_start = out;
1425 char *out_end = out + olen;
1426 const uint8_t *huff_end = huff + hlen;
1427 uint32_t curr = 0;
1428 uint32_t next = 0;
1429 uint32_t shift;
1430 uint32_t code; /* The 30-bit code being looked up, MSB-aligned */
1431 uint8_t sym;
1432 int bleft; /* bits left */
1433 int l;
1434
1435 code = 0;
1436 shift = 64; // start with an empty buffer
1437 bleft = hlen << 3;
1438 while (bleft > 0 && out != out_end) {
1439 while (shift >= 32) {
1440 curr = next;
1441
1442 /* read up to 4 bytes into next. FIXME: this should
1443 * later be optimized to perform a single 32-bit big
1444 * endian read when unaligned accesses are possible.
1445 */
1446 next = 0;
1447
1448 if (huff + 4 <= huff_end) {
1449 next = (huff[0] << 24) + (huff[1] << 16) + (huff[2] << 8) + huff[3];
1450 huff += 4;
1451 }
1452 else {
1453 /* note: we append 0 and not 0xff so that we can
1454 * distinguish shifted bits from a really inserted
1455 * EOS.
1456 */
1457 next = (((huff + 0 < huff_end) ? huff[0] : 0x00) << 24) +
1458 (((huff + 1 < huff_end) ? huff[1] : 0x00) << 16) +
1459 (((huff + 2 < huff_end) ? huff[2] : 0x00) << 8) +
1460 ((huff + 3 < huff_end) ? huff[3] : 0x00);
1461 huff = huff_end;
1462 }
1463
1464 shift -= 32;
1465 }
1466
1467 /* curr:next contain 64 bit of huffman code */
1468 code = curr;
1469 if (shift)
1470 code = (code << shift) + (next >> (32 - shift));
1471
1472 /* now we necessarily have 32 bits available */
1473 if ((code >> 24) < 0xfe) {
1474 /* single byte */
1475 l = rht_bit31_24[code >> 24].l;
1476 sym = rht_bit31_24[code >> 24].c;
1477 }
1478 else if (((code >> 17) & 0xff) < 0xff) {
1479 /* two bytes, 0xfe + 2 bits or 0xff + 2..7 bits */
1480 l = rht_bit24_17[(code >> 17) & 0xff].l;
1481 sym = rht_bit24_17[(code >> 17) & 0xff].c;
1482 }
1483 else if (((code >> 16) & 0xff) < 0xff) { /* 3..5 bits */
1484 /* 0xff + 0xfe + 3..5 bits or
1485 * 0xff + 0xff + 5..8 bits for values till 0xf5
1486 */
1487 l = rht_bit15_11_fe[(code >> 11) & 0x1f].l;
1488 sym = rht_bit15_11_fe[(code >> 11) & 0x1f].c;
1489 }
1490 else if (((code >> 8) & 0xff) < 0xf6) { /* 5..8 bits */
1491 /* that's 0xff + 0xff */
1492 l = rht_bit15_8[(code >> 8) & 0xff].l;
1493 sym = rht_bit15_8[(code >> 8) & 0xff].c;
1494 }
1495 else {
1496 /* 0xff 0xff 0xf6..0xff */
1497 l = rht_bit11_4[(code >> 4) & 0xff].l;
1498 if (l < 30)
1499 sym = rht_bit11_4[(code >> 4) & 0xff].c;
1500 else if ((code & 0xff) == 0xf0)
1501 sym = 10;
1502 else if ((code & 0xff) == 0xf4)
1503 sym = 13;
1504 else if ((code & 0xff) == 0xf8)
1505 sym = 22;
1506 else { // 0xfc : EOS
1507 break;
1508 }
1509 }
1510
1511 if (!l || bleft - l < 0)
1512 break;
1513
1514 bleft -= l;
1515 shift += l;
1516 *out++ = sym;
1517 }
1518
1519 if (bleft > 0) {
1520 /* some bits were not consumed after the last code, they must
1521 * match EOS (ie: all ones).
1522 */
1523 if ((code & -(1 << (32 - bleft))) != (uint32_t)-(1 << (32 - bleft)))
1524 return -1;
1525 }
1526
1527 if (out < out_end)
1528 *out = 0; // end of string whenever possible
1529 return out - out_start;
1530}