blob: 68a9dd8ab15ff921f3a339f23af05bef18601892 [file] [log] [blame]
Willy Tarreau841bc7d2018-12-10 15:26:35 +01001/*
2 * HPACK encoding table generator. It produces a stream of
3 * <len><idx><name> and a table pointing to the first <len> of each series.
4 * The end of the stream is marked by <len>=0. In parallel, a length-indexed
5 * table is built to access the first entry of each length.
6 *
7 * Build like this :
8 * gcc -I../../include -I../../ebtree -o gen-enc gen-enc.c
9 */
10#include <ctype.h>
11#include <stdint.h>
12#include <stdio.h>
13#include <stdlib.h>
14#include <unistd.h>
15#include <common/ist.h>
16#include <common/hpack-tbl.h>
17#include "../../src/hpack-tbl.c"
18
19struct idxhdr {
20 const char *ptr;
21 int len;
22 int idx;
23};
24
25struct idxhdr idxhdr[HPACK_SHT_SIZE];
26static int positions[32];
27static char known_hdr[1024];
28
29/* preferred ordering of headers of similar size. Those not mentioned will be
30 * less prioritized.
31 */
32const struct {
33 const char *name;
34 const int rank;
35} ranks[] = {
36 { .name = "age", .rank = 1 },
37 { .name = "via", .rank = 2 },
38
39 { .name = "date", .rank = 1 },
40 { .name = "host", .rank = 2 },
41
42 { .name = "accept", .rank = 1 },
43 { .name = "server", .rank = 2 },
44 { .name = "cookie", .rank = 3 },
45
46 { .name = "referer", .rank = 1 },
47 { .name = "expires", .rank = 2 },
48
49 { .name = "location", .rank = 1 },
50
51 { .name = "user-agent", .rank = 1 },
52 { .name = "set-cookie", .rank = 2 },
53
54 { .name = "content-type", .rank = 1 },
55
56 { .name = "cache-control", .rank = 1 },
57 { .name = "last-modified", .rank = 2 },
58 { .name = "accept-ranges", .rank = 3 },
59 { .name = "if-none-match", .rank = 4 },
60
61 { .name = "content-length", .rank = 1 },
62
63 { .name = "accept-encoding", .rank = 1 },
64 { .name = "accept-language", .rank = 2 },
65
66 { .name = "content-encoding", .rank = 1 },
67
68 { .name = "transfer-encoding", .rank = 1 },
69 { .name = "if-modified-since", .rank = 2 },
70
71 { .name = "content-disposition", .rank = 1 },
72};
73
74/* returns the rank of header <name> or 255 if not found */
75int get_hdr_rank(const char *name)
76{
77 int i;
78
79 for (i = 0; i < sizeof(ranks) / sizeof(ranks[0]); i++) {
80 if (strcmp(ranks[i].name, name) == 0)
81 return ranks[i].rank;
82 }
83 return 255;
84}
85
86/* sorts first on the length, second on the name, and third on the idx, so that
87 * headers which appear with multiple occurrences are always met first.
88 */
89int cmp_idx(const void *l, const void *r)
90{
91 const struct idxhdr *a = l, *b = r;
92 int ranka, rankb;
93 int ret;
94
95 if (a->len < b->len)
96 return -1;
97 else if (a->len > b->len)
98 return 1;
99
100 ranka = get_hdr_rank(a->ptr);
101 rankb = get_hdr_rank(b->ptr);
102
103 if (ranka < rankb)
104 return -1;
105 else if (ranka > rankb)
106 return 1;
107
108 /* same rank, check for duplicates and use index */
109 ret = strcmp(a->ptr, b->ptr);
110 if (ret != 0)
111 return ret;
112
113 if (a->idx < b->idx)
114 return -1;
115 else if (a->idx > b->idx)
116 return 1;
117 else
118 return 0;
119}
120
121int main(int argc, char **argv)
122{
123 int pos;
124 int prev;
125 int len;
126 int i;
127
128 for (len = 0; len < 32; len++)
129 positions[len] = -1;
130
131 for (i = 0; i < HPACK_SHT_SIZE; i++) {
132 idxhdr[i].ptr = hpack_sht[i].n.ptr;
133 idxhdr[i].len = hpack_sht[i].n.len;
134 idxhdr[i].idx = i;
135 }
136
137 /* sorts all header names by length first, then by name, and finally by
138 * idx so that we meet smaller headers first, that within a length they
139 * appear in frequency order, and that multiple occurrences appear with
140 * the smallest index first.
141 */
142 qsort(&idxhdr[1], HPACK_SHT_SIZE - 1, sizeof(idxhdr[0]), cmp_idx);
143
144 pos = 0;
145 prev = -1;
146 for (i = 1; i < HPACK_SHT_SIZE; i++) {
147 len = idxhdr[i].len;
148 if (len > 31) {
149 //printf("skipping %s (len=%d)\n", idxhdr[i].ptr, idxhdr[i].len);
150 continue;
151 }
152
153 /* first occurrence of this length? */
154 if (positions[len] == -1)
155 positions[len] = pos;
156 else if (prev >= 0 &&
157 memcmp(&known_hdr[prev] + 2, idxhdr[i].ptr, len) == 0) {
158 /* duplicate header field */
159 continue;
160 }
161
162 /* store <len> <idx> <name> in the output array */
163
164 if (pos + 1 + len + 2 >= sizeof(known_hdr))
165 abort();
166
167 prev = pos;
168 known_hdr[pos++] = len;
169 known_hdr[pos++] = idxhdr[i].idx;
170 memcpy(&known_hdr[pos], idxhdr[i].ptr, len);
171 pos += len;
172 //printf("%d %d %s\n", len, idxhdr[i].idx, idxhdr[i].ptr);
173 }
174
175 if (pos + 1 >= sizeof(known_hdr))
176 abort();
177 known_hdr[pos++] = 0; // size zero ends the stream
178
179 printf("const char hpack_enc_stream[%d] = {\n", pos);
180 for (i = 0; i < pos; i++) {
181 if ((i & 7) == 0)
182 printf("\t /* % 4d: */", i);
183
184 printf(" 0x%02x,", known_hdr[i]);
185
186 if ((i & 7) == 7 || (i == pos - 1))
187 putchar('\n');
188 }
189 printf("};\n\n");
190
191 printf("const signed short hpack_pos_len[32] = {\n");
192 for (i = 0; i < 32; i++) {
193 if ((i & 7) == 0)
194 printf("\t /* % 4d: */", i);
195
196 printf(" % 4d,", positions[i]);
197
198 if ((i & 7) == 7 || (i == pos - 1))
199 putchar('\n');
200 }
201 printf("};\n\n");
202 return 0;
203}