1 /*
2 *
3 * Copyright 2015 gRPC authors.
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 */
18
19 /* generates constant tables for hpack.cc */
20
21 #include <assert.h>
22 #include <stddef.h>
23 #include <stdio.h>
24 #include <string.h>
25
26 #include <grpc/support/log.h>
27 #include "src/core/ext/transport/chttp2/transport/huffsyms.h"
28
29 /*
30 * first byte LUT generation
31 */
32
33 typedef struct {
34 const char *call;
35 /* bit prefix for the field type */
36 unsigned char prefix;
37 /* length of the bit prefix for the field type */
38 unsigned char prefix_length;
39 /* index value: 0 = all zeros, 2 = all ones, 1 otherwise */
40 unsigned char index;
41 } spec;
42
43 static const spec fields[] = {
44 {"INDEXED_FIELD", 0X80, 1, 1}, {"INDEXED_FIELD_X", 0X80, 1, 2},
45 {"LITHDR_INCIDX", 0X40, 2, 1}, {"LITHDR_INCIDX_X", 0X40, 2, 2},
46 {"LITHDR_INCIDX_V", 0X40, 2, 0}, {"LITHDR_NOTIDX", 0X00, 4, 1},
47 {"LITHDR_NOTIDX_X", 0X00, 4, 2}, {"LITHDR_NOTIDX_V", 0X00, 4, 0},
48 {"LITHDR_NVRIDX", 0X10, 4, 1}, {"LITHDR_NVRIDX_X", 0X10, 4, 2},
49 {"LITHDR_NVRIDX_V", 0X10, 4, 0}, {"MAX_TBL_SIZE", 0X20, 3, 1},
50 {"MAX_TBL_SIZE_X", 0X20, 3, 2},
51 };
52
53 static const int num_fields = sizeof(fields) / sizeof(*fields);
54
prefix_mask(unsigned char prefix_len)55 static unsigned char prefix_mask(unsigned char prefix_len) {
56 unsigned char i;
57 unsigned char out = 0;
58 for (i = 0; i < prefix_len; i++) {
59 /* NB: the following integer arithmetic operation needs to be in its
60 * expanded form due to the "integral promotion" performed (see section
61 * 3.2.1.1 of the C89 draft standard). A cast to the smaller container type
62 * is then required to avoid the compiler warning */
63 out = (unsigned char)(out | (unsigned char)(1 << (7 - i)));
64 }
65 return out;
66 }
67
suffix_mask(unsigned char prefix_len)68 static unsigned char suffix_mask(unsigned char prefix_len) {
69 return (unsigned char)~prefix_mask(prefix_len);
70 }
71
generate_first_byte_lut(void)72 static void generate_first_byte_lut(void) {
73 int i, j, n;
74 const spec *chrspec;
75 unsigned char suffix;
76
77 n = printf("static CALLTYPE first_byte[256] = {");
78 /* for each potential first byte of a header */
79 for (i = 0; i < 256; i++) {
80 /* find the field type that matches it */
81 chrspec = NULL;
82 for (j = 0; j < num_fields; j++) {
83 if ((prefix_mask(fields[j].prefix_length) & i) == fields[j].prefix) {
84 /* NB: the following integer arithmetic operation needs to be in its
85 * expanded form due to the "integral promotion" performed (see section
86 * 3.2.1.1 of the C89 draft standard). A cast to the smaller container
87 * type is then required to avoid the compiler warning */
88 suffix = (unsigned char)(suffix_mask(fields[j].prefix_length) &
89 (unsigned char)i);
90 if (suffix == suffix_mask(fields[j].prefix_length)) {
91 if (fields[j].index != 2) continue;
92 } else if (suffix == 0) {
93 if (fields[j].index != 0) continue;
94 } else {
95 if (fields[j].index != 1) continue;
96 }
97 GPR_ASSERT(chrspec == NULL);
98 chrspec = &fields[j];
99 }
100 }
101 if (chrspec) {
102 n += printf("%s, ", chrspec->call);
103 } else {
104 n += printf("ILLEGAL, ");
105 }
106 /* make some small effort towards readable output */
107 if (n > 70) {
108 printf("\n ");
109 n = 2;
110 }
111 }
112 printf("};\n");
113 }
114
115 /*
116 * Huffman decoder table generation
117 */
118
119 #define MAXHUFFSTATES 1024
120
121 /* represents a set of symbols as an array of booleans indicating inclusion */
122 typedef struct { char included[GRPC_CHTTP2_NUM_HUFFSYMS]; } symset;
123 /* represents a lookup table indexed by a nibble */
124 typedef struct { unsigned values[16]; } nibblelut;
125
126 #define NOT_SET (~(unsigned)0)
127
128 /* returns a symset that includes all possible symbols */
symset_all(void)129 static symset symset_all(void) {
130 symset x;
131 memset(x.included, 1, sizeof(x.included));
132 return x;
133 }
134
135 /* returns a symset that includes no symbols */
symset_none(void)136 static symset symset_none(void) {
137 symset x;
138 memset(x.included, 0, sizeof(x.included));
139 return x;
140 }
141
142 /* returns an empty nibblelut */
nibblelut_empty(void)143 static nibblelut nibblelut_empty(void) {
144 nibblelut x;
145 int i;
146 for (i = 0; i < 16; i++) {
147 x.values[i] = NOT_SET;
148 }
149 return x;
150 }
151
152 /* counts symbols in a symset - only used for debug builds */
153 #ifndef NDEBUG
nsyms(symset s)154 static int nsyms(symset s) {
155 int i;
156 int c = 0;
157 for (i = 0; i < GRPC_CHTTP2_NUM_HUFFSYMS; i++) {
158 c += s.included[i] != 0;
159 }
160 return c;
161 }
162 #endif
163
164 /* global table of discovered huffman decoding states */
165 static struct {
166 /* the bit offset that this state starts at */
167 unsigned bitofs;
168 /* the set of symbols that this state started with */
169 symset syms;
170
171 /* lookup table for the next state */
172 nibblelut next;
173 /* lookup table for what to emit */
174 nibblelut emit;
175 } huffstates[MAXHUFFSTATES];
176 static unsigned nhuffstates = 0;
177
178 /* given a number of decoded bits and a set of symbols that are live,
179 return the index into the decoder table for this state.
180 set isnew to 1 if this state was previously undiscovered */
state_index(unsigned bitofs,symset syms,unsigned * isnew)181 static unsigned state_index(unsigned bitofs, symset syms, unsigned *isnew) {
182 unsigned i;
183 for (i = 0; i < nhuffstates; i++) {
184 if (huffstates[i].bitofs != bitofs) continue;
185 if (0 != memcmp(huffstates[i].syms.included, syms.included,
186 GRPC_CHTTP2_NUM_HUFFSYMS))
187 continue;
188 *isnew = 0;
189 return i;
190 }
191 GPR_ASSERT(nhuffstates != MAXHUFFSTATES);
192
193 i = nhuffstates;
194 nhuffstates++;
195
196 huffstates[i].bitofs = bitofs;
197 huffstates[i].syms = syms;
198 huffstates[i].next = nibblelut_empty();
199 huffstates[i].emit = nibblelut_empty();
200 *isnew = 1;
201 return i;
202 }
203
204 /* recursively build a decoding table
205
206 state - the huffman state that we are trying to fill in
207 nibble - the current nibble
208 nibbits - the number of bits in the nibble that have been filled in
209 bitofs - the number of bits of symbol that have been decoded
210 emit - the symbol to emit on this nibble (or -1 if no symbol has been
211 found)
212 syms - the set of symbols that could be matched */
build_dec_tbl(unsigned state,unsigned nibble,int nibbits,unsigned bitofs,unsigned emit,symset syms)213 static void build_dec_tbl(unsigned state, unsigned nibble, int nibbits,
214 unsigned bitofs, unsigned emit, symset syms) {
215 unsigned i;
216 unsigned bit;
217
218 /* If we have four bits in the nibble we're looking at, then we can fill in
219 a slot in the lookup tables. */
220 if (nibbits == 4) {
221 unsigned isnew;
222 /* Find the state that we are in: this may be a new state, in which case
223 we recurse to fill it in, or we may have already seen this state, in
224 which case the recursion terminates */
225 unsigned st = state_index(bitofs, syms, &isnew);
226 GPR_ASSERT(huffstates[state].next.values[nibble] == NOT_SET);
227 huffstates[state].next.values[nibble] = st;
228 huffstates[state].emit.values[nibble] = emit;
229 if (isnew) {
230 build_dec_tbl(st, 0, 0, bitofs, NOT_SET, syms);
231 }
232 return;
233 }
234
235 assert(nsyms(syms));
236
237 /* A bit can be 0 or 1 */
238 for (bit = 0; bit < 2; bit++) {
239 /* walk over active symbols and see if they have this bit set */
240 symset nextsyms = symset_none();
241 for (i = 0; i < GRPC_CHTTP2_NUM_HUFFSYMS; i++) {
242 if (!syms.included[i]) continue; /* disregard inactive symbols */
243 if (((grpc_chttp2_huffsyms[i].bits >>
244 (grpc_chttp2_huffsyms[i].length - bitofs - 1)) &
245 1) == bit) {
246 /* the bit is set, include it in the next recursive set */
247 if (grpc_chttp2_huffsyms[i].length == bitofs + 1) {
248 /* additionally, we've gotten to the end of a symbol - this is a
249 special recursion step: re-activate all the symbols, reset
250 bitofs to zero, and recurse */
251 build_dec_tbl(state, (nibble << 1) | bit, nibbits + 1, 0, i,
252 symset_all());
253 /* skip the remainder of this loop */
254 goto next;
255 }
256 nextsyms.included[i] = 1;
257 }
258 }
259 /* recurse down for this bit */
260 build_dec_tbl(state, (nibble << 1) | bit, nibbits + 1, bitofs + 1, emit,
261 nextsyms);
262 next:;
263 }
264 }
265
266 static nibblelut ctbl[MAXHUFFSTATES];
267 static int nctbl;
268
ctbl_idx(nibblelut x)269 static int ctbl_idx(nibblelut x) {
270 int i;
271 for (i = 0; i < nctbl; i++) {
272 if (0 == memcmp(&x, ctbl + i, sizeof(nibblelut))) return i;
273 }
274 ctbl[i] = x;
275 nctbl++;
276 return i;
277 }
278
dump_ctbl(const char * name)279 static void dump_ctbl(const char *name) {
280 int i, j;
281 printf("static const gpr_int16 %s[%d*16] = {\n", name, nctbl);
282 for (i = 0; i < nctbl; i++) {
283 for (j = 0; j < 16; j++) {
284 printf("%d,", ctbl[i].values[j]);
285 }
286 printf("\n");
287 }
288 printf("};\n");
289 }
290
generate_huff_tables(void)291 static void generate_huff_tables(void) {
292 unsigned i;
293 build_dec_tbl(state_index(0, symset_all(), &i), 0, 0, 0, NOT_SET,
294 symset_all());
295
296 nctbl = 0;
297 printf("static const gpr_uint8 next_tbl[%d] = {", nhuffstates);
298 for (i = 0; i < nhuffstates; i++) {
299 printf("%d,", ctbl_idx(huffstates[i].next));
300 }
301 printf("};\n");
302 dump_ctbl("next_sub_tbl");
303
304 nctbl = 0;
305 printf("static const gpr_uint16 emit_tbl[%d] = {", nhuffstates);
306 for (i = 0; i < nhuffstates; i++) {
307 printf("%d,", ctbl_idx(huffstates[i].emit));
308 }
309 printf("};\n");
310 dump_ctbl("emit_sub_tbl");
311 }
312
generate_base64_huff_encoder_table(void)313 static void generate_base64_huff_encoder_table(void) {
314 static const char alphabet[] =
315 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
316 int i;
317
318 printf(
319 "static const struct { gpr_uint16 bits, gpr_uint8 length } "
320 "base64_syms[64] = {\n");
321 for (i = 0; i < 64; i++) {
322 printf("{0x%x, %d},", grpc_chttp2_huffsyms[(unsigned char)alphabet[i]].bits,
323 grpc_chttp2_huffsyms[(unsigned char)alphabet[i]].length);
324 }
325 printf("};\n");
326 }
327
generate_base64_inverse_table(void)328 static void generate_base64_inverse_table(void) {
329 static const char alphabet[] =
330 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
331 unsigned char inverse[256];
332 unsigned i;
333
334 memset(inverse, 255, sizeof(inverse));
335 for (i = 0; i < strlen(alphabet); i++) {
336 inverse[(unsigned char)alphabet[i]] = (unsigned char)i;
337 }
338
339 printf("static const gpr_uint8 inverse_base64[256] = {");
340 for (i = 0; i < 256; i++) {
341 printf("%d,", inverse[i]);
342 }
343 printf("};\n");
344 }
345
main(void)346 int main(void) {
347 generate_huff_tables();
348 generate_first_byte_lut();
349 generate_base64_huff_encoder_table();
350 generate_base64_inverse_table();
351
352 return 0;
353 }
354