Gitiles
Code Review Sign In
git01.mediatek.com / haproxy / f052354892ec0d611f24f2512b916947cfd580b4 / . / contrib / hpack / gen-rht.c
blob: b1b9031725577cd0321c3fb55b38d7674e2f42f9 [file] [log] [blame]
Willy Tarreau8071eae2017-05-19 18:14:51 +0200[diff] [blame]1/* Reverse Huffman table generator for HPACK decoder - 2017-05-19 Willy Tarreau
2 *
3 * rht_bit31_24[256] is indexed on bits 31..24 when < 0xfe
4 * rht_bit24_17[256] is indexed on bits 24..17 when 31..24 >= 0xfe
5 * rht_bit15_11_fe[32] is indexed on bits 15..11 when 24..17 == 0xfe
6 * rht_bit15_8[256] is indexed on bits 15..8 when 24..17 == 0xff
7 * rht_bit11_4[256] is indexed on bits 11..4 when 15..8 == 0xff
8 * when 11..4 == 0xff, 3..2 provide the following mapping :
9 * 00 => 0x0a, 01 => 0x0d, 10 => 0x16, 11 => EOS
10 */
11
12#include <stdint.h>
13#include <stdio.h>
14#include <stdlib.h>
15#include <string.h>
16
17/* from RFC7541 Appendix B */
18static const struct huff {
19 uint32_t c; /* code point */
20 int b; /* bits */
21} ht[257] = {
22 [0] = { .c = 0x00001ff8, .b = 13 },
23 [1] = { .c = 0x007fffd8, .b = 23 },
24 [2] = { .c = 0x0fffffe2, .b = 28 },
25 [3] = { .c = 0x0fffffe3, .b = 28 },
26 [4] = { .c = 0x0fffffe4, .b = 28 },
27 [5] = { .c = 0x0fffffe5, .b = 28 },
28 [6] = { .c = 0x0fffffe6, .b = 28 },
29 [7] = { .c = 0x0fffffe7, .b = 28 },
30 [8] = { .c = 0x0fffffe8, .b = 28 },
31 [9] = { .c = 0x00ffffea, .b = 24 },
32 [10] = { .c = 0x3ffffffc, .b = 30 },
33 [11] = { .c = 0x0fffffe9, .b = 28 },
34 [12] = { .c = 0x0fffffea, .b = 28 },
35 [13] = { .c = 0x3ffffffd, .b = 30 },
36 [14] = { .c = 0x0fffffeb, .b = 28 },
37 [15] = { .c = 0x0fffffec, .b = 28 },
38 [16] = { .c = 0x0fffffed, .b = 28 },
39 [17] = { .c = 0x0fffffee, .b = 28 },
40 [18] = { .c = 0x0fffffef, .b = 28 },
41 [19] = { .c = 0x0ffffff0, .b = 28 },
42 [20] = { .c = 0x0ffffff1, .b = 28 },
43 [21] = { .c = 0x0ffffff2, .b = 28 },
44 [22] = { .c = 0x3ffffffe, .b = 30 },
45 [23] = { .c = 0x0ffffff3, .b = 28 },
46 [24] = { .c = 0x0ffffff4, .b = 28 },
47 [25] = { .c = 0x0ffffff5, .b = 28 },
48 [26] = { .c = 0x0ffffff6, .b = 28 },
49 [27] = { .c = 0x0ffffff7, .b = 28 },
50 [28] = { .c = 0x0ffffff8, .b = 28 },
51 [29] = { .c = 0x0ffffff9, .b = 28 },
52 [30] = { .c = 0x0ffffffa, .b = 28 },
53 [31] = { .c = 0x0ffffffb, .b = 28 },
54 [32] = { .c = 0x00000014, .b = 6 },
55 [33] = { .c = 0x000003f8, .b = 10 },
56 [34] = { .c = 0x000003f9, .b = 10 },
57 [35] = { .c = 0x00000ffa, .b = 12 },
58 [36] = { .c = 0x00001ff9, .b = 13 },
59 [37] = { .c = 0x00000015, .b = 6 },
60 [38] = { .c = 0x000000f8, .b = 8 },
61 [39] = { .c = 0x000007fa, .b = 11 },
62 [40] = { .c = 0x000003fa, .b = 10 },
63 [41] = { .c = 0x000003fb, .b = 10 },
64 [42] = { .c = 0x000000f9, .b = 8 },
65 [43] = { .c = 0x000007fb, .b = 11 },
66 [44] = { .c = 0x000000fa, .b = 8 },
67 [45] = { .c = 0x00000016, .b = 6 },
68 [46] = { .c = 0x00000017, .b = 6 },
69 [47] = { .c = 0x00000018, .b = 6 },
70 [48] = { .c = 0x00000000, .b = 5 },
71 [49] = { .c = 0x00000001, .b = 5 },
72 [50] = { .c = 0x00000002, .b = 5 },
73 [51] = { .c = 0x00000019, .b = 6 },
74 [52] = { .c = 0x0000001a, .b = 6 },
75 [53] = { .c = 0x0000001b, .b = 6 },
76 [54] = { .c = 0x0000001c, .b = 6 },
77 [55] = { .c = 0x0000001d, .b = 6 },
78 [56] = { .c = 0x0000001e, .b = 6 },
79 [57] = { .c = 0x0000001f, .b = 6 },
80 [58] = { .c = 0x0000005c, .b = 7 },
81 [59] = { .c = 0x000000fb, .b = 8 },
82 [60] = { .c = 0x00007ffc, .b = 15 },
83 [61] = { .c = 0x00000020, .b = 6 },
84 [62] = { .c = 0x00000ffb, .b = 12 },
85 [63] = { .c = 0x000003fc, .b = 10 },
86 [64] = { .c = 0x00001ffa, .b = 13 },
87 [65] = { .c = 0x00000021, .b = 6 },
88 [66] = { .c = 0x0000005d, .b = 7 },
89 [67] = { .c = 0x0000005e, .b = 7 },
90 [68] = { .c = 0x0000005f, .b = 7 },
91 [69] = { .c = 0x00000060, .b = 7 },
92 [70] = { .c = 0x00000061, .b = 7 },
93 [71] = { .c = 0x00000062, .b = 7 },
94 [72] = { .c = 0x00000063, .b = 7 },
95 [73] = { .c = 0x00000064, .b = 7 },
96 [74] = { .c = 0x00000065, .b = 7 },
97 [75] = { .c = 0x00000066, .b = 7 },
98 [76] = { .c = 0x00000067, .b = 7 },
99 [77] = { .c = 0x00000068, .b = 7 },
100 [78] = { .c = 0x00000069, .b = 7 },
101 [79] = { .c = 0x0000006a, .b = 7 },
102 [80] = { .c = 0x0000006b, .b = 7 },
103 [81] = { .c = 0x0000006c, .b = 7 },
104 [82] = { .c = 0x0000006d, .b = 7 },
105 [83] = { .c = 0x0000006e, .b = 7 },
106 [84] = { .c = 0x0000006f, .b = 7 },
107 [85] = { .c = 0x00000070, .b = 7 },
108 [86] = { .c = 0x00000071, .b = 7 },
109 [87] = { .c = 0x00000072, .b = 7 },
110 [88] = { .c = 0x000000fc, .b = 8 },
111 [89] = { .c = 0x00000073, .b = 7 },
112 [90] = { .c = 0x000000fd, .b = 8 },
113 [91] = { .c = 0x00001ffb, .b = 13 },
114 [92] = { .c = 0x0007fff0, .b = 19 },
115 [93] = { .c = 0x00001ffc, .b = 13 },
116 [94] = { .c = 0x00003ffc, .b = 14 },
117 [95] = { .c = 0x00000022, .b = 6 },
118 [96] = { .c = 0x00007ffd, .b = 15 },
119 [97] = { .c = 0x00000003, .b = 5 },
120 [98] = { .c = 0x00000023, .b = 6 },
121 [99] = { .c = 0x00000004, .b = 5 },
122 [100] = { .c = 0x00000024, .b = 6 },
123 [101] = { .c = 0x00000005, .b = 5 },
124 [102] = { .c = 0x00000025, .b = 6 },
125 [103] = { .c = 0x00000026, .b = 6 },
126 [104] = { .c = 0x00000027, .b = 6 },
127 [105] = { .c = 0x00000006, .b = 5 },
128 [106] = { .c = 0x00000074, .b = 7 },
129 [107] = { .c = 0x00000075, .b = 7 },
130 [108] = { .c = 0x00000028, .b = 6 },
131 [109] = { .c = 0x00000029, .b = 6 },
132 [110] = { .c = 0x0000002a, .b = 6 },
133 [111] = { .c = 0x00000007, .b = 5 },
134 [112] = { .c = 0x0000002b, .b = 6 },
135 [113] = { .c = 0x00000076, .b = 7 },
136 [114] = { .c = 0x0000002c, .b = 6 },
137 [115] = { .c = 0x00000008, .b = 5 },
138 [116] = { .c = 0x00000009, .b = 5 },
139 [117] = { .c = 0x0000002d, .b = 6 },
140 [118] = { .c = 0x00000077, .b = 7 },
141 [119] = { .c = 0x00000078, .b = 7 },
142 [120] = { .c = 0x00000079, .b = 7 },
143 [121] = { .c = 0x0000007a, .b = 7 },
144 [122] = { .c = 0x0000007b, .b = 7 },
145 [123] = { .c = 0x00007ffe, .b = 15 },
146 [124] = { .c = 0x000007fc, .b = 11 },
147 [125] = { .c = 0x00003ffd, .b = 14 },
148 [126] = { .c = 0x00001ffd, .b = 13 },
149 [127] = { .c = 0x0ffffffc, .b = 28 },
150 [128] = { .c = 0x000fffe6, .b = 20 },
151 [129] = { .c = 0x003fffd2, .b = 22 },
152 [130] = { .c = 0x000fffe7, .b = 20 },
153 [131] = { .c = 0x000fffe8, .b = 20 },
154 [132] = { .c = 0x003fffd3, .b = 22 },
155 [133] = { .c = 0x003fffd4, .b = 22 },
156 [134] = { .c = 0x003fffd5, .b = 22 },
157 [135] = { .c = 0x007fffd9, .b = 23 },
158 [136] = { .c = 0x003fffd6, .b = 22 },
159 [137] = { .c = 0x007fffda, .b = 23 },
160 [138] = { .c = 0x007fffdb, .b = 23 },
161 [139] = { .c = 0x007fffdc, .b = 23 },
162 [140] = { .c = 0x007fffdd, .b = 23 },
163 [141] = { .c = 0x007fffde, .b = 23 },
164 [142] = { .c = 0x00ffffeb, .b = 24 },
165 [143] = { .c = 0x007fffdf, .b = 23 },
166 [144] = { .c = 0x00ffffec, .b = 24 },
167 [145] = { .c = 0x00ffffed, .b = 24 },
168 [146] = { .c = 0x003fffd7, .b = 22 },
169 [147] = { .c = 0x007fffe0, .b = 23 },
170 [148] = { .c = 0x00ffffee, .b = 24 },
171 [149] = { .c = 0x007fffe1, .b = 23 },
172 [150] = { .c = 0x007fffe2, .b = 23 },
173 [151] = { .c = 0x007fffe3, .b = 23 },
174 [152] = { .c = 0x007fffe4, .b = 23 },
175 [153] = { .c = 0x001fffdc, .b = 21 },
176 [154] = { .c = 0x003fffd8, .b = 22 },
177 [155] = { .c = 0x007fffe5, .b = 23 },
178 [156] = { .c = 0x003fffd9, .b = 22 },
179 [157] = { .c = 0x007fffe6, .b = 23 },
180 [158] = { .c = 0x007fffe7, .b = 23 },
181 [159] = { .c = 0x00ffffef, .b = 24 },
182 [160] = { .c = 0x003fffda, .b = 22 },
183 [161] = { .c = 0x001fffdd, .b = 21 },
184 [162] = { .c = 0x000fffe9, .b = 20 },
185 [163] = { .c = 0x003fffdb, .b = 22 },
186 [164] = { .c = 0x003fffdc, .b = 22 },
187 [165] = { .c = 0x007fffe8, .b = 23 },
188 [166] = { .c = 0x007fffe9, .b = 23 },
189 [167] = { .c = 0x001fffde, .b = 21 },
190 [168] = { .c = 0x007fffea, .b = 23 },
191 [169] = { .c = 0x003fffdd, .b = 22 },
192 [170] = { .c = 0x003fffde, .b = 22 },
193 [171] = { .c = 0x00fffff0, .b = 24 },
194 [172] = { .c = 0x001fffdf, .b = 21 },
195 [173] = { .c = 0x003fffdf, .b = 22 },
196 [174] = { .c = 0x007fffeb, .b = 23 },
197 [175] = { .c = 0x007fffec, .b = 23 },
198 [176] = { .c = 0x001fffe0, .b = 21 },
199 [177] = { .c = 0x001fffe1, .b = 21 },
200 [178] = { .c = 0x003fffe0, .b = 22 },
201 [179] = { .c = 0x001fffe2, .b = 21 },
202 [180] = { .c = 0x007fffed, .b = 23 },
203 [181] = { .c = 0x003fffe1, .b = 22 },
204 [182] = { .c = 0x007fffee, .b = 23 },
205 [183] = { .c = 0x007fffef, .b = 23 },
206 [184] = { .c = 0x000fffea, .b = 20 },
207 [185] = { .c = 0x003fffe2, .b = 22 },
208 [186] = { .c = 0x003fffe3, .b = 22 },
209 [187] = { .c = 0x003fffe4, .b = 22 },
210 [188] = { .c = 0x007ffff0, .b = 23 },
211 [189] = { .c = 0x003fffe5, .b = 22 },
212 [190] = { .c = 0x003fffe6, .b = 22 },
213 [191] = { .c = 0x007ffff1, .b = 23 },
214 [192] = { .c = 0x03ffffe0, .b = 26 },
215 [193] = { .c = 0x03ffffe1, .b = 26 },
216 [194] = { .c = 0x000fffeb, .b = 20 },
217 [195] = { .c = 0x0007fff1, .b = 19 },
218 [196] = { .c = 0x003fffe7, .b = 22 },
219 [197] = { .c = 0x007ffff2, .b = 23 },
220 [198] = { .c = 0x003fffe8, .b = 22 },
221 [199] = { .c = 0x01ffffec, .b = 25 },
222 [200] = { .c = 0x03ffffe2, .b = 26 },
223 [201] = { .c = 0x03ffffe3, .b = 26 },
224 [202] = { .c = 0x03ffffe4, .b = 26 },
225 [203] = { .c = 0x07ffffde, .b = 27 },
226 [204] = { .c = 0x07ffffdf, .b = 27 },
227 [205] = { .c = 0x03ffffe5, .b = 26 },
228 [206] = { .c = 0x00fffff1, .b = 24 },
229 [207] = { .c = 0x01ffffed, .b = 25 },
230 [208] = { .c = 0x0007fff2, .b = 19 },
231 [209] = { .c = 0x001fffe3, .b = 21 },
232 [210] = { .c = 0x03ffffe6, .b = 26 },
233 [211] = { .c = 0x07ffffe0, .b = 27 },
234 [212] = { .c = 0x07ffffe1, .b = 27 },
235 [213] = { .c = 0x03ffffe7, .b = 26 },
236 [214] = { .c = 0x07ffffe2, .b = 27 },
237 [215] = { .c = 0x00fffff2, .b = 24 },
238 [216] = { .c = 0x001fffe4, .b = 21 },
239 [217] = { .c = 0x001fffe5, .b = 21 },
240 [218] = { .c = 0x03ffffe8, .b = 26 },
241 [219] = { .c = 0x03ffffe9, .b = 26 },
242 [220] = { .c = 0x0ffffffd, .b = 28 },
243 [221] = { .c = 0x07ffffe3, .b = 27 },
244 [222] = { .c = 0x07ffffe4, .b = 27 },
245 [223] = { .c = 0x07ffffe5, .b = 27 },
246 [224] = { .c = 0x000fffec, .b = 20 },
247 [225] = { .c = 0x00fffff3, .b = 24 },
248 [226] = { .c = 0x000fffed, .b = 20 },
249 [227] = { .c = 0x001fffe6, .b = 21 },
250 [228] = { .c = 0x003fffe9, .b = 22 },
251 [229] = { .c = 0x001fffe7, .b = 21 },
252 [230] = { .c = 0x001fffe8, .b = 21 },
253 [231] = { .c = 0x007ffff3, .b = 23 },
254 [232] = { .c = 0x003fffea, .b = 22 },
255 [233] = { .c = 0x003fffeb, .b = 22 },
256 [234] = { .c = 0x01ffffee, .b = 25 },
257 [235] = { .c = 0x01ffffef, .b = 25 },
258 [236] = { .c = 0x00fffff4, .b = 24 },
259 [237] = { .c = 0x00fffff5, .b = 24 },
260 [238] = { .c = 0x03ffffea, .b = 26 },
261 [239] = { .c = 0x007ffff4, .b = 23 },
262 [240] = { .c = 0x03ffffeb, .b = 26 },
263 [241] = { .c = 0x07ffffe6, .b = 27 },
264 [242] = { .c = 0x03ffffec, .b = 26 },
265 [243] = { .c = 0x03ffffed, .b = 26 },
266 [244] = { .c = 0x07ffffe7, .b = 27 },
267 [245] = { .c = 0x07ffffe8, .b = 27 },
268 [246] = { .c = 0x07ffffe9, .b = 27 },
269 [247] = { .c = 0x07ffffea, .b = 27 },
270 [248] = { .c = 0x07ffffeb, .b = 27 },
271 [249] = { .c = 0x0ffffffe, .b = 28 },
272 [250] = { .c = 0x07ffffec, .b = 27 },
273 [251] = { .c = 0x07ffffed, .b = 27 },
274 [252] = { .c = 0x07ffffee, .b = 27 },
275 [253] = { .c = 0x07ffffef, .b = 27 },
276 [254] = { .c = 0x07fffff0, .b = 27 },
277 [255] = { .c = 0x03ffffee, .b = 26 },
278 [256] = { .c = 0x3fffffff, .b = 30 }, /* EOS */
279};
280
281
282int main(int argc, char **argv)
283{
284 uint32_t c, i, j;
285
286 /* fill first byte */
287 printf("struct rht rht_bit31_24[256] = {\n");
288 for (j = 0; j < 256; j++) {
289 for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
290 if (ht[i].b > 8)
291 continue;
292 c = ht[i].c << (32 - ht[i].b);
293
294 if (((c ^ (j << 24)) & -(1 << (32 - ht[i].b)) & 0xff000000) == 0) {
295 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
296 break;
297 }
298 }
299 }
300 printf("};\n\n");
301
302 printf("struct rht rht_bit24_17[256] = {\n");
303 for (j = 0; j < 256; j++) {
304 for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
305 if (ht[i].b <= 8 || ht[i].b > 16)
306 continue;
307 c = ht[i].c << (32 - ht[i].b);
308
309 if (((c ^ (j << 17)) & -(1 << (32 - ht[i].b)) & 0x01fe0000) == 0) {
310 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
311 break;
312 }
313 }
314 }
315 printf("};\n\n");
316
317 printf("struct rht rht_bit15_11_fe[32] = {\n");
318 for (j = 0; j < 32; j++) {
319 for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
320 if (ht[i].b <= 16 || ht[i].b > 21)
321 continue;
322 c = ht[i].c << (32 - ht[i].b);
323 if ((c & 0x00ff0000) != 0x00fe0000)
324 continue;
325
326 if (((c ^ (j << 11)) & -(1 << (32 - ht[i].b)) & 0x0000f800) == 0) {
327 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
328 break;
329 }
330 }
331 }
332 printf("};\n\n");
333
334 printf("struct rht rht_bit15_8[256] = {\n");
335 for (j = 0; j < 256; j++) {
336 for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
337 if (ht[i].b <= 16 || ht[i].b > 24)
338 continue;
339 c = ht[i].c << (32 - ht[i].b);
340 if ((c & 0x00ff0000) != 0x00ff0000)
341 continue;
342
343 if (((c ^ (j << 8)) & -(1 << (32 - ht[i].b)) & 0x0000ff00) == 0) {
344 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
345 break;
346 }
347 }
348 }
349 printf("};\n\n");
350
351 printf("struct rht rht_bit11_4[256] = {\n");
352 /* fill fourth byte after 0xff 0xff 0xf6-0xff. Only 0xfffffffx are not distinguished */
353 for (j = 0; j < 256; j++) {
354 for (i = 0; i < sizeof(ht)/sizeof(ht[0]); i++) {
355 if (ht[i].b <= 24)
356 continue;
357 c = ht[i].c << (32 - ht[i].b);
358
359 if (((c ^ (j << 4)) & -(1 << (32 - ht[i].b)) & 0x00000ff0) == 0) {
360 //printf("\tj=%02x i=%02x c=%08x l=%d c/l=%08x j/l=%08x xor=%08x\n", j, i, c, ht[i].b, c & -(1 << (32 - ht[i].b)), ((j << 4) & -(1 << (32 - ht[i].b))), (c ^ (j << 4)) & -(1 << (32 - ht[i].b)));
361 printf("\t[0x%02x] = { .c = 0x%02x, .l = %d },\n", j, i, ht[i].b);
362 break;
363 }
364 }
365 }
366 printf("\t/* Note, when l==30, bits 3..2 give 00:0x0a, 01:0x0d, 10:0x16, 11:EOS */\n");
367 printf("};\n\n");
368 return 0;
369}